Файл: Теория и техника передачи данных и телеграфия учебник..pdf

ния циклических (п, к)-кодов

используют представление кодо­

вых комбинаций в виде многочленов,

степень которых не превы­

шает п—\, а коэффициентами

являются двоичные элементы «0»

и «1»

многочленов степени « — 1

и менее, делящихся

на некоторый

многочлен g(х)

степени

n—k,

являющийся

сомножителем

ности: для любой кодовой комбинации

V — (vn,

v},...,

vn^)

циклический

сдвиг на единицу

РЛЄВО

V" =

v2,•

vn}

или

вправо

V"

=

(vn-\,

v0,...,

v„-2)

также

является

кодовой:

комбинацией.

П р и м е р .

Изиестно разложение х7 4

1 на

неприводимые сомножители:

Xі

4-

1 =

(1 + л-) (1

+

х +х3)

(1

+ х2

+ х3).

Найти

все циклические

(п,

6)-коды-

с

п =

7,

котооые можно построить на основе данного разложения.

По определению циклического кода любой делитель Xі + 1 является по­

рождающим многочленом

циклического

кода

длины 7.

Возможные

делители-

XІ

+

1 (порождающие многочлены)

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

им

коды

сведены в-

таблицу.

Делитель

Xі

+

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

многочлен

кода

Код

(-*")

=

14--*

(7.6)

=

1 + X +

X3

(7.4)

gj

(х) =

1 -f X2

+

X3

(7,4)

g4 (X) =

(1

T x) (1

-f

x + x3) =

1 +

л? +

x3 + XІ

(7,3)

g'Ax) =

(1

+ x) (1

4-

X* + x3) =

1 +

x +

Xі

+ x*

(7.3)

gv,(x)

= (! + x + x3)(\ +x* + x3) = l 4- x + X і

+ x3

+ x< + x~°+x«

(7.1)

g(x)

П р и м е р .

Для циклического (7,4)-кода

с

порождающим

многочленом

= 1 -f х +

Xі

построить

порождающую

матрицу. Находим:

1 x x"-i~

1 1 0 1 0 0 0~

х

g(x)

X +ХЇ

+ Xі

0

I 1

0

1

0 0

Jfig

(X)

xn- -f x*

-f X'>

0

0 1

1

0

1 0

_x3g (x)_

XiJ^Xl

-f Xs

0

0 0

1

1

0 і

При задании циклических кодов следует учитывать специ­

фику действий

над многочленами

по сравнению с векторами и,

в

частности

тот факт,

что умножение

многочленов

не совпа­

вектор

(а 0 ,

а , , . . . ,

а„ _ і)

и

соответствующий

ему

многочлен

а

(х)

= а0 +

ахх

+

..

. +

ап^ххп-{

,

а также

вектор

(b0,

Ь и . . . ,

bn-i)

и

соответствующий

ему

многочлен

b (х) = Ь0

+

Ьлх

+ . . .

+ bn-\xn~l.

Будем

считать

многочлены

а{х)

и b(х)

орто­

гональными, если выполняется условие а(х)Ь(х)

= 0.

Коэф­

фициент

при

х'

в

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

с (х)

— а (х)

b (х)

равен с} =

=

а0

bj + a ^ y - i +

. . . +

a.jb0

+

a1+xbn-X

+ . . . +an-\b}+x.

Слагае­

мые,содержащие

0 / + i , . . . , а„-\,

появляются

вследствие

сущест­

вования слагаемых в произведении, которые содержат хп+'.

Так

как

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

приводится

по модулю х" -+- 1, то

+

1 = 0 ,

т. е. хп

— 1 и xn+J

= xL

Равенство

для Cj можно

представить

в

виде

скалярного

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

Cj =

( а 0 ,

а , , . . . ,

а„_і)

Ь0, Ь „ _ і , . . . ,

bj+i). В

этом

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

первый век­

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

а

(х),

а

второй

вектор

содержит

коэффици­

енты

b (х),

расположенные

в

обратном

порядке

и сдвинутые

циклически

на j -+-1

элемент

вправо.

Таким образом, если

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

а{х)Ь{х)

равно

нулю,

то

вектор,

соответствующий

многочлену

а(х),

ортогонален

вектору,

соответствующему многочлену

b (х),

компоненты ко­

торого расположены в обратном порядке,

и, кроме

того,

каж­

дому

циклическому

сдвигу

этого

вектора.

Верно

также

и обратное утверждение. Если

вектор

(а 0 , а,,...,

а„_і) орто­

гонален

вектору

(bn-i, & „ _ 2 , . . . ,

Ь0) и

каждому

циклическому

сдвигу этого вектора, то а(х)Ь(х)

=

0.

Учитывая

данную

Специфику,

необходимо

при матричном описании

циклического

кода элементы матрицы проверок или порождающей

матрицы

записывать в обратном порядке. В этом случае

будет

выпол­

нено условие G ( n

> k) Н(и, k) =

0.

П р и м е р .

Построить матрицу

проверок

для

циклического

(7,4) -кода

из предыдущего примера. Для построения

матрицы

проверок

находим про-

х7

+ 1

h

(х)

-

!

• х

х*

х*

