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

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

ОГЛАВЛЕНИЕ

Следующая >>

получить проверочное соотношение и построить проверочную мат-
рицу, исходя только из свойств циклических кодов. Для этого, вос-
пользуемся 'сформированным ранее утверждением 3.2.5 о том, что
порождающий многочлен д(Х) делит Хп + 1 без остатка. Следова-
тельно, можно написать

Xn + l = h(X)-g(X). (3.43)
3-4- Порождающая и проверочная матрицы I75 ,

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

(3.44)
= a(X)-g(X),

то, с учетом (3.43), произведение v(X)h(X) равно

v{X) • h(X) = a(X) • h{X) • g(X) = (3.45)
п п
= а(Х) • [1 + Х ] = а{Х) + а(Х)Х .

Так как степень многочлена а(Х) не превышает к — 1, правая часть
к
равенства (3.45) не содержит в качестве слагаемых члены с Х ,
+1 1
• • • X™" . Используя это условие для коэффициентов произве-
X
дения v(X)h(X), можно записать п — к проверочных равенств

=0
viOhk® =0
vk+i © h0
vk ©
vk+\ ©

(3.46)
Эти равенства можно записать в матричной форме.. Введя провероч-
ную матрицу

0
(hk hk-i hk-2 0
h0
hi ••• 0 ^

... о
h
0 hk hk-i hk-2 0
/*o

(3.47)
0 0 hk-i hk-2
hk
=
Ло
H( n -fc) X n Ai

••. о

hi ho)
0 hk. hk-i hk-2

получим уже известное матричное уравнение для синдромного деко-
дирования
v © Н г = 0. (3.48)

Определение 3.4.1. Пусть задай порождающий многочлен д(Х)
степени г = п — к циклического (п, &)гкода С. В этом случае, мно-
гочлен h{X) степени к такой, что Хп + 1 = g(X)h(x) называется
проверочным многочленом.
Многочлен, взаимо обратный проверочному многочлену h(X), т.е
многочлен Xk(h(X˜1)) + ••• + hoXk я в л я е т с я порож-
= hk + hk-iX
дающим многочленом (п, п — /г)-кода Gj, дуального коду С.
Замечание. Преобразованию Xlh(X˜l) соответствует зеркальное
отображение его коэффициентов.
I 76 Глава 3. Циклические коды

Пример: Порождающий многочлен кода, дуального циклическо-
му (7,4)-коду Хэмминга.
Рассмотрим опять циклический код с порождающим многочле-
ном д(Х) = 1 + X + X3 из (3.24). Из разложения на множители
X7 + 1 (3.23) следует, что его проверочный многочлен имеет вид
2 3 2 4
= (1 + X) • (1 + X + х ) = 1 + X + X + X , (3.49)
h(x)
поэтому, порождающий многочлен дуального кода определяется как
X4h(X˜1) = X4 + Xs + X2 + l (3.50)
и он порождает циклический (7,4)-код.
Теперь перед нами стоит задача получить порождающую матри-
цу систематического циклического (п, &)-кода, с заданным порожда-
ющим многочленом д(Х), не прибегая к элементарным преобразо-
ваниям матрицы (3.39). Здееь ключевая идея будет состоять в том,
что любые к линейно независимых векторов, делящихся на д{Х), об-
разуют одно и то же кодовое векторное пространство. Надо лишь
выбрать эти векторы таким образом, чтобы им соответствовала по-
рождающая матрица систематического (п, А;)-кода.
г+г
Представим Х в виде
Xr+i = сц(Х)д(Х) + bi{X),
' (3.51)
где Г = 0,1, - - -fc— 1 и
i(X) = bifl + щ^Л + • • • + OjiT._iA . (3.52)
Равенству (3.51) соответствуют к линейно независимых кодовых мно-
гочлена
Vi(X) = <ь(Х)д(Х) - Xr+i + bi(X). (3.53)
Таким образом, векторное пространство систематического цикличе-
ского (п, &)-кода «натянуто» на набор к векторов Хг+г + bi(X), где
г = 0,1, • • • А; — 1. Здесь единицы при Хг+г образуют единичную под-
матрицу и являются признаком независимости базисных многочле-
нов Vi(X).
Порождающая матрица, соответствующая (3.53), имеет вид

^0,0 ^0,1 "0,2 ••' &0,г-1 10 ••• 0
Oj о Ь\ 2 * • * 0 1 * •• 0
b\ i b\r—\
V . '. .... . (3.54)

frfc-i,o bfc-i,i bfc-i,2 • •
• fyt-1,,— 1 0 1 •• 0


Pfcxr Ifcxfc
N
3.5. Схемная реализация циклического кодирования 177

Таблица 3.4. Определение порождающей матрицы в систе-
матическом виде.

Базовый кодовый многочлен
r-i
Многочлен из (3.51)
X




3 3
X= vo(X) = 1 + Х + Х
д(Х) + 1 + Х
4 2 4
X— Хд(Х) + Х + Х2 vt(X) = 1 + Х + Х
хъ— MX) = 1 + Х + Х' + Х
(X2 + 1)д(Х) + 1 + X + Х2 2 ь



х2
(х3 + Х + 1)д(Х) + 1 +
6
6 2
v3(X) = 1 + X + X
X—




Как уже доказывалось ранее, проверочная матрица систематиче-

ского кода образуется из (3.54) в форме

гхп — \*-rxr *^ )• \о.0о)

Пример: Порождающая матрица систематического циклическо-
го (7,4)-кода Хэмминга.

Найдем порождающую матрицу систематического циклического
(7,4)-кода но уже известному порождающему многочлену д(Х) =
3
1 + X + X из (3.24). Для этой цели определим, вначале, разложение
Хг+г согласно (3.51) и базисные кодовые многочлены Vi(X) из (3.53)
для г = 0,1,2,3 (табл. 3.4).
Порождающая матрица непосредственно строится по базисным
кодовым многочленам vo(X),V\(X),V2{X),V3(X) и полностью совпа-
дает с (3.42)


11 0 1 00 0
01 1 10 0
0
(3.56)
0
11 1 01
0
1
10 1 00
0

'4x3 14x4



3.5. Схемная реализация циклического кодирования
Важнейшее преимущество циклических кодов по сравнению с дру-
гими методами кодирования заключается в простоте их технической
реализации. Использование в схемах кодеров и декодеров регистров
178 Глава 3. Циклические коды

Таблица 3.5. Алгоритм Евклида деления многочлена
2 4 2
f(x) = 1 + X + X + X на д(х) = 1 + X .


/W
4 2
X - +1
-
X + X
2 2
X* X Х д{Х)
1 Остаток
X +




сдвига с обратными связями, позволяет просто и достаточно эффек-
тивно защищать от ошибок информационные массивы очень боль-
шой длины.
Замечание. Эта особенность присуща всем, циклическим кодам
над полями Галуа. Для простоты изложения, здесь мы ограничим-
ся только двоичными кодами, т.е. циклическими кодами nadGF(2).
Так как процедура деления многочленов является основной в ко-
дерах и декодерах циклических кодов, покажем, прежде всего, как
эта процедура может быть реализована с помощью регистров сдвига
с обратными связями. Для начала, сопоставим деление многочлена
f{X) = 1+Х+Х2+ХА на многочлен д(Х) = 1+Х2 по алгоритму Ев-
клида (табл. 3.5) с его схемной реализацией (рис. 3.5). В таблице 3.5
2
делитель д(Х) домножается на X , так как степень f(X) равна 4 и
вычитается из делимого f(X). В результате, полученный многочлен
имеет степень, меньшую д(Х), так что мы сразу же имеем остаток
от деления f(X) на д(Х). Аналогичная процедура имеет место и на
рис. 3.5, однако, здесь требуется три такта для того, чтобы младшие
разряды f{X) заняли место остатка.




: 1+Х2.
Р и с . 3.5. Схема деления многочлена \+Х+Х2+Х4

Теперь рассмотрим схемную реализацию деления двоичных мно-
гочленов в общем случае. Пусть заданы: делимое степени т

(3.57)
f(X) = /о f2X2 + ••• + fmX"
179)
3.5. Схемная реализация циклического кодирования


и делитель степени г, причем, г <т

(3.58)
= д0 + дхХ + д2Х2 дгХг.
д(Х) + ••• +

В результате деления мы должны получить разложение

(3.59)
= a(X)g(X)+b(X)
с сомножителем а(Х) степени m - г и остатком Ъ{Х) со степенью, на
превышающей г — 1.
Схема деления многочленов общего вида представлена на рис.
3.6.
Сначала регистр сдвига полностью загружается старшими раз-
рядами делимого. Ключ 51 включен, а переключатель 52 находится
в верхнем положении. Далее'начинается сам процесс деления. В пер-
вом такте производится сдвиг содержимого регистра на один разряд
вправо. Так как fm = 1, эта единица, в соответствии с коэффициен-
том двигателя д(Х), суммируется с аналогичными разрядами дели-
мого. В результате, мы получаем укороченный многочлен

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

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

ОГЛАВЛЕНИЕ

Следующая >>