Префиксный код Шеннона-Фано. Коды шеннона - фано

Одно и тоже сообщение можно закодировать различными способами. Наиболее выгодным является такой код, при использование которого на передачу сообщений затрачивается минимальное время. Если на передачу каждого элемента символа (например, 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

Процесс декодирования сообщения

Принятая кодовая последовательность

Итак, слово, полученное в результате декодирования принятой кодовой комбинации – «кодер».

Кодирование Шеннона-Фано является одним из самых первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон (Shannon) и Фано (Fano). Данный метод сжатия имеет большое сходство с кодированием Хаффмана , которое появилось на несколько лет позже. Главная идея этого метода - заменить часто встречающиеся символы более короткими кодами, а редко встречающиеся последовательности более длинными кодами. Таким образом, алгоритм основывается на кодах переменной длины. Для того, чобы декомпрессор впоследствии смог раскодировать сжатую последовательность, коды Шеннона-Фано должны обладать уникальностью, то есть, не смотря на их переменную длину, каждый код уникально определяет один закодированый символ и не является префиксом любого другого кода.
Рассмотрим алгоритм вычисления кодов Шеннона-Фано (для наглядности возьмём в качестве примера последовательность "aa bbb cccc ddddd"). Для вычисления кодов, необходимо создать таблицу уникальных символов сообщения c(i) и их вероятностей p(c(i)) , и отсортировать её в порядке невозрастания вероятности символов.

c(i)	p(c(i))
d	5 / 17
c	4 / 17
space	3 / 17
b	3 / 17
a	2 / 17

Далее, таблица символов делится на две группы таким образом, чтобы каждая из групп имела приблизительно одинаковую частоту по сумме символов. Первой группе устанавливается начало кода в "0", второй в "1". Для вычисления следующих бит кодов символов, данная процедура повторяется рекурсивно для каждой группы, в которой больше одного символа. Таким образом для нашего случая получаем следующие коды символов:

Длина кода s(i) в полученной таблице равна int(-lg p(c(i))) , если сиволы удалость разделить на группы с одинаковой частотой, в противном случае, длина кода равна int(-lg p(c(i))) + 1 .

длиной в 39 бит. Учитывая, что оргинал имел длину равную 136 бит, получаем коэффициент сжатия ~28% - не так уж и плохо.
Глядя на полученную последовательность, возникает вопрос: "А как же теперь это расжать?". Мы не можем, как в случае кодирования, заменять каждые 8 бит входного потока, кодом переменной длины. При расжатии нам необходимо всё сделать наоборот - заменить код переменной длины символом длиной 8 бит. В данном случае, лучше всего будет использовать бинарное дерево, листьями которого будут являтся символы (аналог дерева Хаффмана).
Кодирование Шеннона-Фано является достаточно старым методом сжатия, и на сегодняшний день оно не представляет особого практического интереса (разве что как упражнение по курсу структур данных). В большинстве случаев, длина сжатой последовательности, по данному методу, равна длине сжатой последовательности с использованием кодирования Хаффмана. Но на некоторых последовательностях всё же формируются не оптимальные коды Шеннона-Фано, поэтому сжатие методом Хаффмана принято считать более эффективным. Для примера, рассмотрим последовательность с таким содержанием символов: "a" - 14, "b" - 7, "c" - 5, "d" - 5, "e" - 4. Метод Хаффмана сжимает её до 77 бит, а вот Шеннона-Фано до 79 бит.

символ	код Хаффмана	код Шеннона-Фано
a	0	00
b	111	01
c	101	10
d	110	110
e	100	111

Кстати, в одном источнике (не буду указывать каком), эту последовательность сжали методом Шеннона-Фано до 84 бит, а методом Хаффмана до тех же 77. Такие отличаи в степени сжатия возникают из-за нестрогого определения способа деления символов на группы.
Как же мы делили на группы? Достаточно просто:

Из-за такой неопределённости у некоторых людей возникают даже такие мысли: "... программа иногда назначает некоторым символам..." и так далее - рассуждения о длине кодов. Если вы не пишете AI, то такое понятие, как "программа иногда" что-то делает, звучит смешно. Правильно реализованный алгоритм - работает строго опеределённо.

Код Шеннона-Фано

Код строится следующим образом:

1) буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей;

2) затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковы;

3) всем буквам верхней половины в качестве первого символа приписывается 1, а всем нижним - 0;

4) каждая из полученных групп, в свою очередь, разбивается на две подгруппы с одинаковыми суммарными вероятностями и т. д.

Процесс повторяется до тех пор, пока в каждой подгруппе останется по одной букве.

