Участник:Nikita/Построение матрицы Адамара: различия между версиями

Версия 15:12, 14 октября 2016

Построение матрицы Адамара
Последовательный алгоритм
Последовательная сложность	[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]R[/math] (элементы [math]r_i[/math]) размера [math]2p[/math]. В этом векторе индексация идет от нуля, первые [math]p[/math] элементов образуются следующим образом:
- ыфвыв

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

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

1.3 Вычислительное ядро алгоритма

1.4 Макроструктура алгоритма

1.5 Схема реализации последовательного алгоритма

1.6 Последовательная сложность алгоритма

1.7 Информационный граф

1.8 Ресурс параллелизма алгоритма

1.9 Входные и выходные данные алгоритма

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

2 Программная реализация алгоритма

2.1 Особенности реализации последовательного алгоритма

2.2 Локальность данных и вычислений

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.5 Динамические характеристики и эффективность реализации алгоритма

2.6 Выводы для классов архитектур

2.7 Существующие реализации алгоритма

3 Литература

@@ Строка 12: / Строка 12: @@
 === Общее описание алгоритма ===
+Матрицы Адамара были введены в математический обиход в конце прошлого века и играют важную роль в алгебре и комбинаторике. Сравнительно недавно (в 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)
 === Математическое описание алгоритма ===