АЛФАВИТНОЕ КОДИРОВАНИЕ

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

и .

Элементы алфавита называются буквами. Упорядоченный набор в алфавите А назовем словом

,где , число п показывает количество букв в слове и называется длиной слова , обозначается п =l( )=| |.

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

Для слова

буква a1, называется началом, или префиксом, слова , а буква an — окончанием, или постфиксом, слова .

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

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

Множество всех непустых слов алфавита А обозначим А*:

Множество А называют алфавитом сообщений, а множество В — кодирующим алфавитом. Множество слов, составленных в алфавите В,обозначим В*.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово назовем кодом слова .

Кодированием называют универсальный способ отображения информации при ее хранении, передаче и обработке в виде системы соответствий между элементами сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким образом, код — правило однозначного преобразования (т.е. функция) сообщения из одной символической формы представления (исходного алфавита А) в другую (объектный алфавит В), обычно без каких-либо потерь информации. Процесс преобразования F: А*→В* слов исходного алфавита А в алфавит Вназывается кодированием информации.

Процесс обратного преобразования слова в слово называется декодированием. Таким образом, декодирование — функция, обратная F, т.е. F-1.

Так как для любого кодирования должна выполняться операция декодирования, то отображение должно быть обратимым (биекция).

Если |B|= m, то F называется m-ичным кодированием, наиболее распространенный случай В = {0, 1}- двоичное кодирование. Именно этот случай и рассматривается в дальнейшем.

Если все кодовые слова имеют одинаковую длину, то код на­зывается равномерным, или блочным.

Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка . Тогда

, где , .

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

Пример:

Пусть заданы алфавиты

А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

В = {0, 1}.

Тогда таблица кодирования может быть подстановкой:

.

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

Однако схема

не является взаимно-однозначной. Например, набор из шести единиц 111111 может соответствовать как слову 333, так и 77, а также 111111, 137, 3311 или 7111 плюс любая перестановка.

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

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

Алфавитное кодирование с разделимой схемой допускает де­кодирование. Можно доказать, что префиксная схема является разделимой.

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