14.5. МАКСИМАЛЬНО-НЕЛИНЕЙНЫЕ ФУНКЦИИ

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

Определение. Булева функция называется максимально-нелинейной, если все коэффициенты ее преобразования Адамара, задаваемые уравнением (14.8), равны

Примеры. (1). максимально-нелинейная функция, так как для всех и (см. пример, предшествующий лемме 2).

(2). - максимально-нелинейная функция, как следует из последней строки на рис. 14.6. Поскольку - целое число (из уравнения (14.8)), должно быть четным, если максимально-нелинейная функция. В дальнейшем предполагается четным.

Теорема 6. Максимально-нелинейная функция удалена от любой линейной функции дальше, чем любая другая булева функция. Более точно, функция максимально-нелинейна тогда и только тогда, когда соответствующий

ей вектор отстоит на расстояние от любого слова кода Если не является максимально-нелинейной, то в коде найдется слово такое, что его расстояние от меньше чем

Доказательство. Если не является максимально-нелинейной, то не все коэффициенты равны Так как в (14.15) имеется ровно слагаемых, то из следствия 3 вытекает, что некоторые величины должны быть больше чем Следовательно, из уравнений (14.13) или (14.14) вытекает, что расстояние между и некоторым словом кода меньше чем

Теорема 7. Функция является максимально-нелинейной тогда и только тогда, когда -матрица элемент которой равен представляет собой матрицу Адамара.

Доказательство. Вытекает из леммы

Заметим, что если является максимальио-нелинейной функцией, то можно записать:

Это задает булеву функцию Коэффициенты преобразования Адамара от функции (для их вычисления надо положить в равны Следовательно, также является максимально-нелинейной функцией!

Таким образом, максимально-нелинейные функции образуют естественные пары:

Упражнение. (12). Доказать, что функция является максимально-нелинейной тогда и только тогда, когда матрица, ( элемент которой равен для представляет собой матрицу Адамара.

Теорема 8. Если максимально-нелинейная

Доказательство. Предположим, что максимально-нелинейная функция и Доказательство основано на разложении «функции даваемом теоремой 1 гл. 13, и на результате, который мы выделим в отдельную лемму.

Пусть преобразование Адамара функции задаваемое формулой (14.8), и определяется уравнением (14.25).

Лемма 9. Если — произвольный -код, то

где все суммы вычисляются в поле действительных чисел.

Доказательство. Это утверждение является простой переформулировкой леммы 2 гл. 5. Достаточно вспомнить, что

и положить в этом равенстве

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

где а — некоторый вектор из его дополнение. Тогда и (14.26) дает:

Далее согласно теореме 1 гл. 13

где

Отсюда следует, что задается уравнением (14.27). Но если то правая часть в (14.27) четна и равно нулю. Таким образом, степень многочлена не может превосходить

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

Перейдем теперь к построению некоторых семейств максимально-нелинейных функций. Теорема 10.

является максимально-нелинейной функцией (от переменных) тогда и только тогда, когда обе функции являются максимально-нелинейными функциями от своих аргументов.

Доказательство. Запишем в виде где Из уравнения (14.8) для имеем:

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

Пример.

Чтобы найти первые строки матриц воспользуемся работой Виноградова [1371] для вычислений вычетов и невычетов:

Следовательно, первые строки матриц равны:

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

Матрица А часто оказывается обратимой, и в этих случаях порождающая матрица кода может быть записана в виде

где ортогональная циркулянтная матрица.

Пример. (Продолжение.) Обратным многочлену по модулю является многочлен Таким образом, матрица приводится к виду

(17). Доказать, что являются по существу единственными максимально-нелинейными функциями от 2 и 4 переменных.

Булева функция называется разложимой, если существует такая двоичная матрица А, что для некоторого I имеет место равенство В противном случае она называется неразложимой.

Упражнение. (18). Доказать, что всякая максимально-нелинейная функция степени (1/2) неразложима.

Теорема 12. Функция

максимально-нелинейна при произвольной функции

Доказательство. Согласно уравнениям (14.8) и (14.13) функция является максимально-нелинейной тогда и только тогда, когда число векторов являющихся корнями многочлена

равно для всех Подставляя (14.30) в (14.31), получаем:

(i). При произвольном первая сумма не равна тождественно нулю и является линейной функцией от Следовательно, имеется способов выбора при которых обращается в нуль. Общее число корней такого типа для многочлена равно .

(ii). Теперь предположим, что Тогда что дает 0 или 1 независимо от Если эта величина равна 1, то общее число корней многочлена равно Но если эта величина равна 0, то имеется дополнительных корней (и — произвольно, что в общем дает корней.

Упражнения. (19). Пусть

Доказать, что являются неэквивалентными максимально-нелинейными функциями степеней соответственно

(20). Доказать, что если произвольная булева функция, а функция задает взаимно-однозначное отображение пространства на себя, то функция

является максимально-нелинейной.

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

Задача (нерешенная). (14.1). Дать классификацию всех максимально-нелинейных функций от переменных.

ЗАМЕЧАНИЯ К ГЛ. 14

(см. скан)

(см. скан)