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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 159

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

отсюда получаем

порождающую

матрицу

 

 

 

1

0

0

0

 

1 0

1

 

G

 

0

1 0

0

 

1 1 1

 

 

 

 

 

 

 

 

 

 

 

 

0

0

1 0

1

1 0

 

 

 

0

0

0

1 0

1 1

Контрольная матрица разделимого циклического кода

имеет вид:

 

 

 

 

 

 

 

 

 

 

 

H =

 

| | R t I n - f c | | -

Данную матрицу можно записать следующим

образом:

 

 

 

 

 

 

 

 

 

H = |U«\ -V+ i

-?V - 1

1,

X,

 

 

 

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

 

, х

 

 

 

 

 

 

имея в виду, что вектор-столбцами Н являются располо­ женные в порядке возрастания их индекса коэффициен­ ты вычетов по модулю G(x). Поэтому контрольную мат­ рицу циклического кода иногда записывают в виде

Н:

1, х, хй,..., хп~1\\

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

(3 5)

3-2. НЕКОТОРЫЕ КЛАССЫ ЦИКЛИЧЕСКИХ КОДОВ

Среди циклических кодов существует аналог рассмот­ ренных в тл. 2 кодов Хэмминга с минимальным расстояни­ ем d—З. Эти коды порождаются так называемыми при­ митивными1 полиномами. Смысл использования прими­ тивных полиномов можно пояснить следующим об­ разом.

Пусть G(x) — некоторый полином степени

/\ Длину

кода п, порождаемого данным полиномом G(x),

опреде­

ляем делением xi на G(x)

при последовательном

увеличе­

нии степени I до тех пор,

пока не будет выполнено срав­

нение (3-2). Найденное значение степени п, удовлетво^ ряющее сравнению (3-2), равно длине порождаемого

кода. Значение п равно количеству различных

ненулевых

остатков, которые получаются при делении xi

на

 

G(x)

(при дальнейшем увеличении степени эти остатки

перио-

1 Примитивным называется неприводимый полином, корнем ко­

торого является примитивный элемент поля Галуа GF(2r),

где

г —

степень полинома. Элемент поля GF(2r) является примитивным,

если

его порядок равен 2Г —1.

 

 

 

5*

 

 

67

дически повторяются). Так как степень G(x) равна г, то количество различных ненулевых остатков не может пре­ восходить величины 2'"—1, и если п — 2г—1, то G(x) яв­ ляется примитивным полиномом. Таким образом, исполь­ зование в качестве G(x) примитивного полинома позво­ ляет получить максимально возможную длину п корректи­ рующего кода с d=3 при данном количестве контроль­ ных разрядов /-.

Таблицу

неприводимых полиномов до 34-й степени

с указанием

примитивных можно найти в монографии

[Л. 8]. В табл. 3-1 приведены параметры и порождающие полиномы циклических кодов Хэмминга длиной п не бо­

лее 2 047

разрядов.

Примитивные полиномы

 

одинаковой

степени

порождают

 

эквивалентные

коды. В

табл.

3-1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Т а б л и ц а

 

3-1

(я, А)-код с ми­

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

нимальным

рас­

 

 

 

 

ПорождлющиН полином С (.v)

 

 

 

 

стоянием

</=3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(7.

4)

 

 

13

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(15,

 

11)

 

23

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(31,

 

26)

 

45,

75,

67

 

 

 

 

 

 

 

 

 

 

 

(63,

 

57)

 

103,

147,

155

 

 

 

 

 

 

 

 

 

 

(127,

 

120)

 

211,

217,

235,

367,

277,

325,

203,

313,

345

 

 

(255,

 

247)

 

435,

551,

747,

453,

545,

543,

537,

703

 

 

 

(511,

 

502)

 

1021 ,

1131 ,

1461,

1423,

1055,

1167,

1541,

1333,

 

 

 

 

 

1605

,

1751 ,

1743,

1617,

1553,

1157,

1715,

1563,

 

 

 

 

 

1713

,

1175

 

1725,

1225,

1275,

1773,

 

1425, 1267

(1023,

1013)

2011

,

2415

 

3771,

2157,

3515,

2773,

2033,

2443,

 

 

 

 

 

2461

,

3023

 

3543,

2745,

2431,

3177,

3525,

2617,

 

 

 

 

 

3471

,

3323

 

3507,

3623,

2707,

2327,

3265,

2055,

 

 

 

 

 

3575

,

3171 , 2047, 3025, 3337,

3211

 

 

 

 

 

(2047,

2036)

4005

,

4445 ,

4215,

4055,

6015

 

 

 

 

 

 

 

П р н м е ч а н н е. Коэффициенты

полиномов

О(х)

записи/ ы в

восьмеричной

сис­

теме. Например, 23=01001 \—х* +

х+1.

 

 

 

 

 

 

 

 

 

 

 

представлена только половина примитивных полиномов соответствующей степени. Примитивными являются поли­ номы, двойственные к указанным. Двойственный поли­

