Вернер М. Основы кодирования (2004), страница 4

Основная идея азбуки Морзе - передавать частовстречающиеся буквы кодовыми словами короткой длины и, наоборот, редко встречающиеся буквы длинными кодовыми словами длятого, чтобы минимизировать средние затраты. Такой способ кодирования называют так же кодированием с минимальной избыточностью или энтропийным кодированием.Так, например, в азбуке Морзе часто встречающаяся буква «Е»кодируется одним знаком «•», а редкая «X» четырьмя знакамиВ 1952 г.

Хаффман показал, что предложенное им кодированиес переменной длиной кодовых слов является оптимальным префиксным кодом для дискретных источников без памяти. То есть, средняядлина слова кода Хаффмана минимальна и он так же является кодомбез запятой. Термин «код без запятой» означает, что при установленной синхронизации.возможна непрерывная передача потока сообщений с однозначным декодированием без специального разделениякодовых слов.В префиксном коде никакое кодовое слово не является префиксомдругого слова.Давид Хаффман (1925-1999) - американский ученый.Самуэль Морзэ (1791-1872) американский художник и изобретатель.Глава 3. Кодирование для дискретных источников без памятиТаблица 3.1. Буквы, символы азбуки Морзе и их относительная частота в немецком литературномтексте.БукваСимволазбукиМорзеОтносительная частотаБукваСимволазбукиМорзеОтносительная частотаА••0,0651N0,0992В••••••••0,02570•••••0,0284Р0,0541Q'Е••••0,1669RF••••0,0204SG•••0,0365Н••••I••JКСD••••••••0,02290,00940,0007••••••0,0654•0,06740,0406ти•••0,03700,0782V••••0,0107••••0,0019W•••0,0140•••0,0188X0,0002L•Ш»0,0283YМ•• '0,0301Z••••••••••••0,06780,00030,0100Замечание.

Коды Хаффмана играют важнейшую роль в кодировании изображений. Они являются основной частью стандартовJPEG, MPEG и H.261 J19]. Кроме этого, они так же используютсяпри оцифровке аудио сигналов. В литературе, в качестве примеровэнтропийного кодирования, упоминаются коды Шеннона и Фано, ноони не во всех случаях являются оптимальными и мы пропустимих описание.Кодирование Хаффмана производится за три шага. Мы нагляднопоясним этот процесс на маленьком примере.Кодирование Хаффмана.1. Упорядочение. Расположить знаки в порядке убывания ихвероятностей.2.

Редукция. Объединить два знака с наименьшими вероятно-3.2. Коды ХаффманаТаблица 3.2. Вероятности и энтропия двух символов.аPiI(pi)битН(Х)бит0,05Ь0,154,32 бит 2,74 битс0,05dеf0,40,20,154,32 бит 1,32 бит 2,32 бит 2,74 бит« 2,25стями в один составной знак. Переупорядочить список знаковв соответствии с шагом 1. Продолжать этот процесс до тех пор,пока все знаки не будут объединены.3.

Кодирование. Начать с последнего объединения. Приписать первой компоненте составного знака символ «0», а второй - символ «1». Продолжать этот процесс до тех пор, пока все простыезнаки не будут закодированы.В случае, когда несколько знаков имеют одинаковые вероятности,объединяются те два из них, которые до этого имели наименьшеечисло объединений. Этим достигается выравнивание длин кодовыхслов, что облегчает передачу информации.Рис.

3.3. Кодирование Хаффмана п = 4.Пример:Кодирование Хаффмана наглядно показано на примере источника, заданного табл. 3.2. При этом мы немного упростим кодирование,Глава 3. Кодирование для дискретных источников без памятиТаблица 3.3. Кодирование кодом Хаффмана к рис. 3.3.Xidfbеаср.0,40,20,150,150,050,05Кодовое слово0100101ПО11101111Длина кодового слова133344отказавшись от наглядных переупорядочений знаков на втором шаге, т.к.

в таком маленьком примере это можно сделать сделать «вуме». В соответствии с первым шагом, расположим все знаки в порядке убывания их вероятностей (рис.3.3).На втором шаге объединим символы «а» и «с», обладающие наименьшими вероятностями, в составной символ «ас». Далее объединим «е» с «ас» в составной символ «еас» с вероятностью 0.25.

