Теория информации
Конспект лекций
назад | содержание | вперед

3. ПОБУКВЕННОЕ КОДИРОВАНИЕ

 

3.2 Префиксные и разделимые коды

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

При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

Пример 3.2.1  Код из примера 3.1 не является разделимым, поскольку кодовое слово 010010 может быть декодируемо двумя способами:   или .

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

Пример 3.2.2. Код из примера 3.1 не является префиксным, поскольку элементарный код буквы является префиксом элементарного кода буквы .

Утверждение. Префиксный код является разделимым.

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

Пример 3.2.3. Заметим, что разделимый код может быть не префиксным.

Пусть . Пример разделимого, но не префиксного кода:

 

 

наверх

 


назад | содержание | вперед