Участник:Nikita/Построение матрицы Адамара: различия между версиями
Перейти к навигации
Перейти к поиску
Nikita (обсуждение | вклад) |
Нет описания правки |
||
| Строка 42: | Строка 42: | ||
* Число <math>p=n-1</math>; | * Число <math>p=n-1</math>; | ||
* Вектор вычетов <math>R</math> (элементы <math>r_i</math>) размера <math>2p</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</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=0,1, ... ,n-1;</math> | |||
** <math>h_{ij}=r_{j-i+p}, i=0,1, ... ,n-1, j=0,1, ... ,n-1.</math> | |||
Версия от 12:35, 14 октября 2016
| Построение матрицы Адамара | |
| Последовательный алгоритм | |
| Последовательная сложность | [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=0,1, ... ,n-1, j=0,1, ... ,n-1. }[/math]