Составители:
Рубрика:
20
1.7. Циклические коды Боуза –Чоудхури –Хоквингема
Коды Боуза – Чоудхури - Хоквингема (БЧХ) представляют собой обширный класс
кодов, способных исправлять несколько ошибок и занимающих заметное место в тео-
рии и практике кодирования. Интерес к кодам БЧХ определяется по меньшей мере
тремя следующими обстоятельствами:
1) среди кодов БЧХ при небольших длинах существуют хорошие (но, как
правило, не лучшие из известных) коды;
2) известны относительно простые и конструктивные методы их кодирования и
декодирования;
3) полное понимание построения кодов БЧХ является наилучшей отправной
точкой для изучения многих других классов кодов.
Коды БЧХ независимо открыли Хоквингем (1959) и Боуз и Рой-Чоудхури (1960),
которые доказали ряд теорем, устанавливающих существование таких ЦК, у которых
минимизируется число проверочных символов, а также указывающих пути нахождения
порождающих полиномов для этих кодов.
Корректирующие свойства ЦК могут быть определены на основании следую-
щей теоремы: для любых значений m и g
и
существует ЦК длиной n = 2
m
-1, исправ-
ляющий все ошибки кратности g
и
и менее (g
и
< m) и содержащий не более n – k ≤ mg
и
проверочных символов. Так, например, при n = 15, m= 4 и различных g
и
число прове-
рочных символов будет равно: g
и
=1, n – k = m·g
и
= 4·1= 4; g
и
= 2, m·g
и
= 4·2 = 8; g
и
= 3,
m·g
и
= 4·3 = 12. Соответствующие коды (n, k) будут (15,11), (15,7), (15,3). Напомним, что
минимальное кодовое расстояние d
min
= 2 · g
и
+1 и применительно к ЦК оно чаще называ-
ется конструктивным расстоянием. Если величины g
и
или d выбрать слишком больши-
ми, то получившийся в результате код будет тривиальным — в нём будет лишь один ли-
бо (при r > n) ни одного информационного символа.
В табл. 3 даны параметры и порождающие полиномы некоторых кодов БЧХ. По-
линомы приведены в восьмеричной форме записи, старшая степень расположена слева.
Например, коду (15, 7) соответствуют двоичное представление 111010001 и мно-
гочлен G(X) = X
8
+ Х
7
+ Х
6
+ X
4
+1. Подробные таблицы порождающих полиномов цик-
лических кодов БЧХ приведены в [6].
Таблица 3
mn k rg
и
G(X) – mod 8 m n k r g
и
G(X) – mod 8
3
4
5
6
7
15
31
63
4
11
7
26
21
16
11
57
51
45
39
36
3
4
8
5
10
15
20
6
12
18
24
27
1
1
2
1
2
3
5
1
2
3
4
5
13
23
721
45
3551
107657
5423325
103
12471
1701317
166623567
1033500423
7
8
127
255
120
113
106
99
92
247
239
231
223
215
7
14
21
28
35
8
16
24
32
40
1
2
3
4
5
1
2
3
4
5
211
41567
11554743
3447023271
624730022327
435
267543
156720665
75626641375
23157564726421
Коды БЧХ с длиной 2
m
-1 называют примитивными кодами БЧХ. К ним, в част-
ности, относятся классические коды Хемминга, исправляющие однократные ошибки. К
кодам БЧХ относятся также коды, длина n которых является делителем 2
m
-1. Напри-
мер код Голея (23, 12, 7) (см. подраздел 1.4) также принадлежит классу кодов БЧХ, по-
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
