ДЛЯ f= 1, 2, . . ., d-1. Но

(15.18) iMirL +

(г) а (Z)

= /(22) = [/(z)p,

где deg / <. [d - 1)/2. Следовательно, ввиду формулы (15.16) и тео- ремы 2.15, б (z) = о (z).

Кал<дая из li - 1 строк проверочной матрицы (15.14) является] элементом поля GF (д"). Если эту матрицу продолжить на GF (д), то код Сривэставы будет иметь \d - 1) m проверочных символов.] Однако в общем случае строки проверочной матрицы линейно! зависимы. Ранг системы строк матрицы ей? будет зависеть от выбора! элементов а, Cg, . . ., da-i- Пока не известно ни одного метода xopo-J шего выбора этих элементов.

Мало что известно и о числе информационных символов кодов] Сривэставы. Во всяком случае они лишь незначительно хуже БЧХ- кодов, а в лучшем случае обеспечивают значительно большую ско- рость передачи информации.

Коды Сривэставы, несомненно, заслуживают дальнейшего иссле-j дования.

15.2. Вычетные коды - хорошие коды с трудным декодированием]

15.21. Определение. Если п - простое число, а е делит! п - 1, то число г, 1 г <п, называется вычетом степени е по\ модулю п, если разрешимо сравнение х" = г mod п.

Пусть порядок q по mod п делит (тг - i)/e, а - примитивный корень степени п в расширении поля GF (д), а i?o - множество всех вычетов степени е по mod п. Тогда можно образовать два е-вычетных кода с блоковой длиной nnajxGF (g). Они определяются как циклические коды с порождающими многочленами

П (х -ос") -расширенный код; гено

j (x - i) W (х-а)-суженный код. гено

i-удлиненный е-вычетный код длины = и + 1 может быть построен путем присоединения общей проверки на четность к расширенному е-вычетному коду.

15.22. Теорема. Пусть d - минимальный вес Хэмминга для кодовых слов расширенного е-вычетного кода длины п над GF (q), не принадлежащих суженному коду, и предположим, что е 2. Тогда d" > п.

Доказательство. Так как п простое, то множество классов вычетов по mod п образует конечное поле GF (п), содержащее элемент а с мультипликативным порядком и - 1. Пусть Л j-множе-

е-1 п-1

П C<>(x) = Omod S х\

г=0 1=0

ТО из китайской теоремы об остатках вытекает, что : 15.221) Д с** {X) S 5 mod(x"- 1).

Гак как вес Хэмминга произведения нескольких многочленов по mod(x" -1) не превосходит произведения весов сомножителей, то из сравнения (15.221) следует, что

П d>n.

Так как п - простое, то имеет место строгое неравенство, щ

ство вычетов вида а" (i = 1, 2, . . . , е - 1), где О / < (д - i)/e. Тогда Rq состоит из вычетов степени е по модулю п. Положим g-l (х) = \1 (х - а). Тогда

(i)(x)-= П (х-аО = П [-г;-(«У].

Циклические коды, порожденные многочленами g") (х), (х), . . ., g-C-i) (х), эквивалентны. В двоичном случае эта эквивалентность вытекает из теоремы 5.81 и следствия 5.82, а в недвоич-ноы случае -из непосредственного обобщения этих результатов. Если С°) (х) - кодовое слово расширенного кода, не принадлежащее суженному коду, то С*" (х) кратно (х) и не кратно (х - 1). Эквивалентные коды, порожденные многочленами g-C) (х), g-() (х), . . ., g-C-i) (х), соответственно содержат кодовые слова С" (х), С(Ч (х), . . ., С(") (х), являющиеся перестановками кодового слова СС (х). Все эти слова не кратны многочлену х - 1.

Рассмотрим произведение П СЩх). Оно кратно многочлену

р-1 . г=0

[J"() И не кратно х-1. Следовательно,

пс* (х) = /(х) sx\

i=0 t=0

где /(1) =s-ненулевой скаляр поля GF{q). Так как

П C<>(a:)=sremod(x-l)

Наиболее важный класс вычетных кодов получается при е = 2. Эти коды называются квадратично-вычетными кодами (КВ-кодами). Для КВ-кодов теорема 15.22 означает, что (Р > п. Если п = \ = -Imod 4, то эту границу можно улучшить с помощью теоремы 15.23.

15.23. Теорема (Мэттсон - Соломон [1961]). Если п простое и п= -1 mod 4, то минимальный вес Хэмминга кодовых слов] расширенного КВ-кода с блоковой длиной п, не принадлежащих сужен- \ ному КВ-коду, удовлетворяет неравенству - d + 1 п.

Доказательство. Как и в доказательстве теоремы 15.22, каждое слово кода с порождающим многочленом gC) (а;) соответствует 1 некоторому слову кода с порождающим многочленом g() (х). Так как] п S-1 mod 4, то -1-квадратичный невычет но mod п и С*) (х) = = С") (а;) - взаимному многочлену С") (х). При этом уравнение] (15.221) запишется в виде

С<о (х) С"» {x)s 2 mod (а;" - 1).

Если d -вес С«» (а;) и С"» (а;), то вес 0°(х) €<>> (х) не Ъревосходит! <Р - d + 1, так как в произведение входят d членов]

с ГеС"». .

Согласно теореме 6.54, КВ-коды длины п над GF (2) существуют] тогда и только тогда, когда п- простое число, сравнимое с +1 по] mod 8. Хотя порождающая матрица двоичного КВ-кода может быть! построена путем соответствующих сдвигов порождающего многочлена] кода, выбор проверочной матрицы в виде, показанном на рис. 15.1,] дает некоторые преимущества.

