КОДИРОВАНИЕ СООБЩЕНИЙ, КОДЫ ФАНО, ШЕННОНА И ХАФФМАНА 19.03.2019 1

i = 1,2…,K ) в алфавит некоторых кодовых символов R={xj},

(j = 1,2,…,N ).

Обычно размер алфавита кодовых символов |R| существенно меньше размера алфавита источника |A|.

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

источника сообщений в кодовые слова, называют кодом.

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

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

Еще одной целью кодирования является засекречивание передаваемой информации. При этом элементарным сообщениям
ak1 ak2…akn
 
из алфавита A ставятся в соответствие последовательности, к примеру, цифр или букв из специальных кодовых таблиц, известных лишь отправителю и получателю информации.

Примером кодирования может служить преобразование дискретных сообщений ak1 ak2…akn из одних систем счисления в другие.
Кодирование в канале, или помехоустойчивое кодирование информации, используется для уменьшения количества ошибок, возникающих при передаче по каналу с помехами.

неравномерные. Если кодовые слова имеют разную длину, то код называется

неравномерным. Типичным представителем этой группы является код Морзе.


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

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

Наибольшее распространение получили двоичные коды, или коды с основанием 2, для которых размер алфавита кодовых символов R={0,1} равен двум

соответствие сообщениям ai соответствующие им коды

кодового дерева

с некоторой точки - корня кодового дерева - проводятся ветви

- 0 или 1. На вершинах кодового дерева находятся буквы алфавита источника, причем каждой букве соответствуют свой лист и свой путь от корня к листу. К примеру, букве А соответствует код 000, букве В – 010, букве Е – 101 и т.д.

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


Равномерные коды очень широко используются в силу своей простоты и удобства процедур кодирования-декодирования: каждой букве – одинаковое число бит; при получении заданного числа бит – в кодовой таблице ищется соответствующая буква

кода с использованием N кодовых символов необходимо обеспечить выполнение следующего

условия:
K ≤ Nq ,

или



где q – количество элементов кодовой последовательности.
Например, при двоичном кодировании 32-х букв русского алфавита используется q = log2 32 = 5 разрядов, на чем и основывается телетайпный код.

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

максимальна при равновероятных буквах исходного текста.


Например, для телетайпного кода Н0 = 5 бит, а с учетом неравномерности появления различных букв исходного алфавита Н  4,35 бит. Устранение избыточности достигается применением неравномерных кодов, в которых буквы, имеющие наибольшую вероятность, кодируются наиболее короткими кодовыми последовательностями, а более длинные комбинации присваиваются редким буквам.

qi, то средняя длина комбинации


Считая кодовые буквы равномерными, определяем

наибольшую энтропию закодированного алфавита как qср log K, которая не может быть меньше энтропии исходного алфавита Н, т.е.

qср log K  Н.


Отсюда имеем qср  (Н / log K).

Обычно К=2 и qср  Н !!

кодирование. В идеальном случае, когда qср  Н, код называют

эффективным.


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

В равномерных кодах такая проблема не возникает, т.к. при расшифровке

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

Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101

буквам алфавита соответствовали лишь листья кодового дерева (Рисунок). Здесь ни

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

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

Рассмотрим

пример кодирования сообщений ai из алфавита объемом K = 8 с помощью произвольного q-разрядного двоичного кода.
Пусть источник сообщений выдает некоторый текст с алфавитом от А до З и одинаковой вероятностью букв Р(ai) = 1/8.
Кодирующее устройство кодирует эти буквы равномерным трехразрядным кодом (см. таблицу).
Определим основные информационные характеристики источника с таким алфавитом:
энтропия источника




избыточность источника



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


- избыточность кода .

(равномерного) кода оказалась равной нулю.
Пусть теперь вероятности появления в тексте

различных букв будут разными :

H =1,781

Среднее число символов на одно сообщение при использовании того же равномерного трехразрядного кода,



а избыточность

или довольно значительной величиной - в среднем 4 символа из 10 не несут никакой информации !!!

коды обладают большой избыточностью, было предложено использовать неравномерные коды, размер

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



Методы построения префиксных кодов

следующих ПЯТИ шагов:

1. Буквы алфавита А упорядочиваем по убыванию

вероятностей:
Р(a1) ≥ Р(a2) ≥…≥ Р(aK).

2. Множество упорядоченных букв разбивается на два подмножества А(0), А(1) с помощью некоторого порогового целого числа 1 ≤ k(1) ≤ K -1 так, чтобы величина

достигала наименьшего возможного значения.
Буквам из подмножества А(0) приписываем 0, буквам подмножества А(1) приписываем 1.

