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

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

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

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

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

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

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

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

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

Пример

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

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

,

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

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

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

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

,

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

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

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

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

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

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

Доказательство

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

Поскольку , значит,, но это противоречит тому, что схема префиксная.

ЗАМЕЧАНИЕ

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

Пример

Разделимая, но не префиксная схема: .

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

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

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

, где

Доказательство

Обозначим . Рассмотримn-ю степень левой части неравенства

.

Раскрывая скобки, имеем сумму

где i_1...i_n– различные наборы номеров элементарных кодов. Обозначим черезколичество входящих в эту сумму слагаемых вида 1/2^t, гдеt=l_i1+…+l_in. Для некоторыхtможет быть, что=0. Приводя подобные, имеем сумму

.

Каждому слагаемому вида ()^-1можно однозначно сопоставить код (слово в алфавитеB) вида. Это слово состоит изnэлементарных кодов и имеет длинуt.

Таким образом, - это число некоторых слов вида, таких, что. В силу разделимости схемы, в противном случае заведомо существовали бы два одинаковых слова, допускающих различное разложение. Имеем

Следовательно, , и значит, откуда

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

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

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

Доказательство

Без ограничений общности можно считать, что . Разобьем множество {l₁,…,l_n} на классы эквивалентности по равенству {L₁,…,L_m},mn.

Пусть

Тогда неравенство Макмиллана можно записать так:

Из этого неравенства следуют mнеравенств для частичных сумм:

	(1)
	(2)
……….
	(m)

Рассмотрим слова длины в алфавите В. Поскольку, из этих слов можно выбратьразличных словдлины. Исключим из дальнейшего рассмотрения все слова из В^*, начинающиеся со слов. Далее рассмотрим множество слов в алфавите В длинойи не начинающихся со слов. Таких слов будет. Но, значит, можно выбратьразличных слов. Обозначим их. Исключим слова, начинающиеся с, из дальнейшего рассмотрения. И та далее, используя неравенства для частичных сумм, мы будем наi-м шаге выбиратьслов длины,, причем эти слова не будут начинаться с тех слов, которые были выбраны раньше. В то же время длины этих слов все время растут (так как), поэтому они не могут быть префиксами тех слов, которые выбраны раньше. Итак, в конце имеем набор изnслов, кодыне являются префиксами друг друга, а значит, схемабудет префиксной и, по теореме предыдущего подраздела, разделимой.

Пример

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

<A01,B1000,C1010,D100,E0,F0010,G110,

H0000,I00,J0111,K101,L0100,M11,N10,

O1111,P0110,Q1101,R010,S000,T1,U001,

V0001,W011,X1001,Y1011,Z1100>,

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

¼+1/16+1/16+1/8+½+1/16+1/8+1/16+¼+1/16+

1/8+1/16+1/4+1/4+1/8+1/16+1/16+1/8+1/8+

½+1/8+1/16+1/8+1/16+1/16+1/16 =

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

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