1

1

1

0

1

(I

0;

х h

(х)

х

-~ Xі-г

X* -Ь х:'

— О I

I

1 0

1

0;

х2/г

(х) =

х2

-Ь л;:'

х<

f х л

= 0

0

1

1

1

0

1.

4(7,4) в

обратной последовательности:

0

0

1 0

1

1

Г

Н(7,4)

0

1 0

1 1 1 0

1 0

1 1 1 0

0

В

полученной матрице проверок в качестве столбцов записаны все семь

ненулевых

последовательностей длины

3. Следовательно, данный код явля­

ется кодом Хэмминга.

6.6.3.

Каноническая

форма

порождающей

и проверочной

матриц

Условимся

в кодовой

комбинации

циклического

(/г,

k)-кода

первые n

— k

элементов,

т. е. коэффициенты

при Л"°,

х\

х 2 , . . . ,

xn-k-i

^ использоБать в качестве

проверочных

элементов, а по­

следние k

элементов, т. е. коэффициенты при

хп-

в

качестве

информационных

(рис. 6.7).

Такое

разме­

щение информационных и проверочных

элементов

обусловлено

ройств

циклических

кодов.

о

_/

п-к

п-г

1Ы

X

X ' '

• X X X

• • • X X

избыточные

(Інірормааионньїе

м ементы

зле

менты

r*L (х)

ас

fx)

• х а ' к

Рис. 6.7.

Методика формирования кодовой комбинации, соответству­

ющей

данной

структуре,

заключается

в

следующем.

Пусть

at(x)

есть

многочлен

степени k — 1, соответствующий

комби­

нации простого ^-элементного кода,

которую

необходимо за^

кодировать

циклическим

(п,

k)-кодом.

В

комбинации

цикли­

ческого ( « ,

&)-кода

данную

^-элементную

комбинацию

необ­

этого многочлен а,(х) следует

умножить

на хп~к.

В резуль­

тате получим многочлен xn~kai (х),

степень

которого

р а в н а я — 1 .

ции на

g(x).

В общем случае

при

делении

хп~"аі(х)

на g

(х)

получается

частное qt

(х)

степени

k — 1 и остаток,

степень

ко­

торого

не превышает

n — k—

1. Результат

деления

представим

в виде

. ., .

хп-*а,

(х) =

g (х) qt

{х) + г І

(х).

Рассмотрение многочлена rL (х)

4- xn~kai

(х)

показывает,

что

коэффициенты при х°, Xі,

х2,.

t-n-k

— X являются

коэффици­

ентами остатка rt{x),

а

коэффициенты

при

степенях

хп~к,

х"~к+*,...,

хп~1 — элементами

первичной

кодовой

комбина­

ции

aL{x).

С

другой

стороны,

rt(x)

І - xn^kal

(х)

=

g

(х)

qt{x),

т. е. многочлен rt (х) + хп~ка1{х)

делится

на g

(х)

без

остатка.

Итак,

ri

(х)

-j- xn~kal

(х)

и

есть

искомая

кодовая

комбинация

циклического

(п,

к)-кода.

Теперь

можно

записать

порождающую

матрицу

цикличес­

кого

(п,

к)

-кода

в канонической

форме:

G(n, k) = [ Rfcx(n-ft)lfc],

где

\k

— единичная

матрица

размеров

ky^k;

Rkx(n-k) — матрица

из k

строк

и п — k столбцов,

/-я строка

которой

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

остатку

от

деления

х!+п~к~х

на

g

(х).

Матрица

проверок

в

канонической

форме

Н<п, *,

строится

на основании матрицы

G ( n , k ) ;

Н(л,fc)= [l(n-fe)R*X(n-*)]-

П р и м е р .

Построить

порождающую матрицу

и

матрицу

проверок

в канонической форме для циклического (7,4)-кода

с порождающим много­

членом

g

(х)

=

I -j- х

+

х3.

Находим остатки от деления х>

иа g (х)

и записываем

в форме равен­

ства

xn~kai

(х) =

g(x)qi(x)

+

П

(x).

x°

=

g(x)-0

1 0

0

x=g(x)0

0

1 0

x*=g(x)-0

xi

0

0 1

xi

=

g(x)-l

+

1 +

x

1 1 0

H (7,4)

x*=g(x)-x

+

x- • X*

0

1 1

M X 3

X° = g (X)

(1 +

Jfl)

+

1 +x

-

x*

1

1 1

x* =

g(x)

(1 +X

+

X*)

1

+

x4-

1

0 1

Окончательно получаем

1

1

0

1

0

0

0"

O i l

0 1 0 0

° ( 7 , 4 )

-

1 1 1

0 0 1 0

J

0

1

о 0 0 1_

Из рассмотренного примера видно, что проверочная мат­

рица

Н(„, к)

циклического

(л,

k)-кода

содержит

в

качестве

столбцов остатки от деления л:0 ,

х,

х

2 , х п ~

х

на

порожда­

ющий

многочлен.

6.6.4. Корректирующие

свойства

циклических

(п,

к)-кодов

Определение корректирующих свойств циклических (п, k) -ко­

дов

сводится к нахождению

минимального

кодового

расстояния