15.24. Теорема. Пусть N = п + I, Но ~ множество {ненуЛ левых) квадратичных вычетов по mod п, а Н - множество квадратич-1 ных невычетов. Тогда {N хН)-матрица §, определенная равенствамь

00, р = 1 для всех V, за исключением z; = сю; f О, если п=1 mod8; ""1 1, если «=-lmod8; 1, если v - uRo; u, с = I О, если v - uRi, У о, если V - и = 0,

является порождающей для i-удлиненного двоичного КВ-кода с блока вой длиной N.

Замечание. Хотя такая матрица содержит N строк, размер ность пространства ее строк равна только N12.

Так как каждый 1-удлинен11ый двоичный КВ-код эквивалентен своему дуальному, то матрица, описанная в теореме 15.24, может быть также выбрана в качестве проверочной матрицы 1-удли11енного КВ-кода.

Доказательство. Как видно из примера, указапиого на рис. 15.1, строки матрицы §, не отмеченные символом сю, являются

циклическими сдвигами многочлена f {х)= х . Если а - прими-

тивныи корень п-й степени из единицы, то [/ (а)[ = / (а), так что / (а) 6 GF (2), и, если i 6 о, то / (а) = / (а). Если i 6 Ri, то / (а) = = 1 + / (а), так как / (а) + / (а*) - сумма всех примитивных корней п-й степени из единицы и она равна 1, потому что совпадает с коэффициентом при х в круговом многочлене (J" (х). Следовательно, существует такой примитивный корень а п-й степени из единицы, что / (а"") = О, если г Но, и / (а = 1, если г 6 i-

Кратные многочлена / (х) совпадают, таким образом, с кратными порождающего многочлена расширенного КВ-кода или суженного КВ-кода в зависимости от того, будет ли / 1) равно О или1. Если 71 = 1 mod 8, то (п - 1)/2 четно и / (1) = 0. В этом случае кратные многочлена / (х) суть слова суженного КВ-кода с блоковой длиной п. Расширенный КВ-код с блоковой длиной N может быть построен путем 2-удлинения этого кода путем дописывания единичного вектора длины N к порождающей матрице кода. Это приводит к матрице, описанной в формулировке теоремы. Если п = -1 mod 8, то {п - 1)/2 нечетно и /(1) = 1. В этом случае кратные многочлена / (х) являются словами расширенного КВ-кода с блоковой длиной п. Расширенный КВ-код с блоковой длиной N может быть построен из него путем добавления общей проверки на четность. Это также приводит к порождающей матрице, указанной в формулировке теоремы, щ

Если г - квадрат примитивного элемента поля GF (п), а s - квадратичный невычет из GF (п), то N элементов множества GF (п) 1J сю можно упорядочить следующим образом: сю. О, 1, г, г, г, . . ., S, sr, sr, .... Как и на рис. 15.1, такое упорядочение координат приводит к порождающей матрице вида

(15.241)

где Л, и - квадратные циркулянтные матрицы размерности (га - 1)/2, причем матрицы Л ж % симметричны. Если Л, 3§ или % обратимы, то с помощью подходящего линейного преобразования

с помощью подходящей перестановки строк и столбцов эта матрица может] быть приведена к виду:

15..2. Вычетные коды - хорошие коды с трудным декодированием 365 порождающую матрицу можно привести к виду

(15.242)

где J - единичная матрица размерности {п - 1)/2, а. 3) - квадрат-пая циркулянтная матрица такой же размерности. Карлин [1969] показал, что такая форма порождающей матрицы двоичного КВ-кода очень полезна при исследовании весовой структуры кода. Так как порождающие матрицы многих хороших двоичных КВ-кодов могут быть представлены в виде (15.242), то Мак-Вильямс [1968, 1970] недавно предприняла попытку изучения новых кодов такого вида.

Преимущество записи порождающей матрицы в форме, приведенной в теореме 15.24, показывает также доказательство следующей теоремы.

15.25. Теорема. Каждый i-удлиненный двоичный КВ-ко(? инвариантен относительно перестановок Си *-* C „-i, где арифметические операции над индексами производятся в множестве GF (п) [] оо, причем +0~ = оо, а + оо~ = 0.

Доказательство. Мы утверждаем, [ u.v + o.v, если uRi;

(15.251) u-i,v-i-

0. о "

Р и с. 15.1. Порождающая матрица 1-удлиненного КВ-кода длины 18.

Если один из индексов и или z; равен О или оо либо если и = и, то равенство (15.251) непосредственно вытекает из теоремы (15.25). Для разбора остальных случаев заметим, что -u-i,-v-iu,v = О тогда и только тогда, когда (z; - и) (-г~ + и~) Rg. Так как (V - и) (-y-i + и-) = -1 + u/v + v/u - i = iu/v)[(u/v)--i]\ то -u-1,u, в =0 тогда и только тогда, когда (u/v) Ro, что эквивалентно формуле (15.251).щ

Так как матрица в правой части (15.251) получается из и, v путем линейного преобразования строк, а матрица в левой части (15.251) получается из и, v с помощью описанных в теореме перестановок строк и столбцов, то теорема доказана, g

Глизон, Прейндж, Ассмус и Мэттсон показали, что если в качестве Ссо выбрать скалярное кратное общей проверки на четность, то 1-удлиненный недвоичный КВ-код инвариантен относительно преобразования Са -- ± C-u-i, где выбор знака определяется квадратичным характером и.

Все арифметические операции (за исключением О X оо) можно определить в множестве GF (п) [} оо очевидным образом. [Если а GF (п), то а -f оо = оо; если а GF (п) \ О, то аоо = оо.] Эти