15.5. КОД КЕРДОКА И ЕГО ОБОБЩЕНИЯ

В этом несколько длинном параграфе мы собираемся исследовать один частный случай подкодов РМ кода второго порядка Пусть обозначает множество симплектических форм соответствующих словам этого подкода (см. уравнения (15.4) и (15.19)). Тогда ранг каждой ненулевой формы из не меньше, чем и ранг суммы любых двух различных форм из

также равен по меньшей мере где некоторое фиксированное число в диапазоне В гл. 21 мы увидим, что максимально возможный объем такого множества 9 равен

Следовательно, максимально возможный объем соответствующего подкода в равен В гл. 21 мы найдем также число симплектических форм каждого ранга в множестве максимальной мощности и, следовательно, спектр весов соответствующего кода.

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

Случай (I), нечетно; Типичное слово кода записывается в виде

Многочлен Мэттсона-Соломона для такого слова равен

так что соответствующая булева функция и симплектическая форма имеют вид

и

где

Полагая в (15.28) первые или последние элементов равными нулю, получаем симплектическую форму, ранг которой не меньше, чем Ясно, что сумма двух таких симплектических форм также имеет для тех же значений индекса (Это и обусловливает линейность соответствующего кода.)

Теорема 15. Если то ранг симплектической формы (15.28) не меньше чем

Доказательство. Если то

где степень не превосходит

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

Теорема 16. Если то ранг симплектической формы (15.28) не меньше чем

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

Полагая мы удаляем из кода идемпотент Поэтому в качестве следствия из теорем 15 и 16 имеем.

Следствие 17. Пусть и пусть любое число в диапазоне Тогда в коде существуют два подкода с параметрами Они получаются путем расширения циклических подкодов в порожденных идемпотентами

и

Эти коды содержат слова весов для всех в диапазоне

Доказательство. Мы видели, что ранги всех ненулевых симплектических форм, соответствующих кодовым словам, не меньше чем Тогда утверждение вытекает сразу из теоремы 5.

Замечание. Согласно формуле (15.26) эти коды имеют максимально допустимую мощность. Спектр весов этих кодов может быть вычислен с помощью результатов, приведенных в § 2.1.

Случай (II). Мы опять начнем с поиска максимального по объему множества симплектических форм, ранг которых не меньше чем и такого, что ранг суммы любых двух различных форм также не меньше чем Но в данном случае для четного это множество уже оказывается нелинейным. Мы

начнем со случая и построим коды Кердока. Прежде чем давать определение, дадим на рис. 15.6 краткое описание этого семейства кодов рис. 2.19).

Рис. 15.6. Свойства кода Кердока

Рис. 15.7 Спектр весов (или расстояний) кода Кердока

Определение кода Кердока . Код является объединением кода смежных классов кода по Смежные классы выбираются так, чтобы они имели максимальный ранг и чтобы ранг суммы любых двух смежных классов также был равен Иными словами, булевы функции, соответствующие этим смежным классам, являются максимально нелинейными квадратичными функциями (см. § 14.5) такими, что сумма любых двух из них опять является максимально нелинейной. Так как имеется всего таких смежных классов (или соответствующих симплектических форм), то согласно (15.27) мощность кода имеет максимально возможное значение.

Мы будем записывать слова кода в виде где (см. теорему 2 гл. 13). В этих обозначениях код состоит из слов

где /

Код Кердока определяется для как код, состоящий из кода смежных классов кода

по коду для которых в качестве представителей смежных классов выбираются

для всех где, как обычно, . В качестве всегда выбирается нулевое слово

Таким образом, типичное кодовое слово из записывается в виде

где или 1 и

Упражнения (11) Пусть код, состоящий из линейного кода его смежных классов, в качестве представителей которых выбраны элементы

Таким образом, В групповой алгебре коды представляются соответственно элементами (см § 5.5)

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

(12) Доказать, что линейный код, порождаемый кодом равен коду

МС-многочлены для левой и правой половин элемента за таваемого выражением (15 33), соответственно равны

и

где зависит от

Пусть элементы поля выписаны в некотором фиксированном порядке Тогда

где для всех

