Участник:Маркова Екатерина/Построение матрицы Адамара: различия между версиями
Katemeron (обсуждение | вклад) Нет описания правки |
Katemeron (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
Основной автор статьи: Маркова Е.А. 615 гр. | Основной автор статьи: Маркова Е.А. 615 гр. | ||
== Свойства и структура алгоритма == | == Свойства и структура алгоритма == | ||
=== | === Общее описание алгоритма=== | ||
Матрица Адамара <math>H</math> - это квадратная матрица размера <math>N\times N</math>, составленная из чисел <math>1</math> и <math>-1</math>, столбцы которой ортогональны, так что справедливо соотношение: | Матрица Адамара <math>H</math> - это квадратная матрица размера <math>N\times N</math>, составленная из чисел <math>1</math> и <math>-1</math>, столбцы которой ортогональны, так что справедливо соотношение: | ||
| Строка 9: | Строка 9: | ||
где <math>E_n</math> - это единичная матрица размера <math>n</math>. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов. | где <math>E_n</math> - это единичная матрица размера <math>n</math>. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов. | ||
=== | === Математическое описание алгоритма === | ||
Пусть <math>H_N</math> <math>-</math> матрица Адамара порядка <math>N</math> и <math>-H_N</math> <math>-</math> матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом: | Пусть <math>H_N</math> <math>-</math> матрица Адамара порядка <math>N</math> и <math>-H_N</math> <math>-</math> матрица с противоположными элементами. Тогда матрица <math>H_{2N}</math> получается следующим образом: | ||
| Строка 18: | Строка 18: | ||
</math> | </math> | ||
=== | === Вычислительное ядро алгоритма === | ||
Вычислительное ядро рекурсивного алгоритма состоит из <math>\;N^2\;</math> присвоений значений и . | Вычислительное ядро рекурсивного алгоритма состоит из <math>\;N^2\;</math> присвоений значений и . | ||
=== | === Макроструктура алгоритма === | ||
Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы. | Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы. | ||
=== | === Схема реализации последовательного алгоритма=== | ||
В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы. | В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы. | ||
| Строка 43: | Строка 43: | ||
=== | === Последовательная сложность алгоритма=== | ||
Для заполнения матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\;N^2\;</math> присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''. | Для заполнения матрицы <math>H</math> размера <math>N\times N</math> необходимо <math>\;N^2\;</math> присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с ''квадратичной сложностью''. | ||
=== | ===Информационный граф=== | ||
Зависимость данных для матрицы размерностью <math>4*4</math> можно увидеть на рис.1. | Зависимость данных для матрицы размерностью <math>4*4</math> можно увидеть на рис.1. | ||
| Строка 53: | Строка 53: | ||
[[Файл:Pic_hadamard.png|border|500px|Some text]] | [[Файл:Pic_hadamard.png|border|500px|Some text]] | ||
=== | === Ресурс параллелизма алгоритма=== | ||
Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо. | Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо. | ||
Внутри каждой части происходит <math>2^{2N}-2^{2(N-1)}</math> независимых присвоений, где <math>N</math> - номер шага алгоритма, причем размерность матрицы на шаге <math>N</math> равна <math>2^N</math>. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки. | Внутри каждой части происходит <math>2^{2N}-2^{2(N-1)}</math> независимых присвоений, где <math>N</math> - номер шага алгоритма, причем размерность матрицы на шаге <math>N</math> равна <math>2^N</math>. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки. | ||
=== | ===Входные и выходные данные алгоритма=== | ||
Входные данные: <math>N</math> - размерность матрицы. | Входные данные: <math>N</math> - размерность матрицы. | ||
| Строка 66: | Строка 66: | ||
Объем выходных данных: <math> N^2</math>. | Объем выходных данных: <math> N^2</math>. | ||
=== | ===Свойства алгоритма=== | ||
Алгоритм полностью детерминирован. | Алгоритм полностью детерминирован. | ||
| Строка 72: | Строка 72: | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
=== | === Существующие реализации алгоритма=== | ||
Реализация ''MATLAB'' | Реализация ''MATLAB'' | ||
Версия от 13:01, 28 октября 2016
Основной автор статьи: Маркова Е.А. 615 гр.
Свойства и структура алгоритма
Общее описание алгоритма
Матрица Адамара [math]\displaystyle{ H }[/math] - это квадратная матрица размера [math]\displaystyle{ N\times N }[/math], составленная из чисел [math]\displaystyle{ 1 }[/math] и [math]\displaystyle{ -1 }[/math], столбцы которой ортогональны, так что справедливо соотношение:
[math]\displaystyle{ H*H^T = N*E_N }[/math],
где [math]\displaystyle{ E_n }[/math] - это единичная матрица размера [math]\displaystyle{ n }[/math]. Матрицы Адамара применяются в различных областях, включая комбинаторику, численный анализ, обработку сигналов.
Математическое описание алгоритма
Пусть [math]\displaystyle{ H_N }[/math] [math]\displaystyle{ - }[/math] матрица Адамара порядка [math]\displaystyle{ N }[/math] и [math]\displaystyle{ -H_N }[/math] [math]\displaystyle{ - }[/math] матрица с противоположными элементами. Тогда матрица [math]\displaystyle{ H_{2N} }[/math] получается следующим образом: [math]\displaystyle{ H_{2N} = \begin{bmatrix} H_N & H_N \\ H_N & -H_N \end{bmatrix} }[/math]
Вычислительное ядро алгоритма
Вычислительное ядро рекурсивного алгоритма состоит из [math]\displaystyle{ \;N^2\; }[/math] присвоений значений и .
Макроструктура алгоритма
Алгоритм не использует в качестве составных частей другие алгоритмы. Как это было описано в вычислительном ядре, в пустые блоки дублируются со сменой или без смены знака значения первого блока матрицы.
Схема реализации последовательного алгоритма
В описанном виде алгоритм представляет из себя примитивное дублирование элементов матрицы, полученной на предыдущем этапе, в пустующие блоки новой матрицы.
Сначала заполняется правый верхний блок матрицы [math]\displaystyle{ H }[/math]
[math]\displaystyle{ H_{ij} = H_{i(j - \frac{N}{2})} }[/math], где [math]\displaystyle{ i = 1..\frac{N}{2} }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math];
затем левый нижний блок
[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})j} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = 1.. \frac{N}{2} }[/math].
Последним заполняется нижний правый блок матрицы
[math]\displaystyle{ H_{ij} = H_{(i-\frac{N}{2})(j-\frac{N}{2})} }[/math], где [math]\displaystyle{ i = \frac{N}{2}+1..N }[/math], [math]\displaystyle{ j = \frac{N}{2}+1..N }[/math].
Последовательная сложность алгоритма
Для заполнения матрицы [math]\displaystyle{ H }[/math] размера [math]\displaystyle{ N\times N }[/math] необходимо [math]\displaystyle{ \;N^2\; }[/math] присвоений значений. Из чего можно сделать вывод, что рекурсивный метод построения матрицы Адамара является алгоритмом с квадратичной сложностью.
Информационный граф
Зависимость данных для матрицы размерностью [math]\displaystyle{ 4*4 }[/math] можно увидеть на рис.1.
Ресурс параллелизма алгоритма
Логически алгоритм можно разделить на три части, которые на каждом шаге выполняются независимо. Внутри каждой части происходит [math]\displaystyle{ 2^{2N}-2^{2(N-1)} }[/math] независимых присвоений, где [math]\displaystyle{ N }[/math] - номер шага алгоритма, причем размерность матрицы на шаге [math]\displaystyle{ N }[/math] равна [math]\displaystyle{ 2^N }[/math]. При этом необходимо ждать завершения предыдущего шага, то есть необходимы синхронизирующие блокировки.
Входные и выходные данные алгоритма
Входные данные: [math]\displaystyle{ N }[/math] - размерность матрицы.
Выходные данные: матрица размером [math]\displaystyle{ N\times N }[/math].
Объем выходных данных: [math]\displaystyle{ N^2 }[/math].
Свойства алгоритма
Алгоритм полностью детерминирован.
Программная реализация алгоритма
Существующие реализации алгоритма
Реализация MATLAB [1]
Реализация PYTHON [2]
Реализация WOLFRAM [3]
На языке Java реализован класс Hadamard не входящий в стандарт языка. С кодом можно ознакомиться по ссылке[4].
Литература
1. Мак-Вильямс Ф., Слоэн Н. — "Теория кодов, исправляющих ошибки" (1979)
2. Кронберг, Ю.И. Ожигов, А.Ю. Чернявский — "Алгебраический аппарат квантовой информатики 2"
3. М. Н. Аршинов, Л. Е. Садовский — "Коды и математика" (1983)