Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску
Строка 13: Строка 13:
 
=== Общее описание алгоритма ===
 
=== Общее описание алгоритма ===
  
Матрицы Адамара были введены в математический обиход в конце прошлого века и играют важную роль в алгебре и комбинаторике. Сравнительно недавно (в 1960 г.) было замечено, что эти матрицы могут быть использованы для построения кодов с большим кодовым расстоянием.
+
Матрицы Адамара были введены в математический обиход в конце прошлого века и играют важную роль в алгебре и комбинаторике. Они находят широкое применение в теории кодирования (коды, исправляющие ошибки), теории планирования многофакторных экспериментов (блок-схемы) и других областях математики. Сравнительно недавно (в 1960 г.) было замечено, что эти матрицы могут быть использованы для построения кодов с большим кодовым расстоянием.
  
 
'''''Матрицей Адамара порядка n''''' называется <math>n*n</math> матрица <math>H</math>, элементами которой являются +1 и −1 такая, что <math>H H^T = n E_n</math>,  
 
'''''Матрицей Адамара порядка n''''' называется <math>n*n</math> матрица <math>H</math>, элементами которой являются +1 и −1 такая, что <math>H H^T = n E_n</math>,  
Строка 22: Строка 22:
 
* Скалярное произведение любой строки саму на себя равно n
 
* Скалярное произведение любой строки саму на себя равно n
 
* Умножение любой строки или столбца на -1 переводит H в другую матрицу Адамара
 
* Умножение любой строки или столбца на -1 переводит H в другую матрицу Адамара
 +
* Если все элементы первой строки и первого столбца равны +1, то матрица Адамара называется нормализованной
  
Если все элементы первой строки и первого столбца равны +1, то матрица Адамара называется нормализованной.
+
Для матриц Адамара справедлива следующая '''гипотеза''': если существует матрица Адамара порядка n, то n равно 1 или 2 или делится на 4, однако до сих пор не была доказана.
  
Для матриц Адамара справедливо следующее утверждение: если существует матрица Адамара порядка n, то n равно 1 или 2 или делится на 4.
+
Примеры матриц (1,2,4,8)
  
Примеры матриц (1,2,4,8)
+
Предполагается, что существуют матрицы Адамара всех порядков n, кратных 4, хотя это до сих пор еще не было доказано. Известно большое число методов построения, и наименьший порядок, для которого матрица Адамара еще не построена, равен 268 (на 1977 г.). Мы приведем метод построения Пейли, который важен для теории кодирования. Это построение дает матрицы Адамара любого порядка <math>n=p+1</math>, кратного 4, где p-простое число.
 +
Сначала мы построим матрицу Джекобстола <math>Q=(q_ij)</math>. Она представляет собой (pxp)-матрицу, строки и столбцы которой пронумерованы числами 0,1,..., p-1, а элементы <math>q_ij=X(j-i)</math>
  
 
=== Математическое описание алгоритма ===
 
=== Математическое описание алгоритма ===

Версия 15:59, 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)

Предполагается, что существуют матрицы Адамара всех порядков n, кратных 4, хотя это до сих пор еще не было доказано. Известно большое число методов построения, и наименьший порядок, для которого матрица Адамара еще не построена, равен 268 (на 1977 г.). Мы приведем метод построения Пейли, который важен для теории кодирования. Это построение дает матрицы Адамара любого порядка [math]n=p+1[/math], кратного 4, где p-простое число. Сначала мы построим матрицу Джекобстола [math]Q=(q_ij)[/math]. Она представляет собой (pxp)-матрицу, строки и столбцы которой пронумерованы числами 0,1,..., p-1, а элементы [math]q_ij=X(j-i)[/math]

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_{0j}=1, j=0,1, ... ,n-1;[/math]
    • [math]h_{i0}=1, i=1,2, ... ,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].

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

Вычислительное ядро алгоритма состоит из [math](n-1) \times (n-1)[/math] операций присваивания вида [math]h_{ij}=r_{j-i+p}, i=1,2, ... ,n-1, j=1,2, ... ,n-1.[/math]

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 Литература