20. МАТРИЦЫ АДАМАРА И КОДИРОВАНИЕ
Из определения следует, что для любой пары строк с номерами I и / (г'#/) верно равенство:
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века *). Сравнительно недавно (в 1960 г.) было замечено, что эти матрицы могут быть использованы для построения колов
Квадратная матрица Н порядка п с элементами ±1 называется матрицей Адамара, если выполняется условие
Вот несколько примеров матриц Адамара:
Рассмотрим произвольную матрицу Адамара
Таким образом, различные строки матрицы Адамара попарно ортогональны. Далее, число слагаемых в (1), равных + 1, должно совпадать с числом слагаемых, равных —1. Следовательно, п четно и любые две строки совпадают ровно в л/2 позициях и различаются в остальных.
Пусть теперь Л — двоичная матрица, получающаяся из матрицы Н заменой элемента +1 на 0 —1 на 1. Множество векторов-строк матрицы А образует тогда код с расстоянием Хемминга между любыми кодовыми словами, равным я/2. Так, из матрицы Адамара порядка 8 получаем матрицу А, задающую код длины 8 с кодовым расстоянием 4?
Не меняя кодового расстояния, можно уменьшить длину кода, если отбросить первый (нулевой) символ каждого слова.
Указанным образом из всякой матрицы Адамара порядка л можно получить двоичный код Адамара типа (п—1, п, п/2) (л—1 —длина кодового слова, п — число слов кода, п/2 — кодовое расстояние). Это, как правило, код, не являющийся линейным.
С матрицей А связаны еще два кода, которые тоже называют кодами Адамара.
Первый из них получается так. Перейдем от матрицы А к матрице А, заменив все элементы матрицы А их дополнениями (т. е. заменив единицы нулями, а нули — единицами). Тогда строки матриц Л и Л в совокупности образуют код типа (п, 2л, п/2), что легко проверяется с помощью равенства (1).
Другой код Адамара получается из предыдущего отбрасыванием первого символа в каждом кодовом слове.
Это будет код типа
Например, из матрицы (2) можно получить таким способом коды Адамара типов (8,16, 4) и (7, 16, 3).
Коды Адамара, как видно из их определения, обладают интересной особенностью: расстояние между любыми двумя кодовыми словами одинаково и совпадает поэтому с кодовым расстоянием. Подобные коды называют эквидистантными, и в некоторых случаях их использование дает особые преимущества.
Коды Адамара, обладая большим кодовым расстоянием, позволяют соответственно исправить и большое количество ошибок (первые два из них исправляют ошибки примерно в четверти позиций кодового слова). Достигается это, конечно, ценой высокой избыточности.
Для построения и реализации кода Адамара той или иной длины необходимо построить сначала матрицу Адамара соответствующего порядка. Надо сказать, что такое построение является совсем нелегким делом, и этому вопросу посвящен внушительный раздел современной комбинаторики. Некоторые методы построения будут рассмотрены ниже в разделе «Задачи и дополнения» (см. также [4]).
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок п матрицы Адамара при гС^З может быть лишь четным. Более того, нетрудно доказать, что при гС^4 порядок обязан делиться на 4 (см. дополнение 3). До настоящего времени остается открытым вопрос: для любого ли п, кратного 4, существует матрица Адамара порядка п? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
Задачи и дополнения
1. Укажем наиболее простой способ построения матриц Адамара сколь угодно больших порядков. Пусть Нп—матрица Адамара порядка п и —Нп—матрица с противоположными элементами. Составим из них матрицу порядка 2п следующим образом:
Именно таким обра" м получались одна из другой матрицы порядков I, 2, 4, 8, приведенные в начале этого параграфа.
Доказать, что матрица Н2п является матрицей Адамара.
Следующие две операции преобразуют матрицу Адамара снова в матрицу Адамара:
перестановка строк (или столбцов);
умножение строки (или столбца) на —1.
С помощью этих операций любую матрицу Адамара можно преобразовать в так называемую нормализованную матрицу Адамара, у которой первая строка и первый столбец состоят из одних единиц.
Докажем, что если Н — матрица Адамара порядка п>2, то п кратно 4.Действительно, можно считать матрицу Н нормализованной матрицей Адамара. Переставляя ее столбцы, всегда можно добиться, чтобы первые три строки матрицы имели вид!
Получается четыре типа столбцов. Пусть (, /, к, I означают соответственно число столбцов первого, второго, третьего и четвертого типов. Свойство ортогональности строк влечет тогда также равенства:
Кроме того,
откуда и следует наше
Из этих равенств получаем
утверждение.
4. Изложим еще один метод построения матрицы Адамара — метод Пэли. Рассмотрим поле %р вычетов по модулю р, где р — простое число. Всякий элемент %р, являющийся квадратом какого-либо элемента того же поля, называется квадратичным вычетом, всякий другой — квадратичным невычетом. Определим на следующую функцию Х('). называемую символом Лежандра ):
Исходя из этого определения, можно доказать, что для всякого сфО выполняется равенство
Рассмотрим теперь квадратную матрицу Ф порядка р, элементы которой о,-,- (/, /=1, 2 п) определяются следующим образом:
Пусть Е — единичная матрица порядка р, а У — квадратная матрица того же порядка, все элементы которой равны 1. Тогда, пользуясь (3), можно доказать равенства
является матрицей Адамара порядка р+1, Действительно, вычисляя произведение ННТ, получаем
Далее, как нетрудно проверить, матрица (2 порядка р=4й—I совпадает с матрицей —<2Т. Отсюда с учетом (4) имеем:
Таким образом,
5. В качестве примера построим матрицу Адамара порядка 8. Ппи этом 0=7. Функция у(7) задается следующей таблицей:
Матрицы <2 и Н имеют тогда вид:
Пусть теперь р=4й—1, В этом случае матрица
б. Построить методом Пэли матрицу Адамара порядка 12 и найти соответствующие коды Адамара