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 и найти соответствующие коды Адамара