Алгоритм получения разрешенной кодовой комбинации циклического кода из комбинации простого кода

Пусть задан полином P(x) = ar−1 xr + ar−2 xr−1 + … + 1, определяющий корректирующую способность кода и число проверочных разрядов r, а также исходная комбинация простого k-элементного кода в виде многочлена Ak−1(x).

Требуется определить разрешенную кодовую комбинацию циклического кода (n, k).

1. Умножаем многочлен исходной кодовой комбинации на xr:

Ak−1(x) · xr

2. Определяем проверочные разряды, дополняющие исходную информационную комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином:

Ak−1(x) · xr ⁄ Pr(x) ⇒ R(x)

3. Окончательно разрешенная кодовая комбинация циклического кода определится так:

An−1(x) = Ak−1(x) · xr + R(x)

Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Пример. Пусть требуется закодировать комбинацию вида 1101, что соответствует A(х) = х3 + х2 + 1.

Определяем число контрольных символов r = 3. Из таблицы возьмем многочлен P(х) = х3 + х + 1, т. е. 1011.

Умножим A(х) на хr:

A(x) · xr = (x3 + x2 + 1) · x3 = x6 + x5 + x3 ⇒ 11010000

Разделим полученное произведение на образующий полином g(х):

A(x) · xr ⁄ P(x) = (x6 + x5 + x3) ⁄ (х3 + х + 1) = х3 + х2 + х + 1 + 1 ⁄ (х3 + х + 1) ⇒ 1111 + 001 ⁄ 1011

При делении необходимо учитывать, что вычитание производится по модулю 2. Остаток суммируем с h(х) · хr. В результате получим закодированное сообщение:

F(x) = (x3 + x2 + 1) · (x3 + x + 1) = (x3 + x2 + 1) · x3 + 1 ⇒ 1101001

В полученной кодовой комбинации циклического кода информационные символы A(х) = 1101, а контрольные R(х) = 001. Закодированное сообщение делится на образующий полином без остатка.

Алгоритм определения ошибки

Пусть имеем n-элементные комбинации (n = k + r) тогда:

1. Получаем остаток от деления Е(х) соответствующего ошибке в старшем разряде [1000000000], на порождающий полином Pr(x):

E1(x) ⁄ Pr(x) = R0(x)

2. Делим полученный полином Н(х) на Pr(x) и получаем текущий остаток R(x).

3. Сравниваем R0(x) и R(x).

o Если они равны, то ошибка произошла в старшем разряде.

o Если нет, то увеличиваем степень принятого полинома на x и снова проводим деления:

H(x) · x ⁄ Pr(x) = R(x)

4. Опять сравниваем полученный остаток с R0(x).

o Если они равны, то ошибки во втором разряде.

o Если нет, то умножаем Н(х) · х2 и повторяем эти операции до тех пор, пока R(x) не будет равен R0(x).

Ошибка будет в разряде, соответствующем числу, на которое повышена степень Н(х), плюс один.

Например: H(x) · x3 ⁄ Pr(x) = R0(x)

БЧХ

Французский ученый А. Хоквингем (1959 г.) и американцы Р. К. Боуз и Д. К. Рой-Чоудхури (1960 г.) нашли большой класс кодов, обеспечивающий произвольное минимальное кодовое расстояние dmin ≥ 5. Они получили название БЧХ (Боуза-Чоудхури-Хоквингема). Порождающие полиномы для таких кодов в зависимости от предъявляемых к ним требований, можно найти [7] в таблице:

k n m s dmin Порождающий полином
Символическая запись Запись в виде полинома

Где n — общее число элементов, m — число информационных элементов, k — число избыточных элементов (n = m + k).

Процедура построения кода БЧХ по заданным M и dmin:

1. по dmin найти значение, при котором обеспечивается необходимое число информационных элементов mmin:

1. по dmin найти значение, при котором обеспечивается необходимое число информационных элементов m при минимальной избыточности kmin;

return false">ссылка скрыта

2. найти в таблице соответствующий порождающий полином;

3. если dmin четное, умножить найденный полином на (x + 1);

4. если mтабл >> mзадан, то можно перейти к укороченному циклическому коду, вычеркивая в порождающей матрице исходного кода с параметрами mтабл, kmin (mтабл − mзадан) столбцов слева и столько же строк сверху.