Участник:Ivanov.kir.m/Быстрое дискретное преобразование Фурье: различия между версиями
| Строка 5: | Строка 5: | ||
| pf_width = <math>n</math> | | pf_width = <math>n</math> | ||
| input_data = <math>n</math> действительных чисел | | input_data = <math>n</math> действительных чисел | ||
| − | | output_data = <math>\lfloor | + | | output_data = <math>\lfloor n/2 \rfloor+1</math> комплексных чисел |
}} | }} | ||
'''Быстрое преобразование Фурье (БПФ, FFT)''' — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем <math>O(N^{2})</math>, требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность <math>O(N\log(N))</math>. | '''Быстрое преобразование Фурье (БПФ, FFT)''' — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем <math>O(N^{2})</math>, требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность <math>O(N\log(N))</math>. | ||
| Строка 14: | Строка 14: | ||
Одним из вариантов '''быстрого преобразования Фурье''' для вектора '''действительных чисел''' с размерностью равной степени двойки является '''алгоритм Кули-Тьюки'''. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет '''эрмитовой избыточности''' (''Hermitian redundancy'') , т.е. <math>out[i]</math> является сопряженным с <math>out[n-i]</math>. Это обстоятельство позволяет достичь роста скорости и снижения затрат памяти примерно в 2 раза по сравнению с комплексным аналогом алгоритма. | Одним из вариантов '''быстрого преобразования Фурье''' для вектора '''действительных чисел''' с размерностью равной степени двойки является '''алгоритм Кули-Тьюки'''. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет '''эрмитовой избыточности''' (''Hermitian redundancy'') , т.е. <math>out[i]</math> является сопряженным с <math>out[n-i]</math>. Это обстоятельство позволяет достичь роста скорости и снижения затрат памяти примерно в 2 раза по сравнению с комплексным аналогом алгоритма. | ||
| − | == Математическое описание алгоритма == | + | === Математическое описание алгоритма === |
| + | Входные данные: вектор действительных чисел <math>a = (a_1,a_2,...,a_n)</math>. | ||
| + | Выходные данные: вектор комплексных чисел <math>b = (b_1,b_2,...,b_(\lfloor n/2 \rfloor+1))</math>. | ||
| − | + | '''''Замечание:''''' поскольку '''алгоритм Кули-Тьюки''' применим только к векторам '''размерности степени двойки''', вектора иной размерности необходимо '''дополнять''' до ближайшей степени двойки. Данный факт делает '''алгоритм Кули-Тьюки''' не самым эффективным алгоритмом БПФ, поскольку необходимость дополнения до степени двойки может сильно усложнить задачу. | |
| − | + | ==== Рекурсивное описание ==== | |
| − | == | + | Алгоритм: |
| − | + | 1. Входной вектор a = (a_1,a_2,...,a_n) дополняется элементами до ближайшей степени двойки | |
| − | + | Вектор записывается по строкам по 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>-й шаг вычисляет только суммы и разности. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
Версия 14:26, 18 сентября 2016
| Алгоритм Кули-Тьюки одномерного преобразования Фурье для действительных чисел | |
| Последовательный алгоритм | |
| Последовательная сложность | O (n log_{2} n) |
| Объём входных данных | n действительных чисел |
| Объём выходных данных | \lfloor n/2 \rfloor+1 комплексных чисел |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | O (log_{2} n) |
| Ширина ярусно-параллельной формы | n |
Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем O(N^{2}), требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность O(N\log(N)).
Содержание
1 ЧАСТЬ. Свойства и структура алгоритмов
1.1 Общее описание алгоритма
Одним из вариантов быстрого преобразования Фурье для вектора действительных чисел с размерностью равной степени двойки является алгоритм Кули-Тьюки. Отличительной особенностью данного алгоритма является то, что он обходится без использования специфических приемов, использующихся именно для степеней четверки, восьмерки и т.п. Однако благодаря тому, что на вход данному алгоритму подается вектор чисто вещественных чисел, выходной вектор удовлетворяет эрмитовой избыточности (Hermitian redundancy) , т.е. out[i] является сопряженным с out[n-i]. Это обстоятельство позволяет достичь роста скорости и снижения затрат памяти примерно в 2 раза по сравнению с комплексным аналогом алгоритма.
1.1.1 Математическое описание алгоритма
Входные данные: вектор действительных чисел a = (a_1,a_2,...,a_n). Выходные данные: вектор комплексных чисел b = (b_1,b_2,...,b_(\lfloor n/2 \rfloor+1)).
Замечание: поскольку алгоритм Кули-Тьюки применим только к векторам размерности степени двойки, вектора иной размерности необходимо дополнять до ближайшей степени двойки. Данный факт делает алгоритм Кули-Тьюки не самым эффективным алгоритмом БПФ, поскольку необходимость дополнения до степени двойки может сильно усложнить задачу.
1.1.1.1 Рекурсивное описание
Алгоритм: 1. Входной вектор a = (a_1,a_2,...,a_n) дополняется элементами до ближайшей степени двойки Вектор записывается по строкам по 2 элемента в каждой. После этого над каждой строкой выполняется преобразование Фурье порядка 2, получившиеся элементы умножаются на поворотные множители exp (2 \pi i(m-1)(j-1)/n) (m - номер строки, j - номер столбца), после чего выполняется БПФ порядка n/2 над каждым из столбцов. Поскольку для 1-го столбца поворотные множители равны 1, то реально умножение на них не выполняется, а умножения на поворотные множители элементов второго столбца соединяются с преобразованием Фурье порядка 2. Эта комбинация, называемая "бабочкой" в среде специалистов по БПФ, и является основной операцией в простом алгоритме Кули-Тьюки. "Бабочка" состоит из вычисления суммы двух комплексных чисел, а также из вычисления их разности с последующим умножением на комплексное число. Всего на каждом шаге выполняется n/2 "бабочек", а шагов - l-1. Последний, l-й шаг вычисляет только суммы и разности.
2 ЧАСТЬ. Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.3 Динамические характеристики и эффективность реализации алгоритма
2.4 Существующие реализации алгоритма
3 Литература
[1] Википедия [Электронный ресурс]. Тема: Быстрое преобразование Фурье – Электрон. дан. – URL Быстрое преобразование Фурье (дата обращения 17.09.2016)
