Какие коды удовлетворяют свойству однозначного декодирования
Тема: Кодирование и декодирование информации.
Что
нужно знать:
·
кодирование – это перевод информации с одного
языка на другой (запись в другой системе символов, в другом алфавите)
·
обычно кодированием называют перевод информации
с «человеческого» языка на формальный, например, в двоичный код, а
декодированием – обратный переход
·
один символ исходного сообщения может заменяться
одним символом нового кода или несколькими символами, а может быть и наоборот –
несколько символов исходного сообщения заменяются одним символом в новом коде
(китайские иероглифы обозначают целые слова и понятия)
·
кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной
длины, это затрудняет декодирование
·
закодированное сообщение можно однозначно
декодировать с начала, если выполняется
условие Фано: никакое кодовое слово не является началом другого кодового
слова;
·
закодированное сообщение можно однозначно
декодировать с конца, если выполняется обратное
условие Фано: никакое кодовое слово не является окончанием другого кодового
слова;
·
условие Фано – это достаточное, но не
необходимое условие однозначного декодирования.
Пример задания:
Для кодирования некоторой
последовательности, состоящей из букв А, Б, В, Г и Д, используется
неравномерный двоичный код, позволяющий однозначно декодировать полученную
двоичную последовательность. Вот этот код: А–00, Б–010, В–011, Г–101, Д–111.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код
по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не
должны. Выберите правильный вариант ответа.
1)
для буквы Б – 01 2)
это невозможно
3)
для буквы В – 01 4)
для буквы Г – 01
Решение
(1 способ, проверка условий Фано):
1) для
однозначного декодирования достаточно, чтобы выполнялось условие Фано или
обратное условие Фано;
2) проверяем
последовательно варианты 1, 3 и 4; если ни один из них не подойдет, придется
выбрать вариант 2 («это невозможно»);
3) проверяем
вариант 1: А–00, Б–01, В–011, Г–101, Д–111.
«прямое»
условие Фано не выполняется (код буквы Б совпадает с началом кода буквы В);
«обратное»
условие Фано не выполняется (код буквы Б совпадает с окончанием кода буквы Г);
поэтому этот вариант не подходит;
4) проверяем
вариант 3: А–00, Б–010, В–01, Г–101, Д–111.
«прямое»
условие Фано не выполняется (код буквы В совпадает с началом кода буквы Б);
«обратное»
условие Фано не выполняется (код буквы В совпадает с окончанием кода буквы Г);
поэтому этот вариант не подходит;
5) проверяем
вариант 4: А–00, Б–010, В–011, Г–01, Д–111.
«прямое»
условие Фано не выполняется (код буквы Г совпадает с началом кодов букв Б и В);
но «обратное»
условие Фано выполняется (код буквы
Г не совпадает с окончанием кодов остальных буквы); поэтому этот вариант подходит;
6) правильный
ответ – 4.
Решение
(2 способ, дерево):
1) построим
двоичное дерево, в котором от каждого узла отходит две ветки, соответствующие
выбору следующей цифры кода – 0 или 1; разместим на этом дереве буквы А, Б, В,
Г и Д так, чтобы их код получался как последовательность чисел на рёбрах,
составляющих путь от корня до данной буквы (красным цветом выделен код буквы В
– 011):
2) здесь
однозначность декодирования получается за счёт того, что при движении от корня
к любой букве в середине пути не встречается других букв (выполняется условие
Фано);
3) теперь
проверим варианты ответа: предлагается перенести одну из букв, Б, В или Г, в
узел с кодом 01, выделенный синим цветом
4) видим,
что при переносе любой из этих букв нарушится условие Фано; например, при
переносе буквы Б в синий узел она оказывается на пути от корня до В, и т.д.;
это значит, что предлагаемые варианты не позволяют выполнить прямое условие
Фано
5) хочется
уже выбрать вариант 2 («это невозможно»), но у нас есть еще обратное условие
Фано, для которого тоже можно построить аналогичное дерево, в котором движение
от корня к букве дает её код с конца
(красным цветом выделен код буквы В – 011, записанный с конца):
видно,
что обратное условие Фано также выполняется, потому что на пути от корня к
любой букве нет других букв
6) в
заданных вариантах ответа предлагается переместить букву Б, В или Г в синий
узел; понятно, что Б или В туда перемещать нельзя – перемещённая буква
отказывается на пути от корня к букве Г; а вот букву Г переместить можно, при
этом обратное условие Фано сохранится
7) правильный
ответ – 4.
Ещё пример задания:
Для кодирования некоторой
последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать
неравномерный двоичный код, позволяющий однозначно декодировать двоичную
последовательность, появляющуюся на приёмной стороне канала связи. Использовали
код:
А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть
закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех
возможных. Код должен удовлетворять свойству однозначного декодирования.
1) 00 2) 01 3)11
4)
010
Решение:
8) заметим,
что для известной части кода выполняется условие Фано – никакое кодовое слово
не является началом другого кодового слова
9) если
Д = 00, такая кодовая цепочка совпадает с началом Б = 000 и В = 001, невозможно
однозначно раскодировать цепочку 000000: это может быть ДДД или ББ; поэтому
первый вариант не подходит
10) если
Д = 01, такая кодовая цепочка совпадает с началом Г = 011, невозможно
однозначно раскодировать цепочку 011: это может быть ДА или Г; поэтому второй
вариант тоже не подходит
11) если
Д = 11, условие Фано тоже нарушено: кодовое слово А = 1 совпадает с началом
кода буквы Д, невозможно однозначно раскодировать цепочку 111: это может быть
ДА или ААА; третий вариант не подходит
12) для
четвертого варианта, Д = 010, условие Фано не нарушено;
13) правильный
ответ – 4.
Возможные ловушки:
·
условие Фано – это достаточное, но не необходимое условие однозначного
декодирования, поэтому для уверенности полезно найти для всех «неправильных»
вариантов контрпримеры: цепочки, для
которых однозначное декодирование невозможно
Еще пример задания:
Для кодирования букв А, Б, В, Г решили
использовать двухразрядные последовательные двоичные числа (от 00 до 11,
соответственно). Если таким способом закодировать последовательность символов
БАВГ и записать результат шестнадцатеричным кодом, то получится
1) 4B16 2) 41116 3)BACD16 4)
102316
Решение:
14) из
условия коды букв такие: A – 00, Б –01, В – 10 и Г – 11, код равномерный
15) последовательность
БАВГ кодируется так: 01 00 10 11 = 1001011
16) разобьем такую запись на тетрады справа налево и
каждую тетраду переведем в шестнадцатеричную систему (то есть, сначала в
десятичную, а потом заменим все числа от 10 до 15 на буквы A, B, C, D, E, F);
получаем
1001011 = 0100 10112 = 4B16
17) правильный
ответ – 1.
Возможные ловушки:
·
расчет на то, что
при переводе тетрад в шестнадцатеричную систему можно забыть заменить большие
числа (10–15) на буквы (10112 = 11, получаем неверный ответ 41116)
·
может быть дан
неверный ответ, в котором нужные цифры поменяли местами (расчет на
невнимательность), например, B416
·
в ответах дана последовательность, напоминающая
исходную (неверный ответ BACD16),
чтобы сбить случайное угадывание
Еще пример задания:
Для 5 букв латинского алфавита заданы их двоичные коды (для некоторых
букв – из двух бит, для некоторых – из трех). Эти коды представлены в таблице:
A | B | C | D | E |
000 | 01 | 100 | 10 | 011 |
Определить, какой набор букв
закодирован двоичной строкой 0110100011000
1) EBCEA 2) BDDEA 3)
BDCEA 4) EBAEA
Решение (вариант 1,
декодирование с начала):
1) здесь
используется неравномерное кодирование, при котором декодирование может быть
неоднозначным, то есть, заданному коду может соответствовать несколько разных
исходных сообщений
2) попробуем
декодировать с начала цепочки, первой буквой может быть B или E, эти случаи
нужно рассматривать отдельно
3) пусть
первая буква – E с
кодом 011, тогда остается цепочка 0100011000
·
для кода 0100011000 первой буквой может быть
только B с кодом 01,
тогда остается 00011000 ( начало исходной цепочки – EB?)
·
для кода 00011000 первой буквой может быть
только A с кодом 000,
тогда остается 11000, а эта цепочка не может быть разложена на заданные коды
букв
·
поэтому наше предположение о том, что первая
буква – E, неверно
4) пусть
первая буква – B с кодом 01, тогда остается цепочка 10100011000
·
для кода 10100011000 первой буквой может быть
только D с кодом 10, тогда остается 100011000
(можно полагать, что начало исходной цепочки – BD?)
·
для кода 100011000 первой буквой может быть
только С с кодом 100, тогда остается 011000 (начало исходной цепочки – BDC?)
Несмотря на то, что среди ответов есть единственная
цепочка, которая начинается с BDC,
здесь нельзя останавливаться, потому что «хвост» цепочки может «не сойтись»
·
для кода 011000 на первом месте может быть B (код 01) или E (011); в
первом случае «хвост» 1000 нельзя разбить на заданные коды букв, а во втором –
остается код 000 (буква А), поэтому исходная цепочка может быть декодирована
как BDCEA
5) правильный
ответ – 3
Возможные ловушки и проблемы:
·
при декодировании неравномерных кодов может
быть очень много вариантов, их нужно рассмотреть все; это требует серьезных
усилий и можно легко запутаться
·
нельзя останавливаться, не закончив
декодирование до конца и не убедившись, что все «сходится», на это обычно и
рассчитаны неверные ответы
Решение
(вариант 2, декодирование с конца):
1) для
кода 0110100011000 последней буквой может быть только А (код 000), тогда остается цепочка 0110100011
2) для
0110100011 последней может быть только буква E (011), тогда остается цепочка 0110100
3) для
0110100 последней может быть только буква C (100), тогда остается
цепочка 0110
4) для
0110 последней может быть только буква D (10), тогда остается 01
– это код буквы B
5) таким
образом, получилась цепочка BDCEA
6) правильный
ответ – 3
Возможные ловушки и проблемы:
·
при декодировании неравномерных кодов может
быть очень много вариантов (здесь случайно
получилась единственно возможная цепочка), их нужно рассмотреть все; это
требует серьезных усилий и можно легко запутаться
·
нельзя останавливаться, не закончив
декодирование до конца и не убедившись, что все «сходится», на это обычно и
рассчитаны неверные ответы
Решение
(вариант 3, кодирование ответов):
1) в
данном случае самое простое и надежное – просто закодировать все ответы,
используя приведенную таблицу кодов, а затем сравнить результаты с заданной
цепочкой
2) получим
1) EBCEA –
01101100011000 2) BDDEA
– 011010011000
3) BDCEA – 0110100011000 4) EBAEA – 01101000011000
3) сравнивая
эти цепочки с заданной, находим, что правильный ответ – 3.
Возможные проблемы:
·
сложно сравнивать длинные двоичные последовательности,
поскольку они однородны, содержат много одинаковых нулей и единиц
Еще пример задания:
Для передачи по каналу связи сообщения,
состоящего только из букв А, Б, В, Г, решили использовать неравномерный по
длине код: A=0, Б=10, В=110. Как нужно закодировать букву Г, чтобы длина кода
была минимальной и допускалось однозначное разбиение кодированного сообщения на
буквы?
1) 1 2) 1110 3)
111
4) 11
Решение
(вариант 1, метод подбора):
1) рассмотрим
все варианты в порядке увеличения длины кода буквы Г
2) начнем
с Г=1; при этом получается, что сообщение «10» может быть раскодировано двояко:
как ГА или Б, поэтому этот вариант не подходит
3) следующий
по длине вариант – Г=11; в этом случае сообщение «110» может быть раскодировано
как ГА или В, поэтому этот вариант тоже не подходит
4) третий
вариант, Г=111, дает однозначное раскодирование во всех сочетаниях букв,
поэтому…
5) …
правильный ответ – 3.
Возможные проблемы:
·
при переборе можно ошибиться и «просмотреть»
какой-нибудь вариант
Решение
(вариант 2, «умный» метод):
1) для
того, чтобы сообщение, записанное с помощью неравномерного по длине кода,
однозначно раскодировалось, требуется, чтобы никакой код не был началом другого
(более длинного) кода; это условие называют условием
Фано
2) как
и в первом решении, рассматриваем варианты, начиная с самого короткого кода для
буквы Г; в нашем случае код Г=1 является началом кодов букв Б и В, поэтому
условие Фано не выполняется, такой код не подходит
3) код
Г=11 также является началом другого кода (кода буквы В), поэтому это тоже ошибочный
вариант
4) третий
вариант кода, Г=111, не является началом никакого уже известного кода; кроме
того, ни один уже имеющийся код не является началом кода 111; таким образом,
условие Фано выполняется
5) поэтому
правильный ответ – 3.
Возможные проблемы:
·
нужно знать условие Фано
Еще пример задания[i]:
Черно-белое
растровое изображение кодируется построчно, начиная с левого верхнего угла и
заканчивая в правом нижнем углу. При кодировании 1 обозначает черный цвет, а 0
– белый.
Для компактности результат записали в
шестнадцатеричной системе счисления. Выберите правильную запись кода.
1) BD9AA5 2)
BDA9B5
3) BDA9D5 4) DB9DAB
Решение:
1)
«вытянем» растровое изображение в цепочку:
сначала первая (верхняя) строка, потом – вторая, и т.д.:
1 строка | 2 строка | 3 строка | 4 строка |
2)
в этой полоске 24 ячейки, черные заполним
единицами, а белые – нулями:
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |||||||||
1 строка | 2 строка | 3 строка | 4 строка | ||||||||||||||||||||
3)
поскольку каждая цифра в шестнадцатеричной
системе раскладывается ровно в 4 двоичных цифры, разобьем полоску на тетрады – группы из четырех ячеек (в
данном случае все равно, откуда начинать разбивку, поскольку в полоске целое
число тетрад – 6):
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
4) переводя
тетрады в шестнадцатеричную систему, получаем последовательно цифры B (11), D(13),
A(10), 9, D(13) и 5, то есть, цепочку BDA9D5
5) поэтому
правильный ответ – 3.
Возможные проблемы:
·
нужно уметь быстро переводить тетрады в
шестнадцатеричные цифры (в крайнем случае, это можно сделать через десятичную
систему)
Еще пример задания:
Для передачи чисел по каналу с помехами
используется код проверки четности. Каждая его цифра записывается в двоичном
представлении, с добавлением ведущих нулей до длины 4, и к получившейся
последовательности дописывается сумма её элементов по модулю 2 (например, если передаём 23, то получим последовательность 0010100110). Определите, какое число передавалось по
каналу в виде 01010100100111100011?
1) 59143 2) 5971 3)
102153
4) 10273
Решение:
1) сначала
разберемся, как закодированы числа в примере; очевидно, что используется код
равномерной длины; поскольку 2 знака кодируются 10 двоичными разрядами
(битами), на каждую цифру отводится 5 бит, то есть
2
→ 00101 и 3 → 00110
2) как
следует из условия, четыре первых бита в каждой последовательности – это
двоичный код цифры, а пятый бит (бит четности) используется для проверки и
рассчитывается как «сумма по модулю два», то есть остаток от деления суммы
битов на 2; тогда
2 = 00102, бит четности (0 + 0 + 1 + 0) mod 2 =
1
3 = 00112, бит четности (0 + 0 + 1 + 1) mod 2 = 0
3) но
бит четности нам совсем не нужен,
важно другое: пятый бит в каждой пятерке можно
отбросить!
4) разобъем
заданную последовательность на группы по 5 бит в каждой:
01010, 10010, 01111, 00011.
5) отбросим
пятый (последний) бит в каждой группе:
0101, 1001, 0111, 0001.
это и есть двоичные коды передаваемых чисел:
01012 = 5, 10012 = 9, 01112
= 7, 00012 = 1.
6) таким
образом, были переданы числа 5, 9, 7, 1 или число 5971.
7) Ответ:
2.
Источник
Пусть слово Р е В* имеет вид
где Р’, Р”е В*. Тогда слово Р’ называется префиксом (или началом), а Р” – постфиксом (или окончанием) слова р. При этом пустое слово Л и само Р считаются префиксами и постфиксами слова р. Все префиксы и постфиксы слова Р, отличные от Л и р, называются собственными. Например, для слова р = 011 собственными префиксами выступают слова 0 и 01, а собственными постфиксами – 1 и 11.
Алфавитный код ср(А) называется префиксным, если ни один элементарный код из (р(А) не является префиксом другого элементарного кода из ср(А). О таких кодах говорят, что они обладают свойством префикса.
Очевидно, что если в ф(А) имеется хотя бы одна пара совпадающих элементарных кодов Р„ ру, т. е. Р, = Ру, то префиксность ф(А) нарушается, поскольку р, = ру Л и Ру – префикс для Р„ Ру = Р, Л и Р, – префикс для Ру. То же самое имеет место и в случае, когда ф(А) имеет элементарный код, представимый в виде конкатенации других элементарных кодов из ф(А). Очевидно, что пустое слово Л не может быть составляющей алфавита префиксного кода, поскольку Л является префиксом любого слова. В дальнейшем будем полагать, что Л g ф(А).
Пусть задан алфавитный код ср(А) = {рь р„}. Обозначим через Р( слово, получающееся из Р, е ф(А) «обращением»:
Под ф(А) будем понимать алфавитный код
Справедливо следующее достаточное условие однозначного декодирования алфавитного кода, которое нетрудно доказать методом от противного.
Утверждение 8.1. Если ф(А) или ф(А) является префиксным кодом, то ф(А) допускает однозначное декодирование.
Пример 8.4. Вернемся к алфавитному коду ф(А) = {0, 01} из примера 8.1. Этот код не является префиксным, так как = 0 — префикс для р2= 01. Однако ф(А) = {0, 10} обладает свойством префикса.
По утверждению 8.1 код ф(А) допускает однозначное декодирование, что подтверждает результат примера 8.1.
Пример 8.5. Равномерный двоично-десятичный код
из примера 8.2 обладает свойством префикса, поэтому он является однозначно декодируемым.
Кома-код – это разновидность префиксного кода. При его использовании каждая буква алфавита А кодируется элементарным двоичным кодом из единиц, в конце которого стоит нуль. Так, при | А | = 5 кома-код имеет вид ф(А) = {0, 10, 110, 1110, 11110}. Кома-код легко строится, но он обладает явным недостатком: его элементарные коды могут быть очень длинными и занимать большой объем памяти. Поэтому на практике используются более экономные префиксные коды.
Важно отметить, что свойство префикса является достаточным, но не является необходимым условием однозначного декодирования алфавитного кода. Это иллюстрирует следующий пример.
Пример 8.6. Пусть заданы А = {a, b,c,d,e}, В = {О, 1,2,3} и код
Здесь коды ф(А) и ф(А) = {10, 23, 0, 33021, 02} не обладают свойством префикса. Однако в примере 8.11 показано, что код ф(А) допускает однозначное декодирование.
Из-за простоты декодирования префиксные коды иногда называют мгновенными кодами. Рассмотрим процесс декодирования префиксного кода. Пусть А = {ah… , а„} – исходный алфавит, В = {Ь,… ,bq} – кодирующий алфавит, при этом п > q> 1. Предположим, что кодирование выполняется побуквенно на основе схемы
где А/ е А, Р, е В*, i = 1, …, п. Задан код р = ф(а) Ф Л некоторого сообщения а. Декодирование слова Р е В*, т. е. определение а – ф~'(Р) можно выполнить с помощью следующего алгоритма.
Алгоритм 8.1. Декодирование слова р = ф(а) по префиксному коду ф(А)
- 1. Просматривать слово Р по одной букве, начиная с первой. Как только прочитанный префикс (не обязательно собственный) совпадает с некоторым элементарным кодом из ф(А), следует этот префикс заменить соответствующей буквой из А, а затем исключить из слова р.
- 2. Пункт 1 повторять до тех пор, пока р ф Л.
Очевидно, что время работы данного алгоритма составляет О(тп), где m = |Р|, я = |А|.
Алгоритм 8.1 легко модифицировать на случай, когда ф(А) является префиксным кодом. Для этого необходимо просмотр слова р вести с последней буквы, т. е. справа налево, и выделять не префиксы, а постфиксы. Ясно, что алгоритм декодирования однозначных, но не обязательно префиксных кодов является гораздо более сложным, чем алгоритм 8.1. По этой причине на практике используются в основном префиксные коды.
Пример 8.7. Рассмотрим алфавит А = {а, Ъ, с}. Для кодирования используем кома-код
который является префиксным, а значит, однозначно декодируемым. Слову а = abbc в этом коде соответствует слово Р = ф(а) = 01010110. Применим к слову р алгоритм 8.1.
Считываем первую букву 0 из р. Ей соответствует буква а е А. Производим декодирование и исключаем 0 из дальнейшего рассмотрения. В результате имеем: а = а, Р = 1010110.
Считываем следующую букву 1. Такого элементарного кода нет. После считывания следующей буквы 0 получаем префикс 10, которому соответствует элементарный код буквы be А. После декодирования и исключения префикса 10 из р имеем: а = ab, Р= 10110.
Аналогично на третьей итерации алгоритма можно декодировать еще один префикс 10. В результате получим: а – abb, Р = 110.
На четвертой итерации декодируется вся оставшаяся часть слова Р, поскольку в ср(А) нет элементарных кодов 1 и 11. В итоге имеем: а = abbc и Р = Л. Процесс декодирования завершается.
Для распознавания однозначного декодирования можно применять следующее необходимое условие [25].
Утверждение 8.2 (неравенство Макмиллана). Для всякого однозначно декодируемого кода в ^-буквенном алфавите с набором длин элементарных кодов 1, всегда выполняется неравенство
Для двоичного кодирования неравенство Макмиллана принимает вид
По утверждению 8.2, если для алфавитного кода ср(А) = {рь..р„} неравенство Макмиллана не выполняется, т. е.
где ?, — | pi |, j = 1,___, и, то (р(А) не допускает однозначного декодирования. При выполнении неравенства Макмиллана об однозначности кода ср(А) ничего сказать нельзя.
Пример 8.8. Возьмем из примера 8.6 однозначно декодируемый код
Для него ix = ?2 = 2, ?3 = 1, ?4 = 5, ?5 = 2. Вычислим сумму
Неравенство Макмиллана выполняется.
Пример 8.9. Пусть заданы алфавиты А = {0, 1, 2, 3,4, 5,6, 7, 8, 9}, В = {0, 1} и код
Заметим, что ф(А) не обладает свойством префикса. Для ф(А) имеем = ?2 = 1, €3 = ?4 = 2, ?5 — — ?7 — = 3, ?9 = ?ю = 4. Выполним вычисление левой части неравенства Макмиллана:
Неравенство не выполняется, поэтому код ф(А) не является однозначно декодируемым. Действительно, слово (3 = 111111 разделяется на элементарные коды двумя способами: р = (11) (11) (11), Р = (111) (111). Отсюда |3 = ф(ЗЗЗ) и [3 = ф(77) одновременно.
Следующий пример показывает, что неравенство Макмиллана не может служить достаточным условием распознавания однозначного декодирования кода.
Пример 8.10. Рассмотрим алфавиты А = {a, b, с, d, е}, В = {0, 1} и код
Нетрудно убедиться, что для (р(А) неравенство Макмиллана выполняется. Между тем ф(А) не является однозначно декодируемым. Например, слово Р = 11011101 допускает две расшифровки:
Существуют необходимые и одновременно достаточные условия однозначного декодирования алфавитного кода. Эти условия проверяются с помощью соответствующих алгоритмов: алгоритма Маркова и алгоритма анализа окончаний [8, 25]. Приведем второй из них как наиболее простой и эффективный. Пусть задан исходный алфавитный код ср(А) = (ft, … , Р„}, для которого п > 1 иЛ? ф(А).
Алгоритм 8.2. Распознавание однозначности кода ф(А) путем анализа окончаний
- 1. Положить W:= 0. Рассмотреть все пары элементарных кодов Р„ р, е ф(А), i Ф j. Если среди них есть равные пары кодов, то процесс завершить ответом: ф(А) не является однозначно декодируемым кодом. В противном случае найти пары, в которых один элементарный код является собственным префиксом другого элементарного кода. Для каждой такой пары найти собственное окончание, которое остается после удаления префикса из начальной части более длинного элементарного кода. Например, для пары Р, = 10 и Ру = 10010 окончанием будет слово 010. Все найденные собственные окончания записать в W и перейти на пункт 2. Если таких пар нет в ф(А), т. е. W не изменилось и осталось пустым, то процесс завершить ответом: ф(А) – префиксный, а значит, однозначно декодируемый код.
- 2. Выполнить сравнение всех возможных пар слов, одно из которых принадлежит W, а другое – алфавитному коду ф(А), и выделить собственные окончания. Все новые окончания добавить в W.
- 3. Пункт 2 повторять до тех пор, пока будут появляться новые окончания.
- 4. Выполнить проверку условия:
- – если W п (р(А) — 0, т. е. ни одно окончание из W не совпадает ни с одним элементарным кодом из ср(А), процесс завершить ответом: ф(А) является однозначно декодируемым кодом;
- – иначе ответ: ф(А) не допускает однозначного декодирования.
Очевидно, что алгоритм 8.2 имеет полиномиальную сложность. Проиллюстрируем его работу на примерах.
Пример 8.11. Вернемся к коду из примера 8.6:
Применим к нему алгоритм 8.2. В результате попарного сравнения в пункте 1 элементарных кодов из ф(А) получим W = {1}. После первой итерации пункта 2 имеем W= {1, 2033}. Повторение пункта 2 дает
после чего W уже не изменяется. Итак, W п ф(А) = 0 и ф(А) – однозначно декодируемый код.
Пример 8.12. Для алфавитного кода
из примера 8.9 алгоритм 8.2 работает следующим образом. Выполнение пункта 1 дает
В пункте 2 множество W не пополняется. В итоге
Поэтому ф(А) не является однозначно декодируемым кодом, что подтверждает результат примера 8.9.
Пример 8.13. Вновь рассмотрим алфавитный код
Из примера 8.10 известно, что данный код не допускает однозначного декодирования. В самом деле, в процессе выполнения алгоритма 8.2 множество W принимает вид W = {1, 00, 01, 101, 1011}. Имеем неоднозначность алфавитного кода ср(А), поскольку W п ср(А) = = {101} *.
Алгоритм 8.2 также работает верно, когда один элементарный код является конкатенацией других.
Пример 8.14. Пусть задан алфавитный код
где Pi = 01, р2 = 11, Рз = 011101 = Pi р2 Pi. Сравнение элементарных кодов в пункте 1 приводит к W = {1101}. При выполнении пункта 2 множество W пополняется окончанием 01. В итоге
Это свидетельствует о том, что (р(А) не является однозначно декодируемым кодом.
Источник