Участник: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{ p }[/math]) [math]\displaystyle{ R }[/math] (элементы [math]\displaystyle{ r_i }[/math]) размера [math]\displaystyle{ 2p }[/math]. В этом векторе индексация идёт с нуля, вторые [math]\displaystyle{ p }[/math] элементов ([math]\displaystyle{ i=p,1,...,2p-1 }[/math]) являются копией первых [math]\displaystyle{ p }[/math] элементов ([math]\displaystyle{ r_i=r_{i-p} }[/math]), которые, в свою очередь, определяются следующим образом:
  • [math]\displaystyle{ r_i=1 }[/math], если [math]\displaystyle{ i \in \{1^2 }[/math] [math]\displaystyle{ mod }[/math] [math]\displaystyle{ p, 2^2 }[/math] [math]\displaystyle{ mod }[/math] [math]\displaystyle{ p, ... , (\frac{p-1}{2})^2 }[/math] [math]\displaystyle{ mod }[/math] [math]\displaystyle{ p\} }[/math], [math]\displaystyle{ i=0,1,...,p-1 }[/math], то есть если [math]\displaystyle{ i }[/math] является квадратичным вычетом по модулю [math]\displaystyle{ p }[/math];
  • [math]\displaystyle{ r_i=-1 }[/math], иначе.

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

• Матрица Адамара [math]\displaystyle{ H }[/math] (элементы [math]\displaystyle{ h_{ij} }[/math]) размера [math]\displaystyle{ n \times n }[/math]. Индексация строчек и столбцов идёт с нуля. Элементы находятся следующим образом:
  • [math]\displaystyle{ h_{1j}=1, j=0,1, ... ,n-1; }[/math]
  • [math]\displaystyle{ h_{i1}=1, i=0,1, ... ,n-1; }[/math]
  • [math]\displaystyle{ h_{ij}=r_{j-i+p}, i=1,2, ... ,n-1, j=1,2, ... ,n-1. }[/math]

Алгоритм:

1. Строится вектор квадратичных вычетов [math]\displaystyle{ R }[/math];
2. Строится матрица Адамара [math]\displaystyle{ H }[/math].