Алфавитное (побуквенное) кодирование

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

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

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

.

Множество букв называется множеством элементарных кодов. Таким образом, буква кодируется словом в алфавите .

Алфавитное кодирование пригодно для любого множества сообщений :

.

Пример. Рассмотрим алфавиты ={0,1,2,3,4,5,6,7,8,9} и схему

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

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

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

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

Теорема. Префиксная схема является разделимой.

Чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы длины элементарных кодов удовлетворяли определенному соотношению, известному как неравенство Макмиллана.

Теорема. Если схема разделима, то , где .

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

Теорема. Если числа удовлетворяют неравенству , то существует разделимая схема алфавитного кодирования , где .

Пример. Для схемы кодирования

левая часть неравенства Макмиллана может быть записана в виде

.

Отсюда следует, что данная схема кодирования не разделима.

Для случая двоично–десятичного кодирования –

– имеем

,

что говорит о разделимости схемы кодирования.

Пример. Схему кодирования, лежащую в основе азбуки Морзе, можно записать

,где по историческим и техническим причинам 0 называется точкой, а 1 – тире. Проведя проверку на разделимость получим

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