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

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

Префикс и постфикс слова

Пусть задано конечное множество А = {a₁,…, a_n}, которое называется алфавитом. Элементы алфавита называются буквами. Последовательность букв называется словом (в данном алфавите). Множество слов в алфавите А обозначается А*. Если слово  = a₁,…, a_k  А*, то количество букв в слове называется длиной слова: || =|a₁…a_k| = k.

Пустое слово обозначается :   А*, || = 0,   А.

Если = ₁₂, то ₁ называется началом, или префиксом, слова , а ₂ — окончанием, или постфиксом, слова . Если при этом ₁   (соответственно, ₂  ), то ₁ (соответственно, ₂) называется собственным началом (соответственно, собственным окончанием) слова .

Таблица кодов

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

:=< a₁ ₁ , … , a_n _n>, a_i  A, _i  B* .

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

F: A*B*, a_i1 … a_ik=a A*, F(a): = _{i1 …}_ik .

Пример

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

 : =(0  0, 1 1, 2  10, 3  11, 4  100, 5  101, 6  110,

7  111, 8  1000, 9  1001).

Эта схема однозначна, но кодирование не является взаимно однозначным:

F_ (333) = 111111 = F_ (77),

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

 : =(0  0000, 1 0001, 2  0010, 3  0011, 4  0100, 5  0101,

6  0110, 7  0111, 8  1000, 9  1001).

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

Разделимые схемы

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

_i1 … _ik =_i1 … _ik  k = l&  t 1..k i_t = j_t,

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

Если таблица кодов содержит одинаковые элементарные коды, то есть если

 i,j ij & _i =_j,

где _i , _j  V , то схема заведомо не является разделимой. Такие схемы далее не рассматриваются, то есть

ij _i , _j  V  _i _j.

Префиксные схемы

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

( ij _i , _j  V)  (   B* _i _j).

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

Пример. Разделимая, но не префиксная схема: А = {a, b}, В = {0,1},  = {а  О, b  01}.

Неравенство Макмиллана

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

ТЕОРЕМА Если схема разделима, то

, где l_i=|_i|

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

ТЕОРЕМА Если числа l₁, … , l_n удовлетворяют неравенству

,

то существует разделимая схема алфавитного кодирования , где i l_i = |_i|.

Пример

Азбука Морзе — это схема алфавитного кодирования

(А01, B  1000, С  1010, D  100,Е  0,F  0010, G  110,

H  0000, I  00, J  0111, К  101, L  0100, M ll, N 10,

О  111, P 0110, Q  1101, R  010, S  000, T  1, U  001,

V  0001, W  011, X  1001, Y  1011, Z  1100),

где по историческим и техническим причинам 0 называется точкой и обозначается знаком «•», а 1 называется тире и обозначается знаком «—». Имеем:

1/4 + 1/16 + 1/16 + 1/8 + 1/2 + 1/16 + 1/8 + 1/16 + 1/4 + 1/16 + 1/8 + 1/16 + 1/4 + 1/4 + 1/8 + 1/16 + 1/16 + 1/8 + 1/8 + 1/2 + 1/8 + 1/16 + 1/8 + 1/16 + 1/16 + 1/16 = 2/2 + 4/4 + 7/8 + 12/16 = 3 + 5/8 > 1.

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