Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

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

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


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

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

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

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

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru