Обратное условие Фано — это соблюдение принципа, согласно которому при кодировании не существует кодовых слов, которые будут окончаниями иных кодовых последовательностей.
Введение
Когда кодируются символы, что всегда делается при использовании текстовой информации на компьютере, обычно считается, что всякому символьному знаку предоставлено одинаковое количество разрядов. Например, при использовании кодов ASCII, для кодирования выделяется байт, где сохраняется номер символа в этой таблице. Этот метод кодирования символьных знаков достаточно прост, но не считается совершенным. Большая часть символов использует мало двоичных разрядов из выделенных им для кодирования байтов, то есть старшие биты, как правило, просто нули. Но даже когда в текстовом файле используются не все символы, которые есть в таблице кодов (к примеру, текст содержит только прописные русские буквы), используются всё равно коды, состоящие из восьми битов.
Однако, есть и более совершенные и занимающие меньше места способы кодировки, которые имеют название неравномерных. В таких кодах количество битов, отводимых для кодирования символов, имеет зависимость от количества используемых в текущем случае различных символов, по-другому, от мощности алфавита. То есть кодировка различных символов обладает разной длиной в двоичном коде. Такое кодирование можно сделать оптимальным за счёт учёта условия, как часто повторяются разные символы. Это позволяет задать часто используемым знакам минимальные кодовые последовательности. Главное правило при таком непостоянном по длине кодировании состоит в предоставлении возможности чёткого и однозначного декодирования информации, которая была подвергнута такой методике кодирования. При декодировании нужно последовательно выделять и распознавать в текущем потоке бинарных кодов отдельные знаки. А, чтобы гарантировать однозначное декодирование текста, который кодировался способом неравномерных кодов, эти коды нужно формировать для символов согласно условиям Фано.
Принципы Фано
Прямое условие Фано можно сформулировать так: неравномерную кодовую последовательность можно безошибочно декодировать тогда, когда код каждого символа не имеет совпадений с первыми значениями (префиксами) всех остальных кодов, имеющих большую длину. Такое кодирование называется «префиксным».
Обратное условие Фано имеет следующую формулировку: неравномерное кодирование можно правильно декодировать тогда, когда не существует кодов, имеющих совпадения с конечными значениями (постфиксами) каждого иного кодирования, имеющего большую длину. Такое кодирование называется «постфиксным».
Для безошибочной и безусловной расшифровки набора кодов, необходимо и достаточно выполнение по крайней мере одного из условий Фано. При этом, если есть прямое условие Фано, то шифр можно правильно декодировать, начиная с первых кодов. А когда работает обратное условие Фано, то коды можно правильно расшифровать, начиная с конечных кодов.
Если требуется разрешить задачу кодирования и декодирования неравномерных кодов, то сначала нужно осуществить проверку кодирования, которое задаётся условием задачи. Когда начальные кодовые последовательности соответствуют прямому условию Фано, необходимо использовать его для определения решения. Когда прямое условие Фано не выполняется, надо выполнить анализ кодовой последовательности на соответствие обратному условию Фано и если оно выполняется, то следует использовать только его. Далее, при учёте того, какое именно условие Фано есть для текущих кодов, необходимо сделать выбор нужного направления расшифровки такого кодового набора. Конкретно, если для текущего кодового набора справедливо прямое условие Фано, то начинать декодирование необходимо слева направо (с начала). В случае соблюдения для данного кодового набора обратного условия Фано, расшифровку нужно начинать с последних кодов (справа налево). А когда выполнены оба условия Фано, расшифровку кодов можно делать в любую сторону с одинаковым итоговым результатом.
Проверка условий Фано
Чтобы проверить соответствие кодовых последовательностей прямому условию Фано, нужно последовательно сравнивать все кодовые пары, с соблюдением следующих условий:
- Если кодовая пара, которая сравнивается, обладает одной и той же длиной, то достаточно проверки на совпадение.
- Если кодовая пара, которая сравнивается, разной длины, то необходимо выполнить проверку на равенство более маленького кода с первыми величинами кода, обладающего большими размерами. Это будет проверка на соответствие прямому условию Фано. Или же выполнить проверку с конечными значениями кодового набора, имеющего большую длину. Это будет проверка на соответствие обратному условию Фано.
При проверке выполнения второго пункта условий Фано, анализ осуществляется следующим образом. Сначала пишется более длинная кодовая последовательность. Затем ниже прописывается кодовый набор, имеющий меньшую длину, таким образом, чтобы совпадало местоположение значений. При этом, когда выполняется проверка прямого условия Фано, то записи идёт по расположению знаков слева, а когда проверяется обратное условие Фано, то по расположению знаков справа.
Пример проверки
Есть исходные символьные коды: A – 10, B – 11, C – 011. Требуется выполнить проверку соответствия условиям Фано для этой кодовой последовательности. Алгоритм разрешения такой проблемы возможно описать таким образом:
Сравниваются коды знаков А и В. Длина кодов у них одинаковая, по два бита у каждого, но значения кодов различны. Следовательно, можно сделать вывод о выполнении прямого и обратного условия Фано для выбранной символьной пары А и В.
Сравниваются коды символов А и С. У них различная длина кодирования:
- Проводим анализ выполнения прямого условия Фано:
C: 011
А: 10
Кодовая последовательность буквы А (более короткая) не имеет совпадений с начальным кодированием буквы С (более длинного). Можно сделать вывод о выполнении прямого условия Фано для этих символов.
- Проводим анализ выполнения обратного условия Фано:
C: 011
A: 10
Кодовая последовательность буквы А (более короткая) не имеет совпадений с концом кодирования буквы С (более длинным). Можно сделать вывод, что обратное условие Фано выполнено.