Если элементы поля записать в виде пар где равно 0 или 1, то координаты вектора (или любого другого вектора из можно нумеровать этими парами, полагая в них для левой половины вектора для правой.

Например, если (так что длина вектора равна 16), то элементы поля GF(24) могут быть записаны в виде пар где равно 0 или 1, как это показано на рис. 15.8. Здесь у — примитивный элемент поля GF(24), причем примитивный элемент поля причем

Рис. 15.8. Запись элементов поля GF(24) в виде пар , где

На рис. 15.9 приведен конкретный пример, в котором сначала (рис. представитель смежного класса и некоторые слова кода записаны как слова циклического расширенного кода с общей проверкой на четность, помещенной в позиции с номером а затем (рис. указана нумерация координат этих же слов с помощью пар или 1. Для перехода от записи на рис. к записи на рис. 15.9(b)

надо пользоваться рис. 15.8. Отметим, что выбранный для рис. 15.9 элемент равен следовательно, лежит в коде

Рис. 15.9. и некоторые слова кода

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

и, конечно,

Основной результат раздела дается следующей теоремой.

Теорема является максимально нелинейной функцией, и при функция также максимально нелинейна.

Доказательство. Для доказательства достаточно показать, что ранги симплектических форм, соответствующих функциям равны Согласно равенству (15.5) симплектическая форма, соответствующая функции равна:

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

и, следовательно, элемент должен быть равен 0.

Таким образом, единственной парой, для которой при всех является Следовательно, ранг формы равен

Остается доказать, что ранг формы при также равен Доказательство этого факта аналогично предыдущему и предоставляется читателю.

Спектр весов кода Согласно теореме 5 смежный класс кода ранга содержит векторов веса векторов веса Сам код Рида-Маллера первого порядка содержит слов веса слова 0 и 1. Это приводит к спектру весов, выписанному на рис. 15.7. Согласно упражнению (11) и теореме 18 спектр попарных расстояний также равен спектру на рис. 15.7. В частности, эквивалентен коду так как единствен (§ 8 гл. 2).

В § 15.6 будет описан другой нелинейный код, код Препараты который обладает тем удивительным свойством, что его спектр весов (или расстояний) равен преобразованию

Мак-Вильямс от спектра весов кода Иными словами, согласно (5.13)

где многочлен Кравчука (§ 5.2). Легко проверить, что минимальное расстояние кода равно Тогда из теоремы 9 гл. 6 сразу вытекает, что слова каждого фиксированного веса в коде образуют -схему (так как

Случай (II). (продолжение). Рассмотрим теперь общий случай, когда произвольное число в диапазоне Нелинейные коды, к описанию которых мы переходим, были открыты Дельсартом и Геталсом и обозначаются через Вот их определение.

Положим для код равным а для выберем в качестве -код, задаваемый выражением (15.31) следствия 17. Пусть векторы, определяемые условием (15.33), и пусть

Определение. При код определяется как множество векторов вида

где равно 0 или 1.

Теорема 19. При код имеет длину минимальное расстояние и содержит слов Если то а при код является нелинейным подкодом кода .

Доказательство. Всего имеется слов вида (15.37). Тот факт, что все они различны и что действительно минимальное расстояние между ними равно будет следовать из доказываемой ниже теоремы 20.

Заметим, что содержит код Кердока в качестве подкода. Это происходит потому, что множество векторов содержит все слова кода Кроме того, код равен коду Таким образом, рассматриваемые коды являются обобщением кодов Кердока. Согласно упражнению (12) линейный код, порожденный кодом совпадает со всем кодом

Несколько первых кодов семейства приведены на рис. 15.10; здесь равно двоичному логарифму числа кодовых слов и равно минимальному расстоянию кода.

Код содержится в и является объединением некоторых смежных классов кода по коду Рассмотрим смежный класс, содержащий слово, задаваемое

Рис. 15.10 Параметры минимальное расстояние) первых кодов

выражением (15.37). Симплектическая форма, соответствующая этому классу, равна:

Первый член в этом равенстве обусловлен частью в соответствии с выражениями (15.28) и (15.29), а остальные — вектором в соответствии с выражением (15.35). Элемент у соответствует вектору Число различных симплектических форм такого типа равно Из (15.27) и следующей ниже теоремы вытекает, что это число является максимально возможным.

Основное свойство кодов рассматриваемого класса описывается следующим образом.

Теорема 20. Ранг любой симплектической формы вида (15.38), так же как и ранг суммы двух таких форм, не меньше чем

Доказательство. Перепишем (15.38) в виде

где

Достаточно показать, что ранг суммы двух таких форм не меньше чем Так как линейный код, то где задается

равенством (15.39) при соответствующем выборе Следовательно,

Нам удобно определить функцию которая представляет собой симплектическую форму от Тогда

где

Пусть ранг формы равен Покажем, что Рассмотрим разложение

Тогда

Будем предполагать, что рассматриваемая булева функция имеет канонический вид, задаваемый теоремой 4. Ее МС-многочлен определяется выражением (15.11). Нетрудно догадаться, что соответствующая симплектическая форма равна где

линейно независимые элементы поля

Сравнивая (15.41) и (15.42), видим, что для

Если положить

то станет ясно, что

Определим как множество элементов так что

Пусть наименьшее подпространство в содержащее все множество Ясно, что Пусть линеаризованный многочлен, соответствующий множеству (см. § 4.9); он задается равенством

Заметим, что (так как в противном случае полный квадрат). Тогда, используя (15.45), получаем:

Теперь предположим, что и придем к противоречию. Это и будет служить доказательством того, что или как и утверждалось.

Полагая в и используя (15.44), заключаем, что Полагая затем приходим к заключению, что для всех Но что и дает противоречие.

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

Лемма 21. Пусть симплектическая форма вида

где линеаризованный многочлен над Пусть

Тогда, если уравнение не имеет решений в поле то

Доказательство леммы. Для того чтобы определить ранг формы надо знать число пар таких, что для всех Полагая видим, что Таким образом, и должно выполняться равенство Если уравнение не

имеет решений, то единственной возможностью является Так что множество корней задается условием

Из (15.20) далее имеем: (ядро следовательно, (ядро Таким образом, ранг формы 38 больше ранга формы т. е. (так как он не может быть больше этой величины). Это завершает доказательство леммы.

Возвращаясь к доказательству теоремы, напомним, что формы 38 и 38 задаются равенствами (15.40) и (15.41) и что Чтобы завершить доказательство, мы должны доказать, что если ранг формы равен то уравнение не имеет решений в поле Предположим, что для некоторого Тогда из равенства (15.43) следует, что линейно зависит от т. е. для некоторых выполняется равенство

Обозначим через множество элементов:

а через наименьшее подпространство поля содержащее Очевидно, что Определив далее величину

легко непосредственно проверить, что Тогда, повторяя те же самые рассуждения, что и выше, заключаем, что для всех Но опять и получаем противоречие. Следовательно, наше предположение о том, что неверно, что и завершает доказательство теоремы.

Из теоремы 5 вытекает, что возможными значениями расстояний для кода являются: при .

В § 21.8 мы покажем, как вычисляется спектр расстояний этого кода. Спектры расстояний для частных случаев приведены на рис. 15.7 и 15.13.

Упражнение. (13). Доказать, что представляет собой объединение непересекающихся сдвигов кода