13.5. Эквидистантные коды

Для того чтобы код достигал границы, указанной в теореме 13 49, его минимальное расстояние должно совпадать со средним расстоянием Это возможно только тогда, когда расстояние между любыми двумя различными кодовыми словами одно и то же (такой код называется эквидистантным)

Наиболее важный класс эквидистантных кодов описывается определением 13 51 и теоремой 13 52

13.51. Определение Регистровым кодом максимальной длины называется циклический, негациклический или констациклический код, проверочный многочлен которого является примитивным многочленом степени к над полем Если блоковая длина кода, то делит где и порядок равен

13.52. Теорема. Каждое ненулевое кодовое слово циклического, негациклического или констациклического регистрового кода максимальной длины является циклическим, негациклическим или констациклическим сдвигом любого другого ненулевого кодового слова Таким образом, в метрике Хэмминга все регистровые коды максимальной длины, а в метрике Ли все циклические и негациклические регистровые коды максимальной длины являются эквидистантными.

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

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

Для некоторых регистровых кодов максимальной длины теорема 13.52 указывает истинный минимальный вес, больший, чем можно было бы предположить из других соображений. Например, рассмотрим негациклический регистровый код максимальной длины с блоковой длиной 63 над (Этот код приведен в табл. 9.1.) Согласно теореме 9.34, код исправляет в метрике Ли 63 ошибки. Однако, согласно теореме 13.52, вес каждого ненулевого слова этого кода равен Следовательно, код исправляет в 16 раз больше ошибок, чем это следует из теоремы 9.34.

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

Над полем регистровые коды максимальной длины имеют блоковую длину и содержат кодовых слов. Для многих других значений К эквидистантные двоичные коды из К слов с блоковой длиной могут быть построены на основе матриц Адамара. Матрицей Адамара называется ортогональная матрица, элементами которой являются числа +1 и —1. Например,

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

Легко показать, что -матрицы Адамара существуют только тогда, когда или К кратно 4. Не доказана и не опровергнута гипотеза, что для всех таких К существуют матрицы Адамара. Первый контрпример возможен при ; для всех меньших значений К (и многих больших значений) матрицы Адамара могут быть построены с помощью методов, предложенных Холлом [1967] или в более ранних работах Спенсом [1967] и Гёталсом и Зейделем [1967].

В то время как полное расстояние произвольного линейного кода равно где задается теоремой 13.49, нелинейный код может иметь и меньшее полное расстояние. Нелинейный код может быть эквидистантным даже в тех случаях, когда его кодовое расстояние лежит намного ниже границы Плоткина. Например, двоичный код, словами которого являются строки единичной матрицы, является эквидистантным с расстоянием 2. Хотя этот код является тривиальным, ничего лучшего построить нельзя, если потребовать, чтобы каждый вектор имел вес 1. Вообще, если на вес каждого кодового слова наложить некоторые ограничения, среднее расстояние между парами слов не может быть большим. Это замечание лежит в основе вычисления границы Элайеса, которая выводится в следующем разделе.