Естественно возникает вопрос: существуют ли неравномерные коды, для которых декодирование всегда однозначно? Да, существуют.
Роберт Фано сформулировал следующее достаточное условие того, что код имеет однозначное декодирование: никакое кодовое слово не является началом другого кодового слова.Если это условие выполнено, то никаких проблем с декодированием не будет.
Пусть A1, A2 и A3 - слова над некоторым алфавитом такие, что A1=A2A3, то есть A1 получается из A2 простым приписыванием к нему слова A3(слова A2 или A3 могут быть односимвольными). Назовем слово A2, которое является начальной частью слова A1, префиксом слова A1. Например, для слова 11101101 префиксами будут слова 1110110, 111011, 11101, 1110, 111, 11, 1.
Тогда условие Фано для кодов, можно сформулировать так:
Никакое кодовое слово не является префиксом другого кодового слова.
Коды, удовлетворяющие условию Фано, называются префиксными. Итак, если код префиксный, он допускает однозначное декодирование.
Например, код, состоящий из кодовых слов {0, 10, 11}, является префиксным, и следующую кодовую последовательность 01001101110 можно разбить на кодовые слова единственным образом: 0 10 0 11 0 11 10.
А код, состоящий из кодовых слов {0, 10, 11, 100}, префиксным не является и он не допускает однозначного декодирования. Действительно, ту же самую последовательность можно разбить на кодовые слова разными способами: 0 10 0 11 0 11 10или 0 100 11 0 11 10.
Важно отметить, что условие Фано является только достаточным условием однозначного декодирования для кодов, но не является необходимым условием.
Например, простой код, состоящий всего из двух кодовых слов {1, 10}, очевидно не является префиксным, но он дает однозначное декодирование любой кодовой последовательности, полученной при кодировании этим кодом. Действительно, в такой последовательности не может стоять рядом два нуля. А тогда каждый ноль со стоящей перед ней единицей заменяем на прообраз второго кодового слова, а все оставшиеся единицы - на прообраз первого слова, это и будет однозначным декодированием.
Существуют и другие, менее простые коды, обладающие тем же свойством. Например, код {01,10,011} также не является префиксным, но обладает однозначным декодированием (попробуйте доказать это самостоятельно).
Как же все-таки определить является ли код однозначно декодируемым, если для него не выполняется условие Фано? Можно использовать следующий метод.
Пусть слово A2 является префиксом слова A1. Тогда A1=A2A3 , где A3 некоторое слово, конечная часть слова A1. Назовем A3 суффиксом пары слов A1 и A2, одно из которых является префиксом другого, а саму пару A1 и A2 назовем префиксной.
Рассмотрим в заданном коде все префиксные пары кодовых слов и построим по ним множество всех суффиксов. Далее рассмотрим все пары префиксных слов, из которых одно является кодовым, а другое – суффиксом, и для них построим суффиксы, расширяя множество суффиксов. Продолжим этот процесс до тех пор пока не перестанут появляться новые суффиксы. Код является однозначно декодируемым тогда и только тогда, когда никакой суффикс не совпадает ни с каким кодовым словом.
Например, для кода {01,10,011}множеством суффиксов будет {1,0,11}. Ни один суффикс здесь не совпадает ни с одним кодовым словом, поэтому, можно утверждать, что этот код является однозначно декодируемым.
Задача 1. Определить обладают ли свойством однозначной декодируемости следующие коды: а) {110, 11, 100, 00, 10} б) {100, 001, 101, 1101, 11011}.
Декодирование последовательностей, полученных кодами, не являющимися префиксными, требует более сложного анализа, чем для префиксных кодов. Префиксные коды иногда называют мгновенными (мгновенно декодируемыми), так как для них при чтении кодовой последовательности конец кодового слова распознается сразу по достижении конечного символа слова. В этом состоит преимущество префиксных кодов.
