2. 5. Коды бчх, исправляющие две ошибки

Рассмотрим класс двоичных циклических кодов, которые обнаруживают и исправляют любые t - кратные ошибки. Это так называемые коды Боуза-Чоудхури-Хоквингема ( или, кратко, коды БЧХ ).

Здесь опишем обобщение кодов Хэмминга, позволяющее исправлять две ошибки с помощью проверочной матрицы H_r кода Хэмминга H_r .

Пусть n = 2 ^r - 1 - длина кода Хэмминга, r - число проверочных символов кодовых слов H_r ,

H_r = [ 1 , 2 , 3 ,..., 2 ^r - 1]

- проверочная матрица размерности ( r  2 ^r - 1 ) кода H_r.

Построим проверочную матрицу H_r' обобщённого кода Хэмминга, исправляющего две ошибки, путём добавления ещё r строк к проверочной матрице H_r кода Хэмминга следующим образом:

1 2 3 . . . 2 ^r - 1

H_r' = f(1) f(2) f(3) . . . f(2 ^r - 1) ,

где f(i) - некоторая функция, отображающая r - мерные вектора в r - мерные вектора.

Допустим, что произошли две ошибки - на позициях i и j. Нам необходимо выбрать функцию f(i) так, чтобы декодер по синдрому S принятого слова x' мог найти i и j.

Т ак как i + j к ₁

S = H'x'^T = H_i' + H'_j = f(i) + f(j) = к ₂ ,

то для обнаружения двух ошибок необходимо декодеру решить систему уравнений:

 i + j = к ₁ ,



 f(i) + f(j) = к ₂ .

Можно проверить, что при выборе функции f(i) = i³ система имеет ровно два решения i и j.

В самом деле при f(i) = i ³ имеем:  i + j = k ₁ ,



 i³ + j³ = k ₂ ,

откуда при к ₁  0 находим, что

 i + j = k ₁ ,



 i * j = k²₁ + к ₂ / к ₁ ,

т.е. i и j являются корнями уравнения

Z ² + k ₁ Z + k²₁ + к ₂ / к ₁ = 0.

Таким образом, проверочная матрица H_r' искомого кода принимает вид:

1 2 3 . . . 2 ^r - 1

H_r' = 1 ³ 2 ³ 3 ³ . . . (2 ^r - 1) ³ ,

а его параметры - n = 2 ^r - 1 , k = n - 2 r , d = 5.

Заметим, что для операций над r - мерными векторами удобно интерпретировать каждый двоичный вектор как некоторый двоичный полином степени не больше r - 1, а сами операции выполнять над соответствующими полиномами по модулю неприводимого над GF(2) полинома М(х) степени r. Тогда результат любой операции будет полином степени не выше r - 1, и которому будет соответствовать r - мерный вектор.

В частности, при r = 3, М( х ) = х ³ + х + 1 двоичный код БЧХ длины 7, исправляющий две ошибки, имеет проверочную матрицу:

0 0 0 1 1 1 1

0 1 1 0 0 1 1

1 0 1 0 1 0 1

H_r' = 0 0 1 1 1 1 0

0 1 0 0 1 1 1

1 1 0 1 0 1 0

Здесь

 ₀  ₁  ₂  ₀х ² +  ₁х +  ₂ ,

т.е. каждому 3 -мерному вектору сопоставлен полином 3-й степени и все операции выполнены по модулю М( х ) = х ³ + х + 1 в поле GF(2).

На практике для построения проверочной матрицы H_r' кода БЧХ необходимо воспользоваться степенными представлениями элементов полей Галуа. Так, например, проверочной матрице H₃ кода H₃ соответствует матрица

H₃ = [ 1   ²  ³  ⁴  ⁵  ⁶ ] ,

а проверочной матрице H₃' кода БЧХ -

1   ²  ³  ⁴  ⁵  ⁶

H₃' = ,

1 ³  ⁶  ²  ⁵   ⁴

где   GF(2 ³) - корень уравнения  ³ +  + 1 = 0.

В общем случае можно доказать, что таким образом построенный код

БЧХ является циклическим кодом с порождающим полиномом

g ( x ) = М _ ( х ) М _ ³ ( х ) ,

где М _ ( х ) и М _ ³( х ) - минимальные полиномы элементов  и  ³ соответственно.

2.5.1. Найти степенные представления элементов поля GF(2 ⁴) и построить соответствующую проверочную матрицу кода БЧХ.

2.5.2. Определить все примитивные полиномы поля GF(2 ⁴).

2.5.3. Разработать алгоритм декодирования кодов БЧХ.

2.5.4. Доказать, что коды БЧХ являются циклическими кодами.

2.5.5. Доказать, что код БЧХ с порождающим полиномом

g ( x ) = М _ ( х ) М _ ³( х ) имеет кодовое расстояние равное 5.

2.5.6. Найти все корни полинома g ( x ) = М _ ( х ) М _ ³( х ).

2.5.7. Построить троичный код БЧХ, исправляющий две ошибки.

2.5.8. Построить двоичный код БЧХ, исправляющий более двух ошибок.

2.5.9. Определить кодовое расстояние циклического кода по порождающему полиному g ( x ).

2.5.10. Пусть g (x) имеет d корней  , ² , . . . , ^{d - 1}. Установить связь между d и минимальным расстоянием кода БЧХ с порождающим полиномом g ( x ).