6.9. КОДЫ НАД GF(q)

Большинство результатов этой главы может быть распространено на коды над GF(q). Сначала надо ввести, так же как это было сделано в § 6.2, параметры с той лишь разницей, что вес и расстояние заменяются соответственно на вес Хэмминга и расстояние Хэмминга.

Уравнение (6.1) теперь запишется в виде

где а теорема 2 формулируется следующим образом.

Теорема 2. Если то

для всех где Аналогично изменяется и теорема 4, в то время как лемма 1 и теоремы 3, 6, следствие 5 остаются неизменными.

Так как в рассматриваемом случае не существует больше единственного вектора веса то нельзя ввести параметр и поэтому не существует аналога теоремы 7.

t-схемы, получаемые из недвоичных кодов. Если — линейный код длины над то попытаемся образовать хему из кодовых слов веса следующим образом. Множество из координат, в которых кодовое слово имеет ненулевые элементы, назовем опорным множеством кодового слова. Конечно (так как данный код — линейный), кодовых слов, пропорциональных данному слову, имеют одно и то же опорное множество. Каждое такое опорное множество (взятое, конечно, один раз, а не и составляет блок -схемы.

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

Например, рассмотрим код из гл. 1. Кодовые слова имеет опорное множество Таким образом, восемь кодовых слов веса 3 дают следующие четыре блока образующих тривиальную -схему.

Приведем теперь теорему, дающую достаточные условия тою, что наш метод построения приведет к -схеме.

Теорема 29. (Ассмус и Мэттсон.) Пусть линейный код над GF(q). Предположим, что мы можем найти целое число где такое, что имеется самое большое чисел удовлетворяющих условию (Здесь, как и в § 6.2, числа представляют собой значения весов, встречающихся в коде Тогда опорные множества кодовых слов веса в коде образуют -схему.

Доказательство. Пусть любое множество координат и пусть (как и в § 6.5) код образован удалением этих координат из Таким образом, — это -код. Дуальным этому коду является код По предположению, код имеет не более ненулевых весов, а дуальный ему код имеет минимальное расстояние Поэтому мы можем применить теорему 2 и найти весовой спектр кода а следовательно, согласно теореме 13. гл. 5 мы можем найти также и весовой спектр кода . В частности, это дает то, что число кодовых слов веса в коде (обозначим его через а) не зависит от выбора

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

Пример. Самодуальный код из гл. 1 содержит только кодовые слова веса 0 и 3. Таким образом, Следовательно, мы можем выбрать и заключить на основании теоремы 29, что опорные множества кодовых слов веса 3 образуют -схему. На самом делё, как мы видели выше, они образуют -схе-му, поэтому утверждение теоремы не всегда приводит к наилучшему возможному результату.

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

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

Далее доказательство аналогично доказательству теоремы 29.

Например, троичный [12, 6, 6]-код Голея (см. гл. 20) является самодуальным кодом со значениями весов 0, 6, 9, 12. Тогда и поэтому опорные множества кодовых слов весов 6 и 9 образуют -схемы.

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

Следствие 31. Пусть 43— двоичный линейный -код. Если выполняются условия теоремы 29, то кодовые слова любого веса образуют -схему.

Пример. Для расширенного [24, 12, 8]-кода Голея можно выбрать так как имеется числа в интервале а именно 8, 12, 16. Таким образом, кодовые слова любого веса образуют -схему, в чем мы уже убедились ранее.

Нам не удалось обобщить теорему 13, и поэтому мы сформулируем следующие задачи.

Задачи (нерешенные). (6.4) Обобщить теорему 13 на случай GF(q).

Упражнение. (13) Показать, что следствие 31 влечет следствие 14.

(6.5). Верно ли, что следствие 31 сильнее, чем следствие 14?

Весовые спектры сдвигов кода и совершенные коды. Все результаты § 6.6, 6.8 справедливы и для кодов над GF(q). В двоичном случае доказательства проводятся на языке групповой алгебры, введенной в гл. 5. Для кодов над GF(q) доказательства совершенно аналогичны, но требуют более разработанного аппарата групповой алгебры, который мы не намерены вводить.

Например, теорема Ллойда звучит следующим образом.

Теорема 32 (Ллойд). Если существует совершенный -код над то многочлен Ллойда

имеет целых корней удовлетворяющих условию Здесь многочлен определяется выражением (5.53).

Упражнение. (14). Пусть линейный -код над GF(q). Показать, что 43 является совершенным кодом, если и только если кодовые слова веса образуют

Показать, что если совершенный код, то число кодовых слов веса в коде равно: