4. Требования к кодам для каналов связи без шума. Классификация эффективных кодов и их основные характеристики. Правило построения кодового дерева. Теоремы Шеннона об эффективном кодировании.

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

Требования: Код должен быть однозначно декодируемым и содержать минимум нулей и единиц в кодовой комбинации.

Классификация эффективных кодов

Коды сжатия:

I. С потерями – сжатие за счет удаления визуальной избыточности.

II. Без потерь –за счет устранения статистической избыточности:

1. С известной статистикой сообщений

• Хаффмена

• Шеннона-Фано

• Арифметический

2. С неизвестной статистикой сообщений

• Комбинаторный метод

• Словарные методы

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

Теоремы Шеннона об эффективном кодировании:

1. Для любого однозначно декодируемого кода всегда выполняется неравенство:

и существует однозначно декодируемый код для которого

(1)

2. Используя кодирование блоков можно получить среднее число символов на сообщение, сколь угодно мало отличающихся от энтропии.

Обозначим множество всех блоков длины в алфавите от А как Аⁿ, тогда энтропия множества всех блоков: H(Аⁿ )=n∙H(A)

(2)

Выражение (2) вытекает из выражения (1). Если в (1) заменим среднюю длину кодовой комбинации на среднюю длину блока, а энтропию на множество:

H(A) на H(Аⁿ )

то

Чем больше длина кода, тем лучше, но увеличивается сложность кодирования-декодирования.

4. Эффективное кодирование при известной статистике сообщений: коды Шеннона-Фано и Хаффмана. Правила построения. Достоинства и недостатки кодов. Применение.

Метод Шеннона

1. Все имеющиеся сообщений располагают в один столбик в порядке убывания вероятностей.

2. Затем упорядоченные сообщения разбивают на две группы (верхнюю и нижнюю) так, чтобы суммарные вероятности этих групп были по возможности ближе друг к другу.

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

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

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

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

1. Все имеющиеся сообщений располагают в один столбик в порядке убывания вероятностей.

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

3. Далее берут два сообщения, имеющие наименьшие вероятности, объединяют их в одно и вычисляют их общую вероятность.

4. Шаги 2 и 3 повторяют до тех пор, пока не получат единственное сообщение, вероятность которого равна единице.

5. Проводя линии, объединяющие сообщения и образующие последовательные подмножества, получают дерево, в котором отдельные сообщения являются концевыми узлами. Соответствующие им кодовые слова можно построить, приписывая ветви, которые идут вниз - «0», а вверх - «1».

Коды Шеннона-Фано и Хаффмена эффективнее равномерного кода. Средний коэффициент сжатия равен 2…4. Применяются для сжатия текстов, изображений и т.д.

Недостатки:

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

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

3. Минимальная длина кодового слова не может быть меньше 1, тогда как энтропия сообщения может составлять 10-е, 100-е доли бит/сообщ.

4. Для Хаффмена необходимо иметь таблицу вероятностей для каждого типа сжимаемых данных.