13.2. Совершенные коды

Получив некоторую границу, естественно попытаться найти случаи, когда эта граница достигается. Коды, для которых в границе сферической упаковки (13.11) достигается равенство, называются совершенными или плотно упакованными.

Двоичный код с повторениями при нечетной блоковой длине исправляет вплоть до ошибок. Для имеем Таким образом, двоичный код с повторениями и нечетной блоковой длиной является совершенным. Как будет показано в разд. 13.6, все другие совершенные коды должны иметь либо большую скорость передачи, либо малую блоковую длину. Теорема 13.21 описывает бесконечный класс совершенных кодов с большой скоростью и малой корректирующей способностью теорема 13.25 описывает бесконечный класс совершенных кодов в метрике Ли с малой блоковой длиной и произвольной корректирующей способностью.

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

13.21. Теорема. В метрике Хэмминга совершенный систематический код с исправлением одной ошибки и блоковой длиной над алфавитом из букв существует тогда и только тогда, когда

для некоторого числа

Если степень простого числа и удовлетворяет равенству (13.22), то в метрике Хэмминга существует совершенный линейный констациклический код, исправляющий одну ошибку. Циклический совершенный код, исправляющий одну ошибку в метрике Хэмминга, существует тогда и только тогда, когда имеет место равенство (13.22) и

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

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

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

Так как целое число, то число степень удовлетворяет равенству (13.22).

В метрике Ли значит, число кодовых слов совершенного кода, исправляющего одну ошибку, равно

Так как целое число, то число степень числа удовлетворяет уравнению (13.23). Существование совершенных негациклических кодов с блоковой длиной исправляющих одну ошибку, для нечетного простого гарантируется теоремой 9.34.

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

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

Любой ненулевой синдром может быть записан в виде где Так как то этот синдром, очевидно, соответствует одной ошибке величины с локатором

При этот совершенный код с исправлением одной ошибки является циклическим примитивным двоичным БЧХ-кодом. Однако, при он уже не циклический, так как констациклический и его кодовые слова — многочлены некоторого идеала в кольце многочленов по

Если то над полем в метрике Хэмминга существует циклический совершенный код с блоковой длиной исправляющий одну ошибку. В качестве корней порождающего многочлена этого кода могут быть выбраны элементы где и примитивный корень степени из единицы. В этом случае мы получим БЧХ-код с конструктивным расстоянием Хзмминга 2. Однако можно положить где а — другой примитивный корень степени из единицы, решение сравнения Тогда и среди корней порождающего многочлена имеются две последовательные степени элемента а. При этом возникает БЧХ-код общего вида с расстоянием Хэмминга 3, согласно разд. 10.3.

Если н. о. д. , то над полем в метрике Хэмминга никакой совершенный код с блоковой длиной исправляющий одну ошибку, не может быть циклическим. Порождающий многочлен такого кода должен быть неприводимым делителем многочлена Но где а — примитивный элемент поля Следовательно, любой неприводимый делитель многочлена имеет делитель степени вес Хэмминга которого равен 2.

Известны также и другие классы совершенных кодов с исправлением одной ошибки. Васильев [1962] и Шёнгейм [1968] построили много систематических нелинейных совершенных кодов, исправляющих одну ошибку. Ллойд [1957] и Рус [1965] показали, что если существуют некоторые другие нелинейные совершенные коды, то они также должны иметь определенную алгебраическую структуру. Представляется также возможным существование совершенных кодов с метрикой Хэмминга, исправляющих одну ошибку над алфавитом, порядок которого не есть степень простого числа. В настоящее время не известно ни одного примера таких кодов. Голомб и Познер [1964] показали, что при в метрике Хэмминга нет ни одного кода, исправляющего одиночные ошибки. Часть своего доказательства они приписывают Блоку и Холлу.

Теорема 13.25 доказывает существование коротких совершенных кодов над алфавитом составного порядка, исправляющих несколько ошибок в метрике Ли.

13.25. Теорема. Для любого натурального над кольцом классов вычетов в метрике Ли существует совершенный код с блоковой длиной исправляющий ошибок. Этот код является негациклическим и порождается многочленом .

Доказательство. Как видно из рис. 13.3, множество векторов ошибок для которых может быть разбито на пять классов:

Рис. 13.3. Двумерный шар с радиусом Ли, равным 3,

класс 3:

класс 4:

