Приложение 8 - История изменений

ASA: Полностью удалено содержимое страницы

2015-09-17T08:17:03Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:17, 17 сентября 2015
Строка 1:		Строка 1:
	~~= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =~~

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

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

	'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

	~~Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).~~

	~~При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>~~

	~~==== Рекурсивное описание ====~~

	Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
	получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
	Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
	~~<math>l</math>-й шаг вычисляет только суммы и разности.~~

	~~==== Тригонометрические функции ====~~

	Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

	Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

	Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

	Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
	При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

	Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

	~~=== Информационный граф ===~~
	[[file:Cooley-Tukey Fourier Transform algorithm.png\|center\|thumb\|600px\|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

	Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

	Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

	~~'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~'''Объём входных данных''': <math>n</math> .~~

	~~'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).~~

	~~'''Объём выходных данных''': <math>n</math>.~~

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

	При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

	~~При этом алгоритм полностью детерминирован.~~

	Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

	~~== Литература ==~~

	~~<references />~~

ASA в 08:16, 17 сентября 2015

2015-09-17T08:16:31Z

← Предыдущая версия	Версия от 08:16, 17 сентября 2015
Строка 1:	Строка 1:
		= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =

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

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

		'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

		Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).

		Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).

		При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>

		==== Рекурсивное описание ====

		Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
		получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
		Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
		<math>l</math>-й шаг вычисляет только суммы и разности.

		==== Тригонометрические функции ====

		Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

		Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

		Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

		Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
		При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

		Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

		=== Информационный граф ===
		[[file:Cooley-Tukey Fourier Transform algorithm.png\|center\|thumb\|600px\|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

		Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

		Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

		'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).

		'''Объём входных данных''': <math>n</math> .

		'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).

		'''Объём выходных данных''': <math>n</math>.

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

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

		При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

		При этом алгоритм полностью детерминирован.

		Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

		== Литература ==

		<references />

ASA: Полностью удалено содержимое страницы

2015-09-16T14:07:12Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 14:07, 16 сентября 2015
Строка 1:		Строка 1:
	~~= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =~~

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

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

	'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

	~~Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).~~

	~~При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>~~

	~~==== Рекурсивное описание ====~~

	Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
	получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
	Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
	~~<math>l</math>-й шаг вычисляет только суммы и разности.~~

	~~==== Тригонометрические функции ====~~

	Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

	Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

	Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

	Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
	При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

	Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

	~~=== Информационный граф ===~~
	[[file:Cooley-Tukey Fourier Transform algorithm.png\|center\|thumb\|600px\|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

	Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

	Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

	~~'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~'''Объём входных данных''': <math>n</math> .~~

	~~'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).~~

	~~'''Объём выходных данных''': <math>n</math>.~~

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

	При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

	~~При этом алгоритм полностью детерминирован.~~

	Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

	~~== Литература ==~~

	~~<references />~~

ASA в 14:06, 16 сентября 2015

2015-09-16T14:06:38Z

← Предыдущая версия	Версия от 14:06, 16 сентября 2015
Строка 1:	Строка 1:
		= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =

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

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

		'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

		Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).

		Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).

		При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>

		==== Рекурсивное описание ====

		Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
		получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
		Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
		<math>l</math>-й шаг вычисляет только суммы и разности.

		==== Тригонометрические функции ====

		Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

		Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

		Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

		Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
		При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

		Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

		=== Информационный граф ===
		[[file:Cooley-Tukey Fourier Transform algorithm.png\|center\|thumb\|600px\|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

		Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

		Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

		'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).

		'''Объём входных данных''': <math>n</math> .

		'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).

		'''Объём выходных данных''': <math>n</math>.

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

		Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

		При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

		При этом алгоритм полностью детерминирован.

		Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

		== Литература ==

		<references />

ASA: Полностью удалено содержимое страницы

2015-09-11T08:10:56Z

Полностью удалено содержимое страницы

← Предыдущая версия		Версия от 08:10, 11 сентября 2015
Строка 1:		Строка 1:
	~~= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =~~

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

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

	'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

	~~Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).~~

	~~При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>~~

	~~==== Рекурсивное описание ====~~

	Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
	получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
	Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
	~~<math>l</math>-й шаг вычисляет только суммы и разности.~~

	~~==== Тригонометрические функции ====~~

	Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

	Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

	Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

	Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
	При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

	Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

	~~=== Информационный граф ===~~
	[[file:Cooley-Tukey Fourier Transform algorithm.png\|center\|thumb\|600px\|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

	Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

	Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

	~~'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).~~

	~~'''Объём входных данных''': <math>n</math> .~~

	~~'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).~~

	~~'''Объём выходных данных''': <math>n</math>.~~

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

	Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

	При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

	~~При этом алгоритм полностью детерминирован.~~

	Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

	~~== Литература ==~~

	~~<references />~~

ASA: Новая страница: «= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки = == Свой…»

2015-09-11T08:10:25Z

Новая страница: «= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки = == Свой…»

Новая страница

= Простой алгоритм Кули-Тьюки быстрого преобразования Фурье для степеней двойки =

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

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

'''Простой алгоритм Кули-Тьюки''' - один из вариантов '''быстрого преобразования Фурье''' для ''комплексных'' векторов с размерностью, равной степени двойки, без использования специфичных приёмов, использующихся для степеней четвёрки, восьмёрки и др.<ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> Заключается в последовательном применении метода быстрого преобразования Фурье и сведении преобразования к последовательности преобразований Фурье размерности 2 и выполнения умножений на т.н. поворотные множители. Несмотря на то, что проигрывает алгоритмам Кули-Тьюки, разлагающим степени двойки на степени 4, 8 и др. и использующим их специфику, весьма распространён, что связано с самой простой из алгоритмов БПФ записью программной реализации.

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

Исходные данные: преобразуемый комплексный вектор <math>a</math> (элементы <math>a_{i}</math>).

Вычисляемые данные: комплексный вектор - результат преобразования <math>b</math> (элементы <math>b_{i}</math>).

При этом размерность векторов - <math>n</math>, причём <math>n = 2^l</math>

==== Рекурсивное описание ====

Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2,
получившиеся элементы умножаются на поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math> (<math>m</math> - номер строки, <math>j</math> - номер столбца), после чего выполняется БПФ порядка <math>n/2</math> над каждым из столбцов.
Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется <math>n/2</math> "бабочек", а шагов - <math>l-1</math>. Последний,
<math>l</math>-й шаг вычисляет только суммы и разности.

==== Тригонометрические функции ====

Несмотря на то, что в вычислениях используются поворотные множители <math>exp (2 \pi i(m-1)(j-1)/n)</math>, нецелесообразно вычислять их в процессе выполнения алгоритма Кули-Тьюки, поскольку вычисления косинусов и синусов (в мнимой экспоненте) тогда составили бы львиную долю вычислений алгоритма. Поэтому обычно (как и в других версиях БПФ) поворотные множители вычисляются заранее и хранятся в специальном массиве. Здесь мы будем предполагать, что алгоритм выполняется именно так.

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

Вычислительное ядро алгоритма составляют "бабочки", состоящие из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего их <math>(1/2) n log_{2} n </math> штук, при этом в <math>n/2</math> из них умножение не выполняется.

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

Макроструктура алгоритма лучше всего описывается рекурсивно, как <math>n/2</math> преобразований Фурье порядка 2, умножение <math>n/2</math> пар комплексных чисел и затем 2 БПФ порядка <math>n/2</math>.

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

Нерекурсивная схема организации состоит в том, что на каждом шаге (а всего их <math>log_{2} n </math>) для выполнения "бабочки" все элементы разбиваются на <math>n/2</math> пар. В зависимости от номера шага, разница координат для каждой пары элементов удваивается. На первом шагу она равна 1, на последнем - <math>n/2</math>.
При этом результат суммы записывается в элемент с меньшим номером, а результат вычитания с последующим умножением - в элемент с большим.

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

Если считать только главные члены выражений для последовательной сложности алгоритма, то простой алгоритм Кули-Тьюки может быть выполнен за <math>n log_{2} n</math> операций комплексного сложения и <math>(1/2) n log_{2} n </math>операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''линейно-логарифмическому'' классу по последовательной сложности.

=== Информационный граф ===
[[file:Cooley-Tukey Fourier Transform algorithm.png|center|thumb|600px|Рисунок 1. Простой алгоритм Кули-Тьюки для n=8. Op+ - операция сложения двух комплексных чисел. Op- - операция вычитания двух комплексных чисел и умножения результата вычитания на комплексное число (поворотный множитель). В последнем столбце операций умножение не производится. Привязка вершин выполнена по оси абсцисс - к параметру внешнего цикла, по оси ординат - к обрабатываемым элементам массива]]

Как видно из рисунка, этот граф не является линейным ни по размерам, ни по формулам для дуг графа. По размерам он линейно-логарифмический, а формулы дуг имеют экспоненциальные компоненты.В элементарной "бабочке" на i-м шаге каждый раз участвует пара элементов массива, у которых запись их номеров, уменьшенных на единицу, в двоичной системе различается только в i-1-м бите.

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

Если считать только главные члены выражений, то простой алгоритм Кули-Тьюки имеет критический путь, состоящий из <math>log_{2} n </math> операций комплексного сложения/вычитания и <math>log_{2} n </math> операций комплексного умножения. Таким образом, простой алгоритм Кули-Тьюки может быть отнесён к ''логарифмическому'' классу по параллельной сложности. По ширине ЯПФ сложность алгоритма ''линейна''.

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

'''Входные данные''': вектор <math>a</math> (элементы <math>a_{i}</math>).

'''Объём входных данных''': <math>n</math> .

'''Выходные данные''': вектор <math>b</math> (элементы <math>b_{i}</math>).

'''Объём выходных данных''': <math>n</math>.

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

Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является ''линейным''.

При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – ''логарифмическая''.

При этом алгоритм полностью детерминирован.

Заметим, что простой алгоритм Кули-Тьюки не является оптимальным даже для векторов размером степень двойки. Однако здесь мы не рассматриваем другие алгоритмы БПФ.

== Литература ==

<references />