Алфавитное кодирование

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

Пусть задано конечное множество , которое называется алфавитом. Элементы алфавита называются буквами. Последовательность букв называется словом. Множество слов в алфавите A обозначается . Если слово , то количество букв в слове называется длиной слова: .

Пустое слово обозначается .

Если , то называется началом, или префиксом, слова , а – окончанием, или постфиксом, слова . Если при этом (соответственно, ), то (соответственно, ) называется собственным началом (соответственно, собственным окончанием) слова .

Алфавитное (или побуквенное) кодирование задается схемой (или таблицей кодов) :

.

Множество кодов букв называется множеством элементарных кодов. Алфавитное кодирование пригодно для любого множества сообщений :

, , .

Пример 9.1. Рассмотрим алфавиты , и схему:

Эта схема однозначна, но кодирование не является взаимно однозначным: , а значит, невозможно декодирование. С другой стороны, схема

известная под названием «двоично-десятичное кодирование», допускает однозначное декодирование.