Прокис Дж. Цифровая связь (2000) (1151856), страница 20
Текст из файла (страница 20)
Чтобы увидеть этот недостаток, предположим, что мы приняз~рефик< последовательность 001001... Ясно, что 00 декодируется как аз. Однако последуюшф>рядка четыре бита декодируются неоднозначно. Они могут декодироваться или как а,а„или и~ а,а,а,. Возможно, неоднозначность может быть разрешена путем ожидания последующз1 Выб битов, но такое декодирование крайне нежелательно.
Мы должны рассмотреть тольн~траня~ коды, которые допускают немедленное декодирование, т.е. без задержки в декодере. ~потупи Код 11 в табл. 3.3.1 обеспечивает однозначное и немедленное декодирование. Удобф~бор у представлять кодовые слова этого кода графически как узлы на дереве, как показано ~ рис. 3.3.1.
Видно, что 0 указывает на окончание кодового слова в первых трех кодовыми„ словах. Эта характеристика вместе с тем обстоятельством, что ни одно кодовое слово ~ содержит более трех двоичных символов, делает этот код немедленно декодируемы( Заметим, что ни одно кодовое слово этого кода не является префиксом (началом) другов кодового слова.
В общем, префиксное условие кода требует, чтобы для данного кодово~( Всег слова С„длины й с элементами (Ь„Ь„... Ь„) не существовало других кодовых слов длии1аким о~ / < к с элементами (Ь„Ь„... Ь)для 1<1< й — 1. Мк иллг рстоящ 84 а, ,е о а, е о а, 1 а, 1 а, — ° . ° а °вЂ” "е- Рва З,З.!. Кодовое дерево для кода П в табл.3.3.1 Рис.
3.3.2. Кодовое дерево для кода П1 в табл.3.3.1 Неравенство Крафта. Необходимым и достаточным условием существования !ясачного кода с кодовыми символами длины л! < и, «.... пе, удовлетворяющего условию !рефиксиости, является е ~г-"" <1. (3.3.8) I ! Сначала мы докажем„что (3.3.8) является достаточным условием для существования !рефиксного кода. Чтобы построить такой код, мы начнем с полного двоичного дерева !орядка л=л, которое имеет 2" конечных узлов, причем от каждого узла порядка й — 1 'растут" по два узла порядка Й, 1 < 1г < л .
Выберем некоторый узел порядка п! в качестве первого кодового слова С!. Этот выбор страняет 2" "конечных узлов (т.е. долю 2 "' от 2" конечных узлов). От остающихся !оступных узлов порядка пз мы выбираем один узел для второго кодового слова Ст. Этот ыбор устраняет 2" а конечных узлов (т.е, долю 2 "'от 2" конечных узлов). Этот процесс родолжается, пока последнее кодовое слово не определено в конечном узле и=п„.
ледовательно, в узле порядка 1' < Ь доля числа отсеченных конечных узлов ~ 2" <~~> 2" <1. я ! е=! Всегда имеется узел порядка 1г > 1, который может быть выбран для следующего слова. 'аким образом, мы создали кодовое дерево, которое встроено в полное дерево из 2" узлов, ак иллюстрируется на рис. 3.3.3, для дерева, имеющего 1б конечных узлов, и источника, зстоящего из пяти символов, отображаемых кодовыми словами длиной и! =1, лт =2, =3 и пя =и =4. 85 Другими словами, нет кодовых слов длины 1<1с, которые совпадают с первыми 1 ячными символами другого кодового слова длины Й>1.
Это свойство делает кодовые ова немедленно декодируемыми. Код 1Н из табл. 3.3.1 имеет кодовое дерево, показанное на рис. 3.3.2. Видим, что в этом имеет место однозначное декодирование, однако требующее задержки. Ясно, что этот код не удовлетворяет префиксному условию. Нада главная цель — создать систематическую процедуру для конструирования означных декодирующих кодов переменной длины, эффективных в том смысле, что двее число бит на один символ источника, определяемое соотношением А Я= ~~ пеР(а„), (3.3.7) ! ! ! о бы минимальным. Условие существования кода переменной длины, которое довлетворяет префиксному условию, дается неравенством Крафта, л уго ли,ч с,, о Ес луч .3.9) м с, . слов) мво с, о о.с, ---, .с Рис.
3.3.3. Конструирование двоичного дерева, встроенного в полное дерево стр! А.! дир (х,), мво. дов! Чтобы доказать, что (3.3.8) является необходимым условием, мы заметим, что в дер порядка и =ив число конечных узлов, отсеченных от общего числа 2" конечных узл ика! ил. П1 еюп равно с ~~> 2" <1, е-! Крафта можно использовать источника (без шумов), кото условию. ~~> 2" " <2". Следовательно, а ! и доказательство (3.3.8) закончено.
Неравенство доказательства следующей теоремы кодирования применяется к кодам, удовлетворяющим префиксному Теорема кодирования источника П. Пусть Х вЂ” ансамбль символов двоичи источника без памяти с конечной энтропией Н(Х) и выходными символами х„, 1< 1с < с соответствующими вероятностями выбора р„1 < 1с < Е. Существует возможность созд~ код, который удовлетворяет префиксному условию и имеет среднюю длину Я, кото)~ удовлетворяет неравенству о, Н(Х) < й < Н(Х)+1.
(3.3.9) о, Чтобы установить нижнюю границу в (3.3.9), обратим внимание на то, что для кодов1 слов, которые имеют длину и„, 1 < 1с < Х, разность Н(Х) — Я может быть выражена в внд Мь Н(Х)-и = ~> р 1о8,— - у р„п, =~~1 р,1о8, —, (3.3.10) Ре в-! а-! Ре Используя неравенство 1пх < х — 1, из (3.3.10) находим ямвол с Рч с Н(Х)-й<(1ой,е)~,р, — -1 <(1оцае) ~2 "' — 1 <О, Рл а-!,! ады где последнее неравенство следует из неравенства Крафта.
Равенство имеет место, если У учае только если р„. = 2 "" для 1 < /с < Е. озна Верхняя граница в (3.3.9) может быть установлена при предположении что л„, 1 < 1с ~ьеди — целые числа, выбираемые из условия 2 " < р, <2 "'". Но если р >2!~~Ры просуммнрованы по 1 < 1г < Х, получаем неравенство Крафта, для которого демонстрировали, что там существует код, удовлетворяющий префиксному условн!о.1мвол иди, что эквивалентно, пя <1-1одр„.
(3,3.1 1) Если умножить обе части неравенства (3.3.11) на ря и просуммировать по 1 < 1г < 2, получаем желательную верхнюю границу, данную в (3.3.9). Это завершает доказательство '3.3.9). Мы установили, что коды переменной длины, которые удовлетворяют префиксному словию, — это эффективные коды для любого дискретного источника без памяти ЯИБП) с :имволами, имеющими различную априорную вероятность.
Опишем теперь алгоритм для >остроения таких кодов. Алгоритм кодирования Хаффмена. Хаффмен (1952) разработал алгоритм одирования переменной длины, основанный на знании априорных вероятностей символов в(х,), 1' = 1,2..., Т, . Этот алгоритм оптимален в том смысле, что среднее число двоичных выводов, требуемых для представления исходных символов, минимально. Получаемые рдовые слова удовлетворяют префиксному условию, определенному выше, что позволяет никально и мгновенно декодировать полученную последовательность. Мы роиллюстрируем этот алгоритм кодирования посредством двух примеров, Пример 3.3.1. Рассмотрим ДИБП с семью возможными символами х,.х„,....х,. ие>ощими вероятности выбора, нллюстрируемые рис.
3.3.4. Символ Вероятность Собственная Кол информация 0.35 0.30 0,20 0,10 0,04 0,005 0,005 Н(Х3 = 2.11 Я = 2,2! Мы упорядочили символы источника в порядке убывания вероятностей, т,е. х,)> Р~ха)>...>Р(х>). Процесс кодирования начинаем с двух наименее вероятных «волов х, н х,. Эти два символа объединяем, как показано на рис.3.3.4, причем >хнему ветвлению присваиваем «О», а нижнему — «1». Вероятности этих двух ветвей >адываются, и общему узлу присваивается суммарная вероятность, равная в данном >чае 0,01. Теперь мы имеем исходные символы х„х„...,х, плюс новый символ, >значим его х,', полученный объединением х, и х,. На следующем шаге снова ьединяются два наименее вероятных символа из набора х„х„х>,хя,х,,хе'.
Это х, их,', .орые имеют объединенную вероятность 0,05. Переходу от х> присваиваем «О», а >еходу от х,' — «1». Эта процедура продолжается, пока мы не исчерпаем все возможные !волы источника. Результат — кодовое дерево с ветвями, которые содержат требуемые 87 другой стороны, если мы берем логарифм р„с 2 "' ", получаем 1ойр„< — и, +1 0,35 0,30 0,20 О,!0 0,04 0,005 0,005 Рис. 3.3.4. Пример кодирования ДИБП кодом переменной длины 1,5146 00 1,7370 01 2,3219 1О 3,3219 110 4,6439 1110 7,6439 11110 7,6439 !11!1 кодовые слова.
Кодовые слова получаются, если двигаться от самого правого узла дере переходя к самому левому узлу. Результирующие кодовые слова приведены на рис. 33 Среднее число двоичных элементов на символ этого кода К = 2,21 бит/символ. Энтро источника — 2,11 бит/символ. Заметим, что полученный код не единственно возможный. Например, предпоследнем шаге процедуры кодирования мы имеем равный выбор между х, н имеющими одинаковые вероятности. В этом пункте мы соединили х, и х, . альтернативном коде мы можем соединить х, и х,' . Результирующий код для этого сл иллюстрируется на рис. 3,3.5. Символ Код 0,35 О,3О <о по п<о и!<о П!<Ко <1 !<!! 0,20 где Я, как уг< о,<о 0,04 П1 и 0,20 0,005 к=22! О,ОО5 для эз эффек' парам! для пе требуе Рис. 3.3.5. Альтернативный код для ДИБП в примере 3.3.1 Среднее число бит на символ для этого кода также равно 2.21.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
