2.3. МАТРИЦЫ АДАМАРА И КОДЫ АДАМАРА

Определение. Матрица Адамара порядка представляет собой -матрицу из элементов +1 и —1, такую, что

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

Легко видеть, что умножение любой строки или столбца на —1 переводит в другую матрицу Адамара. Это означает, что мы можем изменить все элементы первой строки и первого столбца матрицы на Такая матрица Адамара называется нормализованной. На рис. 2.3 показаны нормализованные матрицы Адамара порядков 1, 2, 4, 8, где вместо элемента —1 изображен только символ ; это обозначение будем использовать во всей книге.

Рис. 2.3. Матрицы Адамара порядков 1, 2, 4 и 8 типа Сильвестра

Теорема 5. Если существует матрица Адамара порядка то равно 1 или 2 или делится на 4.

Доказательство. Без ограничения общности будем считать, что представлена в нормализованном виде. Предположим, что и первые строки имеют следующий вид:

Так как строки матрицы ортогональны, то мы имеем:

что влечет цепочку равенств Поэтому т. е. делится на 4

Предполагается, что существуют матрицы Адамара всех порядков кратных 4, хотя это до сих пор еще не было доказано. Известно большое число методов построения, и наименьший порядок, для которого матрица Адамара еще не построена, равен 268 (на 1977 г.). Мы приведем два метода построения, которые важны для теории кодирования.

Метод построения Если матрица Адамара порядка то легко проверить, что

представляет собой матрицу Адамара поря Начав с этим методом получаем матрицы (как показано на рис. 2.3) и т. д. и, следовательно, матрицы Адамара, порядки которых являются степенями двойки. Эти матрицы Адамара называются матрицами Сильвестра.

Для описания второго метода построения нам необходимы некоторые сведения о квадратичных вычетах.

Квадратичные вычеты. Определение. Пусть простое нечетное число. Ненулевые квадраты чисел, приведенные по модулю т. е. числа приведенные по этому модулю, называются квадратичными вычетами по модулю или просто вычетами по модулю

Для того чтобы найти все вычеты по модулю достаточно рассмотреть квадраты чисел от 1 до На самом деле, учитывая, что достаточно рассмотреть квадраты

Все эти вычеты различны, так как если при то делит что возможно лишь при

Следовательно, имеются квадратичных вычетов по модулю Оставшиеся чисел по модулю называются невычетами. Нуль не является ни вычетом, ни невычетом.

Например, если то квадратичные вычеты по модулю - это числа