букв, то разбиваем множество букв каждой из подгрупп на две

подгруппы А(00), А(01) и А(10), А(11), соответственно, с помощью пороговых целых чисел ,








так, чтобы величины

1 ≤ k(11) ≤ k(1) -1,

k(1) ≤ k(12) ≤ K -1

достигали наименьших возможных значений. Буквам из подгрупп А(00), А(10) с нулевыми последними индексами приписываем 0, буквам из подгрупп А(10), А(11) приписываем 1.
Если подгруппа А(ij) i,j = 0,1 состоит более чем из одной буквы, то переходим к шагу 4. Если все подгруппы состоят из одной буквы, то переходим к шагу 5.

то разбиваем каждую из них на две подгруппы, исходя из

соотношения, введенного на шаге 2. Буквам подгрупп с нулевыми последними индексами приписываем нуль, буквам подгрупп с единичными последними индексами приписываем единицу.
Если все образовавшиеся подгруппы состоят из одной буквы, то переходим к шагу 5. Если есть подгруппы, состоящие более чем из одной буквы, то повторяем шаг 4.


5. Если образовавшиеся подгруппы состоят из одной буквы, то последовательно, начиная с первой метки, выписываем нули и единицы, относящиеся к каждой букве алфавита А.
 
В итоге получается двоичный префиксный код для заданного источника.

2,44. Соответствующее кодовое дерево имеет вид:

множество следующее:


S = {00, 01, 10, 110, 1110, 1111}.

n. Предположим, что вершине а n-го порядка предшествует вершина b

(n-l)-гo порядка, из которой выходит единственное ребро, ведущее в а. Других рёбер из вершины b не выходит. Операцию удаления этого ребра и превращения промежуточной вершины b (n-l)-гo порядка в концевую вершину будем называть операцией усечения. Средняя кодовая длина после операции усечения становится меньше. Пример, приведен ниже.

префиксное множество, то можно определить некоторый вектор v(S) = (q1,

q2, ... , qK), состоящий из чисел, являющихся длинами соответствующих префиксных последовательностей т.е. qi – это длина wi.
Вектор (q1, q2, ... , qk), состоящий из неуменьшающихся положительных целых чисел, удовлетворяющих неравенству Крафта

,
называется вектором Крафта.

Для него справедливо следующее утверждение: если S – какое-либо префиксное множество, то v(S) – вектор Крафта.
Иными словами, длины двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта.

множество, то v(S) – вектор Крафта.
Иными словами, длины

двоичных последовательностей в префиксном множестве удовлетворяют неравенству Крафта.
Неравенство Крафта формулируется в виде следующей теоремы:
Теорема. Пусть q1, q2, ... , qK набор положительных целых чисел. Для того чтобы существовал префиксный код с длинами кодовых слов q1, q2, ... , qK, необходимо и достаточно, чтобы выполнялось неравенство

удовлетворяющими неравенству Крафта, является префиксным. Например, множество двоичных кодовых слов

{0,01,11} удовлетворяет неравенству, но не
обладает свойством префикса

Примеры простейших префиксных множеств и соответствующие им векторы Крафта:
S1 = {0, 10, 11} и v(S1) = ( 1, 2, 2 );
S2 = {0, 10, 110, 111} и v(S2) = ( 1, 2, 3, 3 );
S3 = {0, 10, 110, 1110, 1111} и v(S3) = ( 1, 2, 3, 4, 4 );
S4 = {0, 10, 1100, 1101, 1110, 1111} и v(S4) = ( 1, 2, 4, 4, 4, 4 );

Буквы алфавита А упорядочиваем по убыванию вероятностей:
Р(a1) ≥ Р(a2) ≥…≥

Р(aK).
2. Находим числа qi, i=1, …, K, исходя из условия:

3. Подсчитываем накопленные суммы:

P1 =0, Р2 = P(a1), Р3 = P(a1) + P(a2), ...

Рi в двоичную дробь: i=1, …, K. Цифры этого разложения,

стоящие после запятой, являются кодовым словом, соответствующим букве ai.
5. Если необходимо, производим операцию усечения.

Для сравнения методов рассмотрим тот же самый источник сообщений и проделаем последовательно шаги алгоритма:

дерево до и после усечения имеет вид:
Алгоритм Шеннона-Фано применим

и при основании кода больше двух (K > 2). В этом случае алфавит разбивается на K частей примерно одинаковой суммарной вероятности

к хорошему результату, вследствие отсутствия четких рекомендаций относительно того, как

делить множество кодируемых знаков на подгруппы. Рассмотрим методику кодирования Хаффмана, которая свободна от этого недостатка.

