Двоичные последовательности Хаффмена

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

(1.3.1)

где суммирование выполняется по правилу сложения символов 1 и 0 (по модулю 2).

Фильтр (3.1) обладает следующим свойством: через определенное число символов они начинают повторяться. Длина последовательности до 1-го повторения зависит от выбора коэффициентов формирующего фильтра a1, a2, …, am. Значения коэффициентов формирующих приведены в таблице 3.1. При использовании этих фильтров последовательности S(k) имеют максимальную длину (до начала повторения).

Таблица 1.3.1

m

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

Продолжение таблицы 1.3.1

m

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

Окончание таблицы 1.3.1

m

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

В последовательности Хаффмена символы начинают повторяться через Nm значений, где Nm =2 ^m -1.

Приведем несколько примеров:

1) m=4; a1=1; a2=0; a3=0; a4=1; начальная последовательность S(k)=1000 (k=1, 2, 3, 4)

S(k)=S(k-1)ÅS(k-4)

1000111101011001001000…

2) m=5; a1=0; a2=1; a3=0; a4=0; a5=1; начальная последовательность – 11111

S(k)=S(k-2)ÅS(k-5)

1111100110100100001010111011000111…

Изменяя начальные последовательность и коэффициенты формирующего фильтра, можно формировать различные последовательности Хаффмена.

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

(1.3.2)

Отбираются такие кодовые комбинации, у которых d(i, j)>d, где d – задано.

Среди различных способов формирования неразделимых блоковых комбинаций наиболее простым является способ циклической перестановки некоторой исходной n-разрядной кодовой комбинации, взятой из последовательностей Хаффмена. Рассмотрим формирование циклических кодовых слов на примере 15-значной последовательности Хаффмена