Пример. Рассмотрим алфавит из восьми букв (табл. 12). При обычном (не учитывающем статистических характеристик) кодировании для представления каждой буквы требуется три символа.

Таблица 8.12 Таблица 13

Буквы	Вероятности	Кодовые комбинации	Буквы	Вероятности	Кодовые комбинации
	0,22	11		0,22	11
	0,20	101		0,20	10
	0,16	100		0,16	011
	0,16	01		0,16	010
	0,10	001		0,10	001
	0,10	0001		0,10	0001
	0,04	00001		0,04	00001
	0,02	00000		0,02	00000

Вычислим энтропию набора букв: Н

и среднее число символов на букву

где n() - число символов в кодовой комбинации, соответствующей букве.

Значения Н(z) и l ср не очень различаются по величине. Условие теоремы Шеннона выполнено Н(z) <= l ср

Рассмотренная методика Шеннона-Фано не всегда приводит к однозначному построению кода. Ведь при разбиении на подгруппы можно сделать большей по вероятности как верхнюю, так и нижнюю подгруппу.

Множество вероятностей в предыдущей таблице можно было разбить иначе (табл. 13). При этом среднее число символов на букву оказывается равным 2,80. Таким образом, построенный код может оказаться не самым лучшим. При построении эффективных кодов с основанием s > 2 неопределенность становится еще больше.

Метод Хаффмена

Метод Хаффмена свободен от недостатка связанного с неоднозначностью построения кода. Данная методика также использует статистические свойства источника сообщений. Метод гарантирует однозначное построение кода с наименьшим для данного распределения вероятностей средним числом символов на букву.

В таблице 14 показаны основные шаги построения кода.

Таблица 14

Буквы	Вероятности	Вспомогательные столбцы
Буквы	Вероятности	1	2	3	4	5	6	7
	0,22	0,22	0,22	0,26	0,32	0,42	0,58	1
	0,20	0,20	0,20	0,22	0,26	0,32	0,42
	0,16	0,16	0,16	0,20	0,22	0,26
	0,16	0,16	0,16	0,16	0,20
	0,10	0,10	0,16	0,16
	0,10	0,10	0,10
	0,04	0,06
	0,02

Для двоичного кода методика сводится к следующему:

1) Буквы алфавита сообщений выписываются в основной столбец в порядке убывания вероятностей;

2) две последние буквы объединяются в одну вспомогательную букву, которой приписывается суммарная вероятность;

3) вероятности букв, не участвовавших в объединении, и полученная суммарная вероятность снова располагаются в порядке убывания вероятностей в дополнительном столбце, а две последние буквы снова объединяются.

Процесс продолжается до тех пор, пока не получим единственную вспомогательную букву с вероятностью, равной единице.

Для составления кодовой комбинации, соответствующей данному сообщению, необходимо проследить путь перехода сообщений по строкам и столбцам таблицы. Для наглядности строится кодовое дерево(рис.1).

Рис.1 Кодовое дерево

Из точки, соответствующей вероятности 1, направляются две ветви, причем ветви с большей вероятностью присваивается символ 1, а с меньшей - 0. Такое последовательное ветвление продолжается до тех пор, пока не дойдем до каждой буквы (рис. 1).

Теперь, двигаясь по кодовому дереву сверху вниз, можно записать для каждой буквы соответствующую ей кодовую комбинацию;

01 00 111 110 100 1011 10101 10100

Оптимальным кодом можно определить тот, в котором каждый двоичный символ будет передавать максимальную информацию. В силу формул Хартли и Шеннона максимум энтропии достигается при равновероятных событиях, следовательно, двоичный код будет оптимальным, если в закодированном сообщении символы 0 и 1 будут встречаться одинаково часто.

Рассмотрим в качестве примера оптимальное двоичное кодирование букв русского алфавита вместе с символом пробела «-». Полагаем, что известны вероятности появления в сообщении символов русского алфавита, например, приведенные в таблице 3.

Таблица 3.Частота букв русского языка (предположение)

К. Шеннон и Р. Фано независимо предложили в 1948-1949 гг. способ построения кода, основанный на выполнении условия равной вероятности символов 0 и 1 в закодированном сообщении.

Все кодируемые символы (буквы) разделяются на две группы так, что сумма вероятностей символов в первой группе равна сумме вероятностей символов второй группы (то есть вероятность того, что в сообщении встретится символ из первой группы, равна вероятности того, что в сообщении встретится символ из второй группы).

Для символов первой группы значение первого разряда кода присваивается равным «0», для символов второй группы – равными «1».

