17.6. ПОСТРОЕНИЕ ЛИНЕЙНЫХ КОДОВ; АНТИКОДЫ

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

достигает границы Граисмера, так же как и код, порождающая матрица которого состоит из нескольких экземпляров матрицы выписанных друг за другом

Замечательный способ построения хороших линейных кодов заключается в следующем надо взять матрицу или несколько экземпляров и вычеркнуть некоторые столбцы (см рис 17 1а и

Вычеркиваемые столбцы сами образуют порождающую матрицу так называемого антикода (согласно Фореллу и др [418, 420, 421], см также [889], [1098] Антикод представляет собой код, у которого расстояния между кодовыми словами ограничены сверху Допускается даже нулевое расстояние между кодовыми словами, и поэтому антикод может содержать одинаковые кодовые слова

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

Пример (1) Матрица

порождает антикод

длины с 23 кодовыми словами и максимальным расстоянием Каждое кодовое слово встречается дважды Аналогично для любого легко строится антикод длины 3 с кодовыми словами и максимальным расстоянием 2

Использование антикода для построения новых кодов. Предположим сначала, что порождающая -матрица антикода имеет различные столбцы Тогда (см. рис. 17.1а) порождающая матрица нового кода получается вычеркиванием из матрицы столбцов порождающей матрицы антикода Ясно, что длина нового кода равна размерность не более и минимальное расстояние

Рис. 17.la Использование антикода для построения новых кодов

Рис. 17.lb Случай, когда антикод содержит повторяющиеся столбцы

Пример (2) Если то, вычеркивая из матрицы столбцы антикода из примера (1), мы получим -код

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

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

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

Примеры (3) Вычеркнем прямую (состоящую из трех точек) из матрицы

(4) Образуем для антикод, столбцами которого являются 15 точек проективного подпространства размерности 3 и еще одна точка, не лежащая в этом подпространстве, как изображено на рис. 17.2

Рис. 17.2 Порождающая матрица антикода с параметрами

Вычеркивание этих столбцов из матрицы приводит к [-коду, удовлетворяющему границе Грайсмера

(5) Выберем в проективное подпространство размерности -плоскость), содержащее 31 точку, и -плоскость содержащую 15 точек Эти подпространства пересекаются по плоскости (состоящей из 7 точек) Выберем плоскость которая не пересекается с пересекаются по прямой пересекаются в точке Выберем прямую которая не пересекается с или (и пересекается с в точке Наконец, выберем точку которая не принадлежит ни одному из выбранных В качестве столбцов порождающей матрицы антикода возьмем точек конфигураций Столбцы встречаются в этой матрице дважды Максимальный вес равен Вычеркнем столбцы этого антикода из двух экземпляров матрицы как показано на рисунке

Заметим, что точки конфигураций вычеркиваются дважды, по одному разу из каждого экземпляра матрицы

Результирующий код имеет параметры и удовлетворяет границе Грайсмера.

Упражнения. (23). Используя прямую и -плоскость в получить аитикод с параметрами следовательно, получить -код.

(24). Построить -код.

Общий метод пдстроения (Соломон и Стиффлер [1257], Белов и др. [102]; см. также Оллтоп [25]). Следующий способ построения антикодов из подпространств обобщает предыдущие примеры и приводит к широкому классу кодов, достигающих границы Грайсмера.

Для заданных положим

где

Предположим, что мы можем найти такую совокупность проективных подпространств состоит из точек), которая удовлетворяет следующему свойству:

Пересечение любых подпространств В,- пусто. (17.54)

Это означает, что любая точка принадлежит самое большее подпространствам Составим из столбцов антикод; ни один из его столбцов не встречается более раз. Новый код получается вычеркиванием этого антикода из экземпляров матрицы Код имеет длину

размерность минимальное расстояние, определяемое формулой (17.53), и достигает границы Грайсмера. На рис. ПА.2 эти коды обозначаются буквами

Теорема 25. (Белов и др. Описанное построение возможно тогда и только тогда, когда

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

Нам надо показать, что если любое -подмножество множества (когда ) или если (когда ), то Действительно,

так как по условию теоремы

(Достаточность). Предположим, что построение возможно, т. е. условие (17.54) выполняется. Если то ничего доказывать не надо. Предположим, что Тогда согласно (17.54) для любого -множества I выполняется условие . Но в силу упражнения (27)

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

Следствие 26. Если для заданных выполняется неравенство

где числа определяются условиями (17.53), то существует -код, достигающий границы Грайсмера.

Заметим, что -код из всех слов четного веса достигает границы Грайсмера. В этом случае Поэтому условия, сформулированные в следствии, не являются необходимыми для того, чтобы код достигал границы Грайсмера. Как показали Баумерт и Мак-Элис [87], для заданного граница Грайсмера достигается при всех достаточно больших

Задача (нерешенная). (17.7). Найти необходимые и достаточные условия, которым должны удовлетворять числа чтобы граница Грайсмера (17.52) была точной.

Описанный метод построения может быть использован для нахождения линейных кодов наибольшей мощности в диапазоне

Теорема 27. (Вентурини [1369]; переоткрыто Пейтлом [1027]. Обобщение на см. в работе Пейтла [1028].) Пусть для заданных

где целые положительные числа и или 1, и пусть

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

Доказательство опускается. Чтобы построить такой -код, мы поступаем следующим образом. Положим Тогда

и из (17.55) следует, что

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

Упражнение. (25). Показать, что Таким образом, может быть намного меньше чем

Теорема 28. Если -код достигает границы Грайсмера, то не имеет одинаковых столбцов.

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

Обозначим через -код, порожденный матрицей Тогда согласно оценке (17.52)

поэтому код не достигает границы Грайсмера.

Определение. Оптимальным называется антикод наибольшей длины для заданных значений размерности и максимального расстояния 8.

Предположим, что вычеркиваем антикод из соответствующего числа экземпляров симплексного кода. Ясно, что если результирующий код достигает границы Грайсмера, то этот антикод оптимален. Таким образом, описанные выше способы построения дают много оптимальных антикодов, образованных из подпространств. В частности, антикоды, рассмотренные в примерах 3, 4, 5, оптимальны. Форрел и Форрег [420, 421] привели таблицы оптимальных антикодов.

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

Доказательство. По условию теоремы

Из (17.59) и равенства

справедливого для любого —1, вытекает, что

и, следовательно, код достигает границы Грайсмера.

Эта теорема часто позволяет нам получать из оптимального антикода с параметрами оптимальный антикод с параметрами

Простое геометрическое описание имеют не все оптимальные антикоды. Так, -код из всех слов четного веса

достигает границы Грайсмера. Таким образом, представляет собой оптимальный антикод длины с 2 кодовыми словами и максимальным расстоянием —2. Согласно теореме 29 для всех мы получаем оптимальные антикоды, имеющие кодовых слов, и, следовательно, новые коды, достигающие границы Грайсмера.

Пример. (6).

Первые два антикода состоят из трех точек одной прямой. Однако другие антикоды не имеют подобного геометрического описания. Например, антикод из второго примера состоит из 10 точек и 10 прямых в причем каждая прямая состоит из трех точек и через каждую точку проходят три прямые, как изображено на рис. 17.3. На рисунке изображена конфигурация Дезарга; так она называется потому, что возникает при доказательстве теоремы Дезарга (см. книгу Гильберта и Кон-Фоссена [654, рис. 135, с. 123]).

Рис. 17.3 Конфигурация Дезарга

Задача (нерешенная). (17.8). Имеется ли естественное описание геометрических конфигураций, соответствующих другим оптимальным антикодам?

Упражнение. (26). ([420].) Так как антикод может содержать одинаковые слова, то антикоды можно «объединять», чтобы получать новые.

(a). Построить антикоды с параметрами соответственно.

(b). Показать, что конструкции

(где 0 и 1 обозначают столбцы из нулей и единиц соответственно) образуют антикоды с параметрами

Получить, следовательно, и -коды.

В заключение на рис. 17.4 перечислены некоторые

оптимальные линейные коды с k = 6 (дающие, таким образом, значения

Намного более полную таблицу привели Хелгерт и Стинафф [636].

Рис. 17.4. Оптимальные коды с

Упражнения. (27). ([102].) Пусть — двоичный линейный код для Показать, что

{Указание. Использовать индукцию по .]

(28). Показать, что если — оптимальный антикод с четным то к порождающей матрице может быть добавлен еще один столбец, что приведет снова к оптимальному антикоду с параметрами .

(29). ([889].) Пусть код имеет порождающую матрицу где А — матрица размера строки которой имеют вес не более единицы, а столбцы имеют четный вес более нуля. Отсюда следует, что Показать, что представляет собой

-код с максимальным весом