ном

G*(x)=xrG(l/x)

порождает

эквивалентный

код.

Поэтому, например,

(7, 4) -код порождается

полиномами

13 и 15, (15, 11) -код — полиномами 23 и 31 и т. д.

 

Наилучшими из известных циклических кодов для

исправления независимых

ошибок

являются

коды.

Боуза — Чоудхури — Хоквинхема

(БЧХ). В

этих

кодах

число

контрольных

разрядов

r<^rnt

при

длине

кода

68

п = 2т—1, где / — количество

исправляемых

ошибок.

Теория построения этого класса

кодов здесь

не излага­

ется, в табл. 3-2 приведены параметры и порождающие

полиномы .коротких кодов БЧХ (коэффициенты

полино­

мов записаны

в восьмеричной

системе,

см. примечание

к табл.

3-1).

 

 

 

 

 

 

 

 

 

 

 

 

Т а б л и ц а 3-2

(л,

й)-код

Минимальное

Порождающпи'полнном 0(х)

расстояние d

(15,7)

 

721

 

 

 

 

(21,12)

 

1467,

1663

 

 

 

(31,21)

 

2303,

3557,

3551

11253

(63,51)

 

16223,

12471,

11625,

(127,

113)

 

41567

 

 

 

 

К циклическим кодам, предназначенным для обнару­ жения и исправления вспышек ошибок, относятся коды Файра. Порождающий полином этого класса кодов равен произведению двух полиномов:

G(x)=P(x)(xB+-l),

где Р(х) — неприводимый полином степени т. Длина п кода, порождаемого полиномом G(x), определяется из выражения (3-2).

Пусть

л:"' = 1 по модулю Р(х),

где ni — минимальное не равное нулю число, при котором

справедливо

это сравнение.

Учитывая,

что полином

xi + \ делит

полином

х'+\

в том и только

в том случае,

если i делит /, получаем,

что длина кода, порождаемого

полиномом G(x)=P(x)

(хс+1),

равна:

 

 

 

п=[пи

с],

 

где квадратными скобками обозначено наименьшее об­

щее кратное

чисел щ и с. Количество контрольных раз­

рядов равно

степени полинома G(x),

т. е. г=т

+ с. Дан­

ный код позволяет исправить любую одиночную

вспышку

ошибок длиной / или менее и одновременно

обнаружить

любую вторую

вспышку ошибок

длиной

t^l,

если

l + t—l<g:c и

m^l.

При синтезе данного класса

кодов

можно пользоваться таблицей неприводимых полиномов [Л. 8]. В частности, если в качестве Р(х) выбирать гарими-

69

тивный полином

степени

т,

у которого

ni—2m—1,

то

можно для

m ^ l l воспользоваться табл. 3-1.

 

 

Например, пусть требуется найти полином

G(x),

порождающий

код длиной

10 ООО разрядов, который допускает исправление вспы­

шек ошибок

длиной

/^:5 разрядов. Исходя из

условий

 

 

 

с 5*2/—1=9;

 

 

 

 

 

 

Л = [«1, с],

 

 

 

 

выбираем яг=10, с=10 . Если в качество Р(х)

выбрать

примитивный

полином, например, из табл. 3-1 Л(.*)=2011,

то

« i = 2 1 0 — 1 = 1023 и

/г=[ 1023,10]= 10 230

разрядов.

Таким

образом,

искомый код

длиной

/г=10 230 разрядов,

из которых 20

являются контрольными,

порож­

дается полиномом

 

 

 

 

 

 

 

G ( X ) = (.V'° + A - ' + I ) ( * , 0 + I ) .

При необходимости можно производить укорачивание циклических кодов, которое заключается в том, что опре­ деленные символы в кодовых словах полагаются тож­ дественно равными нулю: При этом минимальное рас­ стояние d кода не изменяется, но и теперь не всегда верно, что циклический сдвиг кодового слова также яв­ ляется кодовым словом. Поэтому укороченные цикличе­

ские коды называют

псевдоциклическими.

3-3. СХЕМЫ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ

д л я

ЦИКЛИЧЕСКИХ к о д о в

Для реализации циклических кодов используются многотактные линейные схемы, именуемые часто филь­ трами или сдвигающими регистрами с обратными свя­ зями. Основными компонентами рассматриваемых схем являются: запоминающий элемент или элемент задержки D на один такт (длительность такта .равна периоду сле­ дования символов или синхронизирующих импульсов); сумматор по модулю 2.

В простейшем случае линейный фильтр имеет один

вход и один выход

и не содержит обратных связей

(рис. 3-1). В данной

схеме, кроме элементов задержки и

сумматоров по модулю 2, имеются элементы, осущест­ вляющие скалярное умножение на коэффициенты gi. При 'рассмотрении полиномов над двоичны-м полем gi — 1 обозначает наличие связи, a gi=0 — отсутствие связи.

70

Смотрите также файлы