5.7. Коды, получаемые с помощью матриц Адамара

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

Теорема 5.1. Если существует матрица Адамара размерности то существует двоичный код из символов, образованный векторами, с минимальным расстоянием, равным (Это не обязательно линейный код.)

Доказательство. Пусть матрица Адамара. Код строится следующим образом. Возьмем совокупность из векторов где строки матрицы Н. Затем в каждом из векторов заменим все нулями, единицами. Тогда получится совокупность двоичных векторов длины Поскольку соответствующие компоненты векторов различны, то расстояние между векторами равно Поскольку векторы ортогональны, если то они должны совпадать в половине компонент и отличаться друг от друга в остальных компонентах, так что соответствующие двоичные векторы находятся на расстоянии . Ч. т. д.

Теорема 5.2. Если матрица Адамара размерности то матрица

является матрицей Адамара размерности

Доказательство. Очевидно, что матрица И является квадратной матрицей с элементами, равными +1 или —1. Скалярное произведение строк равно

Для любых других комбинаций строк

Следовательно, И — ортогональная матрица. Ч. т. д.

Легко проверить, что матрица

является матрицей Адамара, и, следовательно, матрица

в соответствии с теоремой 5.2 также является матрицей Адамара. Многократно применяя теорему 5.2, можно построить матрицу Адамара размерности для любого целого положительного Соответствующий ей код совпадает с кодом Рида — Маллера первого поряда и с кодом Макдональда. Действительно, семь ненулевых кодовых слов из кода, полученного с помощью матрицы образуют в точности последние четыре столбца матрицы С, приведенной на стр. 59, и, следовательно, код имеет модулярное представление (0, 0, 0. 1, 1, 1, 1). Вообще, модулярным представлением кода, полученного на основе матрицы является вектор, содержащий нулей, за которыми следуют единиц, если столбцы матрицы М в уравнении (3.8) упорядочены как двоичные числа.

Для других значений двоичные коды, получаемые с помощью матриц Адамара, не могут быть групповыми кодами, поскольку число кодовых векторов не является степенью 2. Можно легко показать, что если то должно быть кратно 4. Методы построения матриц Адамара были найдены Пэли [65], Боузом [5], Уильямсоном [80], [81], Брауэром [12], Стентоном и Спроттом [76]. Существование матриц Адамара доказано для следующих значений (здесь нечетное простое целое число):

Этот список заимствован из работы Боуза и Шрикханде [9], в которой можно найти также дальнейшие подробности относительно двоичных кодов. Перечисленные методы дают возможность строить матрицы Адамара размерности для всех значений кратных 4 и не превосходящих 200, за исключением 92, 116, 156, 184 и 1881). Остается не опровергнутым предположение о существовании матриц Адамара для любого кратного 4.