<< Предыдущая

стр. 30
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>


3.3. Систематические циклические коды
Приведенные в таблице 3.1 кодовые слова образуют несистематиче-
ский код. Однако, путем некоторой модификации алгоритма коди-
рования можно получить систематический циклический код с теми
же параметрами.

Регистр сдвига

тттштт
о I- I о I о
Информационное слово


Р и с . 3.4. Сдвиг информационного многочлена в регистре
сдвига с обратными связями длины п на г = п — к
позиций.

Для этой цели рассмотрим информационный многочлен степени
fc-1
и{Х) = щ + щХ + • • • + ик^Хк-1 (3.25)
и его г = п — fc-кратный сдвиг.
г г г+1 п1
(3.26)
Х и(Х) = щХ + щХ + ---+ик^1Х ' . .

Из рис. 3.4 видно, что такой сдвиг не вызывает переполнения
n-разрядного регистра сдвига (поэтому и может быть записан в ви-
де (3.26)) и соответствует заполнению А правых крайних двоичных
;
разрядов регистра информационным словом. Заполним теперь сво-
бодные г левых двоичных разрядов таким образом, чтобы вектор,
содержащийся в n-разрядном регистре, принадлежал коду. Для это-
г
го представим многочлен Х и(Х) в виде

Хги(Х) = а(Х) • д(Х) + Ь(Х), (3.27)

где Ь(Х) - остаток от деления Хги(Х) на д{Х).
Из (3.27) следует

Хги{Х) + Ь(Х) = а(Х) • д(Х). (3.28)

Из (3.28) вытекает алгоритм кодирования систематического цикли-
ческого (п,/г)-кода:

1. Информационный многочлен и(Х) степени к — 1 умножается
на Хг, где г = п — к;
3.3. Систематические циклические коды, 171

Т
2. Находится остаток Ь(Х) от деления Х и{Х) на д(Х);

3. Многочлен Ь(Х) заносится в г левых разрядов регистра сдвига
(рис. 3.4).

Заметим, что эта операция всегда возможна, так как степень Ь(Х)
по определению не превышает г—1. Таким образом, в регистре сдвига
будет сформирован многочлен

= bo + biX+---br-1Xr-\+ . (3.29)
v(X)
г проверочных символов
г г+1 1
+ + щХ
и0Х + ••• Uk-iX"' .

jt'информационных символов

Многочлен v(X) принадлежит циклическому коду, так как в силу
(3.28) он делится на д(Х) без остатка. Более того, этот код является
систематическим, так как из (3.29) следует, что старшие к разрядов
кодовых векторов являются информационными векторами.
Следующий пример наглядно поясняет алгоритм кодирования
циклических систематических кодов.
Пример: Циклический (7,4)-код в систематической форме.
В качестве порождающего многочлена будем использовать уже
3
известный из предыдущего примера многочлен д(Х) = 1 + X + X
(3.24). Пусть задан информационный вектор

и = (1001). (3.30)

Ему соответствует информационный многочлен

«(X) = 1 + X3. (3.31)

Умножим информационный многочлен на X

Х3и(Х) = Х3 + Х6 (3.32)

и определим остаток Ь(Х) от деления (3.32) на д(Х). Процесс нахо-
ждения остатка Ь(Х) в соответствии с алгоритмом деления Евклида
показан в табл. 3.2. В результате получим

Х3и{Х) = (X + X3)g{X) +X + X2. (3.33)
Глава 3. Циклические коды

Таблица 3.2. Определение проверочных символов для
3 3
и(Х) = 1 + X и д(Х) = 1+Х +Х .

6 2
4
1
X X X
X
5
Л:

1 3
0 1 0 0 0 = Х и(Х)
0
1 3
0 1 1 0 0 0 = Х д(Х)
= Х3и(Х) Х3д(Х)
1 0 0 0 0 +
- -
1
1 0 1 0 = Хд(Х)
= Ь(Х)
1 1 0
- -




Так как кодовый многочлен определяется как

v{X) = Ь(Х) + Х3и(Х), (3.34)

то
1001). (3.35)

