Кодирование с использованием циклических кодов
Предположим, надо закодировать некоторую информационную последовательность
m = ( m0, m1, m2... mk- 1
). (1.62)
Соответствующий ей полином выглядит следующим образом:
m(x)= m0 + m1 × x + m2 × x2 +...+mk- 1 × xk-1. (1.63)
Умножив m(x) на xn-k:
xn-k × m(x)= m0 × xn-k + m1 × xn-k+1 +...+mk- 1 × xn-1
, (1.64)
получим полином степени n-1
или меньшей.
Воспользовавшись теоремой о делении полиномов, можно записать
xn-k × m(x) = q(x) × g(x) + r(x) , (1.65)
где q(x) и r(x) — частное и остаток от деления полинома xn-k × m(x) на порождающий полином g(x).
Поскольку степень g(x) равна (n-k), то степень r(x) должна быть (n-k-1) или меньше, а сам полином r(x) будет иметь вид
r(x)= r0 + r1 × x + r2 × x2 +...+ rn- k- 1 × xn-k-1 . (1.66)
С учетом правил арифметики в GF(2) данное выражение можно переписать следующим образом:
r(x) + xn-k × m(x) = q(x)× g(x) , (1.67)
откуда видно, что полином r(x)+xn-k × m(x)
является кратным g(x) и имеет степень n-1 или меньшую. Следовательно, полином r(x)+xn-k
× m(x) - это кодовый полином, соответствующий кодируемой информационной последовательности m(x).
Раскрыв последнее выражение, получим
r(x)+m(x)× xn-k
=r0 +r1 x +r2 x2 ..+rn- k-1 xn-k-1 + m0 xn-k
+ m1 × xn-k+1 + ..+ mk-1 xn-1,
что соответствует кодовому слову
| U
= | ( r0, r1 ... rn- k-1 , | m0, m1 ... mk-1), | |||
| проверочные символы | информационные символы |
Таким образом, кодовое слово состоит из неизменной информационной части m, перед которой расположено (n-k) проверочных символов.
Проверочные символы являются коэффициентами полинома r(x), то есть остатка от деления m(x) × xn-k на порождающий полином g(x).
Чтобы полученный результат был понятнее, напомним, что умножению некоторого двоичного полинома на xn-k соответствует сдвиг двоичной последовательности m = (m0, m1 ... mk-1) на n-k разрядов вправо.
Рассмотрим пример. С использованием кода, задаваемого порождающим полиномом g(x) = 1 + x + x3, закодируем произвольную последовательность, например m = (0111).
Последовательности m =(0111) соответствует полином m (x)=x+ x2 + x3.
Умножим m(x) на xn-k
:
m(x) × xn-k
=m(x) × x3 =(x + x2 + x3) × x3 = x4 + x5
+ x6 . (1.68)
Разделим m(x) × xn-k на порождающий полином g(x)
:
 X5 + 0 + X3 X5 + 0 + X3 +X2 X2=r(x). (1.69) |
будет иметь следующий вид:
U(x) = 0*X0 + 0*X1 + 1*X2 + 0*X3 + 1*X4 + 1*X5 + 1*X6, (1.70)
а соответствующее кодовое слово U = (0010111).
Итак, циклический (n,k)-код k-разрядной информационной последовательности m = (m0, m1 ... mk-1)
получают следующим образом:
- информационную последовательность m умножают на xn-k, то есть сдвигают вправо на n-k разрядов;
- полином полученной последовательности делят на порождающий полином кода g(x);
- полученный остаток от деления m(x) ×
xn-k на
g(x) прибавляют к m(x) × xn-k,
то есть записывают в младших n-k разрядах кода.
Алгоритм кодирования, основанный на делении полиномов, можно реализовать, используя схему деления. Она представляет собой регистр сдвига, в котором цепи обратной связи замкнуты в соответствии c коэффициентами порождающего полинома g(x) (рис. 1.10).
 |
Кодирование в схеме рис. 1.10 выполняется следующим образом:
- k
символов информационной последовательности m через переключатель П, находящийся в верхнем положении, один за другим передаются в канал и одновременно с этим через открытую схему И записываются в регистр проверочных символов, в котором благодаря наличию цепей обратной связи g0 ... gn-k-1 формируется остаток от деления xn-k × m(x) на g(x) — проверочные символы;
- начиная с (k+1)-го такта переключатель переводится в нижнее положение, и из сдвигового регистра выводятся (n-k)
проверочных символов; цепь обратной связи при этом разомкнута ( схема И
- закрыта ).
Для циклического (7,4)-кода Хемминга (а этот код обладает свойством цикличности), используемого в качестве примера и имеющего порождающий полином g(x) = 1 + x + x3, схема кодирования выглядит следующим образом (рис. 1.11):
Рис. 1.11
В этой схеме, в отличие от обобщенной схемы кодера рис. 1.10, отсутствуют элементы в цепях, где значения коэффициентов обратной связи gi равны нулю, там же, где коэффициенты передачи gi равны единице, цепь просто замкнута.
На примере этого же кода и соответствующего ему кодера рассмотрим в динамике процесс кодирования произвольной последовательности m.
Пусть m = (1001).
Тогда последовательность состояний ячеек сдвигового регистра с обратными связями в процессе кодирования будет определяться табл. 1.4 .
Таблица 1.4
|
Номер такта |
Положение переключателя |
Уровень разрешения |
Вход m |
Состояние ячейки регистра |
Выход |
||
|
P0 |
P1 |
P2 |
U |
||||
|
0 1 2 3 4 5 6 7 |
¯ ¯ ¯ ¯ |
1 1 1 1 0 0 0 0 |
1 0 0 1 0 0 0 0 |
1 0 1 0 0 |
1 1 1 1 0 0 |
0 1 1 1 1 0 0 |
1 0 0 1 1 1 0 |
xn + 1 = g(x)× h(x) + 0. (1.71)
Полином h(x) — частное от деления xn +1 на g(x) - называется проверочным полиномом.
Поскольку h(x) однозначно связан с g(x), он также определяет код. Следовательно, с помощью проверочного полинома h(x) тоже можно производить кодирование. Схема кодирования на основании проверочного полинома h(x) приведена на рис. 1.12.
Рис. 1.12
Процедура кодирования на основании h(x) выглядит следующим образом :
1. На входе "Разрешение"
устанавливается 1, при этом открывается нижняя схема И и закрывается верхняя.
2. Сообщение m
последовательно записывается в k-разрядный сдвиговый регистр и одновременно с этим передается в канал.
3. По окончании ввода
k информационных символов на входе "Разрешение" устанавливается 0, замыкая через верхнюю схему И цепь обратной связи.
4. Производится (n-k)
сдвигов, при этом формируются и выдаются в канал (n-k) проверочных символов.
Для циклического (7,4)-кода с порождающим полиномом g(x)= 1+ x + x3 проверочный полином h(x) имеет вид
С учетом этого схема кодирования на основании полинома h(x)
для (7,4)-кода выглядит следующим образом (рис. 1.13):
Рис. 1.13
