Элементы теории кодирования

Цели кодирования

Решающий вклад в теорию передачи информации в конце 40-х годов, как известно, внес американский ученый Клод Шеннон. Он обосновал, в частности, эффективность ввода в систему передачи информации кодирующих-декодирующих устройств, основное назначение которых - согласование информационных свойств источника сообщений со свойствами канала связи.

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

Такое кодирование называется эффективным или оптимальным.

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

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

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

Такое разделение существенно упрощает исследование и проектирование кодеров-декодеров.

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

Некоторые общие свойства кодов .

Рассмотрим на примерах. Предположим, что дискретный источник выдающий на выходе сообщения , имеет алфавит из N букв или символов, поступающих с вероятностями p₁, p₂, …, p_N.

Каждый символ кодируется с использованием вторичного алфавита из m букв. Обозначим n_i - число букв в кодовом слове, которое соответствует i-й букве источника. Нас будет интересовать средняя длина кодового слова п_ср, которая находится по известной формуле:

В качестве примера рассмотрим возможные способы составления кодовых слов двоичного кода при объеме первичного алфавита к=4

Таблица 4.1

Заметим, что код 1 имеет неудачное свойство, состоящее в том, что буквы с номерами 1 и 2 кодируются одинаково - кодовым словом 0. Поэтому однозначное декодирование при использовании этого кода невозможно.

Код 2 обладает подобным же недостатком: последовательность из двух вторых букв первичного источника будет закодирована в 00, что совпадает с кодовым словом для буквы 3. Затруднений для декодирования в этом случае не будет только тогда, когда между кодовыми словами будет добавлен какой-либо разделительный символ. Но если такой символ ввести, то его можно понимать как дополнительную букву вторичного алфавита. Тогда каждое кодовое слово в конце или в начале просто дополняется этой буквой. В результате такой код можно рассматривать как частный случай кодов без разделительных символов. По этой причине коды с разделительными символами отдельно не рассматриваются.

Примером такого кода может служить код 4, где 0 можно, понимать как разделительный символ.

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

==================================

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

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

Нетрудно заметить, что коды 1 и 2 не являются префиксными.

Вопросы студентам:

1) являются ли коды 3 и 4 префиксными?

2) являются ли коды 3 и 4 однозначно декодируемыми?

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

На рис. 4.2. изображено кодовое дерево кода 3, описанного в таблице 4.1.

Рис. 4.2.

Каждому i-му кодовому слову длиной п_i, ставится в соответствие узел x_i, i-го порядка и определенный путь по кодовому дереву от корня до этого узла.

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