4.2. Алгоритм распознавания однозначности кодирования
Используя нетривиальные разложения элементарных кодов, опишем алгоритм для схемы кодирования Σ.
1. Для каждого элементарного кода выполним всевозможные нетривиальные разложения.
2. Строим множество М следующим образом. В него включаем пустой символ , а также каждое слово типа β, которое встречается в нетривиальных разложениях элементарных кодов как в роли префикса, так и в роли окончания. В разных ролях это слово не обязательно используется в разложении одного и того же элементарного кода.
3. Каждому слову из М сопоставляем вершину графа. Пусть слова , содержатся в М. Выделим среди нетривиальных разложений элементарных кодов схемы Σ разложения вида … . Для каждого из них проведем дугу из в , пометив ее элементарными кодами … . Полученный граф обозначим (Σ).
4. Анализируем граф (Σ), отыскивая в нем ориентированный цикл, содержащий вершину . Если цикл существует, то кодирование не однозначно, иначе кодирование однозначно.
Теорема 4.3. Алфавитное кодирование со схемой кодирования Σ не обладает свойством однозначности, если и только если граф (Σ) содержит ориентированный цикл, проходящий через вершину .
Доказательство приведено в [1].
Для построенных ранее нетривиальных разложений имеем множество М = {, , , }. С этим множеством связаны разложения (рис. 4.1):
= ( )( ),
= ( )( ) = ( ),
= ( )( )( ) = ( ) .
Рис. 4.1
В графе существует ориентированный цикл, проходящий через вершину , то есть кодирование не однозначно. Действительно, слово В = = допускает две расшифровки:
B = ( )( ) = ,
B = ( )( )( )( ) = .
КАДР
4.3. Свойства однозначных кодов
Дана схема кодирования Σ:
,
…
.
Пусть q – число символов алфавита В (значность алфавита В), = l( ).
Теорема 4.4 (неравенство МакМилана). Если кодирование со схемой Σ обладает свойством однозначности, то выполняется соотношение
1.
Доказательство. Рассмотрим всевозможные слова в алфавите А, имеющие длину n. Представим их выражением:
( +…+ ) . (1)
Произвольное слово длины n в алфавите А можно представить в виде , ,…, . Здесь принадлежит первой из n скобок, – второй и т.д. Имея это в виду, запишем соотношение
( +…+ ) = . (2)
Сопоставим рассматриваемым словам коды в алфавите В. Коды получаются заменой символов ,…, элементарными кодами ,…, соответственно. Имеем
( +…+ ) = . (3)
В силу однозначности кодирования, если ( ,…, ) ( ,…, ), то , то есть разным словам в алфавите А соответствуют разные слова в алфавите В.
Соотношению (3) соответствует тождество
= . (4)
Слагаемым правой части, имеющим одинаковые знаменатели, сопоставляются слова одинаковой длины t, t = +…+ . Пусть ν(n, t) – число слов из (3), имеющих длину t. Пусть l = . Тогда
= . (5)
Из однозначности кодирования следует
ν(n, t) . (6)
Действительно, есть число всевозможных слов длины t в алфавите В. Поскольку в (3) все рассматриваемые коды слов длины n в алфавите А различны, то различны и их подмножества – коды одной и той же длины. Следовательно, соотношение (6) выполняется.
Далее имеем
nl.
Тогда получим
.
Это неравенство справедливо для любого n, так как его левая часть не зависит от n. Перейдя к пределу при n, получим неравенство Мак Милана
1.
Ч.Т.Д.
КАДР
Теорема 4.5. Если алфавитное кодирование, заданное схемой Σ, однозначно, Σ:
,
…
,
то существует алфавитное кодирование, задаваемое схемой :
,
…
,
обладающее свойством префикса, причем для элементарных кодов ,…, выполняются равенства
l( ) = l( ),
…
l( ) = l( ).
Доказательство. Пусть … . Воспользуемся неравенством МакМилана
1.
Разобьем числа ,…, , представляющие длины элементарных кодов, на классы равной длины. Пусть μ – число классов 1 μ r; ,…, – длины элементов классов; ,…, – мощности классов. Перепишем неравенство МакМилана с учетом введенных обозначений:
1.
Это неравенство порождает серию вспомогательных неравенств:
1 или ,
+ 1 или – ,
…
+ +…+ 1 или – – –…– .
Рассмотрим слова в алфавите B, имеющие длину . Так как , то можно выбрать из них слов длины . Обозначим выбранные слова через ,…, . Они представляют элементарные коды схемы кодирования .
Исключим из рассмотрения в дальнейшем слова, начинающиеся с ,…, . Выберем слова в алфавите В, имеющие длину и не начинающиеся со слов ,…, . Число таких слов в алфавите В определяется выражением
– .
Так как – , то имеется возможность выбрать нужных нам слов. Обозначим их через ,…, . Они также представляют элементарные коды схемы кодирования .
Исключим в дальнейшем слова, начинающиеся с уже включенных в схему элементарных кодов. В конце концов мы получим все элементарные коды ,…, схемы . Из построения кодов следует:
l( ) = l( ),
…
l( ) = l( ).
Ч.Т.Д.
КАДР