Теперьнаименьшими вероятностями уже обладают символы «f» и «Ь». Объединив их, получим символ «fb». Следующая редукция дает составной символ «fbeac» с вероятностью 0,6. И, наконец, объединив всесимволы, получим составной символ «dfbeac», вероятность которогоравна 1.На третьем шаге будем идти справа налево, приписывая верхнимкомпонентам объединений символ «0», а нижним «1».

Полученныекодовые слова всех простых знаков с их длинами приведены в табл. 3.3.Данный код обладает минимальной средней длиной кодового слова.Средняя длина кодового слова определяется длинами всех слов щ,«взвешенными» с соответствующими вероятностями р;NП=(3.21)В рассмотренном выше примере средняя длина кодового словап = 2,3 бит близка к энтропии Н(Х) = 2,25 бит.

Важнейшей величиной, называемой эффективностью кода или фактором сжатия,является отношение средней длины к энтропии. В нашем примереэффективность кода равна г\ = 0,976.Эффективность кода или фактор сжатия(3.22)3.2. Коды ХаффманаИз примера отчетливо видно, что чем больше разница междувероятностями символов, тем больше выигрыш кода Хаффмана посравнению с простым блоковым кодированием.Теорема Шеннона о кодировании источников показывает, насколько эффективным может быть такое кодирование. Но теория информации также указывает на то обстоятельство, что при кодированиимогут появляться кодовые слова очень большой длины.

Это обстоятельство может препятствовать практическому использованию теоремы кодирования источников.Реализация декодера кода Хаффмана следует непосредственноиз рис. 3.3. На рис. 3.4 представлено дерево, называемое кодовымдеревом декодера.Декодирование каждого нового слова начинается с исходного узла (корня) кодового дерева. Если мы принимаем «О», то идем поребру, соответствующему нулю (по верхнему ребру).

В нашем примере при этом мы достигаем оконечного узла d. Следовательно, былнередан символ d и мы начинаем декодирование нового символа с,корня.Оконечный узелУзелРис. 3.4. Кодовая конструкция для D = 2 и п = 4.Если мы принимаем «1», то идем по нижнему ребру и попадаемв узел, из которого выходят два ребра. Следующий принятый битуказывает, какое из этих двух ребер нужно выбрать. Мы продолжаемэту процедуру до тех пор, пока не достигнем оконечного узла.

Вэтом случае мы принимаем решение о переданном символе и опятьпереходим к корню кодового дерева.При всей простоте построения и декодирования, коды Хаффманаобладают тремя недостатками:• Различные длины кодовых слов приводят к неравномерным за-Глава 3. Кодирование для дискретных источников без памятидержкам декодирования.• Сжатие данных снижает избыточность и поэтому повышаетпредрасположенность к распространению ошибок. В случае кодирования Хаффмана это означает, что один, ошибочно распознанный бит, может привести к тому, что все последующиесимволы будут декодированы неверно.• Кодирование Хаффмана предполагает знание вероятностей событий (знаков), или, по крайней мере, подходящих оценок этихвероятностей.

На практике очень часто вероятности событийнеизвестны, а их оценки весьма затруднены.Именно поэтому для сжатия больших массивов данных часто используют универсальный алгоритм кодирования, известный как алтгоритм Лемпеля-Зива. Описание этого алгоритма приведено в разделе 6.3.

Универсальный' алгоритм сжатия не требует априорногознания статистики источника.ГЛАВА 4ЭНТРОПИЯСВЯЗАННЫХисточниковДо сих пор в своих рассуждениях мы исходили из предположения независимости последовательных событий. Однако, стоит лишьтолько открыть немецкий орфографический словарь, мы сразу жеобнаружим зависимость между рядом стоящими буквами, напримерг«qu», «ch», «ck», «tz» и «sch». Читая немецкий текст, мы видим, чтопосле «q» за редким исключением следует «и».

В этом случае «и»,как почти неизбежное событие, практически не несет в себе никакойинформации. Поэтому, при определении информации подобного рода источников, мы должны принимать во внимание взаимную связьмежду событиями.4.1. Взаимная и условная информацияПри аксиоматическом построении теории информации использовалось такое понятие, как информация пары событий. Напомним иобобщим эти рассуждения. Рассмотрим два дискретных источникаX и У.

