rL(P-l)/4J

Г (Р-П/2

П {2а) (-l)[(p-n/2-L(P-i)/4J] П {р - 2а)

й=1 J La=L(P-U/4J--l

Теперь в первом произведении 2а пробегает по всем четным целым числам от 2 до (р - 1)/2, а во втором произведении р ~2а пробегает по всем нечетным целым числам от 1 до (р - 1)/2 - 1. Это легко проверить, отдельно рассматривая случаи четных и нечетных {р - 1)/2. Объединяя оба произведения, имеем

(р-1)/2 Гр-1)/2

2(р-»/2 П а = (-l)[(p-i)/2-L(p-i)/4J] П а.

Далее, так как в поле GF {р) все члены произведения отличны от нуля, то можно провести сокращение, что дает

2(Р-"/2 = (- l)[(P-l)/2-L(P-l)/4J].

Если р = 8k ± 1, то показатель степени у (-1) равен четному числу и

2(р-!)/2 . 1

Если р = 8k ± 3, то показатель степени у (-1) равен нечетному числу и

2(Р-)/2 = -1,

что И завершает доказательство леммы. □

ляется достаточно трудной теоремой теории чисел, и чтобы облех чить ее доказательство, мы введем несколько лемм.

Лемма 5.9.3. Если р - простое число вида р = 8k ±1, то в поле GF (р) имеет место равенство 2р->/2 = 1. Если р - про-стюе число вида р = 8k 3, то в поле GF (р) имеет место равенство 2(Р-)/2 = -1.

Доказательство. Прежде всего заметим, что в поле GF (р) для любого а справедливо равенство 2а = -(р - 2а), и, таким образом,

л. А, Аг

и 2а= П [-{p-2a)] = {-l)i-iA„~\) П (р - 2а).

а=Ао а=А„ а=Ао

Пусть X обозначает наибольшее целое число, меньшее или равное X. Тогда имеем следующую цепочку равенств:

(р-1)/2 (р~1)/2

2(р-1)/2 П G= П (2а) =

а=1 а=1

Up-D/H (Р-1)/2

= П {2а) П (2а) =

а=1 a=L(p-l)/4J-fl

Лемма 5.9.4. В поле GF (р) число г является квадратичным вычетом тогда и только тогда, когда гр-)!" = 1.

Доказательство. Предположим, что г<р~>/2 Ф I. Тогда j/ г не может существовать, так как если он существует, то (i/ г)"" должно равняться единице, что противоречит предположению.

Предположим теперь, что гр- =1, и обозначим через а примитивный элемент поля GF (р). Все четные степени а, очевидно, являются квадратичными вычетами, и так как половина ненулевых элементов поля является квадратичными невычетами, то отсюда вытекает, что все нечетные степени элемента а образуют квадратичные невычеты. Нам надо только показать, что г равно четной* степени элемента а. Допустим противное; тогда г = а2"+ и

,-(р-1)/2 = (2i+l)(p~I)/2 = сс (р-1)сс(р-)/2 = = а(р-1)/2

так как порядок а равен р - I. Итак, из равенства гР""/ = 1 вытекает, что г равно четной степени элемента а и, следовательно, является квадратичным вычетом. □

Теорема 5.9.5. В простом поле GF (р) элемент 2 является квадратичным вычетом, если р = 8k ±1 для некоторого целого k, и квадратичным невычетом, если р = 8k ±3.

Доказательство непосредственно вытекает из леммы 5.9.3 и 5.9.4. □

ЗАДАЧИ

5.1. Многочлен g [х) = -{- х -{- -{- 1 порождает циклический код над GF (2) длины 15.

а. Найти проверочную матрицу кода.

б. Сколько ошибок может исправлять этот код?

в. Сколько стираний может исправлять этот код?

г. Найти порогкдающую матрицу кода в систематическом виде.

5.2. Найти минимальный многочлен для каждого элемента поля GF (16).

5.3. Найти поро}Кдающий многочлен двоичного (31, 21)-кода, исправляющего две ошибки.

5.4. Найти порождающий многочлен двоичного циклического (21, 12)-кода, исправляющего две ошибки.

5.5 Многочлен g (х) = х<-{- Зх + + + 2х + 2х -Ь 1 порождает над GF (4) циклический код длины 15, исправляющий две ошибки.

а. Найти порождающую матрицу кода в систематическом виде.

б. Показать, что каждое кодовое слово кода из задачи 5.1 принадлежит рассматриваемому коду.

5.6. Пусть g (х) - порождающий многочлен циклического кода над GF [q) длины п. Доказать, что если п к q взаимно просты, то слово, все компоненты которого равны I, принадлежит коду тогда и только тогда, когда 1 не является корнем порождающего многочлена,

ЗАМЕЧАНИЯ 153

5.7. Предположим, что многочлен g (х) = g„ hx" + ... Ч- gn порождает циклический код. Доказать, что gi, не равно нулю. Доказать, что взаимный многочлен g{x) = gox"~ Ч- gix"~~ Ч- •• Ч- gn-k порождает эквивалентный циклический код.

5.8. Предположим, что двоичный циклический код обладает тем свойством, что если с (х) - кодовый многочлен, то и с (х) - кодовый многочлен. Доказать, что g (х)= g (jc). Как формулируется соответствующее утверждение для недвоичного кода?

5.9. Найти порождающий многочлен (9, 7)-кода Хэмминга над GF (8).

5.10. Расширить табл. 5.2, включив в нее все коды Файра, основанные на примитивных многочленах р (х) для \2 т t.

5.11. Предположим, что (х) и й W порождают над GF (q) два кода gl и йг с одинаковой длиной. Доказать, что если все корни многочлена gi (х) являются корнями многочлена (х) (так что gi (х) делит (х)), то ga является подкодом кода el.

5.12. Многочлен g (х) = х» -- Зх° + х-{- х Ч- 2х Ч- 2x4" 1 над GF (4) порождает циклический (15, 9)-код над GF (4), исправляющий две ошибки.

а. Является ли многочлен v (х) == x Ч" Зх Ч-. Ч- 2 кодовым словом?

б. Чему равен синдромный многочлен для многочлена v (х)?

в. Сколько синдромных многочленов нужно затабулировать, чтобы охватить все исправляемые конфигурации ошибок?

5.13. Разложить многочлен х - 1 над GF (3). Сколько имеется циклических кодов над GF (3) длины 8?

5.14. Доказать, что все элементы, сопряженные с примитивным элементом, также являются примитивными.

5.15. Построить над GF (256) порождающий многочлен для кода Файра длины п = 4845, исправляющего все пакеты не более чем из 10 ошибок.

ЗАМЕЧАНИЯ

Центральная идея, объединяющая всю эту главу, была выдвинута в глубоких работах Прейнджа [1957, 1958]. Прейндж ввел понятие циклического кода и указал на его связь с идеалами алгебр, которые независимо изучали он, Питер-сон [1960] и Касами [1960]. Эта работа появилась в конце 50-х годов и заложила фундамент переворота, произошедшего в 60-х годах, когда стало понятно, что циклические коды можно описывать в расширениях полей, и это привело к идеям, которые будут изложены в гл. 7. Большинство материала данной главы использует метод расширения полей.

Исследование кодов, исправляющих пакеты ошибок, было начато Эйбрам-соном [1959]. Большинство из практически используемых кодов было найдено с помощью поиска на ЭВМ, причем многие из них нашел Касами [1963]. Первая таблица из § 5.7 основана на компиляции из книги Питерсона и Уэлдона [1971]. Коды Файра были опубликованы Файром в 1959 г.

Двоичный (23,12,7)-код Голея и троичный (11,6,5)-код Голея были опубликованы в 1949 г. (Ролей [1949]). Наше доказательство теоремы о минимальном расстоянии двоичного кода Голея восходит к Мак-Элису [1977]. Циклическую структуру кодов Хэмминга независимо установили Эйбрамсон [1960] и Элспас [1960]. Квадратично-вычетные коды были введены Прейнджем [1958] и широко изучались впоследствии; резюме посвященных им работ дали Ассмус и Мэттсон [1974].