1.2 Двоичные дискретные сигналы и фильтры
Двоичные дискретные сигналы могут принимать только два значения 1 и 0, например, 1011011100101001. Такие сигналы называются кодовыми комбинациями. Число символов в сигнале определяет его размер (значность). Кодовая комбинация 1011011 называется семизначной, а символы характеризуются разрядностью справа налево, от младшего разряда к старшему. Запишем зет-преобразование рассмотренной семизначной кодовой комбинации
S(z)=1+z-2+ z-3+ z-4+ z-5+ z-6.
В общем случае зет-преобразование двоичных сигналов ничем не отличается от преобразования обычных дискретных сигналов. Однако при описании процессов фильтрации операция суммирования двоичных сигналов имеет свои особенности. Правило суммирования двоичных сигналов базируется на законе сложения символов 0 и 1 по модулю 2: 00=0; 11=0; 10=1; 01=1. Закон умножения символов 0 и 1 такой же, как и для обычных чисел. Здесь знак означает сложение по модулю 2. Например, сумма символов рассмотренного семизначного двоичного сигнала
а сигнала 1111011 равна
Преобразование двоичных сигналов нерекурсивными и рекурсивными двоичными фильтрами описываются формулами
(1.2.1)
(1.2.2)
где ai и i – двоичные коэффициенты, принимающие только два значения 0 и 1.
Заметим, что операции сложения и вычитания
двоичных символов не отличаются между
собой, т. е. 1
1=0;
0
0=0;
1
0=1;
0
1=1.
Рассмотрим последовательные соединения нерекурсивного и рекурсивного фильтров
Преобразуем второе выражение к виду
и сравним с первым. В результате получим
(1.2.3)
Если коэффициенты нерекурсивного и рекурсивного фильтров выбрать равными друг другу (т.е. ai=i), то из (1.2.3) следует, что S1(k)=U(k): кодовая комбинация на выходе рекурсивного фильтра равна кодовой комбинации на входе нерекурсивного фильтра. Такие фильтры называются взаимными. Их дискретные передаточные функции равны
(1.2.4)
Полином
называется формирующим. Из (1.2.4) следует
Таким образом, если дискретный двоичный сигнал U(k) преобразовать нерекурсивным фильтром
(1.2.5)
то его можно восстановить путем преобразования сигнала S(k) рекурсивным фильтром
(1.2.6)
Функции преобразования H(z) соответствует дискретный двоичный сигнал H(k) . Так как S1(z)=H(z)U1(z) и U2(z)=S2(z)/H(z), то нерекурсивный фильтр решает задачу перемножения двоичного сигнала U(k) на двоичный сигнал H(k), а рекурсивный фильтр – задачу деления S(k) сигнала на сигнал H(k). Если при этом S2(z)=S1(z)=S(z), то сигнал S(k) будет делиться на H(k) без остатка и U2(z)=U1(z)=U(z). Рекурсивные и нерекурсивные двоичные фильтры используются для формирования кодовых сигналов и схем оценки помех и восстановления кодовых комбинаций.
1.3 Двоичные последовательности Хаффмена
Двоичные цифровые фильтры можно использовать для формирования кодовых сигналов. Среди них особое место занимают фильтры Хаффмена, которые используются для получения двоичных последовательностей максимальной длины. Формирующие фильтры Хаффмена описываются уравнением
(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 |
4 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
|
5 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
|
6 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
|
|
7 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
Продолжение таблицы 1.3.1
m |
a0 |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
a13 |
7 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
|
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
|
8 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
|
|
|
|
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
|
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
|
|
|
|
|
|
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
|
|
9 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
|
|
|
|
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
|
|
|
|
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
|
|
|
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
|
|
|
|
|
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
|
|
|
|
10 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
|
|
|
|
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
|
Окончание таблицы 1.3.1
m |
a0 |
a1 |
a2 |
a3 |
a4 |
a5 |
a6 |
a7 |
a8 |
a9 |
a10 |
a11 |
a12 |
a13 |
10 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
|
|
|
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
|
|
|
|
11 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
|
|
12 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
|
13 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
В последовательности Хаффмена символы начинают повторяться через Nm значений, где Nm =2m-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…
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-значной последовательности Хаффмена
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |