5.8. Эквивалентность определений циклических кодов при помощи различных примитивных корней n-степени из единицы

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

из единицы. Если мультипликативный порядок числа 2 по модулю то а Так как делит то корни образуют подмножество множества корней многочлена Следовательно, каждый корень многочлена является степенью Таким образом, циклический код с блоковой длиной можно определить заданием примитивного корня степени из единицы и подмножества К чисел к по модулю для которых являются корнями Так как все сопряженные с корнями также являются корнями то множество К должно быть замкнуто относительно умножения на 2 по модулю Например, если то в соответствии с тем, что элементы двоично сопряжены. Аналогично тогда и только тогда, когда Число проверочных позиций кода равно числу элементов множества К. Число информационных позиций кода равно

Для задания порождающего многочлена кода уравнением

необходимо задать и конкретный примитивный корень степени из единицы и множество К степеней приводящих к корням Хотя различным выборам соответствуют различные коды, они эквивалентны в том смысле, что получаются друг из друга подстановкой Точное утверждение дает следующая теорема:

5.81. Теорема. Пусть фиксированный примитивный корень степени из единицы в конечном поле характеристики , К — подмножество чисел по модулю замкнутое относительно Умножения на Пусть произвольное число, взаимно простое с Пусть с произвольный двоичный многочлен степени где причем Многочлен с кратен тогда и только тогда, когда с кратен

Пример. Пусть , а — корень многочлена Делители приведены в разд. 4.7. Положим Так как то Одним из кратных многочлена является многочлен который с помощью подстановки приводится к виду

Доказательство. Пусть Тогда эквивалентны следующие утверждения:

5.82. Следствие. Произвольный двоичный циклический код с нечетной блоковой длиной инвариантен относительно подстановки

Следствие 5.82 оказывается полезным при изучении весовой структуры двоичных циклических кодов. Произвольная группа подстановок, переводящая кодовое слово снова в кодовое слово, разбивает множество всех кодовых слов на непересекающиеся классы, каждый из которых содержит слова, получающиеся друг из друга при помощи подстановок из этой группы. Так как кодовые слова одного класса имеют одинаковый вес, то для полного перечисления всех весов достаточно рассмотреть по одному слову из каждого класса. Мак-Вильямс [1965] и Гёталс [1965], [1966] использовали группу подстановок, порожденную естественными циклическими сдвигами и подстановками, указанными в следствии 5.82, для полного перечисления весов двоичных циклических кодов с блоковой длиной 43.

Если — два примитивных корня степени из единицы с различными минимальными многочленами, то, согласно теореме 5.81, слова кода, порожденного многочленом получаются путем перестановки координат кодовых слов кода, порожденного многочленом Конфигурации ошибок, исправляемые при заданном алгоритме декодирования одним кодом, являются перестановками конфигураций ошибок, исправляемых другим кодом при том же алгоритме декодирования; конфигурации ошибок, приводящие к отказу от декодирования в одном коде, являются перестановками конфигураций ошибок, приводящих к отказу от декодирования в другом коде; конфигурации ошибок, неправильно декодируемые в одном коде, являются перестановками конфигураций ошибок, неправильно декодируемых в другом коде. Таким обравом, с точностью до перестановки, эти два кода эквивалентны.

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

тенденцию к появлению пакетами. Для большинства каналов конфигурация из трех последовательных ошибок является несколько более вероятной, чем какая-нибудь конфигурация из трех ошибок, размазанных по блоку. Поэтому часто оказывается целесообразным задавать код с помощью вполне определенных корней степени из единицы, а не каким-либо другим образом. Например, в примере 5.7 мы видели, что где Любой из этих множителей может быть выбран в качестве порождающего многочлена для двоичного циклического кода с блоковой длиной 17 и восемью проверочными позициями. Код с порождающим многочленом неправильно декодирует тройную ошибку в трех последовательных позициях 3, 4 и 5 как двойную ошибку в позициях 0 и 8. Это ясно видно из того факта, что код содержит слово (сам порождающий многочлен) веса 5 с единицами в позициях 0, 3, 4, 5 и 8. С другой стороны, в коде с порождающим многочленом нет кодовых слов веса 5 с единицами в трех последовательных позициях. Следовательно, код с порождающим многочленом при трех последовательных ошибках приводит к отказу от декодирования. Если использовать алгоритм 5.71, то он приведет к квадратному многочлену ошибок не имеющему корней в множестве корней семнадцатой степени из единицы.

Таким образом, если в канале наблюдается тенденция к группированию ошибок, то может случиться, что задание циклического кода с использованием некоторого корня степени из единицы более целесообразно, чем какое-либо другое задание. В общем случае число обратных связей в схемах кодера и декодера также зависит от выбора частного корня степени из единицы. Конкретный критерий, на основании которого производится выбор, должен учитывать стоимость выбираемых логических цепей и статистику ошибок в канале. Выбор зависит от разложения многочленов Методы отыскания этих разложений описаны в гл. 6.

Задачи

(см. скан)

(см. скан)