Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
§ 1. Критерии однозначности декодирования
Здесь мы рассматриваем алфавитное кодирование для алфавитов ЭД и 59, задаваемое схемой 2:
— В1у
.... (2)' йг 5Г)
и полагаем 8' ($() = 5($), т. е. источник сообщений порождает множество всех слов в алфавите $1. Очевидно, что алфавитное кодирование порождает отображение множества 5 (Я) в множество 5(53). Обозначим через 5?(53) образ множества в этом отображении.
В случае, когда отображение 5(51) на 5х(53) взаимно однозначно, возможно декодирование, т. е. возможно по коду В однозначно восстановить исходное сообщение Л, кодом которого является В. В этом случае говорят также, что алфавитное кодирование является взаимно однозначным.
Пример 2. Рассмотрим алфавитное кодирование, для которого Я = {йь а2), 59 = (?ц, 2ц) и схема имеет вид
Щ 2ц,
2ц2ц.
Пусть В' и В" являются соответственно кодами слов А' и А ". Очевидно, что если А' Ф А ", то В".
Процесс декодирования происходит следующим образом. Произведем разбиение слова В, ?е52(59), на элементарные коды. Для этого заметим, что перед каждым вхождением буквы 2ц в слове В непосредственно находится буква 2ц. Это позволяет выделить все пары (2ц2ц). Оставшаяся часть слова В будет состоять из букв 2ц. Если теперь заменить каждую пару (2ц2ц) ва аг, а каждую из оставшихся букв 2ц — на аи то получим слово 4, являющееся прообразом В,
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
261
Пусть В =* Ь,Ь1Ь2Ь1Ь2Ь1Ь1Ь1Ь2. После выделения пар мы получим разбиение на элементарные коды
В = Ь^ЬД) {Ь1Ь1)Ъ1Ь1{Ъ1Ьг)1 из которого находим слово
Можно привести большое количество примеров, в которых алфавитное кодирование не будет обладать свойством взаимной однозначности. Б связи с этим возникает вопрос: возможно ли по схеме 2 алфавитного кодирования уанать, обладает алфавитное кодирование свойством взаимной однозначности или нет. Трудность решения задачи состоит в том, что для непосредственной проверки взаимной однозначности необходимо просмотреть бесконечное число слов.
Прежде чем приводить общий критерий взаимной однозначности алфавитного кодирования, рассмотрим весьма простой достаточный признак взаимной однозначности.
Определение. Пусть слово В имеет вид
В = В'В\
Тогда слово В' называется началом или префиксом слова В, а В" — концом слова В. При этом пустое слово Л и само слово В считаются началами и концами слова В. Все начала и концы слова В, отличные от него самого, называются собственными.
Определение. Схема 2 обладает свойством префикса, если для любых ? и / (К?, /<г, ?=^;) слово В{ не является префиксом слова Д,-.
Теорема 1. Если схема 2 обладает свойством префикса, то алфавитное кодирование будет взаимно однозначным.
Доказательство. Поскольку схема 2 обладает свойством префикса, все элементарные коды в ней попарно различны, т. е. при ? ^ /. Предположим, что
некоторое слово В из допускает две расшифровки,
а значит и два разбиения на элементарные коды
в - «(1... в.,.
в = в„..,вн.
262
Ч. IV. ТЕОРИЯ КОДИРОВАНИЯ
Пусть Вч - Вк, ..., В^ = В5п_л, В,пфВ^ в та^ ком случае одпо из слов В{п, В^п является префиксом другого. Теорема доказана.
Предыдущий пример показывает, что условие префикс-иости не является необходимым: 2 может пе обладать свойством префикса, а алфавитное кодирование, определяемое 2, будет взаиыпо однозначным.
Пусть В~Ь11. .. Ъ^п—слово из ^(ЗЭ). Обозначим через
Б— слово, получающееся из В путем «обращения», т. е.
Обозначим, далее, через 2 схему вида
Й1 Би
аг — Бт.
Пример 3. Возьмем в качестве 2 схему из примера 2. Тогда 2 имеет вид
аг~ЬгЪ1.
Здесь 2 обладает свойством префикса, и в силу теоремы 1 алфавитное кодирование, задаваемое 2, будет взаимно однозначным.
Замечание. Алфавитное кодирование, определяемое схемой 2, и алфавитное кодирование, определяемое схемой 2, одновременно либо обладают свойством взаимной однозначности, либо пет.
Данное замечание позволяет усилить теорему 1.
Теорема 2. Если либо схема 2, либо схема 2 обладает свойством, префикса, то алфавитное кодирование, задаваемое 2(2), будет взаимно однозначным.
Можно привести пример алфавитного кодирования со схемой 2 так, что и 2 и 2 не обладают свойством префикса, а алфавитное кодирование будет взаимно однозначным.
Для этого предыдущий пример уже не годится, но может быть легко усовершенствован.
Пример 4. Пусть аг, а3} и §3 = {Ьи &2, Ь3).
Рассмотрим схему 2:
Отепидно, 2 и 2 не обладают свойством префикса, в то же время алфавитное кодирование будет взаимно однозначным. В самом деле, если В^52(33), то это слово одпозначным образом разбивается на элементарные коды:
слева от буквы 62 непосредственно находится — выделяем пару (б^);
справа от буквы Ь3 непосредственно находится — выделяем пару (ЬзЬ^;
после выделения всех пар (1\Ь2) и (Ь3ЬУ) в слове останутся ЛИШЬ СИМВОЛЫ Ь |.
13 дальнейшем предположим, что в 2 элементарные коды попарно различпы.
Прежде чем идти дальше, введем ряд обозначений: 1(В) будет обозначать длину слова В, т. е. количество букв в этом слове. В частности для длин элементарных кодов В{ (г = 1, .. ., г) полагаем 1{В^=и. Далее, мерез В обозначим величину 1(В1. ..Вт), т. е. «длину» схемы 2.
