5.7. Пример

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

Решение. Различные степени числа 2 по модулю 17 дают числа 1, 2, 4, 8, —1, —2, —4, —8. Так как мультипликативный порядок числа 2 по модулю 17 равен 8, то круговой многочлен распадается в произведение двух неприводимых двоичных многочленов, степень каждого из которых равна 8. Если а — примитивный корень семнадцатой степени из единицы, то сопряжен с а, так что каждый из двух неприводимых множителей многочлена является и своим взаимным. Поэтому можно заключить, что каждый из неприводимых множителей представим в виде

1. Деление этого многочлена на дает остаток деление на дает остаток ; деление на дает остаток . Так как не является делителем искомого многочлена восьмой степени, то так как также не делит этот многочлен, то так как и многочлен его не делит, то либо либо либо оба эти равенства выполняются одновременно. Таким образом, определяем делители это Так как последний делитель имеет меньше ненулевых коэффициентов, то выбор его в качестве порождающего многочлена кода позволяет построить устройства с меньшим числом обратных связей. Полагаем Читатель может без труда построить кодер для этого кода. Несложно и построение устройства деления принятого слова на и выделения остатка Имея эти данные, декодер легко находит Для исправления двух ошибок необходимо также знать . В данном примере, однако, величина не может быть найдена. Так как число 3 не является степенью 2 по модулю 17, то не является корнем порождающего многочлена кода. Ни одна комбинация проверочных позиций полученного слова не приводит к Для исправления двойных ошибок декодер должен поступать иначе. Конечно, вообще говоря, априори не очевидно, что данный код позволяет исправлять две ошибки. Он, как и БЧХ-код с блоковой длиной 15, имеет только восемь проверочных позиций. Восьми проверочных позиций достаточно для исправления любых двух (или одной ошибки) в блоке из 15 двоичных позиций, но консервативный читатель скептически отнесется к возможности исправления с помощью восьми проверочных позиций любых двух ошибок в блоке из 17 двоичных позиций. Тем не менее даже скептики не могут отрицать такой возможности, пока не найдут для этого достаточных оснований.

Ясно, что декодер не может выявить две ошибки, зная только Так как он не может определить то ему необходима другая дополнительная информация. Декодер может определить Наиболее полезной из этих величин является Если в канале произошли две ошибки, то и дают декодеру два независимых уравнения с двумя неизвестными:

Так как то и Таким образом, в случае двух ошибок декодер может найти многочлен локаторов ошибок. В случае одной ошибки в канале Следовательно, если произошла только одна ошибка, то декодер может ее исправить. Представляется возможным, что декодер может различать случаи одной и двух ошибок. Если в канале произошла одна ошибка, . В принципе такая ситуация возможна и при двух ошибках. Однако в этом случае где примитивный корень третьей степени из единицы. Тогда взаимными корнями многочлена являются локаторы Но так что Так как корни семнадцатой степени из единицы, то также являются корнями семнадцатой степени из единицы. Но Из этого противоречия заключаем, что в случае двух ошибок в канале Следовательно, все двойные и одиночные ошибки можно исправлять с помощью следующего алгоритма:

5.71. Алгоритм декодирования

Все вычисления алгоритма 5.71 выполняются в поле Читатель без труда сможет сконструировать соответствующие схемы.