Пигарев А.Ю.

Воронежский институт МВД, Россия

О некоторых применениях матриц Адамара и их спектральных характеристиках

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

Степенные матрицы (которые часто без всяких оснований связывают с именем Вандермонда) имеют вид:

Они состоят из последовательных степеней элементов второй строки. Вычисление определителя этой матрицы и её обращение были по существу указаны Ньютоном, явные формулы по его идеям вычислил Де Муавр. По сути этими вычислениями определяется и известный метод интерполяции, который впоследствии получил имя Лагранжа. Важную для приложений теорему о неотрицательности миноров этого определителя доказал Н.Г. Чеботарёв. При вычислениях также большую роль играют полученные в последнее время различные удобные факторизации степенной матрицы через матрицы более простой структуры.

Матрицы Коши имеют такой вид:

Доказано, что если все числа в массивах различные, а все знаменатели в матричных элементах ненулевые, то определитель этой матрицы ненулевой, для него Коши вывел явную формулу. Отметим, что частным случаем матрицы и определителя Коши являются матрица и определитель Гильберта. Замечательным свойством матрицы Коши является то, что любой её минор также является матрицей Коши, и поэтому при невырожденности исходной матрицы также невырожден. Это делает подобные матрицы чрезвычайно популярными при кодировании, на них основано известное семейство кодов Гоппы [2].

С другой стороны давно известны приложения в теории кодирования матриц Адамара. Они возникли при рассмотрении Жаком Адамаром достаточно абстрактной математической задачи о достижении равенства в так называемом неравенстве Адамара для определителей. Им был выделен класс бинарных матриц, на которых достигалось равенство. В дальнейшем матрицы Адамара изучались в работах Сильвестра, Пэли и других математиков. В 1970-х годах матрицы Адамара нашли неожиданные применения в теории кодирования, так построенные с их помощью коды позволяют исправлять ошибки, число которых может достигать половины объёма сообщения. Матрицы Адамара, например, были использованы при передаче сигналов спутников с Марса ввиду большого количества сбоев и ошибок, вызванных удалённостью спутника при передаче и большим количеством помех.

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

Автором изучены некоторые спектральные свойства матриц Адамара: собственные значения, наборы собственных векторов. Вычисления проводились на компьютере в системе MATHEMATICA. Знание указанных и других спектральных характеристик позволяет в некоторых случаях оптимизировать вычисления при кодировании.

Литература:

1. Аршинов М.Н., Садовский Л.Е. Коды и математика. М., Наука,1983.

2. Влэдуц С.Г., Ногин Д.Ю., Цфасман М.А. Алгеброгеометрические коды. М., МЦНМО, 1993.

3. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986.

4. Мак-Вильямс Ф. Дж., Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки. М.: Радио и связь, 1979.

5. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2006.

6. Злотник Б.М. Помехоустойчивые коды в системах связи. М.:Радио и связь, 1989.

7. Кларк Дж., мл., Кейн Дж., Кодирование с исправлением ошибок в системах цифровой связи: Пер. с англ.-М.: Радио и связь, 1987.

8. Самойленко С.И. Помехоустойчивое кодирование. М., "Наука", 1966.

9. Муттер В.М. Основы помехоустойчивой телепередачи информации. - Л.: Энергоатомиздат. Ленингр. отделение, 1990.

10. Т.Касами, Н.Токура, Е.Ивадари, Я.Инагаки. Теория кодирования. М.:Мир,1978.

11. Agaian S.S. Hadamard Matrices and Their Applications. Springer, 1985.

12. Horadam K.J. Hadamard Matrices and Their Applications. Princeton University Press, 2007.

13. Zyczkowski K. Complex Hadamard Matrices and Some of Their Applications. 2009.

14. Fletcher R.J., Gysin M., Seberry J. Application of the Discrete Fourier Transform to the Search for Generalized Legendre Pairs and Hadamard Matrices. The Australasian Journal of Combinatorics, 23(2001), P. 75-86.

15. Hedayat A., Wallis W. D. Hadamard Matrices and Their Applications. Ann. Statist. Volume 6, Number 6 (1978), 1184-1238.

16. Seberry J., Wysocki B.J., ·Wysocki T.A. On some applications of Hadamard matrices. Metrika, 2005, P. 1–19.

17. Литвин А.И. Об одном подходе к проблеме Адамара. Вестник Томского государственного университета, 2008, Математика и механика, № 1(2), С. 51-57.

18. Пигарев А.Ю. Спектральные характеристики матриц Адамара

и их применения при кодировании. Сборник материалов II Всероссийской научно-практической конференции с международным участием: "Информационная безопасность в государственных и негосударственных структурах" - ИНФОРМТЕХ-2012. Юго-Западный государственный университет, Курск, 2012. С. 107-109.

19. Пигарев А.Ю. Об одном методе аппроксимации сигналов. Международная конференция:"Современные методы и проблемы теории операторов и гармонического анализа и их приложения". Посвящена памяти Николая Карапетовича Карапетянца (1942--2005). Тезисы докладов. Ростов-на-Дону, Южный федеральный университет, 2012. С. 88.

20. Пигарев А.Ю. Спектральные характеристики матриц Адамара и их применения при кодировании. Сборник материалов Всероссийской научно-практической конференции "Актуальные вопросы эксплуатации систем охраны и защищённых телекоммуникационных систем". Воронеж, ВИ МВД, 2012, С. 141-142.