Доказательство (принадлежит Маркову)

Критерий однозначности кодирования.

Теория кодирования.

– исходный алфавит из букв, – кодовый алфавит из букв, – функция кодирования, .

Различным буквам сопоставляются различные слова. Применим следующие обозначения:
– длины кодовых слов, равные соответственно.
– общая длина кодовых слов.
– максимальное число кодовых слов, которые размещаются в некотором другом кодовом слове.

Если кодирование некорректное, то обязательно найдется пара различных слов в исходном алфавите , длина которых не превосходит и которые отображаются в одно и то же кодирующее слово.
Таким образом, для проверки корректности кодирования достаточно перебрать лишь только исходные слова, длина которых не превосходит и посмотреть на кодирующие слова. Если среди кодирующих слов найдутся одинаковые, то кодирование некорректное. А если среди кодирующих все слова различны, то кодирование корректно.

II

II

II

Рассмотрим кодирование слова минимальной длины, которое допускает, по крайней мере, две различных расшифровки, т.е. для которого найдется, по крайней мере, два различных исходных слова, кодирующим для которых является данное слово. Рассмотрим две различных его расшифровки. Кодовые слова первой расшифровки обведены сверху, а кодовые слова второй расшифровки – снизу. Разрежем кодирующее слово по границам кодовых слов. В результате получим слова-отрезки. Эти слова разобьем на две группы:
1-ая – слова, которые являются кодовыми;
2-ая – слова, которые не являются кодовыми, т.е. все остальные.

Слова 2-ой группы являются либо началом кодовых слов второй расшифровки и концом кодовых слов первой расшифровки, либо началом кодовых слов первой расшифровки и концом кодовых слов второй расшифровки.

Слова 2-ой группы попарно различны. Если бы это было не так, т.е. существовали два одинаковых слова 2-ой группы, то вырежем участок между двумя одинаковыми словами 2-ой группы вместе с одним из этих слов и соединим полученные два слова. Тогда не трудно видеть, что полученное слово также допускает две дешифровки, что противоречит минимальности некорректного данного слова.

Посчитаем, какое максимальное число слов во 2-ой группе может быть. Во 2-ой группе есть непустые начала кодовых слов, которые отличны от самих кодовых слов. Первое слово имеет длину и поэтому число рассмотренных начал для него есть , для второго кодового слова число начал равно , и так для каждого, а для последнего – . Суммируя данные величины, получаем, что число слов во 2-ой группе не более чем .

Слова второй группы разбивают исходное слово на не более чем кусков.

Теперь разобьем слова 2-ой группы на пары соседних и рассмотрим последовательность слова . Таких пар слов не больше, чем (в случае нечетного числа слов, последнее непарное слово – дополнительное). Число кодовых слов в каждом из полученных не более по обеим кодировкам. Согласно одному разбиению в одной половине уложатся не более одного кодового слова, а в другой – не более (согласно второму разбиению ситуация симметрична).

Поэтому общее число кодовых слов, которое содержится в начальном слове не более чем . Что и требовалось показать.

Дата добавления: 2017-01-13