5.9. КВАДРАТИЧНО-ВЫЧЕТНЫЕ КОДЫ

Класс квадратично-вычетных колов представляет собой частный подкласс циклических кодов, широко изучаемых потому, что в этом подклассе было найдено несколько хороших кодов и поэтому имеется надежда найти в нем другие хорошие коды. На рис. 5.2 приведены параметры некоторых квадратично-вычетных кодов с известным минимальным расстоянием. Наиболее известным кодом класса является код Голея. Большинство кодов из этого списка обладают большим минимальным расстоянием, чем любой другой известный код с теми же параметрами что и привлекает внимание исследователей к квадратично-вычетным кодам. Однако не все эти коды хороши, и не известно, существуют ли хорошие квадратично-вычетные коды большой длины. Поэтому неясно, насколько квадратично-вычетные коды полезны в практических приложениях.

Мы рассмотрим только двоичные квадратично-вычетные коды. Название этих кодов отражает их связь с теми элементами простого поля, которые имеют в этом поле квадратный корень. Как показывает теорема 4.6.15, в полях характеристики 2 каждый элемент имеет единственный квадратный корень. В простом поле квадратный корень имеет точно половина ненулевых элементов, а именно те элементов, которые равны четным степеням примитивного элемента. Эти элементы принято называть квадратичными вычетами (так как они равны квадратам своих квадратных корней по модулю Подчеркнем, что,

Рис. 5.2. Параметры некоторых двоичных квадратично-вычетных кодов. Знаком сноски отмечены параметры лучших из известных кодов с данными

хотя мы рассматриваем коды над квадратичные вычеты, входящие в их определение, лежат в поле Не следует также путать поле локаторов с полем которое не является подполем поля локаторов.

Определение 5.9.1. Коадрсипичночзычетным кодом называется циклический код над длина которого равна простому числу делящему при некотором а корнями порождающего многочлена являются все элементы а из такие, что является квадратичным вычетом поля

Как следует из этого определения,

где произведение вычисляется по множеству всех квадратичных вычетов по модулю причем предполагается, что представляет собой многочлен над GF (2). Если такой многочлен не является многочленом над то для этого значения кода не существует.

Из определения многочлена следует также, что

где многочлен определяется тем, что все его корней суть элементы вида из для всех ненулевых квадратичных невычетов из Многочлен является взаимным к и порождает эквивалентный код.

Многочлен

порождает другой код. У этого многочлена корней на один больше, чем у многочлена следовательно, порождаемый им код является подкодом квадратично-вычетного кода. Этот подкод тоже пазывается квадратично-вычетным, но он не так интересен, как исходный код, и в дальнейшем мы не будем его рассматривать.

Квадратично-вычетный код над полем существует только тогда, когда все коэффициенты многочлена лежат в этом поле. Вскоре мы увидим, что квадратично-вычетный код существует только тогда, когда является простым числом вида Но для описания одного такого кода надо знать его минимальное расстояние. Обычно задача вычисления минимального расстояния квадратично-вычетного кода является достаточно сложной, и каждый из кодов требует индивидуального подхода. Один из примеров мы встретили в предыдущем параграфе при исследовании -кода Голея. Для всех перечисленных на рис. 5.2 квадратично-вычетных кодов минимальные расстояния

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

Мы укажем одну границу для минимального расстояния произвольного квадратично-вычетного кода. Граница не очень хороша, но легко доказывается.

Теорема 5.9.2 (граница квадратного корня). Минимальное расстояние произвольного квадратично-вычетного кода длины удовлетворяет неравенству

Доказательство. Зафиксируем произвольный ненулевой элемент поля не являющийся квадратичным вычетом. Каждый элемент поля можно записать в виде для некоторого (так как —поле). Если число является квадратичным вычетом, то, очевидно, будет квадратичным невычетом, если же квадратичный невычет, то является квадратичным вычетом.

Пусть с представляет собой кодовый многочлен минимального веса Тогда с для некоторого Определим с При этом с и вес многочлена с равен самое большее Но если квадратичный вычет, то а если квадратичный невычет, то Таким образом, Следовательно, с делится как на так и на Этот многочлен кратен многочлену а степень его равна самое большее и поэтому

В правой части стоит многочлен веса а так как вес многочлена равен то возможный вес многочлена в левой части не превосходит Итак, что и требовалось доказать.

Теперь определим, когда коэффициенты определенного выше многочлена принимают только двоичные значения. Если 2 является квадратичным вычетом, то все степени двойки также являются квадратичными вычетами. Далее, если -другой квадратичный вычет, то все числа также являются квадратичными вычетами. Следовательно, вместе с все его сопряженные относительно ноля элементы являются корнями порождающего многочлена. В этом случае многочлены представляют собой многочлены над GF (2). Таким образом, квадратично-вычетные коды существуют для всех таких для которых 2 является квадратичным вычетом в ноле Мы увидим, что числа для которых 2 является квадратичным вычетом в поле исчерпываются простыми числами вида для произвольного целого Это утверждение

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

Лемма 5.9.3. Если простое число вида то в поле имеет место равенство Если простое число вида то в поле имеет место равенство

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

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

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

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

Если то показатель степени равен четному числу и

Если то показатель степени равен нечетному числу и

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

Лемма 5.9.4. В поле число является квадратичным вычетом тогда и только тогда, когда

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

Предположим теперь, что и обозначим через а примитивный элемент поля Все четные степени а, очевидно, являются квадратичными вычетами, и так как половина ненулевых элементов поля является квадратичными невычетами, то отсюда вытекает, что все нечетные степени элемента а образуют квадратичные невычеты. Нам надо только показать, что равно четной степени элемента ее. Допустим противное; тогда и

так как порядок а равен Итак, из равенства вытекает, что равно четной степени элемента а и, следовательно, является квадратичным вычетом.

Теорема 5.9.5. В простом поле элемент 2 является квадратичным вычетом, если для некоторого целого и квадратичным невычетом, если

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

ЗАДАЧИ

(см. скан)

(см. скан)

ЗАМЕЧАНИЯ

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

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

Двоичный -код Голея и троичный -код Голея были опубликованы в 1949 г. (Гонеи [19491). Паше доказательство теорены о минимальном расстоянии двоичного кода Голея восходит к Мак-Элису [1977]. Циклическую структуру кодов Хэмминга независимо установили Эйбрамсон [I960] и Элспае [19601 Квадратично-вычетные кода были введены Прейнджем [19581 и широко изучались впоследствии; резюме посвященных им работ дали Лссмус и Мэттсон [1974].