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

циклических

кодов.

Теорема

6.5. Для

любых

значений е

и t существует цикличе­

ский код длины я = 2 е — 1 , исправляющий

все ошибки кратности t

и менее и содержащий не более et проверочных элементов.

Рассмотрим пример практического использования этой тео­

ремы. Найдем циклические

коды

для е = 5 (я = 31), исправляю­

щие ошибки

кратности t=\,

2, 3. Определим количество избы­

точных элементов по заданным значениям t:

t = 1,

я — k = 5-1 = 5;

t =

2,

n —

k - 5 - 2

= 10;

t =

3,

n —

k = 5-3

= 15.

корректирующими

свойствами. Построение

же кодов,

действи­

тельно обладающих этими свойствами, обеспечивается

правиль­

ным выбором порождающего многочлена.

Следующая теорема устанавливает связь между порождаю­

щим многочленом и минимальным кодовым

расстоянием.

Теорема

6.6. Если среди корней порождающего

многочлена

циклического (я,

k)-кода

имеются корни

вида $т°,

fym°+1,

p W

o + d ~ 2 , то минимальное

кодовое расстояние этого

кода равно

по

меньшей

мере

d. В

данной теореме используется

доказан­

корней

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

многочлена

как

степеней

некоторого

числа

р.

6.6.5. Выбор

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

многочлена

для

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

кода

Порождающий

многочлен

для

(я,

я — 1 ) - к о д о в .

Одним

из

возможных

циклических кодов

длины 7 является (7,6) -код

с

g (х)

=

1 +

х.

Покажем,

что этот

код

образуется

на

основе

проверки на

четность всех

информационных элементов

кодо­

вой комбинации. Для этого найдем

проверочный

многочлен

п{х)

и

построим

проверочную

матрицу.

Определим

п(х)

=

=

(X7

+

1)/(1 +Х)

= 1 +X

+ X2

+ X* +

Xi

+

XF-' + X«

И

Н(7,в)

=

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

коде

проверочным

с о ­

отношением

охвачены

все

элементы

кодовой

комбинации.

В общем случае для (я,

я — 1 ) - к о д а

при

любом

значении я

проверочный

многочлен

находится

как

h (х)

= (хп

+ 1)/(1 +

х).

Так как двучлены хп +

1 и

1 + х

имеют общий

корень

х=1,

то х" + 1 делится без остатка на

1 +

х

и

частным

от

деления

всегда является многочлен вида 1 + х

+

хг

+ . . .

+

хп~2

+

хп~х~

Итак, многочлен

вида 1 + х

порождает

(п,

п-~ 1) - код с

про­

веркой на четность по всем элементам.

Порождающий

многочлен

для общего

случая. Теорема

6.6

циклического кода и по его корням

определить корректирующие

свойства этого кода.

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

g(x) =

1 + х + х3

(7,4)-кода, рас­

смотренного выше, имеет своими корнями

(З, Р2, р

4 . Требуется

определить кор­

ректирующие свойсіва этого кода.

П р и м е р .

Дано разложение х 1 5 + !

на

неприводимые

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

указаны корнл этих сомножителей как степени некоторого корня р.

Сомножитель

Степень

сомножителя

Корни

=

\ + х

1

315

= 1

=

1+

х + х<

4

32,

3*,

3 »

/ з М =

1 +

х + хї + х3

+ х*

4

р .

36,

З9, З1 2

ГЛх) =

1 + х

+

х2

2

310

h(x)

=

1 + хз

-\- X*

4

87,

з1 1 ,

з1 3 ,

3"

Требуется

выбрать порождающий многочлен для кода Хэмминга

(15,11) и

для

(15,7)-кода.

Для (15,П)-кода Хэмминга порождающий

многочлен должен иметь сте-

лень 4. Двучлен *| 5

+1 имеет своими сомножителями три многочлена степени. 4:

li(x),

h(x), fs(x').

Многочлен fa{x) имеет две последовательные степени корней

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

гарантирует dMiiH

= 3.

Многочлен }з(х)

не имеет по­

следовательно, гарантирует rfMHH = 3. Итак, для циклического кода Хэмминга:

(15.11) в качестве порождающего многочлена следует выбрать U{x)

или }s(x),.

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

!з(х).

Для (15.7)-кода

порождающий імногочлен должен иметь

степень 8. Мно­

гочлен такой степени можно получить тремя способами: /г(х)

}з(х), h(x) fs(x)

или /з (х)/ь (х). Естественно, желательно выбрать такой многочлен

который

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

многочле­

нов показывает, что fi(x)

їз(х)

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

Р'і $2 , р3 , Р4 и гарантирует rfMllH

=

5; fa(x) f5(x) имеет только две

последова­

тельные степени Р', Р2

или

Р7

, Р8

или З1 3 , Зі4, т. е. гарантирует

dum = 3;

h(x)

fs(x)

имеет четыре

последовательные степени Р " ,

Р 1 2 ,

Р 1 3 , Р 1 4 и

гаранти­

рует

rfMIW

= 5. Итак, для

(15,7)-кода

в качестве

g(x)

целесообразно

выбрать

h(x)

h(x)

или /З(А-) / 5 (х)

и не следует

выбирать

f2(x)

fs{x).

П р и м е р .

Рассмотрим

проверочную

матрицу

(7,3)-кода

с

g{x)

=

= (1 +

х)

(1 + х

-г х3).

Проверочный

многочлен

для

этого

кода

h(x)

=

1 +

4- х 2 +

х'6

и матрица проверок

имеет

вид:

"0

0

0

1

1

0

1

I f

0

0

1 1 0

1 0

( 7 ' 3 ) ~

0 1 1 0

1 0 0

1

1

О

1

о

о

0_

Сложив

1, 2

и 4-ю

строки

и записав

результат вместо 4-й

строки,

получим

проверочную

матрицу

в следующем

виде:

0

0

1

Г О

1

н(7,3)

0

1 1 0

1 0

1

і

о

і о

о ;

|_1

1 1

1

1 1 1

4-й степени на

1 + х . Многочлен

g(x)

=-(1 +х)

(1 + х + х4)

имеет

среди

корней

р°,

р1 , р2 . Здесь

m 0

= 0,

m0 + d-2

= 2,

т. е. й ш ш = А.

Если

взять

g(x)

= (1+х) (1+х

+ х2+х3

+ х*),

то

число

подряд

идущих корней не увеличивается

по сравнению с g(х) = (1 + х +

+ х2 + х3+х4)

и а,Мин = 2.