т. е. числа 1, 3, 4, 5 и 9. Остальные числа 2, 6, 7, 8 и 10 являются невычетами. [Напомним читателю, что выражение

читаемое как «А сравнимо с В по модулю С», означает, что

где вертикальная черточка означает «делит» или, что эквивалентно,

В этом случае числа находятся в одном и том же классе вычетов по модулю

Рассмотрим теперь некоторые свойства квадратичных вычетов.

(Q1). Произведение двух квадратичных вычетов или двух невычетов является квадратичным вычетом, а произведение квадратичного вычета и невычета является невычетом. Доказательство оставляется читателю в качестве упражнения.

(Q2). Если имеет вид то число —1 является квадратичным вычетрм по модулю Если же имеет вид то —1 является невычетом по модулю Доказательство будет приведено в гл. 4.

(Q3). Пусть простое нечетное число. Функция называемая символом Лежандра, определяется на целых числах следующим образом:

Теорема 6. Для любого

Доказательство. Из свойства следует, что

Вклад в сумму слагаемого при равен нулю. Теперь предположим, что и пусть число Для каждого имеется единственное целое число Когда пробегает все числа от 1 до число принимает значения но не 1. Итак,

Замечание. Очень похожие свойства выполняются, когда заменяется на степень любого нечетного простого числа числа заменяются на элементы конечного поля (см. гл. 3), а квадратичные вычеты определяются как ненулевые квадраты в этом поле.

Метод построения II. (Метод Пейли.) Это построение дает матрицы Адамара любого порядка кратного 4 (или порядка кратного 4, если мы используем квадратичные вычеты в поле

Сначала мы построим матрицу Джекобстола Она представляет собой -матрицу, строки и столбцы которой перенумерованы числами а элементы (см. рис. 2.4 для случая р = 7):

Рис. 2.4. Матрица Джекобстола

Заметим, что так как имеет вид (см. свойство и поэтому матрица является кососимметрической, т. е.

Лемма где матрица из всех единиц.

Доказательство. Пусть Тогда

Так же доказывается, что так как каждая строка и каждый столбец матрицы содержат элементов элементов

Пусть теперь

Тогда

Но из леммы 7 следует, что так что Таким образом, лредставляет собой нормализованную матрицу Адамара порядка которую называют матрицей типа Пейли.

Пример. На рис. 2.5 изображены матрицы Адамара порядков 8 и 12, полученные описанным способом.

Рис. 2.5. Матрицы Адамара порядков 8 и 12

Методы построения I и II дают вместе матрицы Адамара для всех порядков

Назовем две матрицы Адамара эквивалентными, если одна может быть получена из другой перестановками строк и

столбцов и умножением строк и столбцов на —1. Легко убедиться, что имеется только один класс эквивалентности матриц Адамара порядков 1, 2 и 4. В гл. 20 мы увидим, что имеется только один такой класс матриц порядка 8 (так что матрицы Адамара порядка 8, изображенные на рис. 2.3 и 2.5, эквивалентны) и один класс матриц порядка 12. Кроме того, известно, что имеется пять классов эквивалентности порядка 16 и три порядка 20. Число таких классов порядка 24 неизвестно.

Упражнение. (3). Если то пусть обозначают различные двоичные -векторы. Показать, что матрица где является матрицей Адамара порядка которая эквивалентна матрице, полученной методом построения

Коды Адамара. Пусть — нормализованная матрица Адамара порядка Если все элементы заменить на 0, а элементы — 1 заменить на 1, то превратится в двоичную матрицу Адамара Так как строки ортогональны, то любые две строки матрицы совпадают в позициях и различаются в позициях, и поэтому расстояние Хэмминга между ними равно

Матрица позволяет построить следующие три кода Адамара:

(i). -код состоящий из строк матрицы с выкинутым первым столбцом (код «58 показан на рис. 2.7, а код 12 образован строками верхней половины рис. 2.1, если символы в строках взять в обратном порядке).

(ii). -код состоящий из векторов кода и их дополнений 2 (код изображен на рис. 2.1).

(iii). -код состоящий из строк матрицы и их дополнений.

Код является симплексным кодом, так как расстояние между любыми двумя кодовыми словами равно (см. § 1.9). В действительности эти три кода представляют собой нелинейные обобщения кодов, изображенных на рис. 1.13. Более того, если матрица где получена методом построения I, то все три кода и являются линейными и совпадают с кодами, показанными на рис. 1.13.

С другой стороны, если построена методом 11, то все полученные коды нелинейны для всех Линейные коды получим, если возьмем линейные оболочки этих кодов; полученные коды называются квадратично-вычетными кодами, и они будут исследованы в гл. 16. Но если матрица не строится ни методом I, ни методом II, то мало что известно о двоичном ранге матрицы

Упражнение. (4). Показать, что если кратно следовательно, двоичный ранг не превышает . [Указание. Использовать тот факт, что над любым полем где матрицы размера теорему 3.11 из работы Маркуса [914]).]

Теорема Левенштейна. В этом параграфе мы докажем теорему Левенштейна, которая утверждает, что существуют коды, достигающие границы Плоткина.

Вначале рассмотрим две простые конструкции.

(i). Кодовые слова кода которые начинаются с 0, после удаления этого нуля образуют (код показан на рис. 2.7).

Рис. 2.6. Построение нового кода «склеиванием» двух экземпляров кодов: 1 — отбрасываемая часть

(ii). Предположим, что мы имеем -код -код Склеим подряд а копий кода а затем копий кода (рис. 2.6). Теперь отбросим последние строк кода (если или последние строк кода (если ). В результате для произвольных натуральных чисел получим -код с где Обозначим этот код через

Теорема 8. (Левенштейн). Если существуют соответствующие матрицы Адамара, то в границах Плоткина (2.3) — (2.6) выполняются равенства. Таким образом, если четное, то

и если нечетное, то

Доказательство. Равенства (2.11), (2.12) следуют из (2.9), (2.10), если воспользоваться теоремой 2, так что мы можем предположить, что четное.

Код Адамара описанный выше, является -кодом, что доказывает (2.10).

Для того чтобы доказать (2.9), мы должны построить -код с для любого и четного удовлетворяющих условию Нам понадобится следующий простой результат, доказательство которого мы оставляем читателю. При положим и

Тогда неотрицательные целые числа и

Если четное, то также четные (это следует из (2.13)). Если нечетное, четное, то b - четное. Если нечетные, то а — четное.

Теперь рассмотрим код , где:

В каждом из этих случаев, как легко следует из конструкции описанной выше, код 92 имеет длину минимальное расстояние и содержит кодовых слов. Существование этого кода устанавливает справедливость (2.9).

Заметим, что для доказательства (2.10) требуется матрица Адамара порядка , а для доказательства (2.9) нам достаточно матриц Адамара порядка (если четное), (если нечетное),

Пример. Проиллюстрируем метод Левенштейна на примере построения -кода. Обращаясь к доказательству теоремы, мы находим, что . В нашем случае нечетные, поэтому код получается склеиванием вместе двух копий кода и одной копии кода

Коды полученные из матриц (см. рис. 2.4), изображены на рис. 2.7.

Рис. 2.7. -код и -код

Построенный -код изображен на рис. 2.8.

Упражнение. (5). Построить ( и (-коды.

Другие применения матриц Адамара.

(1). Максимальные определители. Если матрица Адамара порядка то, переходя в равенстве (2.7) к определителям, получаем, что так что определитель матрицы равен

Рис. 2.8. -код, иллюстрирующий метод построения Левенштейна

Теорема Адамара [572] утверждает, что если - любая вещественная -матрица с элементами то

Более того, равенство выполняется тогда и только тогда, когда существует матрица Адамара порядка Таким образом, должно быть кратно 4 (см. книги Беллмана [100, с. 160], Харди и др. [601, с. 34], Райзера [1136, с. 109]. Если не кратно 4, то мало что известно о наибольших возможных определителях (см. упражнение (8)).

(2). Весовые планы. Взвешивая несколько объектов вместе, а не в отдельности, иногда можно более точно определить их индивидуальные веса. Делается это с помощью так называемых весовых планов, и лучшие из таких планов основаны на матрицах Адамара.

Подобный метод применим к разнообразным задачам измерения не только веса, но и длины, напряжения, сопротивления, концентрации химических элементов, частотного спектра (см. работы Декера [341], Гиббса и Геббая [478], Голея [507, 508], Харвита и др. [622], Филлипса и др. [1042], Слоэна и др. [1234 — 1236]) и вообще к любому эксперименту, где мера множества «объектов является суммой индивидуальных мер. Для простоты, однако, мы опишем сейчас задачу взвешивания.

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

Сначала предположим, что предметы взвешиваются в отдельности. Если неизвестные веса обозначить через результаты взвешиваний — через а (неизвестные) ошибки, допущенные весами, через то четыре взвешивания дают четыре уравнения:

При этом оценки неизвестных весов а, b, с, d получаются следующими:

причем дисперсия каждой оценки равна

С другой стороны, предположим, что мы проделали следующие четыре взвешивания:

Это означает, что при первом взвешивании все четыре предмета положили на левую чашку весов, а при других взвешиваниях два предмета положили на левую чашку и два предмета — на правую. Так как коэффициенты при неизвестных а, Ь, с, d в левой части (2.14) образуют матрицу Адамара, то эту систему легко решить относительно а, Ь, с, d. Так, оценка величины а равна: А

Дисперсия случайной величины где с — константа, в раз больше дисперсии а дисперсия суммы независимых случайных величин равна сумме дисперсий этих величин. Поэтому дисперсия а равна т. е. выигрыш в 4 раза. Аналогичный результат получается и для других неизвестных.

В общем случае, если предметов надо взвесить за взвешиваний и матрица Адамара порядка существует, то описанный метод уменьшает дисперсию от до Известно, что это наименьшая дисперсия, которая может быть получена при любом выборе знаков в левой части выражений (2.14). Для доказательства этого факта и для более подробного знакомства с весовыми планами см. работы Банерджи [65, 66], Герамита и др. ], Хотеллина [665], Муда [972], Пейна [1032], Слоэна и Хэрвита [1236].

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

Коэффициенты определяются очевидным образом из матрицы Адамара изображенной на рис. 2.3. Тогда оценкой веса а является значение (см. упражнение (7))

имеющее дисперсию и то же самое получается для весов других предметов. В общем случае, если имеется предметов и существует матрица Адамара порядка то этот способ уменьшает дисперсию до что в некотором смысле является наилучшим возможным выигрышем (см. работы Муда [972], Рагхаварао [1085, гл. 17], Слоэна и Хэрвита [1236]).

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

Другой тип задач взвешивания, также связанный с теорией кодирования, будет рассмотрен в гл. 6.

(3). Преобразование Адамара. Пусть матрица Адамара порядка Если -вещественный вектор, то его преобразованием Адамара (или Уолша, или дискретным преобразованием Фурье) называется вектор

Пусть обозначает множество всех двоичных векторов длины Матрица, строки и столбцы которой пронумерованы векторами из образует матрицу Адамара порядка если в ячейке записано число (см. упражнение (3)). Если некоторое отображение, определенное на то его преобразование Адамара определяется как

Мы воспользуемся в важной лемме (лемма 2) в гл. 5 и при изучении кодов Рида — Маллера. Преобразования Адамара также широко используются в теории связи и в физике, и им посвящено большое число работ в широком диапазоне (см., например, работы Ахмеда и др. [12—15], Хармута [603—604, 680], Кеннета [757], Пратта и др. [1079], Шенкса [1187], Вэдбрука и Воллонса [1375]). Анализ влияния ошибок на преобразование Адамара требует детального знания смежных классов кодов Рида-Маллера первого порядка (см. Берлекэмп [119]).

Упражнения. (6). Пусть

— нормализованная матрица Адамара порядка Показать, что

(7). Пусть что матрица коэффициентов в соотношениях (2.15)). Показать, что

(8). Задачи о максимальных определителях. Предположим, что вещественная матрица порядка Пусть

Показать, что

Таким образом, все пять задач эквивалентны! Адамар [572] доказал, что причем равенство выполняется тогда и только тогда, когда существует матрица Адамара порядка . Первые несколько значений функции таковы:

(См. по этому поводу, например, работы Бреннера и Каммингс [196], Кона [298], Элиха [403], Элиха и Зеллера [404] и Янга [1445].)