Повторяя процесс кодирования для всех 16 возможных информаци-
онных векторов, получим систематический циклический (7,4)-код.
Его информационные и кодовые векторы приведены в табл 3.3. За-
метим, что циклический систематический (7,4)-код, образованный
порождающим многочленом 1 + X + X3, совпадает с рассмотренным
нами ранее систематическим (7,4)-кодом Хэмминга (см. табл. 2.1).


3.4. Порождающая и проверочная матрицы
Циклические коды образуют подмножество линейных блоковых ко-
дов и, помимо общих особенностей линейных блоковых кодов, они
обладают некоторыми специфическими свойствами и методами опи-
сания. Рассмотрим сначала порождающую матрицу циклического
кода. В соответствии с теоремой 3.2.3, каждый многочлен цикличе-
ского кода может быть представлен в виде произведения

+ - • •+ak_xXk-lg(X).
v(X) = a{X)-g{X) = aog(X)+a1Xg(X) (3.36)

Заметим, что каждое слагаемое в (3.36) представляет собой сдвиг
порождающего многочлена д{Х), которому соответствует вектор

(3.37)
g=
3.4- Порождающая и проверочная матрицы [73j

Таблица 3.3. Циклический (7,4)-код, образованный порож-
3
дающим многочленом д(Х) = 1 + X + X в си-
стематическом виде.

Информационное Кодовое Информационное Кодовое
слово слово слово слово
0000 000 0000 0001 101 0001
1000 ПО 1000 1001 011 1001
0100 011 0100 0101 ПО 0101
1100 1101
101 1100 000 1101
0010 111 0010 010 ООП
ООП

1010 100 1011
001 1010 1011
01 от
0
100 ОНО 0111
ОНО

1110 1111 111 1111
010 1110




поэтому, кодовый вектор v, соответствущий многочлену v(X), может
быть представлен в виде произведения информационного вектора а
на порождающую матрицу G

(3.38)
v
lxn —

где порождающая матрица G имеет вид

0\
/ 1 91 91 • • 9т-\
• 1 О
О
О 1 1
9\ ••• 9г-2 9г-1

(3.39)
00 1 _i
G/cxn — 5r




О-- 0 flr-i 1/
9\ 92 •••


Пример: Порождающая и проверочная матрица циклического
(7,4)-кода Хэмминга.
Используя уже известный порождающий многочлен д(Х) = 1 +
X + X3 (3.24), получим порождающую матрицу несистематического
циклического (7,4)-кода

110100 0
011010 0
(3.40)
001101 0
1
000110
Глава 3. Циклические коды.

Как уже указывалось ранее, кодовое векторное пространство, обра-
зованное порождающим многочленом д(Х) = 1+Х+Х3, совпадает с
линейным векторным пространством (7,4)-кода Хэмминга , следова-
тельно матрицу G из (3.40) можно также рассматривать, как порож-
дающую матрицу циклического кода Хэмминга в несистематической
форме.
Путем элементарных матричных преобразований порождающая
матрица G из (3.40) может быть приведена к систематическому ви-
ду. Так как каждая строка матрицы G является кодовым словом,
замена любой строки суммой этой строки с другой, отличной от нее,
не меняет кодового векторного пространства (меняется лишь систе-
ма соответствий между информационными и кодовыми векторами).
Заменим в (3.40) вначале третью и четвертую строку их суммами с
первой строкой и, далее, полученную четвертую строку - ее суммой
с первой. В результате, получим порождающую матрицу системати-
ческого циклического кода Хэмминга, совпадающую с (2.2)

1 1 0 1 0 0 0\
, , •0 1 10100
,
(3.41)
Х
G4x7 - (Р 4 хз 4) = I ! ! !00!0
1 0 1 0 0 0 1/

Возьмем информационный вектор из (3.30) и = (1 0 0 1). Ему будет
соответствовать кодовый вектор

'1 1 0 1 0 0 0 \
0110100
= (011 1001), (3.42)
= u©G4x7 = (1001)0
1110010
,1010001/

что совпадает с полученным ранее (3.35) кодовым вектором систе-
матического циклического кода и табл. 3.3.
Проверочная матрица циклического систематического (7,4)-кода
может быть получена из порождающей матрицы G' (3.41) по рас-
смотренным ранее формальным правилам. Здесь, однако, мы хотим

<< Предыдущая

стр. 30
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>