Метод кодирования шеннона фано c. Префиксный код Шеннона-Фано

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 14

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

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. Колесник В.Д Полтырев Г.Ш. Курс теории информации. М.: Наука,

При ответе на данный вопрос необходимо привести пример построения префиксного кода Шеннона-Фано для заданного начального алфавита и известных частот использования символов этого алфавита с помощью таблицы и графа.

В 1948-1949 гг. Клод Шеннон (Claude Elwood Shannon ) и Роберт Фано (Robert Mario Fano ) независимо друг от друга предложили префиксный код, названный в последствие в их честь. Алгоритм Шеннона - Фано использует избыточность сообщения, заключённую в неоднородном распределении частот символов его первичного алфавита, то есть заменяет коды более частых символов короткими двоичными последовательностями, а коды более редких символов - более длинными двоичными последовательностями.

Рассмотрим этот префиксный код на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении соответственно {0,15; 0,2; 0,1; 0,3; 0,2; 0,05}. Расположим эти символы в таблице в порядке убывания их вероятностей.

Кодирование осуществляется следующим образом. Все знаки делятся на две группы с сохранением порядка следования (по убыванию вероятностей появления), так чтобы суммы вероятностей в каждой группе были приблизительно равны. В нашем примере в первую группу попадают символы D и B, все остальные буквы попадают во вторую группу. Поставим ноль в первый знак кодов для всех символов из первой группы, а первый знак кодов символов второй группы установим равным единице.

Продолжим деление каждой группы. В первой группе два элемента, и деление на подгруппы здесь однозначно: в первой подгруппе будет символ D, а во второй - символ B. Во второй группе теоретически возможны три способа деления на подгруппы: {E} и {A, C, F}, {E, A} и {C, F}, {E, A, C} и {F}. Но в первом случае абсолютная разность суммарных вероятностей будет |0,2 - (0,15 + 0,1 + 0,05)| = 0,1. Во втором и третьем варианте деления аналогичные величины будут 0,2 и 0,4 соответственно. Согласно алгоритму необходимо выбрать тот способ деления, при котором суммы вероятностей в каждой подгруппе были примерно одинаковыми, а, следовательно, вычисленная разность минимальна. Соответственно наилучшим способом деления будет следующий вариант: {E} в первой подгруппе и {A, C, F} во второй. Далее по имеющемуся алгоритму распределим нули и единицы в соответствующие знаки кода каждой подгруппы.

Осуществляем деление на подгруппы по той же схеме до тех пор, пока не получим группы, состоящие из одного элемента. Процедура деления изображена в таблице (символ Х означает, что данный знак кода отсутствует):

Данный код может быть построен и с помощью графа. Распределим символы алфавита в порядке убывания вероятностей - это будут концевые вершины (листья) будущего двоичного дерева (нижние индексы соответствуют вероятностям появления символов):

Согласно алгоритму построения кода Шеннона-Фано разобьем эти символы на две группы с приблизительно равными суммарными вероятностями появления и соединим первые символы каждой группы с корнем дерева:

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

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

Окончательно имеем следующий граф:

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

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

D 0,3	B 0,2	E 0,2	A 0,15	C 0,1	F 0,05

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

Полученный код удовлетворяет условию Фано, следовательно он является префиксным. Средняя длина этого кода равна (см. формулу на стр.13):

К(Шеннона-Фано, А, Binary) = 0,3*2+0,2*2+0.2*2+0,15*3 +0,1*4+0.05*4 = 2,45 символа.

Теперь по известной нам формуле найдем избыточность кода Шеннона –Фано:

