5.6. Пример
Построить кодер для двоичного циклического кода с блоковой длиной 23, порожденного минимальным многочленом для примитивного корня двадцать третьей степени из единицы. Построить декодер, исправляющий все сочетания из двух или меньшего числа искаженных позиций.
Решение. Различные степени числа 2 по модулю 23 дают числа 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12.
Рис. 5.17. Кодер для БЧХ-кода длины 23, исправляющего две ошибки.
Так как мультипликативный порядок числа 2 по
равен 11, то круговой многочлен
распадается в произведение двух неприводимых двоичных многочленов степени 11. Если
примитивный корень степени 23 из единицы, то элемент
не сопряжен с а, так что два неприводимых множителя многочлена
являются взаимными многочленами. Используя эту информацию и проводя умеренное число вычислений методом
проб и ошибок, определяем, что делителями многочлена
являются
Полагая
получим кодер, изображенный на рис. 5.17.
Работа декодера начинается с деления принятого слова на минимальный многочлен
элемента а, который в данном случае равен многочлену
Так как 3 есть степень двойки по модулю 23, то
Таким образом, остаток
от деления на
равен многочлену
Как только все деления закончены, декодер может определить
Зная
декодер может определить многочлен локаторов ошибок по обычной формуле для двоичных БЧХ-кодов, исправляющих две ошибки:
В рассматриваемом примере элементы поля
удобно задать в виде многочленов от а степени
где
— корень порождающего многочлена. Вычисления
и
могут быть произведены с помощью методов, описанных в гл. 2. Затем, вычисляя
можно определить по процедуре Ченя все ошибки.
Необходимо отметить, что, хотя коэффициентами многочлена локаторов ошибок могут быть любые элементы поля
допустимыми взаимными корнями этого многочлена могут быть только корни двадцать третьей степени из единицы. Если же все корни многочлена локаторов ошибок попадают в множество корней двадцать третьей степени из единицы, то процедура приводит к ошибкам декодирования. В этом случае декодер знает, что в канале связи произошло более двух ошибок.
Хотя рассмотренный неполный алгоритм не позволяет исправлять все тройные ошибки, в разд. 15.2 будет показано, что возможна полная процедура декодирования, позволяющая исправлять все не более чем тройные ошибки.