Участник:Nikita/Построение матрицы Адамара

Построение матрицы Адамара
Последовательный алгоритм
Последовательная сложность	[math]\displaystyle{ O(n^2) }[/math]
Объём входных данных	[math]\displaystyle{ 1 }[/math]
Объём выходных данных	[math]\displaystyle{ n^2 }[/math]
Параллельный алгоритм
Высота ярусно-параллельной формы	[math]\displaystyle{ O(1) }[/math]
Ширина ярусно-параллельной формы	[math]\displaystyle{ O(n^2) }[/math]

Свойства и структура алгоритма

Общее описание алгоритма

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

Матрицей Адамара порядка n называется [math]\displaystyle{ n*n }[/math] матрица [math]\displaystyle{ H }[/math], элементами которой являются +1 и −1 такая, что [math]\displaystyle{ H H^T = n E_n }[/math], где [math]\displaystyle{ E_n }[/math] - единичная матрица размера n.

Матрица Адамара обладает следующими свойствами:

• Различные строки матрицы ортогональны
• Скалярное произведение любой строки саму на себя равно n
• Умножение любой строки или столбца на -1 переводит H в другую матрицу Адамара

Если все элементы первой строки и первого столбца равны +1, то матрица Адамара называется нормализованной.

Для матриц Адамара справедливо следующее утверждение: если существует матрица Адамара порядка n, то n равно 1 или 2 или делится на 4.

Примеры матриц (1,2,4,8)

Математическое описание алгоритма

Исходные данные - это порядок генерируемой матрицы Адамара [math]\displaystyle{ n }[/math], удовлетворяющее следующим свойствам:

• [math]\displaystyle{ n\gt 0 }[/math];

• [math]\displaystyle{ n }[/math] делится на 4;

• [math]\displaystyle{ n-1 }[/math] - простое число.

Вспомогательные данные:

• Число [math]\displaystyle{ p=n-1 }[/math];
• Вектор вычетов [math]\displaystyle{ R }[/math] (элементы [math]\displaystyle{ r_i }[/math]) размера [math]\displaystyle{ 2p }[/math]. В этом векторе индексация идет от нуля, первые [math]\displaystyle{ p }[/math] элементов образуются следующим образом:
  • ыфвыв

Вычисляемые данные:

• Матрица Адамара [math]\displaystyle{ H }[/math] (элементы [math]\displaystyle{ h_{ij} }[/math]) размера [math]\displaystyle{ n \times n }[/math].