Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

быть

больше

(п—1).

Для того чтобы произведение не

содержало степеней

больше (п—1), будем

полагать

фор­

мально xns=l,

т. е.

хп—1=0.

Можно

показать,

что множество полиномов степени

(п—1)

и

менее над

двоичным полем, для

которых

вве­

умножения

(последняя по модулю

хп—\),

образует ли­

нейную

алгебру.

Например, элементами алгебры многочленов над

двоичным полем

по

модулю (х3—1)

являются:

0,

1,

х,

\+х,

х2

\+х2

х+х2,

\+х+х\

Тогда

(х+х2)

(I +х+х2)

=

=х+х2+х3+х2+х3+х''

=

х+х'*=

х+х-х3=х+х-\=х+

+х=(1

+ 1)х = 0.

Циклическим

сдвигом

вектора

А = (а0,

Сь а2,..

.,ап-0

назовем

вектор

ТА =

(ап-и

ао, ait..

.,an-i),

тогда

Т2А

=

— Т(ТА)

= (ап-2,

fln-i,

а0 > .. .,ап _з),

и т. д.

С позиций введенной выше операции умножения по­

линомов

(по модулю хп—1)

циклическому сдвигу

век­

тора

Л соответствует

умножение

полинома

А (х)

на

х:

xA(x)=x(ao+Qix+a2x2jr..

.-\-ап~2хп-2-\-ап-1Хп~^)

=

=

an-i

+ a0x + aix2+..

. +

ап-3хп-2+ап-2хп-1.

Код

называется

циклическим

(соответственно

под­

коду

принадлежит ТА

и, следовательно,

TiA, где i=

= 1,

2,.. .,п—1.

Другими

словами, если

А(х)—кодовый

полином, то полиномы xiA (х)

также принадлежат коду.

Циклический код однозначно задается с помощью так

называемого

порождающего

полинома

G(x)=go+

+giX+

. . . +grxr.

При

этом

многочлен

А(х) степени

чае, если он делится на G(x). Другими словами,

для

кодовых полиномов, имеет место сравнение

/1(х)==0

по модулю G(x);

(3-1)

отсюда

х1А(х)5=0

по модулю G(x).

Если в кодовом слове возникнет

ошибка, то А*(х) —

=А

(х) +Е(х),

где

Е(х)—полином

ошибки.

Пусть

Е(х)=х1,

г'=0,

1, ...,

п—1, т. е. возможны

только

одно­

кратные ошибки. Тогда полином G(x),

порождающий

код с минимальным расстоянием d—2,

может быть най­

ден из условия

х1фО,

по модулю

G(x),

/ = 0 ,

1

п—1.

В

этом

случае обнаруживается

любая

одиночная

ошибка,

так

как не выполняется

сравнение (3-1):

А*(х)

==х*Ф0 .по модулю

G(x).

Полином

минимальной

степени,

удовлетворяющий

условию

(3-1),

равен

\+х.

Таким

образом,

полином

G(x)

— l+x

порождает корректирующий

код с

минималь­

ным

расстоянием

d=2.

Длина п этого кода

произвольна,

количество информационных разрядов

k=n—1

(см. ни­

ми на четность или

нечетность

количества

единиц

в слове.

Покажем, например,

что данный

циклический

код не

ности два

имеет вид:

Е(х)=х1+хк

Пусть для определенности

i>j,

тогда

E(x)=xi(l

+xt-i)

=х* (1

+х1),

где l = i—/. Так как

при

любом

1^=0

полином

1+х' де­

лится на G(x) = \+x,

то

E(x)

=

xi(\4-^0

=

0 п о

модулю

G(x)=\-\-x

и ошибка кратности 2 не обнаруживается.

Длина п циклического кода с минимальным

расстоя­

нием dp>3,

порождаемого заданным

полиномом G(x),

х ™ = 1 по

модулю G(x)

(3-2)

или хп

— 1 =s хп -\-

1 = 0 по модулю G (х).

При таком определении длины кода все вычеты от

Е(х)==х{( где

О ^ г ^ / г — 1 ,

по модулю G(x) будут

раз-

Xs

х3^\-\-х

по модулю

G (х) =

1 +

х -f- л:3

х* =

х-\-х2

Xs з= 1 + X -f- х2

х*^\+х*

л : 7 = л

Таким

образом, полином G(x)

= \+x+xa

порождает

циклический код с минимальным

расстоянием d = 3

дли­

ной п=7

разрядов.

хп+\

Из изложенного следует, что если полином

раскладывается на р, неприводимых1

полиномов

(это

x»

+

\=G,

(x)Gt(x)...GiL(x)

и если

все

Gi(x)

различны, то

можно получить

2^

раз­

личных

полиномов

G(x),

порождающих

код

длиной

п

с минимальным

расстоянием

rf>3.

Таким образом, циклический код полностью описыва­

ется порождающим

полиномом

G(x),

который

делит

хп+):

xn

+ \ =

G(x)H(x).

Пусть полином

Н(х)

имеет

степень

к,

тогда

G(x)

—

степень

г—п—к.

кодовое слово А (х)

Так

как

любое

должно

делиться

на

G(x),

то

A(x)

=

V(x)G(x),

где

V(х)

— частное

от

деления А(х)

на

G(x).

Это

со­

отношение описывает

процесс

кодирования,

в

соответ­

ствии с

которым

исходные

слова

V —

(v0,

у,

1 Полином

А (л.)

выше нулевой

степени

называется

неприводи­

мым, если А(х)

ие может

быть разложен в

произведение двух поли­

номов меньшей степени.

длиной

/г

разрядов, интерпретируемые

как

полиномы

V(x) =

^,

V{XI, умножаются на G(x).

При

этом k — ко-

г=о

который состоит в следующем. Рассмотрим

произведение

кодового полинома А(х)

на Н(х):

А (х) Н{х)

= V[(x) G (х)?±±

= V (х) (х-

- f 1) =з О

по модулю

G(x).

Отсюда следует, что коду принадлежат те и только те

полиномы А(х),

для которых выполняется сравнение

А(х)Н(х)=0

по модулю

+

где Н(х) —проверочный

полином.

выбрать

G(x),

xG(x),

хп->-Ю(х),

где

G(x)=gQ+

+ g i X i +

. . . +grxr

— порождающий

полином

степени г.

Тогда порождающая матрица G циклического неразде­

лимого кода имеет

вид:

G

(х)

.

-gr

0 0 .

. 0

xG

(х)

=

Ogo •

• £ r - l g r 0 .

. 0

xri-r-lQ(xy

0 0

• • gr

Линейная независимость указанных полиномов сле-

ует из того, что

п—г— I

ГС—г—

1

2 biXfG(x)

= G(x)

S biX* =

G(x)B(x).

/=0

i-0

5 - 2 3 6

65

гать, что коэффициенты кодового полинома

А ( х )

=

аа +

+ diX+ ...

-\-ап-&п~1

при 1, х,

..., xh~l

являются

инфор­

мационными

символами, а при xh,

xk+i,

...,

xn~l — конт­

рольными.

Тогда для

кодового слова,

соответствующего

иифор-

ft-i

мационному

полиному

У ( А ' ) = ^ ] vtx',

должно выполняться

сравнение

/

=0

A(x)

=

V(x)-\-x"R(x)=sO

по

модулю

G(x),

где ^ ( л " ) =

2 rk+lx'-

соответствует

контрольным

сим-

;=о

ния контрольных

символов

R(x)~—x-h

V(x) = —xn-hV(x)

по модулю

G(x)

или в случае полиномов над двоичным полем

R(x)

= x-ty(x)

по

модулю G(x).

(3-3)

G(x), i = 0, 1

k — l

G = | | i f c R | | .

(З-4 )

где R —подматрица,

/-я строка которой состоит из ко­

эффициентов полинома

Rj-i(x).

Например,

полипом

G (х) = 1+х2+х3

порождает циклический

(7,4)-код. Тогда

#о М = х3 =

1 +

х=;

Я, (х) = х* =

1 +

х + х г ;

модулю G (х);

R2

(х) = х* =

по

1 +

х;

R3

( х ) = х 6 = х + х 2