13.4. РИДА-МАЛЕРА КОДЫ И ГЕОМЕТРИИ

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

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

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

Вектор инцидентности подмножества равен Из рис. 13.1 видно, что этот вектор является словом кода

Для произвольного целого введем дополнения векторов следующим образом:

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

Например, сами векторы являются характеристическими векторами гиперплоскостей, проходящих через начало координат; векторы описывают подпространства размерности (Естественно, что в геометрии имеются помимо плоскостей и другие гиперплоскости, проходящие через начало координат. Например, ни одна из гиперплоскостей не проходит через точку Аналогично подпространства не исчерпывают всех подпространств равномерности )

Одним из преимуществ геометрического языка является возможность точного указания слов минимального веса, лежащих в РМ коде порядка и длины эти слова являются векторами инцидентности -мерных плоскостей в Этот факт доказывается в теоремах 5 и 7. В теореме 9 этот факт используется для определения числа кодовых слов минимального веса. Затем в § 13.5 мы показываем, что кодовые слова минимального веса порождают код По ходу дела мы доказываем, что выколотый код является циклическим. Доказательства, содержащиеся в § 13.4 и 13 5, могут быть при первом чтении опущены.

Пусть — некоторая гиперплоскость в По определению вектор инцидентности задается точками удовлетворяющими некоторому линейному уравнению относительно Другими словами, булева функция представляет собой линейную функцию от следовательно, задает слово веса в коде

Заметим, что если — вектор инцидентности множества то и является вектором инцидентности множества Теперь можно перейти к первой основной теореме.

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

Например, 14 слов веса 4 в [8, 4, 4] расширенном коде Хэмминга являются 14 плоскостями в

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

Лемма 6. (Ротшильд и Ван Линт) Пусть — подмножество в такое, что или для всех гиперплоскостей в Тогда является -мерной плоскостью в

Доказательство проводится индукцией по При результат тривиален.

(i). Предположим, что для некоторого выполняется равенство Тогда т. е. . Пусть X — некоторая гиперплоскость . В найдется другая гиперплоскость такая, что т. е. или По предположению индукции является -мерной плоскостью в следовательно, в

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

(iii). Остается рассмотреть случай, когда для всех . Имеем:

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

Обратным теореме 5 является следующее утверждение:

Теорема 7. Вектор инцидентности любой -мерной плоскости в является словом кода

Доказательство. Любая -мерная плоскость в состоит из всех точек, которые удовлетворяют системе линейных уравнений над скажем:

или, что эчвивалзнтно,

Это можно заменить одним уравнением

т. е. некоторым многочленом от переменных степень которого не превосходит Следовательно, вектор инцидентности зтой плоскости попадает в

Соединяя теоремы 5 и 7, получаем:

Теорема 8. Множество слов минимального веса в коде в точности совпадает с множеством векторов инцидентности -мерных плоскостей в

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

Теорема 9. Число слов минимального веса:

(a) в коде равно

(b) в коде равно

Доказательство. Теоремы 3 и 5 приложения В.