Построение кода шеннона фано онлайн. Коды шеннона - фано
Оптимальное кодирование
Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.
Кодирование , минимизирующее избыточность кода , называется оптимальным .
Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.
Теорема кодирования
. Сообщения произвольного источника информации Z с энтропией H
(Z
) всегда можно закодировать последовательностями в алфавите B
, состоящем из M символов
, так
, что средняя длина кодового слова будет сколь угодно близка к величине
, но не меньше нее.
Доказательство этой теоремы в силу его сложности не рассматривается.
Теорема утверждает, что разность можно сделать как угодно малой. В этом и заключается задача методов оптимального кодирования.
Вернемся к рассмотрению алфавитного источника информации, генерирующего сообщения в символах алфавита А . Поскольку избыточность кода задается формулой
очевидно, что чем меньше , тем оптимальнее код. Для уменьшения следует кодировать часто встречающиеся символы более короткими словами и наоборот. На соблюдении этого требования основаны все методы оптимального кодирования. Кроме того, для обеспечения декодирования неравномерного кода важно соблюдать принцип префиксности : никакое кодовое слово не должно являться началом другого кодового слова.
Приведем два наиболее известных метода оптимального побуквенного кодирования. Для простоты изложения возьмем двоичный алфавит в качестве кодового.
Шаг 1. Упорядочиваем символы исходного алфавита в порядке невозрастания их вероятностей. (Записываем их в строку.)
Шаг 2. Не меняя порядка символов, делим их на две группы так, чтобы суммарные вероятности символов в группах были по возможности равны.
Шаг 3. Приписываем группе слева "0", а группе справа "1" в качестве элементов их кодов.
Шаг 4. Просматриваем группы. Если число элементов в группе более одного, идем на Шаг 2. Если в группе один элемент, построение кода для него завершено.
Рис. 4.1. Двоичное дерево, соответствующее кодированию по методу Шеннона – Фано
Рассмотрим работу описанного алгоритма на примере кодирования алфавита 
, символы которого встречаются с вероятностями (0,25; 0,05; 0,25; 0,1; 0,25; 0,1) соответственно. Результат кодирования изображен на рис. 4.1.
Очевидно, что процесс построения кода в общем случае содержит неоднозначность, так как мы не всегда можем поделить последовательность на два равновероятных подмножества. Либо слева, либо справа сумма вероятностей будет больше. Критерием лучшего варианта является меньшая избыточность кода. Заметим также, что правильное считывание кода – от корня дерева к символу – обеспечит его префиксность.
ЛАБОРАТОРНАЯ РАБОТА 9
Эффективное кодирование
Цель: Изучение методик эффективного кодирования.
1. Построить код Шеннона-Фано по выбранным вариантам и результаты свести в таблицы.
2. Построить код Хаффмана по выбранным вариантам и результаты свести в таблицы. Для каждого построенного кода построить кодовое дерево.
Отчет по лабораторной работе должен содержать:
– краткие теоретические сведения о коде Шеннона-Фано и коде Хаффмана;
– построить коды Шеннона-Фано и Хаффмана при различных вариантах входных данных (для каждого кода выбрать произвольно три группы по 12 символов в каждой, присвоить каждому символу вероятность (сумма равна единице) и построить указанные коды).
– выводы.
Основные понятия и определения
Код Шеннона-Фано
Код строят следующим образом: знаки алфавита сообщений вписываются в таблицу в порядке убывания вероятностей. Затем их разделяют на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы. Всем знакам верхней половины в качестве первого символа приписывают «0», а всем нижним – «1». Каждую из полученных групп, в свою очередь разбивают на две подгруппы с одинаковыми суммарными вероятностями и т. д. Процесс повторяется до тех пор, пока в каждой подгруппе останется по одному знаку.
Пример 1. Проведем эффективное кодирование ансамбля из восьми знаков, характеристики которого представлены в табл. 3.1.
Таблица 3.1
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0.22 | ||
| Z 2 | 0.2 | ||
| Z 3 | 0.16 | ||
| Z 4 | 0.16 | ||
| Z 5 | 0.1 | ||
| Z 6 | 0.1 | ||
| Z 7 | 0.04 | ||
| Z 8 | 0.02 |
Рис. 3.1. Дерево группового разделения вероятностей Шеннона-Фано
Ясно, что при обычном (не учитывающем статистических характеристик) кодировании для представления каждого знака требуется три двоичных символа. Используя методику Шеннона-Фано, получаем совокупность кодовых комбинаций, приведенных в табл. 3.1.
Так как вероятности знаков представляют собой целочисленные отрицательные степени двойки, то избыточность при кодировании устраняется полностью. Среднее число символов на знак в этом случае точно равно энтропии. Убедимся в этом, вычислив энтропию
,
и среднее число символов на знак
,
где – число символов в кодовой комбинации, соответствующей знаку .
В общем случае для алфавита из восьми знаков среднее число символов на знак будет меньше трех, но больше энтропии алфавита .
Пример 2. Определим среднюю длину кодовой комбинации при эффективном кодировании знаков ансамбля. Приведенного в табл. 3.2.
Энтропия ансамбля равна 2,76. В результате сопоставления отдельным знакам ансамбля кодовых комбинаций по методике Шеннона-Фано (табл. 3.2) получаем среднее число символов на знак, равное 2,84.
Таблица 3.2
Характеристики ансамбля из восьми знаков
| Знаки | Вероятность | Кодовые комбинации | Ступень разбиения |
| Z 1 | 0,22 | ||
| Z 2 | 0,20 | ||
| Z 3 | 0,16 | ||
| Z 4 | 0,16 | ||
| Z 5 | 0,10 | ||
| Z 6 | 0,10 | ||
| Z 7 | 0,04 | ||
| Z 8 | 0,02 |
Следовательно, некоторая избыточность в последовательностях символов осталась. Из теоремы Шеннона следует, что эту избыточность также можно устранить, если перейти к кодированию достаточно большими блоками.
Алгоритм построения сжимающего кода Шеннона – Фано заключается в следующем.
1. Все символов дискретного источника располагаются в порядке убывания вероятностей их появления (табл. 4.2).
Таблица 4.2. Построение кода Шеннона-Фано
2. Образованный столбец символов делится на две группы таким образом, чтобы суммарные вероятности каждой группы мало отличались друг от друга.
3. Верхняя группа кодируется символом «1», а нижняя – «0».
4. Каждая группа делится на две подгруппы с близкими суммарными вероятностями; верхняя подгруппа кодируется символом «1», а нижняя – «0».
5. Процесс деления и кодирования продолжается до тех пор, пока в каждой подгруппе не окажется по одному символу сообщения источника.
6. Записывается код для каждого символа источника; считывание кода осуществляется слева направо.
При использовании простейшего равномерного кода для кодирования шести элементов алфавита источника потребуется по три двоичных символа на каждую букву сообщения. Если же используется код Шеннона – Фано, то среднее число символов на одну букву
Одно и тоже сообщение можно закодировать различными способами. Наиболее выгодным является такой код, при использование которого на передачу сообщений затрачивается минимальное время. Если на передачу каждого элемента символа (например, 0 или 1) тратится одно и то же время, то оптимальным будет такой код, при использование которого на передачу сообщения заданной длины будет затрачено минимальное количество элементарных символов. Коды Шеннона – Фано являются префиксными, т.е. никакое кодовое слово не является префиксом любого другого. Данное свойство позволяет однозначно декодировать любую последовательность кодовых слов
Рассмотрим принцип построения одного из первых алгоритмов сжатия, который сформулировали американские ученые Шеннон и Фано на примере букв русского алфавита. Алгоритм использует коды переменной длины, т.е. часто встречающийся символ кодируется кодом меньшей длины, редко встречающийся – кодом большей длины .
Чтобы составить такой код, очевидно, нужно знать частоты появления букв в русском тексте. Эти частоты приведены в таблице 1 . Буквы в таблице расположены в порядке убывания частот.
Таблица 1
Частота появления букв русского алфавита
Пользуясь таблицей, можно составить наиболее экономичный код на основе соображений, связанных с количеством информации. Очевидно, код будет самым экономичным, когда каждый элементарный символ будет передавать максимальную информацию. Рассмотрим элементарный символ (т. е. изображающий его сигнал) как физическую систему с двумя возможными состояниями: 0 и 1. Информация, которую дает этот символ, равна энтропии этой системы и максимальна в случае, когда оба состояния равновероятны; в этом случае элементарный символ передает информацию 1 (двоичная единица). Поэтому основой оптимального кодирования будет требование, чтобы элементарные символы в закодированном тексте встречались в среднем одинаково часто.
Идея кодирования состоит в том, что кодируемые символы (буквы или комбинации букв) разделяются на две приблизительно равновероятные группы: для первой группы символов на первом месте комбинации ставится 0 (первый знак двоичного числа, изображающего символ); для второй группы − 1. Далее каждая группа снова делится на две приблизительно равновероятные подгруппы; для символов первой подгруппы на втором месте ставится 0; для второй подгруппы − единица и т. д.
Продемонстрируем принцип построения кода Шеннона − Фано на примере материала русского алфавита (см. табл. 1). Отсчитаем первые шесть букв (от «−» до «т»); суммируя их вероятности (частоты), получим 0,498; на все остальные буквы от «н» до «ф» придется приблизительно такая же вероятность 0,502. Первые шесть букв (от «−» до «т») будут иметь на первом месте двоичный знак 0. Остальные буквы (от «н» до «ф») будут иметь на первом месте единицу. Далее снова разделим первую группу на две приблизительно равновероятные подгруппы: от «−» до «о» и от «е» до «т»; для всех букв первой подгруппы на втором месте поставим нуль, а второй подгруппы − единицу. Процесс будем продолжать до тех пор, пока в каждом подразделении не останется ровно одна буква, которая будет закодирована определенном двоичным числом. Механизм построения показан на таблице 2, а сам код приведен в таблице 3.
Таблица 2
Механизм построения кода Шеннона – Фано на примере русского алфавита
| Двоичные знаки | |||||||||
| Буквы | 1 й | 2 й | 3 й | 4 й | 5 й | 6 й | 7 й | 8 й | 9 й |
| - | |||||||||
| о | |||||||||
| е | |||||||||
| а | |||||||||
| и | |||||||||
| т | |||||||||
| н | |||||||||
| с | |||||||||
| р | |||||||||
| в | |||||||||
| л | |||||||||
| к | |||||||||
| м | |||||||||
| д | |||||||||
| п | |||||||||
| у | |||||||||
| я | |||||||||
| ы | |||||||||
| з | |||||||||
| ъ, ь | |||||||||
| б | |||||||||
| г | |||||||||
| ч | |||||||||
| й | |||||||||
| х | |||||||||
| ж | |||||||||
| ю | |||||||||
| ш | |||||||||
| ц | |||||||||
| щ | |||||||||
| э | |||||||||
| ф |
Таблица 3
Результат кодирования букв русского алфавита кодом Шеннона - Фано
Пример 4. Запишем фразу «способ кодирования», используя код Шеннона - Фано.
Решение: Воспользуемся таблицей 3 и получим следующий результат:
(1001)с (110011)п (001)о (1001)с (001)о (111010)б (000)пробел
(10111)к (001)о (110010)д (0110)и (10100)р (001)о (10101)в
(0101)а (1000)н (0110)и (110110)я
Заметим, что здесь нет необходимости отделять друг от друга буквы специальным знаком, так как и без этого декодирование выполняется однозначно благодаря свойству префиксности: ни одна более короткая кодовая комбинация не является началом более длинной кодовой комбинации. Действительно, из таблицы 3 видно, что самыми короткими являются коды для символов «пробел» и «о». При этом не один другой более длинный код не имеет в начале последовательности 000 («пробел») и 001 («о»). То же самое можно наблюдать и для всех других двоичных последовательностей кода Шеннона – Фано, которые приведены в таблице 3.
Необходимо отметить, что любая ошибка при кодирование (случайное перепутывание знаков 0 или 1) при таком коде губительна, так как декодирование всего следующего за ошибкой текста становится невозможным.
Пример 5. Определим, является ли рассмотренный нами код оптимальным при отсутствие ошибок?
Решение: Найдем среднюю информацию, приходящуюся на один элементарный символ (0 или 1), и сравним ее с максимально возможной информацией, которая равна единице. Для этого найдем сначала среднюю информацию, содержащуюся в одной букве передаваемого текста, т. е. энтропию на одну букву (см. формулу 8):
По таблице 1 определяем среднее число элементарных символов на букву:
Таким образом, информация на один символ весьма близка к своему верхнему пределу единице, а данный код весьма близок к оптимальному.
В случае использования пятиразрядного двоичного кода информация на один символ:
Пример 6. Пусть по каналу связи получено сообщение (слово на русском языке) закодированное кодом Шеннона – Фано: 10111001110010010010100.
Необходимо декодировать данную последовательность.
Решение: Процесс декодирования основывается на свойстве префиксности кода и выполняется слева на право. Из таблицы 3 видно, что минимальная длина кода составляет три бита. Отсчитает три бита от начала принятой кодовой комбинации, получим – 101. В таблице такой код отсутствует, поэтому добавляем еще один бит, получим – 1011. Данного кода также нет в таблице, следовательно, необходимо добавить еще один бит, получим комбинацию – 10111, которой соответствует буква «к». Кодовая комбинация 10111 исключается из принятой кодовой комбинации и заменяется исходным символом (буква «к»). Процесс декодирования остальных букв принятого сообщения выполняется аналогично.
Полный процесс декодирования приведен в таблице 4. Знак «-» в таблице означает, что в таблице 3 отсутствует выбранный код.
Таблица 4
Процесс декодирования сообщения
| Принятая кодовая последовательность | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| - | ||||||||||||||||||||||
| к | ||||||||||||||||||||||
| к | о | |||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | - | ||||||||||||||||||||
| к | о | д | ||||||||||||||||||||
| к | о | д | - | |||||||||||||||||||
| к | о | д | е | |||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | - | ||||||||||||||||||
| к | о | д | е | р |
Итак, слово, полученное в результате декодирования принятой кодовой комбинации – «кодер».
