7. Коды Хаффмена (метод синтеза бинарных эквидистантных кодов)

Число последовательных сдвигов вправо, после которого образуется первоначально выбранная комбинация, называют периодом данной комбинации. Например, комбинация 010101 имеет период 2. Действительно, после первого сдвига мы имеем 101010, а после второго 010101, т. е. исходную комбинацию. Комбинация 001001 имеет период 3, а комбинация 1110100 — период 7, т. е. равный ее значности. Кстати, очевидно, что максимально возможное значение периода всегда равно .

В циклическом коде различные комбинации могут иметь разные периоды. Под периодом циклического кода

я обычно понимают наименьший из периодов всех его комбинаций.

Если циклический код порождается полиномом и его период , то

(X.7.1)

Из последнего равенства получаем

(X.7.2)

где - некоторый произвольный полином степени, меньшей, чем .

Но по условию делит без остатка, поэтому

(X.7.3)

Следовательно, делится без остатка на генераторный полином . Число по определению, есть наименьшее среди всех чисел, определяющих периоды комбинаций данного циклического кода. Отсюда вытекает, что если показатель к генераторного полинома равен , то полином порождает циклический код периода . В частности, если показатель полинома равен , то полином порождает циклический код с максимальным периодом, который часто называют кодом или последовательностями Хаффмена.

Степень полинома определяет число информационных символов, причем для кодов Хаффмена , поэтому их значность

(X.7.4)

Коды Хаффмена являются оптимальными и эквидистантными с

(X.7.5)

в частности, в коде (X.6.2) .

Наконец, следует отметить, что коды Хаффмена допускают мажоритарное декодирование, а их комбинации обладают достаточно хорошими автокорреляционными функциями (основной пик в раз больше побочных максимумов).