класс 5:

Число векторов ошибок в каждом из классов 1, 2, 3 и 4 равно так что общее число векторов ошибок с весом Ли равно Следовательно, любой код длины над кольцом вычетов исправляющий ошибок в метрике Ли, является совершенным.

Покажем теперь, что минимальный вес для негациклического кода с порождающим многочленом равен Действительно, пусть ненулевое кодовое слово веса 21. Предположим, что координата с меньшим модулем (в противном случае можно было бы рассмотреть негациклический сдвиг исходного слова. Если то так что , где Так как кратен то Так как то либо либо причем равенство достигается тогда и только тогда, когда Следовательно, минимальный вес любого ненулевого кодового слова равен Он достигается на словах и их негациклических сдвигах.

13.26. Следствие. Если число делит то над алфавитом вычетов в метрике Ли существует совершенный код длины исправляющий ошибок.

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

Теорема 13.25 гарантирует существование совершенных линейных кодов в метрике Ли над некоторыми кольцами чисел, не являющимися полями. Хорошие линейные коды над такими алфавитами весьма исключительны. Например, Леви [1964] показал, что лучшие из длинных линейных кодов над некоторыми алфавитами, не являющимися полями, обеспечивают минимальное расстояние, лежащее существенно ниже известных нижних границ (теорема 13.71) для нелинейных кодов над такими алфавитами.

На рис. 13.4 дается геометрическая интерпретация совершенного кода длины 2 над кольцом вычетов исправляющего 3 ошибки в метрике Ли. 25 кодовых слов обозначены жирными буквами А,

(кликните для просмотра скана)

(Например, ) Буква в каждой из 625 клеток таблицы соответствует тому слову, которое должен выбирать декодер, исходя из полученного слова. Например, если получено слово [11,7], то декодер декодирует его как так как слово является к нему ближайшим. Аналогично, полученное слово [0,4] будет декодировано как

Верхняя строка на рис. 13.4 является соседней с нижней, а левый столбец — соседним с правым: пространство, изображенное на рис. 13.4, топологически эквивалентно тору. С этой точки зрения задача конструирования совершенных кодов в метрике Ли эквивалентна задаче сферической упаковки тора. Рис. 13.4 иллюстрирует упаковку тора размерами двумерными сферами радиуса 3.

Голомб и Велч [1968] показали, что эта задача является частным случаем более общей задачи об упаковке (polyomino-packing problem). Они высказали гипотезу, что при не существует совершенных кодов в метрике Ли, и доказали несколько частных случаев этого предположения.

Помимо двоичных кодов с повторением известны только два совершенных кода с так называемые коды Голея. Оба они являются циклическими. Двоичный код Голея имеет блоковую длину 23, скорость передачи 12/23 и совпадает с БЧХ-кодом, исправляющим две ошибки, рассмотренным в примере 5.6. БЧХ-конструкция этого кода гарантирует, что минимальное расстояние этого кода 5. Однако истинное минимальное расстояние кода равно 7. Он является совершенным и исправляет три ошибки. Троичный код Голея имеет блоковую длину 11, скорость 6/11. Это совершенный код с исправлением двух ошибок. Оба кода Голея принадлежат к кодам, построенным с помощью квадратичных вычетов, которые мы будем рассматривать в разд. 15.2.

Другие совершенные коды не известны. Числа для которых делит редки. Но даже для таких чисел может не существовать совершенных кодов. Например, в двоичном случае Однако Голей [1949], Кохен [1964]и Элтер [1968] доказали, что для и 9 троичный код Голея является единственным нетривиальным совершенным кодом, исправляющим две ошибки.

Для линейного совершенного кода с исправлением ошибок каждое слово веса должно быть лидером смежного класса и каждый лидер смежного класса должен иметь вес

Если каждое слово веса является лидером смежного класса и вес каждого лидера смежного класса то код называется квазисовершенным. Двоичных квазисовершенных кодов оказалось значительно больше, чем двоичных совершенных кодов. Горенстейн, Питерсон и Цирлер [1960] показали, что все двоичные примитивные БЧХ-коды с исправлением двух ошибок являются квазисовершенными, а Вагнер [1966, 1967] построил несколько нециклических

квазисовершенных двоичных кодов. Как будет показано в разд. 13.6, очень длинные коды могут быть квазисовершенными только тогда, когда их скорость передачи очень велика.