15.2. Вычетные коды — хорошие коды с трудным декодированием

15.21. Определение. Если простое число, а делит то число называется вычетом степени по модулю если разрешимо сравнение

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

-удлиненный -вычетный код длины может быть построен путем присоединения общей проверки на четность к расширенному -вычетному коду.

15.22. Теорема. Пусть минимальный вес Хэмминга для кодовых слов расширенного -вычетного кода длины над не принадлежащих суженному коду, и предположим, что Тогда

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

множество вычетов вида где Тогда состоит из вычетов степени по модулю Положим Тогда

Циклические коды, порожденные многочленами эквивалентны. В двоичном случае эта эквивалентность вытекает из теоремы 5.81 и следствия 5.82, а в недвоичном случае — из непосредственного обобщения этих результатов. Если кодовое слово расширенного кода, не принадлежащее суженному коду, то кратно и не кратно Эквивалентные коды, порожденные многочленами соответственно содержат кодовые слова являющиеся перестановками кодового слова Все эти слова не кратны многочлену

Рассмотрим произведение Оно кратно многочлену и не кратно Следовательно,

где ненулевой скаляр поля Так как

и

то из китайской теоремы об остатках вытекает, что

Так как вес Хэмминга произведения нескольких многочленов по не превосходит произведения весов сомножителей, то из сравнения (15.221) следует, что

Так как простое, то имеет место строгое неравенство.

Наиболее важный класс вычетных кодов получается при Эти коды называются квадратично-вычетными кодами (КВ-кодами). Для KB-кодов теорема 15.22 означает, что Если то эту границу можно улучшить с помощью теоремы 15.23.

15.23. Теорема (Мэттсон — Соломон [1961]). Если простое и то минимальный вес Хэмминга кодовых слов расширенного с блоковой длиной не принадлежащих суженному КВ-коду, удовлетворяет неравенству

Доказательство. Как и в доказательстве теоремы 15.22, каждое слово кода с порождающим многочленом соответствует некоторому слову кода с порождающим многочленом Так как то -квадратичный невычет по взаимному многочлену При этом уравнение (15.221) запишется в виде

Если вес то вес не превосходит так как в произведение входят d членов с

Согласно теореме -коды длины над существуют тогда и только тогда, когда простое число, сравнимое с ±1 по Хотя порождающая матрица двоичного KB-кода может быть построена путем соответствующих сдвигов порождающего многочлена кода, выбор проверочной матрицы в виде, показанном на рис. 15.1, дает некоторые преимущества.

15.24. Теорема. Пусть множество (ненулевых) квадратичных вычетов по множество квадратичных невычетов. Тогда -матрица определенная равенствами

является порождающей для -удлиненного двоичного с блоковой длиной

Замечание. Хотя такая матрица содержит строк, размерность пространства ее строк равна только

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

Доказательство. Как видно из примера, указанного на рис. 15.1, строки матрицы не отмеченные символом являются циклическими сдвигами многочлена Если а — примитивный корень степени из единицы, то так что и, если то Если то так как сумма всех примитивных корней степени из единицы и она равна 1, потому что совпадает с коэффициентом при в круговом многочлене Следовательно, существует такой примитивный корень а степени из единицы, что если если

Кратные многочлена совпадают, таким образом, с кратными порождающего многочлена расширенного КВ-кода или суженного КВ-кода в зависимости от того, будет ли равно 0 или 1. Если то четно и . В этом случае кратные многочлена суть слова суженного КВ-кода с блоковой длиной Расширенный KB-код с блоковой длиной может быть построен путем -удлинения этого кода путем дописывания единичного вектора длины к порождающей матрице кода. Это приводит к матрице, описанной в формулировке теоремы. Если то нечетно и . В этом случае кратные многочлена являются словами расширенного КВ-кода с блоковой длиной Расширенный KB-код с блоковой длиной может быть построен из него путем добавления общей проверки на четность. Это также приводит к порождающей матрице, указанной в формулировке теоремы. Если квадрат примитивного элемента поля квадратичный невычет из то элементов множества можно упорядочить следующим образом: Как и на рис. 15.1, такое упорядочение координат приводит к порождающей матрице вида

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

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

порождающую матрицу можно привести к виду

где единичная матрица размерности квадратная циркулянтная матрица такой же размерности. Карлин [1969] показал, что такая форма порождающей матрицы двоичного КВ-кода очень полезна при исследовании весовой структуры кода. Так как порождающие матрицы многих хороших двоичных KB-кодов могут быть представлены в виде (15.242), то Мак-Вильямс [1968, 1970] недавно предприняла попытку изучения новых кодов такого вида.

Преимущество записи порождающей матрицы в форме, приведенной в теореме 15.24, показывает также доказательство следующей теоремы.

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

Доказательство. Мы утверждаем, что

Если один из индексов и или равен 0 или либо если то равенство (15.251) непосредственно вытекает из теоремы (15.25). Для разбора остальных случаев заметим, что тогда и только тогда, когда Так как то тогда И только тогда, когда что эквивалентно формуле (15.251).

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

