4.2 Кодирование в дискретных каналах без шума

Общие принципы кодирования. Дискретным m-ичным каналом без шумов называется канал, в котором сигналы на входе А(t) и выходе В(t) явля­ются последовательностями дискретных случайных величин-символов с основанием кода m, причем входной и выходной сигналы связаны взаимно однозначно (см. рис. 4.1.1)..

Пропускная способность такого канала равна наибольшему возможному значению энтропии сигнала А(t) на его входе

Из (2.4.5) имеем

или

(4.2.1)

где – частота следования символов в канале, симв/с.

Пусть Х⁽¹⁾, Х⁽²⁾, ... – последовательность символов s-ичного источника сообщений при многократном независимом выборе. Тогда скорость создания информации равна

,

(4.2.2)

где – частота следования символов источника,

Н(Х) – энтропия алфавита источника.

Функции кодирующего устройства заключаются в том, чтобы каждой из букв s-ичното алфавита источника поста­вить в соответствие кодовое слово, состоящее из букв m-ичного алфавита, используемого для передачи по каналу.

Кодирующее устройство должно удовлетворять двум основным требованиям:

1) обеспечивать безошибочную передачу информации, т.е. взаимно однозначное соответствие между Х(t) и А(t) (см. рис. 4.1.1);

2) осуществлять кодирование наиболее экономным обра­зом (с минимальной избыточностью).

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

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

1) использование специальной буквы;

2) применение кодовых слов одинаковой длины без разде­лительных букв – равномерное кодирование;

3) кодовая таблица составляется так, чтобы никакое кодо­вое слово не являлось началом другого, более длинного.

Требование экономичности заключается в том, что необходимо добиваться при кодировании минимальной средней дли­ны кодового слова

,

(4.2.3)

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

Средняя длина кодового слова ограничена снизу, так как для безошибочной передачи информации необходимо выпол­нение соотношения Н<С. Это обстоятельство сформулирова­но в теореме Шеннона о кодировании в дискретных каналах без шумов.

Теорема Шеннона. При кодировании множества сигналов с эн­тропией Н(Х) при условии отсутствия шумов средняя длина кодового слова не может быть меньше чем , где m –основание кода. Если вероятности сигналов не являются целочисленными отрицательными степенями числа m, то точное достижение указанной нижней границы невозможно, но при кодировании достаточно длинными блоками к ней можно cколь угодно приблизиться.

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

1) Более вероятным буквам источника соответствуют более короткие кодовые слова (принцип статистического кодирова­ния).

2) Никакое кодовое слово не является началом другого, более длинного.

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

4) Символы в последовательности на выходе кодера прак­тически независимы.

Наилучшим среди этих кодов является код, предложен­ный Д.А. Хафманом.

Код Хафмана. Кодирование алфавита, состоящего из s букв, по методу Хафмана осуществляется следую­щим образом.

1) Буквы алфавита источника располагаем в порядке убы­вания их вероятностей.

2) Выбираем целое число m₀, такое, что

и ,

где а – целое положительное число.

При кодировании в двоичном канале m₀ = m = 2.

Производим первое сжатие алфавита, т.е. группируем вмес­те m₀ букв алфавита источника, имеющих наименьшие вероятности, и обозначаем новой буквой. Вычисляем общую веро­ятность такого сгруппированного подмножества букв.

3) Буквы нового алфавита, полученного в результате пер­вого сжатия, снова располагаем в порядке убывания вероят­ностей.

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

5) Буквы нового алфавита, полученного на 4-м шаге, рас­полагаем в порядке убывания вероятностей.

6) Осуществляем последовательные сжатия алфавита пу­тем повторения операций 4 и 5, пока в новом алфавите не ос­танется единственная буква.

7) Проводим линии, которые соединяют буквы, образую­щие последовательные вспомогательные алфавиты. Получает­ся дерево, в котором отдельные сообщения являются конце­выми узлами. Соответствующие им кодовые слова получаем, если приписать различные буквы m-ичного алфавита ветвям, исходящим из каждого промежуточного узла.

Код Хафмана имеет среднюю длину кодового слова, не боль­шую чем любой другой код.

Код Шеннона-Фано. Кодирование осуществляется следующим образом.

1) Буквы алфавита источника располагаем в порядке убы­вания вероятностей.

2) Делим алфавит источника на m групп так, чтобы общие вероятности букв в каждой из групп были примерно равны. В качестве первого символа кодового слова выбираем 0,1, ..., m-1 в зависимости от того, в которой из групп ока­залась кодируемая буква.

3) Каждую из групп снова разбиваем на m примерно рав­новероятных подгрупп и в качестве второго символа кодово­го слова выбираем 0,1, …, m-1 в зависимости от того, в которой из подгрупп оказалась кодируемая буква.

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

Блоковое кодирование. Выше были рассмотрены способы побуквенного коди­рова­ния, когда каждой букве на выходе источника приписы­валось свое кодовое слово. Такой способ кодирования позво­ляет достигнуть минимальной средней длины кодового слова, равной , только в том случае, когда вероятности букв являются отрицательными целочисленными степенями числа m. Если вероятности не удовлетворяют этому требованию, избыточность при побуквенном кодировании может оказаться недопустимо большой. В таком случае применяют блоковое кодирование.

При кодировании блоками по k букв прежде всего строят вспомогательный алфавит, состоящий из N=s^k букв, так что каждой букве этого алфавита соответствует своя комбинация (блок) из k букв алфавита источника. Вероятность буквы z_ij…q вспомогательного алфавита, соответствующей комбина­ции x_ix_j…x_q, в простейшем случае вычисляется по формуле

.

(4.2.4)

Далее буквы вспомогательного алфавита располагаются в порядке убывания вероятностей, и осуществляется кодирова­ние методом Шеннона-Фэно или Хафмана.

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

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

Код Лемпела–Зива свободен от этого недостатка. Здесь кодовая таблица, изначально почти пустая, заполняется одновременно в пунктах передачи и приема в процессе кодирования (декодирования), причем в эту таблицу вносятся лишь такие все более длинные отрезки передаваемого сообщения, которые еще не встречались ранее. Каждому отрезку в таблице присваивается n-разрядный номер. При внесении очередной записи (строки) в таблицу передается блок, содержащий:

1) номер отрезка, уже имеющегося в таблице;

2) символ, следующий в передаваемом сообщении за этим отрезком.