ИЗ единицы. Если т - мультипликативный порядок числа 2 по модулю п, то а 6 GF (2"). Так как g {х) делит ж" - 1, то корн! g (ж) образуют подмножество множества корней многочлена ж" - ii Следовательно, каждый корень многочлена g (ж) является степенью а.; Таким образом, циклический код с блоковой длиной п можно опреде лить заданием примитивного корня тг-й стецени из единицы и под-i множества К чисел к но модулю п, для которых являются корч ними g (ж). Так как все сопряженные с корнями g (ж) также являютси корнями g (ж), то множество К должно быть замкнуто относительно умножения на 2 по модулю п. Например, если \ К, то 2 £ Л[ А К, Ъ К, . . . в соответствии с тем, что элементы а, а, а* а*, ... двоично сопряжены. Аналогично Ъ К тогда и толькс тогда, когда Q К. Число проверочных позиций кода равн< deg g {х) = \ К \ - числу элементов множества К. Число информа ционных позиций кода равно п - \ К \.

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

g{x)= П (а:-а")

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

5.81. Теорема. Пусть а - фиксированный примитивнь корень п-й степени из единицы в конечном поле характеристики К - подмножество чисел по модулю п, - замкнутое относителъь Умножения на 2, g{x)= (ж -а**). Пусть] - произвольное чис

взаимно простое с п, и g {х) - П ~ °) = П - «)- У<

с (ж) = У1 cjs - произвольный двоичный многочлен степени <; i n-l

а с {х) = 2 CftX**, где с = Ст, причем т = jk той п. Многом

С (ж) кратен g (ж) тогда и только тогда, когда с (ж) кратен g {з

Пример. Пусть 71 = 31, а-корень многочлена x + x + l, К - {1, 2, 16, 3, 6, 12, 24, 17} и / = 7. Делители х-1 приведены в разд. 4.7. Поло g (х} = М(Ч (х) М<Нх)\+а + з + х«л.х» + х»-\-хо и g (х) = МС (х)М<1

подстановки х -* х приводится к виду 1 + а;в + а; + + о;** + a;i + = g (х) (\ + X + 3? + х> + zi" + a;W 4. .16 j.ie .17).

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

с (ж) кратен g (ж);

с (а) = О для всех к К;

с (а*) = О для всех ik £ К;

с (а**) = О для всех к g ]К;

с (а) = О для всех к 6 jK;

с (ж) кратен (ж), щ

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

Cft ci, i = 2к mod п.

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

Если а и а - два примитивных корня п-й степени из единицы с различными минимальными многочленами, то, согласно теореме 5.81, слова кода, порожденного многочленом g{x)- П (ж -а),

получаются путем перестановки координат кодовых слов кода, порожденного многочленом g (ж) = \\ {х - а). Конфигурации

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

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

тенденцию к появлению пакетами. Для большинства каналов конфигурация из трех последовательных ошибок является несколько более вероятной, чем какая-нибудь конфигурация из трех ошибок, размазанных по блоку. Поэтому часто оказывается целесообразным задавать код с помош;ью вполне определенных корней п-я степени из единицы, а не каким-либо другим образом. Например, в примере 5.7 мы видели, что (?<i" (х) = g {х) g{x), где g (х) = 1 + + X? + х + х + 3? и g{x) = 1 + а; + -f х* + а;« + х + х». Любой из этих множителей может быть выбран в качестве порождаю-щего многочлена для двоичного циклического кода с блоковой длиной 17 и восемью проверочными позициями. Код с порождающим многочленом g {х) неправильно декодирует тройную ошибку в трех последовательных позициях 3, 4 и 5 как двойную ошибку в позициях О и 8. Это ясно видно из того факта, что код содержит слово (сам порождающий многочлен) веса 5 с единицами в позициях О, 3, 4, 5 и 8. С другой стороны, в коде с порождающим многочленом g {х) нет кодовых слов веса 5 с единицами в трех последовательных позициях. Следовательно, код с порождающим многочленом g {х) при трех последовательных ошибках приводит к отказу от декодирования. Если использовать алгоритм 5.71, то он приведет к квадратному многочлену ошибок о (z), не имеющему корней в множестве корней семнадцатой степени из единицы.

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

Указание. Если С (z) = О mod (а;<= - 1), то А (х) - В ix) и j = i mod с. 5.3 (Месси [1964]). Код называют реверсивным, если он наряду с кодовым

словом [Со, C,

С„ 2, содержит слово [C„ i, С„ 2

Си Со]

(a) Доказать, что циклический код реверсивен тогда и только тогда, когда для каждого корня порождающего многочлена взаимный корень также является корнем этого многочлена.

(b) Доказать, что если -1 есть стецень q по модулю п, то каждый циклический код с блоковой длиной п над GF (д) реверсивен.

5.4 Постройте реверсивный циклический код, исправляющий две ошибки, с блоковой длиной ге = 4» + 1 и скоростью передачи Л = 1 - 4i/n.

5.5 Пусть п - простое число, т - мультипликативный порядок числа 2 по модулю га и / = (ге -- 1)/т. Доказать следующие утверждения:

(a) Существует точно 2i+i двоичных циклических кодов с блоковой длиной га.

(b) Существует точно 2 "Т 2 " "" двоичных циклических кодов

I, d,

I]} d\l