Далее каждая группа разделяется на две подгруппы, так чтобы суммы вероятностей знаков в каждой подгруппе были равны. Для символов первой подгруппы каждой группы значение второго разряда кода присваивается равным «0», для символов второй подгруппы каждой группы – «1». Такой процесс разбиения символов на группы и кодирования продолжается до тех пор, пока в подгруппах не остается по одному символу.

Пример кодирования символов русского алфавита приведен в табл. 4

Таблица 4. Пример кодирования букв русского алфавита с помощью кода Шеннна-Фано.

Анализ приведенных в таблице кодов приводит к выводу, что часто встречающиеся символы кодируются более короткими двоичными последовательностями, а редко встречающиеся - более длинными. Значит, в среднем для кодирования сообщения определенной длины потребуется меньшее число двоичных символов 0 и 1, чем при любом другом способе кодирования.

Вместе с тем процедура построения кода Шеннона-Фано удовлетворяет критерию различимости Фано. Код является префиксным и не требует специального символа, отделяющего буквы друг от друга для однозначного него декодирование двоичного сообщения.

Таким образом, проблема помехоустойчивого кодирования представляет собой обширную область теоретических и прикладных исследований. Основными задачами при этом являются следующие: отыскание кодов, эффективно исправляющих ошибки требуемого вида; нахождение методов кодирования и декодирования и простых способов их реализации.

Наиболее разработаны эти задачи применительно к систематическим кодам. Такие коды успешно применяются в вычислительной технике, различных автоматизированных цифровых устройствах и цифровых системах передачи информации.

Заключение

Мы рассмотрели задачу кодирования, которая включает в себя:

1.Обеспечение экономичности передачи информации посредством устранения избыточности.

2. Обеспечение надежности (помехоустойчивости) передачи информации

3.Согласование скорости передачи информации с пропускной способностью канала

Задача кодирования является одним из главных понятий информатики, так как кодирование предшествует передаче и хранению информации, и, соответственно, является основой их успешного осуществления.

При передаче сообщений по каналам связи могут возникать помехи, способные привести к искажению принимаемых знаков. Эта проблема решается с помощью помехоустойчивого кодирования. Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Впервые, исследование эффективного кодирования произвел Клод Шеннон. Для теории связи важнейшее значение имеют две теоремы, доказанные Шенноном.

В работе были рассмотрены эти теоремы, и можно прийти к выводу, что первая – затрагивает ситуацию с кодированием при передаче сообщения по линии связи, в которой отсутствуют помехи, искажающие информацию, т.е. эта теорема является эталоном, какими должны быть помехоустойчивые коды, Вторая теорема относится к реальным линиям связи с помехами.

Если рассмотреть примеры кодирования, на основе первой теоремы Шеннона, то можно прийти к выводам, что это кодирования является достаточно эффективным, так как получаемый код практически не имеет избыточности, но, к сожалению, в реальных линиях связи множество помех, и такой результат недостижим. Поэтому код Шеннона не является таким же эффективным как, например код Хафмена. Но, несмотря на это нужно отметить, что Клод Шеннон был одним из основателей теории кодирования и его работы внесли огромный вклад в развитие информатики.

Список литературы:

1. Журнал "Радио", номер 9, 1999г.

наук, г. Москва

2. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984.

3. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР,

4. Рябко Б.Я Фионов А.Н. Эффективный метод адаптивного

арифметического кодирования для источников с большими алфавитами

// Проблемы передачи информации 1999 Т.35, Вып С.95 - 108.

5. Семенюк В.В. Экономное кодирование дискретной информации СПб.:

СПбГИТМО (ТУ), 2001

6. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа,

7. Нефедов В.Н Осипова В.А. Курс дискретной математики. М.: МАИ,

8. Колесник В.Д Полтырев Г.Ш. Курс теории информации. М.: Наука,

Оптимальное кодирование

Теорема кодирования Шеннона. Методы побуквенного оптимального кодирования. Критерии оптимальности кода. Блочное кодирование. Единая система кодирования текстовой информации.

Кодирование , минимизирующее избыточность кода , называется оптимальным .

Вопрос существования таких кодов составляет суть одной из основных теорем теории информации – теоремы кодирования, доказанной К. Шенноном. Приведем одну из эквивалентных формулировок данной теоремы.

Теорема кодирования . Сообщения произвольного источника информации 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.

Очевидно, что процесс построения кода в общем случае содержит неоднозначность, так как мы не всегда можем поделить последовательность на два равновероятных подмножества. Либо слева, либо справа сумма вероятностей будет больше. Критерием лучшего варианта является меньшая избыточность кода. Заметим также, что правильное считывание кода – от корня дерева к символу – обеспечит его префиксность.