Финк М. Теория передачи дискретных сообщений (1970) (1151862), страница 14
Текст из файла (страница 14)
Это сводится, в сущности, к тому, что каждая иэ десяти цифр О, 1,..., 9 изображается двоичным числом: ОООО, 0001,..., 1001. Очевидно, что для этого потребуются четырехразрязные двоичные числа. Таким образом, на каждый элемент со. общения (цифру) при таком кодировании потребуется 4 кодовых символа, тогда как теорема утверждает, что можно осуществить более «экономное» кодирование, приближаясь к количеству кодовых символов 3,332 иа цифру. Покажем, что это можно сделать, если до кодирования произвести укрупнение алфавита источника. Будем рассматривать каждую пару цифр, выдаваемых источником, как двухразрядное десятичное число, т.
е., перейдем от а=10 к !г=!00 и сведем .по прежнему «однрование к изображению этого числа в двоичном счислении. Всякое число меныпе 100 можно представить семиразрядным двоич. ным числом (на том основании, что 2'=128>100, тогда как 2'=64 и поэтому шестиразрядных двоичных чисел не хватит для представленвя всех двухразрядных десятичных чисел). При таком кодировании на каждыс два знака сообщения потребуется семь кодовых символов, т. е. в среднем 3,3 кодового символа на цифру, а не 4, как было до укрупнения алфавита.
Продолжим укрупнение алфавита, рассматривая каждые три цифры, выдаваемые источником, как трехразрядиое десятичное число. Его можно предо>авить в двоичном счислении 10-разрядным чн. слом (так как 2'г= 1024>1000). Следовательно, при таком кодирова- 1О нив на одну цифру потребуется 3 гвЗ,ЗЗЗ кодового символа, что уже очень близко к теоретической величине 3,332. Дальнейшие укрупнения алфавита нозволят еще больше приблиаить скорость передачи цифр по такому двоичному каналу к величине . ° но, конечно, не превзойти ее, Действительно, если 1ойг !О' объединить х цифр, выдаваемых всточником, в к-разрядное деся. тнчное число, то его можно изобразить у-разрядным двоичным чис. лом прн условен, что !Ог<йг нлн х 1оаг!0<у, откуда и при котором справедливы неравенства 1оц ! 1оц ! Ь вЂ” < а<.Ь вЂ” +1.
!оц т 1оц т (2.10) Будем рассматривать каждые Ь букв сообщения как букву укрупненного алфавита объемом !г элементов и установим взаимно однозначное соответствие укрупненных букв кодовым комбинациям равномерного а-разрядного кода, что всегда можао сделать па основании (2.!0) (так как Р<ш"), причем часть комбинаций останется неиспользованной. Тогда каждая комбинация из а символов, переданная по каналу, соответствует Ь буквам первнчвого алфавита сообщении. Скорость передачи сообщения при этом раааа Ь СЬ ы=-о и 1ойг ш (2„!1) 1оа т где т= = 1оя! Из (2.10) имеем Ь!ой 1< а!ой т<(Ь+Т) !оп 1, Это выражение можно записать в форме и (оп> ш = (Ь + 3) (оп, 1, .» О<.й<т- Отсюда (2.12) С Ь С Ь С Ь !ой>! Ь+3 Н Ь+й' Н Ь+т г С Если число Ь выбрать из условия Ь лг ~ — — 1) т, то >Не С (2.13) (2.14) ш = — — ег что и требовалось доказать, Полученный резулыат показывает, что в канале с пропускной способностью С можно, применяя равномерный код, передавать сообщения любого источника, имеющего объем алфавита 1, со ско- С С ростью, сколь угодно блвзкой к — = — букв в секунду.
Нмггг !ойг ! Такой метод кодврования мы будем называть примитивным, Это утверждение, конечно, более слабое, чем требование теоремы, по которому для любого источника с энтропией Н<Н „„, скорость С передачи может быть сколь угодно близкой к —. Н 2.3. Методы устранения избыточности сообн(ения Еслн источник сообщении не имеет избыточности, то его производительность Н'=Н'м„в, и, как было показано в $2.2, с помощью простой процедуры сообщение 69 канал без может Г>ыть закодировано для передачи по каналу с пропускной способностью С>Н'„„к,.
В случае источника с избыточностью Н -. возникает задач с пропускной способнОстыо С аа макс чт р , если только С>Н'. Соответствующее кодирование должно преобразовать последоват ельность элементов сообщения с избыточностью в последовательность кодовых с имволов, не имегошую ее либо имеюшу>о меньшую избыточность. Поэтому таку значительно м звать страненисм изоперацию кодирования можно назвать устр быточности. чник выбираРассмотрим сначала случай, когда источник рет элмн и и независимо друг от друга.
В этом случа л чае вся ностями и нева ез льтатом неравных избыточность источника является резул вероятностей э ей элементов. Эта избыточность может быть а полностью или частично, если при кодир устранена полн менты ко отнии пре дставлять наиболее вероятные эле, р лов, а менее кими последовательностями кодовых симво .
О сю а видно, что такой вероятные — Г>олее длинными. Отсюда эконом , ичный код должен быть неравномерным. Е лсмент сообщения х>, представлен д после овасли з из и симвотельн т ос ью кодовых символов, состоящей и овалов, то среднее ее число символов и в кодовой послед тельности, приходящееся на один элемент, равно й= з р(ха)п>о (2.15) «~! Максимальная энтропия Нм„„(у) код ко оной последов ательности, приходяшаяся на од ин символ, равна — исло различных кодовых символо — в. Сле1ойт, где т — ч , энтропия кодовой последовательности, придовательно, энтропи , б ию (соответстходяшаяся в среднем на одну комбинацию ( вуюшую элементу сообшения): й>Н(у)~>>Н„,„;(у) = ~' р(ха) па1о~т. (2.16) а-.
! Основное требование, предъявляемое к любому ко, заключается в возможности однозначного декодироду, за. вания кодовой последовательности, что привод у ит к словию иН(у) =Н(х), откуда 70 п — — ° = р(„) о>в л=! Подученное выражение дает оценку снизу для средней длины кодовой комбинации. Задача экономичного кодирования заключается в том, чтобы выбрать код, позволяющий по возможности приблизить гг к этой оценке. Если в выражении (2.17) будет достигнуто равенство «, то это значит, что Н(у)=Нм,(у) и полученные кодовые последовательности не будут иметь избыточности. В противном случае сохранится остаточная избыточность, равная г! (У) 1 о (х) ймакс (У) и!Од и Однако эта избыточность всегда может быть сделана значительно меньшей, чем избыточность сообшения г = Й (х) =! — —.
1он 1 Действительно, применяя примитивное кодирование (~ 2.2) равномерным а-разрядным кодом, можно получить а, сколь угодно близкое к 1Оду)опт, что при подстановке в (2.18) даст г„=г,. Но, применяя неравномерный код, можно всегда сократить среднюю длину кодовой комбинации й, используя более короткие комбинации для более вероятных знаков (если только буквы сообщения не равновероятны), врезультатечегополучить г„<г«, т. е. устранить по крайней мере часть избыточности. Заметим, что, используя укрупнение алфавита, можно сделать остаточную избыточность сколь угодно малой. При построении оптимального неравномерного кода, позволяющего предельно сократить избыточность, необходимо учитывать требование однозначного декодирования.
Легко видеть, что это требование будет выполнено, если ни одна комбинация данного кода не совпадает с началом другой более длинной комбинации. Такое свойство кода называется «неприводимостью». При деко~ьв ° .,~,~...,.„„„, „„, ° „„*. н к,,„.„,и стнжкнн, если нагадав на вероятностей г>(ха) равна гл "а, где ла— чалое число. 71 0 рво неприводимости позволяет однозначно разделить эту.последовательность ва кодовые комбинации и сопоставить с каждой кодовой комбинацией соответствующий элемент сообщения, т. е. произвести декодирование *. Так, например, код с основанием т=-2, содержащий кодовые комбинации "' 00, 01, 100, 101, 110 и 111, является неприводимым, тогда как код, содержащий комбинации 00, 01, !О, 11, 000, 001, О!О, не является не- приводимым, поскольку комбинация О! совпадает с началом комбинации 010, а комбинация 00 в с началом комГ>инаций 000 и 001.
Первый из этих кодов позволяет произвести однозначное декодирование. Если принята„ например, кодовая последовательность 0001101010110!01001001100!0001101..., то ее можно разделить на кодовые комбинации только следующим образом: 00 01 !01 01 01 101 01 00 100 !1О О! 00 01 101... Если бы использовался второй код, не облада(ощий свойством неприводимости, то разделение той же последовательности на кодовые комбинации можно было бы произвести различными способами, например: 00 01 1О !О 1О 11 О1 01 00 10 01 10 01 00 01 10... или 000 !1 010 1О 11 010 !О 010 О! 1О 010 00! !О..., или 000 11 01 010 11 01 О! 001 001 10 01 000 !1 01.. и т. д. Известны различные способы [!, 3, 4] (алгоритмы) построения неприводимых неравномерных кодов с основанием т, позволяющих для заданного источника в наибольшей возможной степени устранить избыточность сообщения.
Опишем наиболее универсальный способ, предложенный Хафменом (4, 38). Все буквы алфавита сообщения в количестве ! вып<шываются в порядке уГ>ывающсй вероятности. Если число 1 — 1 не кратно пг — 1, то в алфавит добавляются дополнительные «буквы», которым приписываются вероятности, равные нулю, так чтобы для объема полученного алфавита 1' собл(одалось условие кратности 1' — 1 числу т — 1. Затем последние и элементов полученного алфавита объединяются в «укрупненный» элемент, вычисляется его вероятность, которая записывается в соответству»ощее место алфавита.
То же салюе проделывается с последними пг элементами полученного алфавита (включая укрупненные), и это продолжается до тех пор, пока не останется «алфавит», состоящий из и элементов. Этим элементам приписываются в люГ>ол» порядке одноразрядные кодовые комбинации О, 1, ,, (и — 1). Если в числе оставшихся и элементов есть такие, которые принадлежат исходному алфавиту (т. е. не полученные в результате объединения других элементов), то они оказываются закодированными одноразрядными кодовыми комбинациями. Для тех элементов, которые получены в результате обьедннения и букв исходного алфавита в кодовые комбинации, дописываются вторые символы О, 1, ..., (и — 1), так что эти знаки оказываются закодированными двухразрядными комбинациями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
