Какие коды удовлетворяют свойству однозначного декодирования

Пусть слово Р е В* имеет вид

где Р’, Р»е В*. Тогда слово Р’ называется префиксом (или началом), а Р» — постфиксом (или окончанием) слова р. При этом пустое слово Л и само Р считаются префиксами и постфиксами слова р. Все префиксы и постфиксы слова Р, отличные от Л и р, называются собственными. Например, для слова р = 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. В итоге

Это свидетельствует о том, что (р(А) не является однозначно декодируемым кодом.