Кодирование в дискретном канале связи без помех

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

Пусть имеется некоторый ансамбль сообщений.

Выберем для кодирования сообщений некоторый код с основанием K и закодируем каждое сообщение некоторым словом соответствующей длины: n₁, n₂,,…,n_j,…,n_M. При выборе n_j для кодирования некоторого сообщения с вероятностью P(j) нужно исходить из следующего соображения: чем больше вероятность кодовой комбинации, тем меньше длина слова (количество информации в кодовом слове должно быть не меньше информации в кодируемом сообщении):

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

Таким образом, n_j тем больше, чем P(j) меньше.

Определим среднюю длину кодового слова:

При K = 2 n_CP = H_И.

Выражение logK определяет число бит, переносимых одним элементом, а n_CP – ту предельно короткую длину кодовой комбинации, которую можно получить при наилучшем выборе кода. Учитывая это, коды, средняя длина слов которых удовлетворяет условию

называется оптимальным (n_CP можно не округлять до натурального числа).

Разработаны регулярные (формализованные) методы построения оптимальных кодов для каналов связи без помех:

1. метод Шеннона-Фано;
2. метод Хафмена.