с блоковой длиной п, не эквивалентных в смысле теоремы 5.81.

Задачи

5.1 (Эбрамсон [1959]). Показать, что расширенный код, образованный добавлением общей проверки на четность в конце циклического кода Хэмминга, позволяет исправлять все одиночные ошибки и все двойные смежные ошибки, не затрагивающие общую проверку на четность. Возможно ли так переупо-i рядочить столбцы кода, чтобы он исправлял все одиночные и двойные смежные S «шибки? J

5.2 (Файр [1959]). Пусть е и с - произвольные числа, are - их наименьшее общее кратное. Пусть р (х)-неприводимый делитель Q<(х) над GF (д),т-1 порядок числа q по модулю е и g (х) = р {х) {хс - 1). Доказать, что циклический: код с блоковой длиной п, порожденный многочленом g (х), не содержит кодовых! слов вида С (х) = (х) - xiB {х) mod (хп - 1), где deg А (х) < 7П. и deg А (х) + deg В (х) < с.

Глава 6

Разложение многочленов над конечными

ПОЛЯМИ

6.1. Общий алгоритм

В этом разделе описывается один алгоритм разложения многочлена

•/ (х) - S fkX, /ft G GF (q), в произведение степеней неприводимых

ft=0

многочленов. Для достаточно малых q этот алгоритм оказывается эффективным даже при больших числах т.

1. Строим {т X пг)-матрицу й над GF (q), i-я строка которой соответствует многочлену яfl(->, приведенному по модулю / (ж). В частности,

xs S (2m.ft,iXmod/(a:).

ft=0

Матрица й может быть построена с помощью регистра сдвига,! выполняющего умножение на х по модулю / (ж). В начальном поло- жении в регистре записана 1 - первая строка матрицы й- После q сдвигов в нем содержится вторая строка й и т. д. После q {т - 1щ сдвигов в регистре будет записана последняя строка матрицы S.

Для произвольного многочлена g (х) = 2 giX степени <

над полем GF (q) класс вычетов [g (ж)] по модулю / (ж) может бытв определен с помощью умножения вектор-строки Igg, g, . . ., gm-il на матрицу (g. Это вытекает из следующего соотношения:

[ё(ж)] = ё(ж)= 2 Si

i=: о

m-l m-l m-l m-l

2(2 i(SHi.ft+i)- S (S gi&ui.n,i):.

i = 0 ft= 0

k=Q i = 0

Аналогично класс вычетов Ig (ж)]« - g (ж) по модулю / (ж) може быть найден путем умножения вектор-строки [go, gi, . . ., ётп-на матрицу (й - J), где J -единичная {т X т.)-матрица ш GF (q).

2. Находим множество вектор-строк, образующих нуль-подпространство матрицы й - J. Для этого можно применить соответствующие операции над столбцами матрицы й - J, описанные в разд. 2.5, 2.6. Каждая вектор-строка из нуль-подпространства матрицы й ~ J представима в виде многочлена g (ж), удовлетворяющего сравнению [g (ж)]« - (ж) = О mod / (ж), и, наоборот, каждый многочлен g (ж), удовлетворяющий этому сравнению, является представлением вектор-строки из нуль-подпространства матрицы й - J.

3. Выбираем произвольный из многочленов g (ж), найденных на предыдущем шаге, и, используя алгоритм Евклида, определяем наибольший общий делитель многочленов / (ж) и (ж) - s для всех S GF (q) Тогда имеет место следующее разложение:

6.11. Теорема

/(ж)= П [и.о. д.(/(ж), (ж)-5)].

Замечание. Если g(ж) -скаляр, то это разложение принимает вид

/(ж) = н. о. д. (/(ж), 0) П н. о. д. (/(ж), 5) = /(ж) П 1.

Если же g (ж) - многочлен ненулевой степени, то разложение (6.11) нетривиально. В общем случае это разложение является неполным, ибо н. о. д. (/ (ж), g (ж) - s) может быть разложимым.

Доказательство теоремы 6.11. По условию / (ж) делит [g (ж)]« - g (х) = [] Ig {х) - s]. Следовательно, / (ж) делит

также П [н. о. д. (/ (ж), g (ж) - s)]. С другой стороны, и. о. д.

sGF(q)

if {х), g (ж) - s) делит / (ж). Если s ф t я s, t £ GF (q), то многочлены g (х) ~ S и g (х) - t взаимно просты, так же как и н. о. д. (/ (х), g (ж) - s) и н. о. д. (/ (ж), g (ж) - t). Следовательно, [] [н. о. д. (/ (ж), g (ж) - S)] делит / (ж). Предполагая оба много-

se&F(g)

члена нормированными, приходим к выводу, что они равны, так как они делят друг друга, щ

А, .М* Пример. Пусть / (ж) - двоичный многочлен И10001110001, иначе, / (ж) = 1 + ж -f ж -f ж» -f- ж -f ж» + х\ Последовательные степени ж имеют вид

Практически для определения н. о. д. нет необходимости в д-кратном 1спользовании алгоритма Евклида. Укороченная процедура иллюстрируется примером D.12.