ГЛАВА ПЯТАЯ. ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

5.1. НАЗНАЧЕНИЕ И КЛАССИФИКАЦИЯ КОДОВ

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

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

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

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

Согласование по объему необходимо во всех случаях, когда объем алфавита источника I не совпадает с количеством различных символов для передачи которых пригоден используемый дискретный канал. Чаще всего так что каждый знак источника кодируется несколькими последовательными кодовыми символами. Так, например, в простейшем телеграфном коде Бодо каждая буква русского алфавита кодируется кодовым словом из пяти двоичных символов (0 и 1); в телеграфном коде Морзе на каждую букву алфавита затрачивается от двух до шести символов, принимающих значения «точка», «тире» и «пробел».

Остановимся подробнее на согласовании источника с каналом по избыточности. Пусть случайное сообщение А заменяется кодовой последовательностью В. Поскольку считаем кодирование обратимым, то, в соответствии с (2.141) и (2.142),

где — количество информации в кодовой последовательности относительно сообщения; энтропия сообщения; - энтропия кодовой последовательности. Следовательно, энтропия при кодировании не изменяется.

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

Пусть, например, избыточность источника велика, т. е. Тогда может стоять задача о таком кодировании, при котором избыточность уменьшается (в предельном случае вовсе устраняется). Эта задача эффективного (или экономного) кодирования уже рассматривалась в § 2.10. Там было показано, что оно позволяет увеличить скорость передачи сообщений по каналу с ограниченной пропускной способностью. В частности, осмысленный русский текст можно передавать, затрачивая всего лишь 1,5 двоичных символа на букву, вместо пяти при примитивном равномерном коде.

Не будем возвращаться к методам эффективного кодирования. Отметим только некоторые свойства кодовой последовательности,

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

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

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

При помехоустойчивом кодировании чаще всего считают, что избыточность источника на входе кодера Для этого имеются следующие основания: во-первых, очень многие дискретные источники (например, информация на выходе ЭВМ) обладают малой избыточностью; во-вторых, если избыточность первичных источников существенна, она обычно порождается сложными связями, которые в месте приема трудно использовать для повышения верности. Разумно поэтому в таких случаях по возможности уменьшить избыточность первичного источника путем

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

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

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

Далее коды можно разделить на блочные и непрерывные. Блочными называют коды, в которых последовательность элементарных сообщений источника разбивается на отрезки и каждый из них преобразуется в определенную последовательность (блок) кодовых символов называемую иногда кодовой комбинацией Непрерывные коды образуют последовательность символов не разделяемую на последовательные кодовые комбинации: здесь в процессе кодирования символы определяются всей последовательностью элементов сообщения.

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

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

Избыточностью равномерного кода называют, по аналогии с (2.127), величину

а относительной скоростью кода

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

В дальнейшем будем рассматривать, главным образом, двоичные коды Напомним, что множество всех возможных двоичных блоков или кодовых векторов длины образует линейное пространство (см. § 2.6), если под операцией сложения понимать поразрядное сложение по модулю 2, норму определить формулой (2.104), а под расстоянием понимать расстояние Хэмминга

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