11. Решение проблемы согласования

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

В п. 4 мы начали с обсуждения свойств канала. Мы предположили, что в канале имеется n символов

и что их относительные длительности равны . Мы нашли, что средняя информация на символ максимальна (см. п. 8), когда вероятность символа связана с его длительностью соотношением

где — постоянная.

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

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

Мы получим значительно лучшее решение, кодируя группы знаков посредством групп символов, однако обсуждение такой системы требует предварительного исследования вероятностей групп знаков. Мы имеем:

Определим показатели вероятностей :

(4.74) Группа символов , имеет вероятность

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

перепишем результаты, выражаемые формулами (4.18) и (4.23):

где — среднее число групп знаков при — коэффициент, введенный вместо прежнего . Аналогично

где — среднее число групп знаков при несравним теперь статистические свойства групп знаков и групп символов. Будем кодировать групп знаков посредством групп символов, присваивая, таким образом, кратчайшие кодовые обозначения наиболее часто встречающимся группам знаков. Приравняем и и воспользуемся соотношениями (4.77) и (4.23):

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

Так как и велики, последний член можно отбросить и записать:

Это соотношение выражает пропорциональность между показателем вероятности и длительностью

При таком кодировании символ длительностью будет иметь среднюю вероятность

а это и есть экспоненциальный закон (4.61) оптимального кодирования. Условие (4.78) оставляет нам значительную свободу в выборе частного способа кодирования, однако мы смогли доказать возможность выполнения наших условий согласования языка с каналом. Хорошее согласование требует

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

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

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

Так как и велики, мы можем пренебречь постоянной

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