Экономность кода

Сформулируем основную математическую задачу, с которой приходится иметь дело в технике связи. Пусть имеется сообщение, записанное при помощи некоторого алфавита, содержащего n символов. Требуется закодировать это сообщение, т.е. указать правило, сопоставляющее каждому такому сообщению определённую последовательность из m различных элементарных сигналов (m = 2 - двоичный, m = 3 - троичный)

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

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

Нетрудно понять, какой код будет наиболее выгодным: будем измерять выгодность (эко-номность) данного двоичного кода при помощи максимального числа элементарных сиг-налов (цифр) из 0 и 1, требующегося для передачи одной буквы. Можно показать, что наи-большее число k элементарных сигналов, приходящихся на 1 букву удовлетворяет нера-венству k > log n (n- число букв алфавита). Этот факт объясняется соображениями теории информации: одна буква N - буквенного алфавита может содержать информацию, рав-ную 1б = log n, а каждый передаваемый элементарный сигнал, принимающий одно из двух значений (посылка тока или пауза) может содержать информацию не более, чем 1 бит. Поэтому, для передачи одной буквы надо, чтобы число элементарных сигналов было не менее log n.