14.3. СМЕЖНЫЕ КЛАССЫ ПО КОДУ РИДА—МАЛЛЕРА ПЕРВОГО ПОРЯДКА

Задача вычисления весовых функций для смежных классов по коду Рида — Маллера первого порядка возникает в различных практических ситуациях. В общем виде эта задача не решена до сих пор (см. задачу (1.1) из гл. 1), хотя для 32 все веса описаны полностью. Однако некоторые интересные факты мы уже можем изложить. Например, задача вычисления весового спектра смежного класса, содержащего вектор сводится к вычислению преобразования Адамара для вектора Кроме того задача вычисления весовых функций для смежных классов по коду оказывается эквивалентной задаче классификации булевых функций по модулю линейных функций. Описанные в этом параграфе свойства смежных классов оказываются также полезными при декодировании (см. § 14.4). В конце этого параграфа приводится таблица смежных классов по коду Особенный интерес представляют смежные классы с наибольшим минимальным весом, которые изучаются в последнем параграфе этой главы.

Замечание. Как и в § обозначает вектор из (эти векторы считаются упорядоченными), и если некоторая булева функция, то соответствующий ей двоичный вектор длины

Код Рида — Маллера первого порядка состоит из всех векторов

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

Предположим, что во всех словах кода символ 1 заменен на символ —1, а символ О на символ 1. Получающееся при

Рис. 14.5. Четырехмерный обобщенный октаэдр, вершины которого соответствуют словам кода

этом множество из действительных векторов представляет собой множество вершин правильной фигуры в -мерном евклидовом пространстве, которая называется обобщенным октаэдром. Например, на рис. 14.5 для изображен четырехмерный октаэдр (он имеет 16 трехмерных граней и поэтому называется также -гранником).

Множество всех таких действительных векторов называется также множеством биортогональных сигналов (см. упражнение (43) гл. 1). Если такое же преобразование применить к словам кода то мы получим множество взаимно ортогональных действительных векторов.

обозначает значение функции на произвольном векторе из или, что эквивалентно, координате вектора в позиции, соответствующей и. Нам будет удобно ввести обозначение для действительного вектора, получающегося из двоичного вектора путем замены 1 на —1 и 0 на 1. Обозначим его через Таким образом, координата вектора стоящая в позиции, соответствующей и, равна:

Преобразование Адамара и смежные классы по коду

Напомним, что преобразование Адамара действительного вектора было определено в гл. 2 равенством

представляет собой действительный вектор длины Иначе, где симметричная матрица Адамара размерности равная

Следовательно,

или

Из (14.8) видно, что равно разности между числом нулей и числом единиц в двоичном векторе

Таким образом,

или

Аналогично

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

Теорема 1. Весовой спектр смежного класса по коду содержащего равен

Таким образом, весовой спектр смежного класса, содержащего определяется преобразованием Адамара вектора

Упражнение. (9). Доказать, что если весовой спектр смежного класса по коду От, содержащего равен то весовой спектр смежного класса по коду содержащего равен

Уравнения (14.13) и (14.14) означают, что ближайшими к словами кода являются те слова для которых величина имеет наибольшее значение. Пример. Для имеем:

Предположим, что Тогда (где обозначает —1). Согласно (14.8) коэффициенты преобразования Адамара равны:

Очевидно,

что соответствует (14.11).

Код состоит из векторов Согласно теореме 1 весовой спектр смежного класса этого кода, содержащего равен:

что имеет место на самом деле.

Коэффициенты преобразования Адамара вектора с координатами удовлетворяют следующим соотношениям ортогональности.

Лемма 2.

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

Внутренняя сумма равна Следовательно,

так как

Следствие 3. (Равенство Парсеваля

Отметим, что из следствия 3 и равенства (14.12) вытекает, что весовой спектр смежного класса удовлетворяет условию

Булевы функции и смежные классы по коду Слова кода представляют собой линейные функции (14.7) от Две булевы функции назовем эквивалентными, если разность

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

Теорема 4. Предположим, что булевы функции связаны равенством

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

Доказательство Согласно теореме 1 достаточно показать, что множества совпадают. Действительно,

Положим тогда

где

Таким образом, для того чтобы вытетить смежные классы с одним и тем же весовым спектром, необходимо ввести более сильное соотношение эквивалентности, а именно, определим эквивалентность равенством

где А — некоторая двоичная обратимая матрица; В — двоичный вектор и —константы (0 или 1). При таком определении все булевы функции из одного класса эквивалентности принадлежат к смежным классам по коду с одним и тем же спектром весов

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

и

имеют один и тот же спектр весов:

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

Рис. 14.6 Смежные классы по коду Рида-Маллера первого порядка длины

означает, что имеется 28 смежных классов со спектром весов где или может быть получена из этой функции при помощи преобразования вида (14 17) Эти 28 булевых функций называются максимально-нелинейными по причинам, которые станут ясными в последнем параграфе (см также упражнение (16).