Глава 2. Нелинейные коды, матрицы Адамара, t-схемы и код Голея
2.1. НЕЛИНЕЙНЫЕ КОДЫ
Одно из основных назначений кодов заключается в исправлении ошибок в каналах связи с шумами, и линейные коды, введенные в гл. 1, имеют много практических преимуществ с этой точки зрения. Но если мы хотим получить наибольшее возможное число кодовых слов с заданным минимальным расстоянием, то иногда необходимо использовать нелинейные коды.
Например, предположим, что нам нужен код длины 11, исправляющий две ошибки. Наибольший линейный код содержит 16 кодовых слов, в то время как имеется нелинейный код, показанный на рис. 2.1, содержащий 24 кодовых слова, что дает увеличение на 50%. (Это код Адамара, см. § 2.3.)
Определим нелинейные коды следующим образом.
Определение. Назовем
-кодом множество из
векторов длины
(с компонентами из некоторого поля
такое, что любые два вектора различаются между собой по крайней мере в
позициях и
является наибольшим числом с этим свойством.
В этой главе все коды будут двоичными. Еще раз напомним, что квадратные скобки обозначают линейный код, в то время как круглые скобки используются для кода, который может быть (или не быть) линейным. Двоичный линейный
-код является
-кодом.
Обычно мы предполагаем, что не существует координатной позиции, в которой каждое кодовое слово имеет нуль (в противном случае это был бы
-код). Кроме того, так как расстояния между кодовыми словами не изменяются, если ко всем кодовым словам прибавить фиксированный вектор, можно при желании предположить, что код содержит нулевой вектор.
Будем говорить, что два
двоичных кода
и
эквивалентны, если один может быть получен из другого перестановкой
символов и добавлением фиксированного вектора, или более формально, если существуют подстановка
на множестве
и вектор а такие, что
Если
и
— линейные коды, то это определение сводится к определению эквивалентности, данному в § 1.7. Так, например, коды
эквивалентны (если положить
).
Рис. 21. Пример нелинейного (11,24, 5)-кода Адамара (первые 12 строк образуют
-код Адамара 12; все 24 строки образуют (11, 24, 5)-код Адамара
В общем случае эквивалентность недвоичных кодов определяется следующим образом. Пусть и
будут кодами длины
над полем из
элементов. Тогда
и эквивалентны, если существуют
подстановок
пп на множестве из
элементов и подстановка о на множестве
(позиций) такие, что
Другими словами, сначала в каждой позиции переставляются элементы поля, а затем сами координатные позиции. Если оба кода
являются линейными, то могут быть использованы только подстановки
порожденные скалярными множителями и автоморфизмами поля (см. § 4.6).
Определение. Обозначим через
число кодовых слов веса
-коде
Числа
называются весовым спектром кода
Ясно, что
Весовой спектр мы уже использовали при вычислении вероятностей ошибки в гл. 1.
Если вектор 0 является кодовым словом, то наблюдатель, находящийся в нулевом слове, увидел бы на расстоянии
от себя
кодовых слов. Для линейного кода картина была бы одной и той же в любой кодовой точке. (Почему?) Однако в нелинейном коде не обязательно так, как показывает пример кода
(Если же это справедливо, то говорят, что код инвариантен относительно расстояния. Код Нордстрома — Робинсона (§ 2.8) инвариантен относительно расстояния; другие примеры будут даны в гл. 6.) Поэтому для нелинейного кода полезно рассматривать среднее число кодовых слов на расстоянии
от фиксированного кодового слова.
Определение. Спектр расстояний кода
состоит из чисел
где
Заметим, что
Для линейных кодов весовой спектр и спектр расстояний совладают. Кроме того, код а
полученный сдвигом, имеет такой же спектр расстояний, что и код
Полезно геометрическое представление этих кодов. Двоичный вектор
длины
задает координаты вершины единичного куба размерности
. В таком случае
-код представляет собой некоторое подмножество этих вершин (рис. 2.2).
На этом геометрическом языке проблема теории кодирования заключается в выборе как можно большего числа вершин куба с заданным попарным расстоянием между ними.
Эта проблема представляет собой проблему упаковки, так как в коде с минимальным расстоянием
евклидово расстояние между кодовыми словами не менее чем
Поэтому построение
Рис. 2.2. Куб, иллюстрирующий
-код (а); четырехмерный куб, иллюстрирующий
-код (б)