20. Матрицы Адамара и кодирование

Важную роль в алгебре и комбинаторике играют матрицы Адамара, которые впервые были введены в математический обиход в конце прошлого века ^*). Сравнительно недавно, (в 1960 г.) было замечено, что эти матрицы могут быть использованы для построения кодов с большим кодовым расстоянием

^*) (Жак Адамар (1865-1963) - один из крупнейших французских математиков конца XIX и первой половины XX века, автор ряда основополагающих работ в области теории чисел, алгебры и математического анализа.)

Квадратная матрица Н порядка n с элементами ±1 называется матрицей Адамара, если выполняется условие

Вот несколько примеров матриц Адамара:

Рассмотрим произвольную матрицу Адамара

Из определения следует, что для любой пары строк с номерами i и j (i ≠ j) верно равенство:

Таким образом, различные строки матрицы Адамара попарно ортогональны. Далее, число слагаемых в (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 (см. дополнение 3). До настоящего времени остается открытым вопрос: для любого ли n, кратного 4, существует матрица Адамара порядка n? Неизвестно, в частности, существует ли матрица Адамара порядка 268 (это наименьший порядок, кратный 4, для которого матрица Адамара еще не построена).