Коды Адамара - Доклад
.docxКоды Адамара
Жак Адамар (1865-1963) - один из крупнейших французских математиков конца XIX и первой половины XX века, автор ряда основополагающих работ в области теории чисел, алгебры и математического анализа.
Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века *). Сравнительно недавно, в 1960 г., было замечено, что эти матрицы могут быть использованы для построения кодов с большим кодовым расстоянием
Квадратная матрица Н порядка n с элементами ±1 называется матрицей Адамара, если выполняется условие
НHT = nЕn.
Вот несколько примеров матриц Адамара:
(1),
n = 1
Рассмотрим произвольную матрицу Адамара
hij = ± 1.
Из определения следует, что для любой пары строк с номерами i и j (i ≠ j) верно равенство:
hi1hj1 + hi2hj2 + ... + hinhjn = 0. (1)
Таким образом, различные строки матрицы Адамара попарно ортогональны. Далее, число слагаемых в (1), равных +1, должно совпадать с числом слагаемых, равных -1. Следовательно, n четно и любые две строки совпадают ровно в n/2 позициях и различаются в остальных.
Пусть теперь А - двоичная матрица, получающаяся из матрицы Н заменой элемента +1 на 0 -1 на 1. Множество векторов-строк матрицы А образует тогда код с расстоянием Хемминга между любыми кодовыми словами, равным n/2. Так, из матрицы Адамара порядка 8 получаем матрицу A, задающую код длины 8 с кодовым расстоянием 4:
Не меняя кодового расстояния, можно уменьшить длину кода, если отбросить первый (нулевой) символ каждого слова.
Указанным образом из всякой матрицы Адамара порядка n можно получить двоичный код Адамара типа (n-1, n, n/2) (n-1 - длина кодового слова, n - число слов кода, n/2 - кодовое расстояние). Это, как правило, код, не являющийся линейным.
С матрицей А связаны еще два кода, которые тоже называют кодами Адамара.
Первый из них получается так. Перейдем от матрицы А к матрице A‾, заменив все элементы матрицы A их дополнениями (т. е. заменив единицы нулями, а нули - единицами). Тогда строки матриц A и A‾ в совокупности образуют код типа (n, 2n, n/2), что легко проверяется с помощью равенства (1).
Другой код Адамара получается из предыдущего отбрасыванием первого символа в каждом кодовом слове. Это будет код типа (n - 1, 2n, n/2 - 1).
Например, из матрицы (2) можно получить таким способом коды Адамара типов (8, 16, 4) и (7, 16, 3).
Коды Адамара, как видно из их определения, обладают интересной особенностью: расстояние между любыми двумя кодовыми словами одинаково и совпадает поэтому с кодовым расстоянием. Подобные коды называют эквидистантными, и в некоторых случаях их использование дает особые преимущества.
Коды Адамара, обладая большим кодовым расстоянием, позволяют соответственно исправить и большое количество ошибок (первые два из них исправляют ошибки примерно в четверти позиций кодового слова). Достигается это, конечно, ценой высокой избыточности.
Для построения и реализации кода Адамара той или иной длины необходимо построить сначала матрицу Адамара соответствующего порядка. Надо сказать, что такое построение является совсем нелегким делом, и этому вопросу посвящен внушительный раздел современной комбинаторики. Некоторые методы построения будут рассмотрены ниже в разделе "Задачи и дополнения" (см. также [4]).
С матрицами Адамара связан ряд нерешенных проблем, одна из которых состоит в следующем. Мы уже видели, что порядок n матрицы Адамара при n ≥ 3 может быть лишь четным. Более того, нетрудно доказать, что при n ≥ 4 порядок обязан делиться на 4. До настоящего времени остается открытым вопрос: для любого ли n, кратного 4, существует матрица Адамара порядка n? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).
Задачи и дополнения
1. Укажем наиболее простой способ построения матриц Адамара сколь угодно больших порядков. Пусть Нn - матрица Адамара порядка n и -Нn - матрица с противоположными элементами. Составим из них матрицу порядка 2n следующим образом:
Именно таким образом получались одна из другой матрицы порядков 1, 2, 4, 8, приведенные в начале этого параграфа.
Доказать, что матрица Н2n является матрицей Адамара.
2. Следующие две операции преобразуют матрицу Адамара снова в матрицу Адамара:
1) перестановка строк (или столбцов);
2) умножение строки (или столбца) на -1.
С помощью этих операций любую матрицу Адамара можно преобразовать в так называемую нормализованную матрицу Адамара, у которой первая строка и первый столбец состоят из одних единиц.
3. Изложим еще один метод построения матрицы Адамара - метод Пэли. Рассмотрим поле Zр вычетов по модулю р, где р - простое число. Всякий элемент Zp, являющийся квадратом какого-либо элемента того же поля, называется квадратичным вычетом, всякий другой - квадратичным невычетом. Определим на Zp следующую функцию χ‾(i), называемую символом Лежандра *):
Исходя из этого определения, можно доказать, что для всякого с ≠ 0 выполняется равенство
χ(1‾) χ(‾1 + ‾c) + χ(2‾) χ(‾2 + ‾c) + ... + χ(p-1)‾ χ (p-1‾ + c‾) = -1. (3)
Рассмотрим теперь квадратную матрицу Q порядка р, элементы которой qij (i, j = 1, 2, ..., р) определяются следующим образом:
qij = χ(j‾ - i‾).
Пусть Е - единичная матрица порядка р, a J - квадратная матрица того же порядка, все элементы которой равны 1. Тогда, пользуясь (3), можно доказать равенства
QQT = pE - J, QJ = JQ = 0. (4)
Пусть теперь p = 4k - 1. В этом случае матрица
является матрицей Адамара порядка p + 1. Действительно, вычисляя произведение ННТ, получаем:
Далее, как нетрудно проверить, матрица Q порядка р = 4k - 1 совпадает с матрицей -QT. Отсюда с учетом (4) имеем:
J + (Q - E) (QT - E) = J + QQT - Q - QT + E = J + pE - J - Q + Q + E = (p + 1)E.
Таким образом, HHT = (р + 1)E.