Вернер М. Основы кодирования (2004), страница 4
Описание файла
PDF-файл из архива "Вернер М. Основы кодирования (2004)", который расположен в категории "". Всё это находится в предмете "основы теории и техники радиосистем передачи информации (рспи)" из 9 семестр (1 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 4 страницы из PDF
Выберем для каждого слагаемого такое наименьшее п^, при котором£Г"* < рк.(3.17)Неравенство Крафта при таком выборе будет выполняться, следовательно, используя конструкцию рис. 3.2, мы можем построитьтакой префиксный код. Так как п/, наименьшее целое, при которомимеет место (3.17), то для nk — 1 справедливорк < D-{nk~l).Остальная часть доказательства лишь формальна.(3.18)3.2. Коды Хаффмана29)Используя свойства логарифмической функции, получаемPfclogPfc < Pit log D~(nk~^ = pk(—Пк + l)logi).(3.19)Суммируя по всем К, имеемк(3.20)-H(X)Разделив обе части неравенства на \ogD и переставляя члены сдомножением на —1 (что меняет знак неравенства), получаем искомое доказательство.
•3.2. Коды ХаффманаКоды Хаффмана1 принадлежат к семейству кодов с переменной длиной кодовых слов. Самый известный код неременной длины - азбукаМорзе2 (табл. 3.1). Основная идея азбуки Морзе - передавать частовстречающиеся буквы кодовыми словами короткой длины и, наоборот, редко встречающиеся буквы длинными кодовыми словами длятого, чтобы минимизировать средние затраты. Такой способ кодирования называют так же кодированием с минимальной избыточностью или энтропийным кодированием.Так, например, в азбуке Морзе часто встречающаяся буква «Е»кодируется одним знаком «•», а редкая «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- Энтропия связанных источниковЕсли оба источника каким-то образом связаны между собой, тоследует ожидать, что событие одного источника позволяет делатьнекоторое предположение о событии другого.