Помехоустойчивые циклические коды. Никитин Г.И. - 15 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

15
Занимаясь поиском плотноупакованных кодов ("кодов без потерь"), М. Голей заме-
тил (опубликовано в 1949 году), что
,CCCC
113
23
2
23
1
23
0
23
21771253231 =+++=+++
а это означало, что может существовать плотноупакованный двоичный (23,12) код,
удовлетворяющий условию (4.20), исправляющий все кодовые комбинации с тремя
или менее ошибками. Он показал, что такой код действительно существует и в даль-
нейшем этот код получил его имя.
Код Голея относится к классу ЦК с порождающими двойственными (дуальными)
полиномами (4.9):
.XXXXXX)X(G
~
;XXXXXX)X(G
1
1
567911
24561011
++++++=
++++++=
(4.22)
Простым вычислением проверяется, что
,)X(G
~
)X(G)1X(1X
23
⋅⋅+=+
в связи с чем в качестве порождающего полинома ЦК Голея (23, 12) можно использо-
вать как G(X), так и G̃(X).
Код Голея, гарантированно исправляющий ошибки с кратностью не менее трёх
включительно, обладает минимальным кодовым расстоянием, d
min
=2g
и
+1 = 7, что, как
правило, указывается в маркировке кода (23, 12, 7). Добавление к этому коду общей
проверки на чётность по всем позициям увеличивает на единицу как общую длину кода,
так и минимальное кодовое расстояние d
min
= 8.
Расширенный код Голея, имеющий маркировку (24, 12, 8), состоит из 12 ин-
формационных символов и 12 проверочных, т. е. представляет собой код, обладающий
скоростью 1/2 и избыточностью, также равной 1/2.
Обратим внимание на то, что плотноупакованные коды Хемминга и Голея — цик-
лические, которые принадлежат классу двоичных линейных кодов. Общим для линей-
ных двоичных кодов является наличие, в качестве разрешённого, нулевого кодового
слова 000...00, что приводит к тому, что минимальный вес w
min
ненулевого разрешённо-
го кодового слова равен минимальному кодовому расстоянию d
min
(4.13).
В общем случае вес кодовых комбинаций может принимать различные значения,
и совокупность чисел кодовых комбинаций с постоянным весом N
w
определяют как рас-
пределение весов кода или как спектр весов кода. Распределение весов в коде Голея
(23, 12, 7) следующее:
N
0
= N
23
= 1; N
7
= N
16
= 253; N
8
= N
15
= 506; N
11
= N
12
= 1288,
а в расширенном коде Голея -
N
0
= N
24
= 1; N
8
= N
16
= 759; N
12
= 2576. (4.23)
Кодовые слова с весом 12, 8 и 16, выделенные из кода (24,12,8). образуют КПВ
максимальной мощности.
К сожалению, кроме кодов Хемминга (d
min
= 3, g
и
=1) и кода Голея (23, 12, 7)
пока не найдено других совершенных, плотноупакованных кодов, число синдромов у
которых точно соответствует требуемому значению для гарантированного исправления
ошибок заданной кратности.
1.5. Построение порождающих и проверочных матриц циклических кодов
Наряду с полиномиальным способом задания кода, структуру построения кода
можно определить с помощью матричного представления. При этом в ряде случаев
проще реализуется построение кодирующих и декодирующих устройств ЦК.

Страницы