5.2. ОСНОВЫ ЭФФЕКТИВНОГО КОДИРОВАНИЯ

Сформулируем задачу статистического кодирования, которую часто приходится решать в технике документальной электросвязи. Пусть имеется сообщение, записанное с помощью букв некоторого алфавита содержащего К букв. Алфавит А назовем входным. Требуется закодировать это сообщение, т. е. указать правило, которое сопоставляет каждой букве алфавита последовательность из символов «0» и «1».

Таблица 5.1

Выбранный код, во-первых, должен обеспечивать возможность однозначного декодирования, т. е. позволять по принятой последовательности символов «0» и «1» однозначно восстановить переданное сообщение (букву). Во-вторых, на передачу сообщения в среднем должно быть затрачено минимальное число нулей и единиц, что позволит передать за единицу времени максимальное число сообщений.

Пример 5.1. Пусть Некоторые возможные коды для букв алфавита А представлены в табл. 5.1.

Код 1 не является однозначно декодируемым кодом. Для доказательства этого рассмотрим, например, двоичную последовательность 0101. Она может быть декодирована одним из сообщений: ; Код 2 декодируется однозначно, поскольку все кодовые слова этого кода имеют равные длины и различны. Код 3 также однозначно декодируемый, поскольку никакое его кодовое слово не является началом (префиксом) другого кодового слова.

Код, обладающий тем свойством, что никакое более короткое слово не является началом другого более длинного слова кода, называют префиксным. Префиксные коды всегда однозначно декодируемы.