1.3. Кодирование и декодирование, относящиеся к источнику

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

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

возможных на заданном временном интервале сообщений, допустимых при передаче.

Предположим на время, что множество сообщений, допустимых при передаче, конечно. Если обозначать через число сообщений в этом множестве, то каждому сообщению, подлежащему передаче, можно приписать одно из целых чисел от 0 до Затем число, соответствующее некоторому частному сообщению, можно записать в двоичной форме и этим сопоставить ему последовательность двоичных символов. Например, 27-му сообщению из множества 64 допустимых при передаче сообщений будет приписана последовательность Она получается следующим путем:

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

Для равного любому целому числу, большему 64, но меньшему или равному 128, будет требоваться 7 символов. Вообще, число символов должно быть равно наименьшему целому числу, большему или равному двоичному логарифму от

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

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

Рис. 1.2. Пример кодирования кодами с фиксированной и переменной длиной.

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

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

Средняя длина кодового слова (ожидаемая длина) для множества двоичных кодовых слов рис. 1.2 равна 2,75, что меньше числа символов в двоичных числах, приведенных во втором столбце. Отсюда мы заключаем, что число двоичных символов, требуемых в среднем для представления допустимого при передаче сообщения, можно уменьшить, используя тот факт, что различные сообщения не появляются с одинаковыми вероятностями. Мы увидим в гл. 3, что множество кодовых слов, приведенных в четвертом столбце рис. 1.2, является оптимальным в том смысле, что он задает наименьшее возможное среднее число символов на одно допустимое при передаче сообщение. Мы увидим также, что в оптимальном множестве кодовых слов длина каждого кодового слова равна двоичному логарифму от величины обратной вероятности сообщения (или приближенно равна этой величине, если логарифм не целое число).

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

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

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

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