Алфавитное кодирование. Разделимые схемы. Префиксные схемы. Неравеснтво Макмиллана

Алфавитное кодирование – представление информации в стандартной форме, при которой элементарным синтаксическим единицам языка сообщений (буквам алфавита языка) последовательно сопоставляются кодовые комбинации символов из некоторого заданного алфавита (здесь под информацией понимается линейная запись букв). Примером алфавитного кодирования может служить известный код Морзе, в котором слова кодируются побуквенно, а буквам сопоставлены слова в алфавите трех символов {*, –, ˄ } где ˄ - пробел.

А= {а₁,..., а_n}- алфавит канала связи, т. е. перечень сигналов, которые могут передаваться по каналу, t(а_i) -длительность сигнала а i, В = {b₁,..., b_т}- алфавит языка сообщений. Суть кодирования заключается в том, что каждой букве алфавита А сопоставляется слово из алфавита В согласно схеме кодирования.

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

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

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

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

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

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

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

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

Теорема: Пусть заданы кодируемый и кодирующий алфавиты, состоящие из n и d символов, соответственно, и заданы желаемые длины кодовых слов: l1, l2, …, ln. Тогда необходимым и достаточным условием существования разделимого и префиксного кодов, обладающих заданным набором длин кодовых слов является выполнение неравенства.