Кодируемые знаки, также как при использовании метода Шеннона и Фано, располагают в порядке убывания их вероятностей (таблица).
Далее на каждом этапе две последние позиции списка заменяются одной и ей приписывают вероятность, равную сумме вероятностей заменяемых позиций.
После этого производится пересортировка списка по убыванию вероятностей, с сохранением информации о том, какие именно знаки объединялись на каждом этапе.
Процесс продолжается до тех пор, пока не останется единственная позиция с вероятностью, равной 1.

узел с вероятностью, равной 1.

б) Далее каждому узлу приписываются

два потомка с вероятностями, которые участвовали в формировании значения вероятности обрабатываемого узла.

в) Так продолжают до достижения узлов, соответствующих вероятностям исходных знаков

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

ставится в соответствие символ 1, а с меньшей – 0.
Спуск от корня к нужному знаку дает код этого знака. Правило кодирования в случае равных вероятностей оговаривается особо.
Жирным шрифтом в таблице выделены объединяемые позиции, подчеркиванием – получаемые при объединении позиции.

В ЭТОМ ПРИМЕРЕ:

H(Z) = 2,37

кодов Фано и Шеннона среднее количество двоичных символов, приходящееся на

символ источника, приближается к энтропии источника, но не равно ей.
Данный результат представляет собой следствие теоремы кодирования без шума для источника (первой теоремы Шеннона), которая утверждает:

1. При любой производительности источника сообще­ний, меньшей пропускной способности канала, т. е. при условии

Ī(Z) =Сд – ε, 
где ε — сколь угодно малая, положительная величина,
существует способ кодирования, позволяющий переда­вать по каналу все сообщения, вырабатываемые источ­ником.

2. Не существует способа кодирования, обеспечиваю­щего передачу сообщений без их неограниченного накоп­ления, если Ī(Z) > Сд.

с энтропией Н(Z) всегда можно закодировать последовательностями символов с объемом

алфавита m так, что среднее число символов на знак сообщения qср будет сколь угодно близко к величине
Н(Z)/log m,
но не менее ее.
Данное утверждение обосновывается также указа­нием на возможную процедуру кодирования, при кото­рой обеспечивается равновероятное и независимое по­ступление символов на вход канала, а следовательно, и максимальное количество переносимой каждым из них информации, равное log m. Как мы установили ранее, в общем случае это возможно, если кодировать сообще­ния длинными блоками. Указанная граница достигается асимптотически при безграничном увеличении длины кодируемых блоков.

можно устранить, если перейти к кодированию достаточно большими бло­ками.

Попробуем

на примере алфавита из 2 букв – А и Б.
Пусть р(А)=0.7 и р(Б)=0.3
Н=-0.7*log(0.7)-0.3*log(0.3)=0.881…

код
А 0.7

1
Б 0.3 0


1*0.7+1*0.3=1 двоичн. знаков на букву.

1-0.881= 0.12 . Стало быть, на 12% больше минимального по Шеннону значения 0.881.

код
АА 0.7*0.7=0,49

1
АБ 0.7*0.3=0,21 01
БА 0.3*0.7=0,21 001
ББ 0.3*0.3=0,21 000

1*0.49+2*0.21+3*0.3=1,81

На одну букву приходится 1,81/2=0,905 на 3% больше 0,881 !!!!

Если применить метод Ш-Ф для 3-х буквенных комбинаций ААА, ААБ итд
получится 0, 895 двоичных знаков – на 1.5% больше.

Обычно знаки на вход устройства кодирования поступают через равные промежутки

времени. Если им соответствуют комбинации различной длины, то для обеспечения полной загрузки канала при передаче без потерь необходимо предусмотреть буферное устройство, как на передающей, так и на приемной стороне.
2. Задержка в передаче информации. Достоинства эффективного кодирования проявляются в полной мере при кодировании длинными блоками. Для этого необходимо накапливать знаки, как при кодировании, так и при декодировании, что приводит к значительным задержкам.
3. Низкая помехозащищенность. Даже одиночная ошибка, возникшая в процессе передачи, может нарушить свойство префиксности кода и повлечь за собой неправильное декодирование ряда последующих комбинаций. Это явление называют треком ошибки.
4. Сложность технической реализации. Использование буферных устройств, для обеспечения равномерной загрузки канала, при разной длине кодовых комбинаций и организация кодирования блоками для повышения эффективности приводят к усложнению реализации систем эффективного кодирования.

символов, вероятности появления которых равны 0.6, 0.3 и 0.1. Корреляция

между символами отсутствует. Определить избыточность кода.

y j )= P( y j )P(xi | y j

) .