Объединим их события в пары событий (х{,Уг). Мы получимпростейшую модель связанных источников (рис.4.1).СимволыСвязанные источникиР и с . 4.1. Модель двух связанных источников.Глава 4- Энтропия связанных источниковЕсли оба источника каким-то образом связаны между собой, тоследует ожидать, что событие одного источника позволяет делатьнекоторое предположение о событии другого. В терминах теорииинформации это означает, что неопределенность второго источникаснижается, т.е.

источники обмениваются взаимной информацией.Введем условную вероятность р(х/у) - вероятность события хпри условии, что произошло событие у. Выразим совместную вероятность p(xi, г/г) двух событий Х{ и j/j через их априорные и условныевероятностиp{xi,yi)=p(xi/yi)p(yi)=p(yi/xi)p{Xi).(4.1)Используя логарифмическую функцию, сразу же получаем информации Событий {Xi,yi), (Xi) И (у)-Цим) битi(Vi) битто естьI{xi,Vi) = I(Vi) - ld(ii/3/j) бит = 1(ц) - \og2p{yi/xi) бит.(4.3)Прибавляя и одновременно вычитая I(xi) в первой части (4.3) и,соответственно, I{yi) во второй, получаем'l(Xi, уг) = (Xi) + 1(уг) - log2 ^^бит =Таким образом, информация пары событий (xi,yi) определяетсясуммой информации этих событий за вычетом некоторой неотрицательной величины, которая снижает неопределенность, т.е. сама всвою очередь является информацией.

Поэтому, назовем ее взаимнойинформацией нары событий.Взаимная информация нары событий определяется как7\/ апостериорная вероятность \= log2 (I.\ априорная вероятность /4-1- Взаимная и условном информация-Обратите внимание на то, что взаимная информация /(ж,; у,) всегда положительна. Важным свойством также является симметриявзаимной информации относительно источников, т.к.Р(Уг)Симметрия относительно источников в (4.5) позволяет сделатьвывод, что обмен информацией между источниками является взаимным, а не односторонним.Для того, чтобы лучше представлять себе смысл взаимной информации, рассмотрим два граничных случая.1. Источники независимы. Тогда для пары независимых событийимеемp(*i,Vi) = P{xi)p(yi),'(4.7)то есть источники не обмениваются информацией(4.8)1{Хг;Уг)=0.2.

Источники жестко связаны, то есть событие одного источникаоднозначно определяет событие другого) = 1.•(4.9)В этом случае происходит полный обмен информациейЦХГМ) = 1(ъ) = /(w).(4.10)Из (4.4) следует, что информацию пары событий {xi,yi) можно интерпретировать, как разность между информацией пары независимых событий l{xi) + I(yi) и заранее предсказанной взаимной информацией I(xi;yi), обусловленной связанностью источников X и YЦхит) = I(Xi) + 1{УГ) - 1{ХГ,1Н).(4.11)Рассмотрим еще раз (4.3) и введем понятие условной информации.Условная информация (апостериорная неопределенность)Iixilm)= - l o g a p f o / и ) бит.(4.12)Из (4.3) следует/(*<;») = 1{Уг) + I(Xi/yi)= Цц) + НУг/Xi),(4.13),38Глава 4- Энтропия связанных источниковто есть информацию пары событий можно определить как суммуинформации события у\ и информации события ж, при условии, чтособытие yi уже известно, или, наоборот, как сумму информации события Xi и информации события ;(/, при условии, что событие xt ужеизвестно.4.2.

Совместная и условная энтропияПосле рассмотрения отдельных нар событий в предыдущем разделе,перейдем к средним оценкам источника.На рис. 4.2 показана исходная ситуация.Алфавит Х={х,,...,хи\Вероятность р(х,)1^(ЖШ^^^ШШ"^ЖЖУсловная вероятность р(у} I Xj)Д ^ Д ИСТОЧНИК |„,_^_^_Алфавит К = ( ^УдВероятность р(у*),)II ^Символы-Я Н и ^ и ЛI Вероятность парысимволов р^,,у>)Связанные источникиР и с . 4.2. Два связанных дискретных источника.Совместная энтропия двух источников определяется как математическое ожидание информации всех пар событий.Совместная энтропия двух дискретных источников без памятиX HY^ т).(4.14)Замечание. Здесь подразумевается, что рассматриваются все пары совместных событий, то естьМ NA:Yt=i j=iУсредняя условные информации всех нар событий, получим условную энтропию.4-2. Совместная и условная энтропияТаблица 4.1.