Кодирование с использованием циклических кодов
Циклические коды
Частным и наиболее широко распространенным классом полиномиальных кодов являются циклические коды.
Линейный (n,k)-код называется циклическим, если в результате циклического сдвига кодового слова получается другое кодовое слово данного кода. Другими словами, если U = ( U0, U1, ...Un- 1 ) является кодовым словом, то и V = ( Un- 1, U0, U1, ...Un- 2 ), полученное циклическим сдвигом U, является кодовым словом данного кода.
Циклические коды привлекательны по двум причинам.
Во-первых, операции кодирования и вычисления синдрома для них выполняются очень просто с использованием сдвиговых регистров.
Во-вторых, этим кодам присуща алгебраическая структура, и можно найти более простые и эффективные способы их декодирования.
Основные свойства циклических кодов:
1. В циклическом (n,k)-коде каждый ненулевой полином должен иметь степень, по крайней мере (n-k), но не более n-1.
| g(x)=1 + g1 × x + g2 × x2 +...+ gn-k-1 × xn-k-1 + xn-k, (3.60) |
2. Существует только один кодовый полином g(x) степени (n-k)
вида
называемый порождающим полиномом кода.
3. Каждый кодовый полином U(x)является кратным g(x), то есть
U(x)= m(x) × g(x). (3.61)
Предположим, надо закодировать некоторую информационную последовательность
m = ( m0, m1, m2... mk- 1 ). (3.62)
Соответствующий ей полином выглядит следующим образом:
m(x)= m0 + m1 × x + m2 × x2 +...+mk- 1 × xk-1. (3.63)
Умножив m(x) на xn-k:
xn-k × m(x)= m0 × xn-k + m1 × xn-k+1 +...+mk- 1 × xn-1 , (3.64)
получим полином степени n-1 или меньшей.
Воспользовавшись теоремой о делении полиномов, можно записать
xn-k × m(x) = q(x) × g(x) + r(x) , (3.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 . (3.66)
С учетом правил арифметики в GF(2) данное выражение можно переписать следующим образом:
r(x) + xn-k × m(x) = q(x)× g(x) , (3.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 . (3.68)
Разделим m(x) × xn-k на порождающий полином g(x) :
 X5 + 0 + X3 X5 + 0 + X3 +X2 X2=r(x). (3.69)
|
Таким образом, кодовый полином, соответствующий информационной последовательности m = (0111), будет иметь следующий вид:
U(x) = 0*X0 + 0*X1 + 1*X2 + 0*X3 + 1*X4 + 1*X5 + 1*X6, (3.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).
 |
Рис. 3.10
Кодирование в схеме рис. 3.10 выполняется следующим образом:
- k символов информационной последовательности mчерез переключатель П, находящийся в верхнем положении, один за другим передаются в канал и одновременно с этим через открытую схему Изаписываются в регистр проверочных символов, в котором благодаря наличию цепей обратной связи g0 ... gn-k-1 формируется остаток от деления xn-k × m(x) на g(x) — проверочные символы;
- начиная с (k+1)-го такта переключатель переводится в нижнее положение, и из сдвигового регистра выводятся (n-k) проверочных символов; цепь обратной связи при этом разомкнута ( схема И - закрыта ).
Для циклического (7,4)-кода Хемминга (а этот код обладает свойством цикличности), используемого в качестве примера и имеющего порождающий полином g(x) = 1 + x + x3, схема кодирования выглядит следующим образом (рис. 3.11):
Рис. 3.11
В этой схеме, в отличие от обобщенной схемы кодера рис. 1.10, отсутствуют элементы в цепях, где значения коэффициентов обратной связи gi равны нулю, там же, где коэффициенты передачи gi равны единице, цепь просто замкнута.
На примере этого же кода и соответствующего ему кодера рассмотрим в динамике процесс кодирования произвольной последовательности m.
Пусть m = (1001). Тогда последовательность состояний ячеек сдвигового регистра с обратными связями в процессе кодирования будет определяться табл. 3.4 .
Таблица 3.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 |
Еще одним важным свойством циклического (n,k)-кода, вытекающим из теоремы о существовании циклических кодов, является то, что его порождающий полином делит без остатка двучлен xn +1, то есть
xn + 1 = g(x)× h(x) + 0. (3.71)
Полином h(x) — частное от деления xn +1 на g(x) -называется проверочным полиномом.
Поскольку h(x) однозначно связан с g(x), он также определяет код. Следовательно, с помощью проверочного полинома h(x) тоже можно производить кодирование. Схема кодирования на основании проверочного полинома h(x) приведена на рис. 3.12.
Рис. 3.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) имеет вид
(3.72)
С учетом этого схема кодирования на основании полинома h(x) для (7,4)-кода выглядит следующим образом (рис. 3.13):
Рис. 3.13