Краткие теоретические сведения. Коды БЧХ, разработанные Боузом, Чоудхури и Хоквинхемом
Коды БЧХ, разработанные Боузом, Чоудхури и Хоквинхемом, позволяют обнаруживать и исправлять любое количество ошибок. Заданными величинами при кодировании являются: число ошибок s, которое следует исправить, и общее число символов, посылаемых в линию, т.е. длина слова n. Число информационных символов k и контрольных символов m, а также состав контрольных символов подлежат определению.
Методика кодирования
1. Выбор длины слова. При кодировании по методу БЧХ нельзя выбирать произвольно длину слова n. Первым ограничением является то, что слово может иметь только нечетное число символов. Необходимо, чтобы выполнялось следующее равенство:
. (17)
где h - целое число.
2. Определение кодового расстояния dmin: dmin = 2s + 1.
3. Определение образующего многочлена P(x). Образующий многочлен есть наименьшее общее кратное (НОК) так называемых минимальных многочленов М(x) до порядка (2s - 1) включительно. Причем образующий многочлен составляется из произведения некоторого числа нечетных минимальных многочленов:
. (18)
4. Минимальные многочлены являются простыми неприводимыми многочленами. Заметим, что если среди минимальных многочленов окажутся два одинаковых, то один из них исключается.
5. Определение числа минимальных многочленов L. Из пункта 3 следует, что порядок минимальных многочленов определяется как (2s – 1). Можно показать, что число минимальных многочленов равно числу исправляемых ошибок, то есть L = s.
6. Определение старшей степени l минимального многочлена. Степень l есть такое наименьшее целое число, при котором (2l – 1) нацело делится на n. Это значит, что l = h.
7. Выбор минимальных многочленов. Когда определено число минимальных многочленов L и степень старшего многочлена l, многочлены выписываются из специальной таблицы минимальных неприводимых многочленов различных степеней.
8. Определение степени b образующего многочлена P(x). Степень образующего многочлена не превышает произведения l · s или L · s. В зависимости от НОК, степень P(x) может быть и меньше l · s. После нахождения всех минимальных многочленов образующий многочлен находится по формуле (17).
9. Определение числа контрольных символов. Так как число контрольных символов r равно степени образующего многочлена, то для кода длины n справедливо следующее выражение b = r <= l · s.
10. Определение числа информационных символов производится из равенства k = n - r.
11. Вычисление закодированного сообщения. Закодированное сообщение F(x) можно получить двумя путями:
5) 
, (19)
где P(x) – образующий многочлен.
Q(x) получают следующим образом:
, (20)
где U(x) – комбинация, которую необходимо закодировать,
R(x) – остаток от деления.
6) 
. (21)
Кодирование
Кодовая комбинация, которую необходимо закодировать (21 первых битов ФИО):
.
Закодируем ее с возможностью исправления s = 2 ошибок, причем в канал передачи данных должно будет передаваться k = 21 информационных символов. Найдем общее число бит n, которые будут передаваться в линию, то есть длину закодированного слова. Учитывая, что n = k + r, согласно равенству (17):
.
Видно, что наименьшее натуральное h, которое входит в область допустимых значений данного уравнения с двумя неизвестными:
,
следовательно:
,
тогда:
.
Найдем кодовое расстояние:
.
Будет использовано L = s = 2 минимальных многочлена, причем старшая степень минимального многочлена l = h = 5. Из таблицы выбираем следующие минимальные многочлены: 111101 и 11111. Тогда образующий многочлен будет равен:
111101 · 11111 = 11101101001.
Видим, что степень образующего полинома – 10, что согласуется с рассчитанным выше количеством проверочных разрядов (r = 10).
Кодирование кодом БЧХ аналогично кодированию циклическим кодом с dmin = 3, описанному в п. 3.5.6., поэтому опустим теоретические обоснования и просто произведем расчеты.
1110111111101001111101110000000 | 11101101001
11101101001 |
11101101001
11101101001
11101101001
11101101001
11101101001
Зная остаток от деления, получаем закодированное сообщение:
111011111110100111110111 0101110110.
Декодирование
Пускай при передаче закодированного сообщения произошли ошибки в 4-ом и 5-ом разрядах, и декодер получил следующую искаженную кодовую комбинацию:
111101111110100111110111 0101110110.
Декодирование кода БЧХ аналогично декодированию циклического кода с dmin = 3, описанному в п. 3.5.6., поэтому опустим некоторые теоретические обоснования и просто произведем расчеты.
1111011111101001111101110101110110 | 11101101001
11101101001 |
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
Поскольку вес остатка больше числа исправляемых ошибок данного кода (s = 2), то производим циклический сдвиг принятой комбинации влево на 10 разрядов и снова делим полученную комбинацию на образующий многочлен:
1010111110101011101101111010111 | 11101101001
11101101001 |
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
11101101001
Вес полученного остатка w = 2, значит, выполняем сложение по модулю 2 этого остатка с комбинацией, для которой он был найден:
(+) 1100000
Далее выполняем обратный циклический сдвиг вправо на 10 элементов:
1110111111101001111101110101110110.
Отбрасываем последние 10 проверочных разрядов и получаем декодированное сообщение с исправленной ошибкой:
111011111110100111110111.
Рекуррентный код