Доказательство. Критерий префиксного кодирования Мак-Миллана

Критерий префиксного кодирования Мак-Миллана.

Определение. Кодирование называют типа , если существует штук кодовых слов единичной длины, кодовых слов из двух букв, слов из трех букв, …, слов длины .

Критерий. Префиксное корректное кодирование типа существует тогда и только тогда, когда

– мощность кодирующего алфавита.

Необходимость. Пусть – корректное кодирование типа . Покажем справедливость формулы .

Перепишем формулу в виде:

– длины кодовых слов. Возведем сумму в степень :
,
т.е. возьмем произведений таких сумм

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

Действительно, – это общее число слов в кодирующем алфавите длины , а каждое решение уравнения будет соответствовать некоторому кодирующему слову, которых, в силу корректности, не может быть больше чем общее число слов длины :

Достаточность. Пусть числа удовлетворяют соотношению . Построим префиксное кодирование типа .

Перепишем сумму по слагаемым:

Наша задача – построение кодовых слов таких, что никакое кодовое слово не начинается на другое кодовое слово. Построим в начале кодовые слова единичной длины, а потом длины 2 и т.д.

Из неравенства следует, что , т.е. . В кодирующем алфавите есть букв и мы должны выбрать различных кодовых слов единичной длины, а из неравенства следует, что это действительно можно сделать.

Далее построим кодовые слова длины 2. Тогда выполняется неравенство , из которого следует, что , где – общее число слов длины 2 в кодовом алфавите, а – число слов длины 2, которые начинаются на кодовые слова единичной длины. Таким образом, число допустимых слов длины 2 равно . Из полученного неравенства следует, что мы действительно можем выбрать кодовые слова длины 2, чтобы выполнялись условия префиксности.

Допустим, что уже выбраны кодовые слова длины меньшей , причем соблюдая условия префиксности. Покажем, что можно выбрать кодовые слова длины .

Из неравенства следует, что
,
где – общее число слов длины в кодирующем алфавите, – число слов длины , которые начинаются на кодовые слова длины и т. д., число слов длины , которые начинаются на кодовые слова длины 1. Таким образом, мы построили префиксное кодирование типа .

Теория кодирования имеет применение в задачах устойчивой пердачи информации.

Основная литература:

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