Реферат: Коды Боуза-Чоудхури-Хоквингема

m £ h S.

Определим параметр h из формулы

n = 2^h -1,h = log₂ (n+1) = log₂ 32 = 5,

при этом: m £ h S = 5 × 3 = 15 ; k = n-m = 31-15 = 16 .

Таким образом, получили (31, 16)-код.

2.Определим параметры образующего полинома:

- количество минимальных многочленов, входящих в образующий

L = S = 3;

- порядок старшего минимального многочлена

r = 3S-1 = 5;

- степень образующего многочлена

b = m £ 15.

1. Выбор образующего многочлена.

Из таблицы для минимальных многочленов для кодов БЧХ ( приложение 4) из колонки 5 (т. к. l = h = 5 ) выбираем три минимальных многочлена 1, 3 и 5 (т. к. r = 5 ):

M₁ (x) =100101;

M₂ (x) =111101;

M₃ (x) =110111.

При этом

P(x) = M₁ (x) × M₂ (x) × M₃ (x) =1000111110101111=

= x¹⁵ + x¹¹ +x¹⁰ + x⁹ + x⁸ + x⁷ + x⁵ + x³ + x² +x+ 1 .

4. Строим образующую матрицу. Записываем первую строку образующей матрицы, которая состоит из образующего полинома с предшествующими нулями, при этом общая длина кодовой комбинации равна n = 31 . Остальные строки матрицы получаем в результате k-кратного циклического сдвига справа налево первой строки матрицы.

000000000000000100011111011111

G(31,16)=000000000000001000111110111110

. . .

100011111011111000000000000000

Строки образующей матрицы представляют собой 16 кодовых комбинации кода БЧХ, а остальные могут быть получены путем суммирования по модулю 2 всевозможных сочетаний строк матрицы.

Декодирование кодов БЧХ

Коды БЧХ представляют собой циклические коды и, следовательно, к ним применимы любые методы декодирования циклических кодов. Открытие кодов БЧХ привело к необходимости поиска новых алгоритмов и методов реализации кодеров и декодеров. Получены существенно лучшие алгоритмы, специально разработанные для кодов БЧХ. Это алгоритмы Питерсона, Бэрлекэмпа и др.

Рассмотрим алгоритм ПГЦ (Питерсона-Горенстейна-Цирлера). Пусть БЧХ код над полем GF(q) длины n и с конструктивным расстоянием d задается порождающим полиномом g(x), который имеет среди своих корней элементы , — целое число (например 0 или 1). Тогда каждое кодовое слово обладает тем свойством, что . Принятое слово r(x) можно записать как r(x) = c(x) + e(x), где e(x) — полином ошибок. Пусть произошло ошибок на позициях (t максимальное число исправляемых ошибок), значит , а — величины ошибок.

Можно составить j-ый синдром Sj принятого слова r(x):