Q(Шеннона-Фано, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

То есть избыточность кода Шеннона-Фано для нашего шестибуквенного алфавита составляет всего около 1,7 %. Для русского алфавита этот избыточность кодирования кодом Шеннона-Фано составила бы примерно 1,47%.

Префиксный код Хаффмана.

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

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

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

Рассмотрим алгоритм построения кода Хаффмана на примере. Пусть имеется первичный алфавит, состоящий из шести символов: {A; B; C; D; E; F}, также известны вероятности появления этих символов в сообщении соответственно {0,15; 0,2; 0,1; 0,3; 0,2; 0,05}. Расположим эти символы в таблице в порядке убывания их вероятностей.

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

Теперь начинается второй этап алгоритма кодирования по Хаффману. Для формирования кода мы нумеруем символы всех промежуточных алфавитов, начиная с последнего. В нашем примере – с А 4 .

В А 4 всего два символа. Они получают соответственно номера 0 и 1. В алфавите А 3 уже три символа. Причем, один из символов алфавита А 4 , назовем этот символ «предок», был получен объединением двух символов алфавита А 3 , назовем первый из этих символов «дочкой», а второй «сыном». Коды этих двух символов формируются следующим образом. К номеру «предка» приписываются справа 0, чтобы получить номер «дочки», и 1 – чтобы получить номер «сына». Следующая итерация алгоритма по той же схеме формирует коды символов алфавита А 2 . В нем два первых символа будут иметь те же коды, что были у них в А 1 , а два последних символа изменят свой код, удлинив его на 1 символ («0» и «1» соответственно). Процесс останавливается при достижении первичного алфавита A 0 – коды для знаков первичного алфавита получены.

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

В получившемся промежуточном алфавите вновь выбираем два символа с наименьшей частотой использования. Это символ А с вероятностью 0,15 и новый символ, получившийся в результате объединения символов C и F на предыдущем этапе и имеющий ту же вероятность использования. Соединяем эти символы дугами, исходящими из одного узла N-2 уровня:

Посчитаем среднюю длину кодового слова для кода Хаффмана и нашего первичного алфавита А.

К(Хаффман, А, Binary) = = 0,3*2 + 0,2*2 + 0.2*2 + 0,15*3 + 0,1*4 + 0.05*4 = 2,45 символа

Среднее количество информации на один символ первичного алфавита равно:

I A = - (0,3* log 2 0,3 + 0,2* log 2 0,2 + 0,2* log 2 0,2 + 0,15* log 2 0,15 + + 0,1* log 2 0,1 + 0,05* log 2 0,05) = 2,41 бит.

Относительная избыточность кода Хаффмана в нашем случае:

Q(Хаффмана, A, Binary) = 2,45/2,41 – 1 = 0,01659751.

Таким образом, для нашего примера код Шеннона-Фано и код Хаффмана обладают одинаковой избыточностью. Однако, в тех случаях когда вероятности символов первичного алфавита сильно разнятся, ситуация меняется. Код Хаффмана обладает существенно меньшей избыточностью. Например, для русского языка избыточность кодирования кодом Хаффмана оказывается равной примерно 0,0090.

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

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

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

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

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

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

Алгоритм метода Шеннона-Фано - один из первых алгоритмов сжатия, который впервые сформулировали американские учёные Шеннон и Фано, и он имеет большое сходство с алгоритмом Хаффмана. Алгоритм основан на частоте повторения. Так, часто встречающийся символ кодируется кодом меньшей длины, а редко встречающийся - кодом большей длины.
В свою очередь, коды, полученные при кодировании, префиксные. Это и позволяет однозначно декодировать любую последовательность кодовых слов. Но все это вступление.

Для работы оба алгоритма должны иметь таблицу частот элементов алфавита.

Итак, алгоритм Хаффмана работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные .
2. Выбираются две наименьших по частоте буквы алфавита, и создается родитель (сумма двух частот этих «листков»).
3. Потомки удаляются и вместо них записывается родитель, «ветви» родителя нумеруются: левой ветви ставится в соответствие «1», правой «0».
4. Шаг два повторяется до тех пор, пока не будет найден главный родитель - «корень».

Алгоритм Шеннона-Фано работает следующим образом:

1. На вход приходят упорядоченные по невозрастанию частот данные.
2. Находится середина, которая делит алфавит примерно на две части. Эти части (суммы частот алфавита) примерно равны. Для левой части присваивается «1», для правой «0», таким образом мы получим листья дерева
3. Шаг 2 повторяется до тех пор, пока мы не получим единственный элемент последовательности, т.е. листок

Ну вот, быстро осмыслив информацию, можно написать код алгоритма Шеннона-Фано на паскале. Попросили именно на нем написать. Поэтому приведу листинг вместе с комментариями.

Program ShennonFano; uses crt; const a:array of char = ("a","b","c","d","e","f"); { символы } af:array of integer = (10, 8, 6, 5, 4, 3); { частота символов } { Процедура для поиска кода каждой буквы } procedure SearchTree(branch:char; full_branch:string; start_pos:integer; end_pos:integer); var dS:real; { Среднее значение массива } i, m, S:integer; { m - номер средней буквы в последовательности, S - сумма чисел, левой ветки } c_branch:string; { текущая история поворотов по веткам } begin { проверка если это вход нулевой то очистить историю } if (a<>" ") then c_branch:= full_branch + branch else c_branch:= ""; { Критерий выхода: если позиции символов совпали, то это конец } if (start_pos = end_pos) then begin WriteLn(a, " = ", c_branch); exit; end; { Подсчет среднего значения частоты в последовательности } dS:= 0; for i:=start_pos to end_pos do dS:= dS + af[i]; dS:= dS/2; { Тут какой угодно можно цикл for, while, repeat поиск середины } S:= 0; i:= start_pos; m:= i; while ((S+af[i] to show"); ReadLn; ClrScr; { Поиск кода Фано, входные параметры начало и конец последовательности } SearchTree(" "," ", 1, 6); ReadLn; end;

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

Спасибо за внимание!