Глизон, Прейндж, Ассмус и Мэттсон показали, что если в качестве выбрать скалярное кратное общей проверки на четность, то -удлиненный недвоичный KB-код инвариантен относительно преобразования где выбор знака определяется квадратичным характером и.

Все арифметические операции (за исключением ) можно определить в множестве очевидным образом. [Если а то а если а то ] Эти

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

Так как единственным преобразованием дробно-линейной группы, оставляющим на месте каждую координату вектора , является тождественное преобразование, то порядок этой группы равен Дробно-линейная группа содержит подгруппу индекса 2 всех подстановок вида

где Ее порядок равен Эта подгруппа называется проективной унимодулярной группой. Она порождается подстановками и где, а — примитивный элемент поля

Каждый -удлиненный двоичный циклический код инвариантен относительно подстановки так как эта подстановка есть циклический сдвиг. Согласно теореме -удлиненный двоичный KB-код инвариантен также относительно подстановки а по теореме 5.81 этот код инвариантен также относительно всех подстановок вида Это дает теорему 15.26.

15.26. Теорема. Каждый -удлиненный двоичный KB-код инвариантен относительно дважды транзитивной проективной унимодулярной группы где и

15.27. Следствие. Минимальный вес d расширенного двоичного КВ-кода с блоковой длиной есть четное число, удовлетворяющее неравенству если и неравенству если

Следствие 15.27 немедленно вытекает из теорем 15.26, 10.39, 15.22 и 15.23.

В силу следствия 15.27 минимальное расстояние расширенного двоичного KB-кода с блоковой длиной 23 (кода Голея) равно по меньшей мере 7. Согласно границе сферической упаковки (разд. 13.1), ни один двоичный код с такой же блоковой длиной и скоростью передачи информации не может иметь большее минимальное расстояние, так как Поэтому коды Голея совершенны: на них достигается граница сферической упаковки.

Скорость передачи информации для всех -удлиненных КВ-кодов равна Эти коды включают в себя -удлиненный двоичный код Хэмминга с блоковой длиной 8, исправляющий одну ошибку, -удлиненный двоичный код Голея с блоковой длиной -удлиненный троичный код Голея с блоковой длиной 12. Минимальное расстояние, которое гарантирует следствие 15.27, слабо растет с ростом Однако KB-коды часто имеют минимальный вес, превосходящий эту границу. Например, мы видели (теорема 16.33), что минимальное расстояние -удлиненного двоичного KB-кода с блоковой длиной 48 равно 12, а следствие 15.27 гарантирует минимальный вес

Так как -укороченные KB-коды также имеют хорошие параметры, то много исследований посвящено определению минимального веса -удлиненных двоичных КВ-кодов. Лучшие из известных результатов в этом направлении были получены Глизоном, Прейнджем (неопубликовано); Ассмусом, Мэттсоном и Турином [1965, 19661; Плесс [1963] и Карлином [1969]. Большинство из них подытожено на рис. 15.2. Результаты для получены Ассмусом и Мэттсоном [1966] на основе хитроумного метода, использующего таблицы круговых чисел, построенные Маскетом. Этот метод позволил им определить кодовые слова малого веса в некоторых KB-кодах длины при больших

В общем случае минимальное расстояние КВ-кодов с умеренными блоковыми длинами незначительно лучше минимального расстояния сравнимых БЧХ-кодов. Однако, к сожалению, KB-коды значительно труднее декодировать. Теоремы 15.22, 15.23, 15.27 и 16.33 дают нижнюю границу для минимального расстояния некоторых КВ-кодов, по их доказательства не приводят к реализуемым алгоритмам декодирования.

В общем случае декодеру нет необходимости определять ошибки в проверочных позициях. Это замечание лежит в основе так называемого перестановочного декодирования, введенного Мак-Вильямс [1964]. Декодер подходящим образом переставляет позиции полученного слова до тех пор, пока ошибки не окажутся сдвинутыми в проверочные позиции кода, после чего слово исправляется. Перестановочное декодирование хорошо применять к кодам, инвариантным

Рис. 15.2. (см. скан) Минимальное расстояние Хэмминга для некоторых расширенных КВ-кодов длины над При результаты получены Ассмусом и Мэттсоном [1966].

относительно большой группы подстановок. Как будет видно из задачи 15.3, некоторые -удлиненные KB-коды инвариантны относительно значительно более мощной группы подстановок, чем проективная унимодулярная группа. Однако, как показал Шаугнесси [1968], некоторые другие -удлиненные KB-коды инвариантны только относительно простой проективной унимодулярной группы. Хотя

перестановочное декодирование — один из наиболее простых методов декодирования КВ-кодов (включая и код Голея), он значительно сложнее декодирования сравнимых БЧХ-кодов. С практической точки зрения, относительно большое минимальное расстояние КВ-кодов и трудности в их декодировании делают эти коды более приемлемыми в тех приложениях, где пригодны неполные алгоритмы декодирования.