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

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

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

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

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

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

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

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

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

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

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

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

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

• [math]n\gt 0[/math];

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

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

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

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

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

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

Алгоритм:

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