13.5. ВЕКТОРЫ МИНИМАЛЬНОГО ВЕСА ПОРОЖДАЮТ КОД

Теорема 10. Векторы инцидентности проективных подпространств геометрии порождают код при

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

Как обычно, представим подмножество этих точек в виде многочлена

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

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

Пусть код, порождаемый всеми многочленами где — некоторое подпространство Очевидно, циклический код, содержащийся в теорема утверждает, что на самом деле Мы докажем это, показав, что

Размерность кода равна числу таких элементов что они не являются нулями кода т. е. числу таких элементов, что для некоторого Имеем:

где суммирование распространяется на все ненулевые -после-довательности Обозначим последнее выражение через Тогда, полагая имеем:

Это выражение является однородным многочленом степени от

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

Итак, необходимо подсчитать число таких многочленов которые содержат коэффициенты, не равные нулю по модулю 2. Заметим, что: (i) такой многочлен не может равняться тождественно нулю, и должны быть

линейно зависимы (упражнение (8)). По теореме Лукаса полиномиальный коэффициент

несравним с нулем по модулю 2 тогда и только тогда, когда для всех

где обозначает цифру в двоичном разложении числа х.

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

Число таких в диапазоне равно

Упражнение. (8). Доказать, что если линейно зависимы, то многочлен по модулю 2 равен тождественно нулю.

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

Теорема 11. Выколотый РМ-код является циклическим кодом, все нули которого исчерпываются элементами удовлетворяющими условиям и .

Порождающий и проверочный многочлены выколотого РМ кода для —1 равны:

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

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

а Это приводит к замене на на Соответственно получаем:

Если порождающий многочлен кода задан формулой (13.7), то согласно теореме 4 гл. 7 формула (13.10) задает порождающий многочлен дуального кода.

Порождающий идемпотент кода равен

или, что эквивалентно (опять при замене а на

где пробегает множество представителей циклотомических классов, определено так же, как в гл. 8.

Порождающий идемпотент кода, дуального согласно теореме 5 гл. 8 равен:

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

где произвольный многочлен.

Вложенные семейства. На рис. 13.5 показано, как вкладываются друг в друга семейства кодов БЧХ и выколотых РМ кодов. Здесь через обозначен код БЧХ с конструктивным расстоянием а двоичные числа в фигурных скобках задают показатели нулей кода (по одному из каждого циклотомического класса).

Рис. 13.5. Вложенные семейства кодов БЧХ и выколотых РМ-кодов

При движении вниз страницы объем кодов становится меньше. Мы видим, что

код БЧХ с конструктивным расстоянием

расширенный код БЧХ с конструктивным расстоянием

Теорема 12. Векторы инцидентности -мерных плоскостей в порождают код

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

Теорема 13. (Мак-Вильямс и Манн.) Ранг над матрицы инцидентности гиперплоскостей в -мерной евклидовой или в проективной геометрии над равен

где равно для проективной и —1 для евклидовой геометрии.

Задача (нерешенная). (13.1). Существует ли кодовое слово которое равно вектору инцидентности некоторого подпространства и порождает код