Быстрое преобразование Фурье

Алгоритм дискретного преобразования Фурье O(N log N)

Пример структуры алгоритма БПФ с использованием разложения на БПФ половинного размера.

Дискретный анализ Фурье суммы косинусоидальных волн на частоте 10, 20, 30, 40 и 50 Гц.

Быстрое преобразование Фурье ( БПФ ) — это алгоритм , который вычисляет дискретное преобразование Фурье (ДПФ) последовательности или его обратное преобразование (ИДПФ). Анализ Фурье преобразует сигнал из исходной области (часто времени или пространства) в представление в частотной области и наоборот. ДПФ получается путем разложения последовательности значений на компоненты разных частот. ^[1] Эта операция полезна во многих областях, но ее вычисление непосредственно из определения часто бывает слишком медленным, чтобы быть практичным. БПФ быстро вычисляет такие преобразования путем факторизации матрицы ДПФ в произведение редких (в основном нулевых) факторов. ^[2] В результате удается снизить сложность вычисления ДПФ от , которая возникает, если просто применить определение ДПФ, до , где n - размер данных. Разница в скорости может быть огромной, особенно для длинных наборов данных, где n может исчисляться тысячами или миллионами. При наличии ошибки округления многие алгоритмы БПФ оказываются гораздо более точными, чем прямое или косвенное вычисление определения ДПФ. Существует множество различных алгоритмов БПФ, основанных на широком спектре опубликованных теорий, от простой арифметики комплексных чисел до теории групп и теории чисел . ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

Представление на основе времени (вверху) и представление на основе частоты (внизу) одного и того же сигнала, причем нижнее представление может быть получено из верхнего путем преобразования Фурье.

Быстрые преобразования Фурье широко используются в инженерии , музыке, науке и математике. Основные идеи были популяризированы в 1965 году, но некоторые алгоритмы были разработаны еще в 1805 году. ^[1] В 1994 году Гилберт Стрэнг описал БПФ как «самый важный численный алгоритм нашего времени», ^{[3] [4]} и был включен в десятку лучших алгоритмов 20-го века по версии журнала IEEE Computing in Science & Engineering . ^[5]

Самые известные алгоритмы БПФ основаны на факторизации n , но существуют БПФ со сложностью для всех, даже простых n . Многие алгоритмы БПФ зависят только от того факта, что это примитивный корень n -й степени из единицы , и, таким образом, могут быть применены к аналогичным преобразованиям над любым конечным полем , таким как теоретико-числовые преобразования . Поскольку обратное ДПФ — это то же самое, что и ДПФ, но с противоположным знаком в показателе степени и коэффициентом 1/ n , любой алгоритм БПФ можно легко адаптировать для него. ${\displaystyle O(n\log n)}$ ${\textstyle e^{-2\pi i/n}}$

История

Развитие быстрых алгоритмов ДПФ можно проследить до неопубликованной работы Карла Фридриха Гаусса 1805 года об орбитах астероидов Паллада и Юнона . Гаусс хотел интерполировать орбиты на основе выборочных наблюдений; ^{[6] [7]} его метод был очень похож на тот, который был опубликован в 1965 году Джеймсом Кули и Джоном Тьюки , которым обычно приписывают изобретение современного общего алгоритма БПФ. Хотя работа Гаусса предшествовала даже результатам Жозефа Фурье 1822 года, он не анализировал сложность метода и в конечном итоге использовал другие методы для достижения той же цели.

Между 1805 и 1965 годами некоторые версии БПФ были опубликованы другими авторами. Фрэнк Йейтс в 1932 году опубликовал свою версию под названием « Алгоритм взаимодействия» , которая обеспечивала эффективное вычисление преобразований Адамара и Уолша . ^[8] Алгоритм Йейтса до сих пор используется в области статистического планирования и анализа экспериментов. В 1942 году Г. К. Дэниэлсон и Корнелиус Ланцос опубликовали свою версию расчета ДПФ для рентгеновской кристаллографии , области, где вычисление преобразований Фурье представляло собой серьезное узкое место. ^{[9] [10]} В то время как многие методы в прошлом были сосредоточены на уменьшении постоянного коэффициента для вычислений, используя преимущества «симметрии», Дэниэлсон и Ланцос поняли, что можно использовать «периодичность» и применить «трюк удвоения» к « double [ n ] с лишь немногим более чем удвоенным трудом», хотя, как и Гаусс, они не провели анализ, чтобы обнаружить, что это привело к масштабированию. ^[11] ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

Джеймс Кули и Джон Тьюки независимо заново открыли эти более ранние алгоритмы ^[7] и опубликовали более общее БПФ в 1965 году, которое применимо, когда n является составным и не обязательно представляет собой степень 2, а также для анализа масштабирования . ^[12] Тьюки пришла в голову эта идея во время заседания Научно-консультативного комитета при президенте Кеннеди , где обсуждалась тема обнаружения ядерных испытаний Советского Союза путем установки датчиков для окружения страны извне. Для анализа выходных данных этих датчиков потребуется алгоритм БПФ. В дискуссии с Тьюки Ричард Гарвин признал общую применимость алгоритма не только к проблемам национальной безопасности, но и к широкому кругу задач, включая одну, представляющую для него непосредственный интерес, определение периодичности ориентаций спинов в трехмерном кристалле. гелия-3. ^[13] Гарвин передал идею Тьюки Кули (оба работали в лабораториях IBM Watson ) для реализации. ^[14] Кули и Тьюки опубликовали статью за относительно короткий срок — шесть месяцев. ^[15] Поскольку Тьюки не работал в IBM, патентоспособность идеи была поставлена ​​под сомнение, и алгоритм стал достоянием общественности, что благодаря компьютерной революции следующего десятилетия сделало БПФ одним из незаменимых алгоритмов в цифровой обработке сигналов . ${\textstyle O(n\log n)}$

Определение

Пусть это будут комплексные числа . ДПФ определяется по формуле ${\displaystyle x_{0},\ldots ,x_{n-1}}$

${\displaystyle X_{k}=\sum _{m=0}^{n-1}x_{m}e^{-i2\pi km/n}\qquad k=0,\ldots ,n-1,}$

где – примитивный корень n -й степени из 1. ${\displaystyle e^{i2\pi /n}}$

Оценка этого определения напрямую требует операций: имеется n выходов X _k  , и каждый выход требует суммы n членов. БПФ — это любой метод вычисления одних и тех же результатов в операциях. Все известные алгоритмы БПФ требуют операций, хотя нет известных доказательств того, что меньшая сложность невозможна. ^[16] ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$ ${\textstyle O(n\log n)}$

Чтобы проиллюстрировать экономию при использовании БПФ, рассмотрим подсчет комплексных умножений и сложений точек данных. Оценка сумм ДПФ напрямую включает в себя сложные умножения и сложные сложения, операции из которых можно сэкономить, исключив тривиальные операции, такие как умножение на 1, оставив около 30 миллионов операций. Напротив, алгоритм Кули-Тьюки с основанием 2 для n , степени 2, может вычислить тот же результат только с помощью комплексных умножений (опять же, игнорируя упрощения умножения на 1 и тому подобное) и сложных сложений, всего около 30 000 операций - в тысячу раз меньше, чем при прямой оценке. На практике реальная производительность современных компьютеров обычно зависит от других факторов, помимо скорости арифметических операций, и анализ является сложным предметом (например, см. Frigo & Johnson , 2005), ^[17] , но общее улучшение от до сохраняется. ${\textstyle n=4096}$ ${\textstyle n^{2}}$ ${\textstyle n(n-1)}$ ${\textstyle O(n)}$ ${\textstyle (n/2)\log _{2}(n)}$ ${\textstyle n\log _{2}(n)}$ ${\textstyle O(n^{2})}$ ${\textstyle O(n\log n)}$

Алгоритмы

Алгоритм Кули – Тьюки

Безусловно, наиболее часто используемым БПФ является алгоритм Кули – Тьюки. Это алгоритм «разделяй и властвуй» , который рекурсивно разбивает ДПФ любого составного размера на множество меньших ДПФ размеров и , а также умножения на комплексные корни из единицы, традиционно называемые коэффициентами вращения (по Джентльмену и Санде, 1966). ^[18] ${\textstyle n=n_{1}n_{2}}$ ${\textstyle n_{1}}$ ${\textstyle n_{2}}$ ${\displaystyle O(n)}$

Этот метод (и общая идея БПФ) был популяризирован публикацией Кули и Тьюки в 1965 году ^[12] , но позже было обнаружено ^[1] , что эти два автора независимо заново изобрели алгоритм, известный Карлу Фридриху Гауссу. около 1805 г. ^[19] (и впоследствии несколько раз переоткрыт в ограниченных формах).

Наиболее известное использование алгоритма Кули-Тьюки состоит в разделении преобразования на две части размера n/2 на каждом шаге и, следовательно, ограничено размерами степени двойки, но в целом можно использовать любую факторизацию (как было показано известный как Гауссу, так и Кули/Тьюки ^[1] ). Они называются случаями счисления счисления-2 и смешанного счисления соответственно (и другие варианты, такие как БПФ с разделенным основанием, также имеют свои собственные названия). Хотя основная идея является рекурсивной, большинство традиционных реализаций меняют алгоритм, чтобы избежать явной рекурсии. Кроме того, поскольку алгоритм Кули-Тьюки разбивает ДПФ на более мелкие ДПФ, его можно произвольно комбинировать с любым другим алгоритмом ДПФ, например описанным ниже.

Другие алгоритмы БПФ

Существуют другие алгоритмы БПФ, кроме Кули – Тьюки.

Для взаимно простых и можно использовать алгоритм простого фактора (Гуда-Томаса) (PFA), основанный на китайской теореме об остатках , для факторизации ДПФ аналогично Кули-Тьюки, но без коэффициентов вращения. Алгоритм Рейдера-Бреннера (1976) ^[20] представляет собой факторизацию типа Кули-Тьюки, но с чисто мнимыми коэффициентами вращения, сокращающими умножения за счет увеличения сложений и снижения числовой стабильности ; Позже он был заменен вариантом Кули – Тьюки с разделенной системой счисления (который обеспечивает тот же счетчик умножения, но с меньшим количеством сложений и без ущерба для точности). Алгоритмы, которые рекурсивно разлагают ДПФ на более мелкие операции, отличные от ДПФ, включают алгоритмы Брюуна и QFT. (Алгоритмы Рейдера-Бреннера ^[20] и QFT были предложены для размеров степени двойки, но возможно, что их можно адаптировать к общему составному n . Алгоритм Брюуна применим к произвольным даже составным размерам.) Алгоритм Брюуна , в частности, , основано на интерпретации БПФ как рекурсивной факторизации полинома , здесь в полиномы с реальными коэффициентами формы и . ${\textstyle n=n_{1}n_{2}}$ ${\textstyle n_{1}}$ ${\textstyle n_{2}}$ ${\displaystyle z^{n}-1}$ ${\displaystyle z^{m}-1}$ ${\displaystyle z^{2m}+az^{m}+1}$

Другая полиномиальная точка зрения используется в алгоритме БПФ Винограда ^{[21] [22]} , который разбивается на круговые многочлены — они часто имеют коэффициенты 1, 0 или -1 и, следовательно, требуют небольшого количества (если таковые имеются) умножений, поэтому Винограда можно используется для получения БПФ с минимальным умножением и часто используется для поиска эффективных алгоритмов для небольших коэффициентов. Действительно, Виноград показал, что ДПФ можно вычислить только с помощью иррациональных умножений, что привело к доказанной достижимой нижней границе количества умножений для размеров степени двойки; к сожалению, это происходит за счет многих дополнительных дополнений, а это компромисс, который больше не выгоден для современных процессоров с аппаратными множителями . В частности, Виноград также использует PFA, а также алгоритм Радера для БПФ простых размеров . ${\displaystyle z^{n}-1}$ ${\displaystyle O(n)}$

Алгоритм Рейдера , использующий существование генератора для мультипликативной группы по модулю простого числа n , выражает ДПФ простого размера n как циклическую свертку (составного) размера n – 1 , которая затем может быть вычислена с помощью пары обычных БПФ через теорема о свертке (хотя Виноград использует и другие методы свертки). Другое БПФ простого размера принадлежит Л. И. Блюстейну и иногда называется алгоритмом chirp-z ; он также повторно выражает ДПФ как свертку, но на этот раз того же размера (который может быть дополнен нулями до степени двойки и оценен, например, с помощью БПФ Кули – Тьюки по основанию 2) через тождество

${\displaystyle nk=-{\frac {(k-n)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}.}$

Шестиугольное быстрое преобразование Фурье (HFFT) направлено на вычисление эффективного БПФ для данных с гексагональной выборкой с использованием новой схемы адресации для гексагональных сеток, называемой адресацией набора массивов (ASA).

Алгоритмы БПФ, специализирующиеся на реальных или симметричных данных.

Во многих приложениях входные данные для ДПФ являются чисто реальными, и в этом случае выходные данные удовлетворяют симметрии

${\displaystyle X_{n-k}=X_{k}^{*}}$

и для этой ситуации были разработаны эффективные алгоритмы БПФ (см., например, Соренсен, 1987). ^{[23] [24]} Один из подходов состоит в использовании обычного алгоритма (например, Кули-Тьюки) и удалении избыточных частей вычислений, что позволяет сэкономить примерно в два раза время и память. В качестве альтернативы можно выразить ДПФ вещественного ввода четной длины как комплексное ДПФ половины длины (действительная и мнимая части которого являются четными/нечетными элементами исходных реальных данных) с последующими операциями постобработки. ${\displaystyle O(n)}$

Когда-то считалось, что ДПФ реального ввода можно более эффективно вычислять с помощью дискретного преобразования Хартли (ДНТ), но впоследствии утверждалось, что обычно можно найти специализированный алгоритм ДПФ реального ввода (БПФ), который требует меньше операций, чем соответствующий алгоритм DHT (FHT) для того же количества входов. ^[23] Алгоритм Брууна (выше) — это еще один метод, который изначально предлагался для использования реальных входных данных, но он не оказался популярным.

Существуют дополнительные специализации БПФ для случаев реальных данных, которые имеют четную/нечетную симметрию, и в этом случае можно получить еще один коэффициент примерно в два раза по времени и памяти, и ДПФ становится дискретным косинус / синусоидальным преобразованием(ями) ( DCT / DST ). Вместо прямой модификации алгоритма БПФ для этих случаев DCT/DST также можно вычислять с помощью БПФ реальных данных в сочетании с предварительной и постобработкой. ${\displaystyle O(n)}$

Вычислительные проблемы

Границы сложности и количества операций

Нерешенная задача в информатике :

Какова нижняя граница сложности алгоритмов быстрого преобразования Фурье? Могут ли они быть быстрее, чем ? ${\displaystyle O(N\log N)}$

(еще нерешенные проблемы по информатике)

Фундаментальным вопросом, вызывающим давний теоретический интерес, является доказательство нижних границ сложности и точного количества операций быстрого преобразования Фурье, и многие открытые проблемы остаются. Строго не доказано, действительно ли ДПФ требуют (т. е. порядка или большего) операций, даже для простого случая степени двух размеров, хотя алгоритмы с меньшей сложностью неизвестны. В частности, в центре внимания таких вопросов обычно находится подсчет арифметических операций, хотя реальная производительность современных компьютеров определяется многими другими факторами, такими как оптимизация кэша или конвейера ЦП . ${\textstyle \Omega (n\log n)}$ ${\displaystyle n\log n}$

Следуя работе Шмуэля Винограда (1978), ^[21] известна точная нижняя граница количества действительных умножений, необходимых для БПФ. Можно показать, что для вычисления ДПФ длины степени двойки требуются только иррациональные действительные умножения . Более того, известны явные алгоритмы, позволяющие добиться такого подсчета (Heideman & Burrus , 1986; ^[25] Duhamel, 1990 ^[26] ). Однако эти алгоритмы требуют слишком большого количества дополнений, чтобы быть практичными, по крайней мере, на современных компьютерах с аппаратными умножителями (Дюамель, 1990; ^[26] Frigo & Johnson , 2005). ^[17] ${\displaystyle \Theta (n)}$ ${\textstyle 4n-2\log _{2}^{2}(n)-2\log _{2}(n)-4}$ ${\displaystyle n=2^{m}}$

Точная нижняя граница количества необходимых дополнений неизвестна, хотя нижние оценки были доказаны при некоторых ограничительных предположениях в отношении алгоритмов. В 1973 году Моргенштерн ^[27] доказал нижнюю границу количества сложений для алгоритмов, в которых мультипликативные константы имеют ограниченные величины (что верно для большинства, но не для всех алгоритмов БПФ). Пан (1986) ^[28] доказал нижнюю оценку, предполагая оценку меры «асинхронности» алгоритма БПФ, но общность этого предположения неясна. В случае n степени двойки Пападимитриу ( 1979) ^[29] утверждал , что количество сложений комплексных чисел, достигаемых алгоритмами Кули-Тьюки, является оптимальным при определенных предположениях о графике алгоритма (его предположения подразумевают, среди прочего, кроме того, не используются никакие аддитивные тождества в корнях единицы). (Этот аргумент подразумевает, что требуются как минимум реальные сложения, хотя это не является жесткой границей, поскольку дополнительные сложения требуются как часть умножения комплексных чисел.) До сих пор ни один опубликованный алгоритм БПФ не достигал меньшего количества сложений, чем сложение комплексных чисел ( или их эквивалент) для степени двойки n . ${\displaystyle \Omega (n\log n)}$ ${\displaystyle \Omega (n\log n)}$ ${\textstyle n\log _{2}n}$ ${\textstyle 2N\log _{2}N}$ ${\textstyle n\log _{2}n}$

Третья проблема — минимизировать общее количество действительных умножений и сложений, иногда называемое «арифметической сложностью» (хотя в этом контексте рассматривается точный подсчет, а не асимптотическая сложность). Опять же, не было доказано никакой жесткой нижней границы. Однако с 1968 года самый низкий опубликованный счетчик для степени двойки n долгое время достигался с помощью алгоритма БПФ с расщепленным основанием , который требует реальных умножений и сложений для n > 1 . Недавно это число было сокращено до (Джонсон и Фриго, 2007; ^[16] Ланди и Ван Баскирк, 2007 ^[30] ). Было показано , что немного больший отсчет (но все же лучше, чем разделенное основание системы счисления для n ≥ 256 ) является доказуемо оптимальным для n ≤ 512 при дополнительных ограничениях на возможные алгоритмы (потоковые графы, подобные расщепленному основанию, с мультипликативными коэффициентами единичного модуля), путем уменьшения к проблеме выполнимости по модулю теорий , которую можно решить грубой силой (Haynal & Haynal, 2011). ^[31] ${\textstyle 4n\log _{2}(n)-6n+8}$ ${\textstyle \sim {\frac {34}{9}}n\log _{2}n}$

Большинство попыток снизить или доказать сложность алгоритмов БПФ были сосредоточены на обычном случае сложных данных, поскольку он является самым простым. Однако БПФ для комплексных данных настолько тесно связаны с алгоритмами для решения подобных задач, таких как БПФ для реальных данных, дискретные косинусные преобразования , дискретные преобразования Хартли и т. д., что любое улучшение одного из них немедленно приведет к улучшению других ( Дюамель и Веттерли, 1990). ^[32]

Приближения

Все рассмотренные выше алгоритмы БПФ точно вычисляют ДПФ (т. е. пренебрегая ошибками с плавающей запятой ). Однако было предложено несколько алгоритмов «БПФ», которые вычисляют ДПФ приблизительно с ошибкой, которую можно сделать сколь угодно малой за счет увеличения объема вычислений. Такие алгоритмы обменивают ошибку аппроксимации на увеличение скорости или других свойств. Например, приближенный алгоритм БПФ Эдельмана и др. (1999) ^[33] достигает меньших требований к связи для параллельных вычислений с помощью метода быстрых мультиполей . Приближенное БПФ на основе вейвлетов , разработанное Гуо и Буррусом (1996) ^[34], учитывает разреженные входные/выходные данные (локализация по времени/частоте) более эффективно, чем это возможно при точном БПФ. Другой алгоритм для приближенного вычисления подмножества результатов ДПФ принадлежит Шентову и др. (1995). ^[35] Алгоритм Эдельмана одинаково хорошо работает как для разреженных, так и для неразреженных данных, поскольку он основан на сжимаемости (дефиците ранга) самой матрицы Фурье, а не на сжимаемости (разреженности) данных. И наоборот, если данные разрежены, то есть если только k из n коэффициентов Фурье отличны от нуля, то сложность можно уменьшить до , и это, как было продемонстрировано, приводит к практическому ускорению по сравнению с обычным БПФ для n / k > 32 в примере с большим n ( n = 2 ²² ) с использованием вероятностного аппроксимационного алгоритма (который оценивает самые большие k коэффициентов с точностью до нескольких десятичных знаков). ^[36] ${\displaystyle O(k\log n\log n/k)}$

Точность

Алгоритмы БПФ допускают ошибки при использовании арифметики с плавающей запятой конечной точности, но эти ошибки обычно весьма малы; большинство алгоритмов БПФ, например Кули-Тьюки, обладают превосходными числовыми свойствами вследствие структуры попарного суммирования алгоритмов. Верхняя граница относительной ошибки для алгоритма Кули-Тьюки равна , по сравнению с наивной формулой ДПФ, ^[18] где 𝜀 — относительная точность машины с плавающей запятой. Фактически, среднеквадратичные (rms) ошибки намного лучше этих верхних границ, только для Кули-Тьюки и для наивного ДПФ (Шацман, 1996). ^[37] Эти результаты, однако, очень чувствительны к точности коэффициентов, используемых в БПФ (т.е. значений тригонометрической функции ), и нет ничего необычного в том, что неосторожные реализации БПФ имеют гораздо худшую точность, например, если они используют неточные значения. тригонометрические рекуррентные формулы. Некоторые БПФ, кроме Кули-Тьюки, такие как алгоритм Рейдера-Бреннера, по своей сути менее стабильны. ${\textstyle O(\varepsilon \log n)}$ ${\textstyle O(\varepsilon n^{3/2})}$ ${\textstyle O(\varepsilon {\sqrt {\log n}})}$ ${\textstyle O(\varepsilon {\sqrt {n}})}$

В арифметике с фиксированной запятой ошибки конечной точности, накапливаемые алгоритмами БПФ, хуже, при этом среднеквадратичные ошибки растут, как и в алгоритме Кули – Тьюки (Welch, 1969). ^[38] Достижение такой точности требует пристального внимания к масштабированию, чтобы минимизировать потерю точности, а алгоритмы БПФ с фиксированной точкой включают изменение масштаба на каждом промежуточном этапе разложения, как Кули-Тьюки. ${\textstyle O({\sqrt {n}})}$

Чтобы проверить правильность реализации БПФ, можно получить строгие гарантии во времени с помощью простой процедуры проверки линейности, импульсной характеристики и свойств сдвига во времени преобразования на случайных входных данных (Ergün, 1995). ^[39] ${\textstyle O(n\log n)}$

Многомерные БПФ

Как определено в статье о многомерном ДПФ , многомерное ДПФ

${\displaystyle X_{\mathbf {k} }=\sum _{\mathbf {n} =0}^{\mathbf {N} -1}e^{-2\pi i\mathbf {k} \cdot (\mathbf {n} /\mathbf {N} )}x_{\mathbf {n} }}$

преобразует массив x _n с d -мерным вектором индексов с помощью набора d вложенных суммаций ( по каждому j ), где деление выполняется поэлементно. Эквивалентно, это композиция последовательности из d наборов одномерных ДПФ, выполняемых по одному измерению за раз (в любом порядке). ${\textstyle \mathbf {n} =\left(n_{1},\ldots ,n_{d}\right)}$ ${\textstyle n_{j}=0\ldots N_{j}-1}$ ${\textstyle \mathbf {n} /\mathbf {N} =\left(n_{1}/N_{1},\ldots ,n_{d}/N_{d}\right)}$

Эта композиционная точка зрения сразу же обеспечивает самый простой и наиболее распространенный многомерный алгоритм ДПФ, известный как алгоритм строки-столбца (после двумерного случая, описанного ниже). То есть просто выполняется последовательность d одномерных БПФ (по любому из вышеперечисленных алгоритмов): сначала выполняется преобразование по измерению n ₁ , затем по измерению n ₂ и так далее (фактически работает любое упорядочение). Легко показать, что этот метод имеет обычную сложность, где общее количество преобразованных точек данных. В частности, существует n / n ₁ преобразований размера n ₁ и т. д., поэтому сложность последовательности БПФ равна: ${\textstyle O(n\log n)}$ ${\textstyle n=n_{1}\cdot n_{2}\cdots n_{d}}$

${\displaystyle {\begin{aligned}&{\frac {n}{n_{1}}}O(n_{1}\log n_{1})+\cdots +{\frac {n}{n_{d}}}O(n_{d}\log n_{d})\\[6pt]={}&O\left(n\left[\log n_{1}+\cdots +\log n_{d}\right]\right)=O(n\log n).\end{aligned}}}$

В двух измерениях x _k можно рассматривать как матрицу , и этот алгоритм соответствует сначала выполнению БПФ всех строк (соответственно столбцов), группировке полученных преобразованных строк (соответственно столбцов) вместе в другую матрицу, а затем выполнение БПФ для каждого из столбцов (соответственно строк) этой второй матрицы и аналогичная группировка результатов в окончательную матрицу результатов. ${\displaystyle n_{1}\times n_{2}}$ ${\displaystyle n_{1}\times n_{2}}$

При наличии более чем двух измерений для локальности кэша часто бывает выгодно группировать измерения рекурсивно. Например, трехмерное БПФ может сначала выполнять двумерное БПФ каждого плоского «среза» для каждого фиксированного n ₁ , а затем выполнять одномерное БПФ в направлении n ₁ . В более общем смысле, асимптотически оптимальный алгоритм без учета кэша состоит из рекурсивного разделения измерений на две группы , которые рекурсивно преобразуются (округление, если d нечетное) (см. Frigo and Johnson, 2005). ^[17] Тем не менее, это остается простой вариацией алгоритма строка-столбец, который в конечном итоге требует только одномерного алгоритма БПФ в качестве базового случая и по-прежнему имеет сложность. Еще одним вариантом является выполнение матричных транспозиций между преобразованиями последующих измерений, чтобы преобразования работали над смежными данными; это особенно важно для ситуаций с использованием внеъядерной и распределенной памяти , когда доступ к несмежным данным занимает чрезвычайно много времени. ${\textstyle (n_{1},\ldots ,n_{d/2})}$ ${\textstyle (n_{d/2+1},\ldots ,n_{d})}$ ${\displaystyle O(n\log n)}$

Существуют и другие алгоритмы многомерного БПФ, которые отличаются от алгоритма строки-столбца, хотя все они имеют сложность. Возможно, самым простым БПФ без строк и столбцов является алгоритм БПФ с векторным основанием , который является обобщением обычного алгоритма Кули – Тьюки, в котором на каждом шаге размеры преобразования делятся на вектор оснований. (Это также может иметь преимущества для кэша.) Самый простой случай векторного основания - это когда все основания равны (например, векторное основание-2 делит все измерения на два), но это не обязательно. Векторное основание счисления только с одним неединичным основанием за раз, т. е . по существу представляет собой алгоритм строки-столбца. Другие, более сложные методы включают алгоритмы полиномиального преобразования Нуссбаумера (1977), ^[40] , которые рассматривают преобразование с точки зрения сверток и полиномиальных произведений. См. Дюамель и Веттерли (1990) ^[32] для получения дополнительной информации и ссылок. ${\textstyle O(n\log n)}$ ${\textstyle \mathbf {r} =\left(r_{1},r_{2},\ldots ,r_{d}\right)}$ ${\textstyle \mathbf {r} =\left(1,\ldots ,1,r,1,\ldots ,1\right)}$

Другие обобщения

Обобщение сферических гармоник на сфере s ² с n ² узлами было описано Моленкампом ^[41] вместе с алгоритмом , сложность которого предположительно (но не доказана); Моленкамп также предоставляет реализацию в библиотеке libftsh. ^[42] Алгоритм сферической гармоники со сложностью описан Рохлиным и Тайгертом. ^[43] ${\textstyle O(n^{5/2}\log n)}$ ${\textstyle O(n^{2}\log ^{2}(n))}$ ${\textstyle O(n^{2}\log n)}$

Алгоритм быстрого свертывания аналогичен БПФ, за исключением того, что он работает с серией объединенных сигналов, а не с серией действительных или комплексных скалярных значений. Вращение (которое в БПФ представляет собой умножение на комплексный вектор) представляет собой круговой сдвиг формы сигнала компонента.

Различные группы также опубликовали алгоритмы «БПФ» для неравноотстоящих данных, как описано в Potts et al. (2001). ^[44] Такие алгоритмы не строго вычисляют ДПФ (которое определено только для равноотстоящих друг от друга данных), а, скорее, некоторую его аппроксимацию (неравномерное дискретное преобразование Фурье , или NDFT, которое само по себе часто вычисляется только приблизительно). В более общем плане существуют различные другие методы спектральной оценки .

Приложения

БПФ используется в программном обеспечении цифровой записи, дискретизации, аддитивного синтеза и коррекции высоты тона . ^[45]

Важность БПФ обусловлена ​​тем фактом, что оно сделало работу в частотной области такой же вычислительной, как и работу во временной или пространственной области. Некоторые из важных применений БПФ включают: ^{[15] [46]}

• быстрые алгоритмы умножения больших целых чисел и полиномиальное умножение,
• эффективное умножение матрицы на вектор для теплицевых , циркулянтов и других структурированных матриц,
• алгоритмы фильтрации (см. методы перекрытия-добавления и перекрытия-сохранения ),
• быстрые алгоритмы дискретного косинусного или синусоидального преобразования (например, быстрый DCT , используемый для кодирования и декодирования JPEG и MPEG / MP3 ),
• быстрое приближение Чебышева ,
• решение разностных уравнений ,
• расчет изотопных распределений . ^[47]
• модуляция и демодуляция сложных символов данных с использованием мультиплексирования с ортогональным частотным разделением каналов (OFDM) для 5G, LTE, Wi-Fi, DSL и других современных систем связи.

Оригинальное применение БПФ в финансах , особенно при оценке опционов, было разработано Марчелло Миненной. ^[48]

Области исследований

Большие БПФ

С бурным ростом больших данных в таких областях, как астрономия, возникла потребность в 512 тыс. БПФ для некоторых интерферометрических расчетов. Данные, собранные такими проектами, как WMAP и LIGO, требуют БПФ в десятки миллиардов точек. Поскольку этот размер не помещается в основную память, так называемое внеядерное БПФ является активной областью исследований. ^[49]

Приблизительные БПФ

Для таких приложений, как МРТ, необходимо вычислять ДПФ для неравномерно расположенных точек сетки и/или частот. Подходы, основанные на мультиполях, могут вычислять приблизительные количества с коэффициентом увеличения времени выполнения. ^[50]

Групповые БПФ

БПФ также можно объяснить и интерпретировать с помощью теории представления групп , допускающей дальнейшее обобщение. Функция на любой компактной группе, в том числе и нециклической, имеет разложение по базису из неприводимых матричных элементов. Остается активной областью исследований поиск эффективного алгоритма для выполнения этого изменения базиса. Приложения, включая эффективное разложение по сферическим гармоникам , анализ некоторых марковских процессов , робототехнику и т. д. ^[51]

Квантовые БПФ

Быстрый алгоритм Шора для факторизации целых чисел на квантовом компьютере имеет подпрограмму для вычисления ДПФ двоичного вектора. Это реализовано как последовательность 1- или 2-битных квантовых вентилей, теперь известная как квантовое БПФ, которая фактически представляет собой БПФ Кули-Тьюки, реализованное как особая факторизация матрицы Фурье. Расширение этих идей в настоящее время изучается. ^[52]

Справочник по языку

Смотрите также

Алгоритмы, связанные с БПФ:

• Перестановка с обращением битов

• Алгоритм Герцеля - вычисляет отдельные члены дискретного преобразования Фурье.

Реализации БПФ:

• ALGLIB - библиотека C++ и C# с двойной лицензией GPL (также поддерживающая другие языки) с реальной/сложной реализацией БПФ.
• FFTPACK - еще одна библиотека БПФ на Фортране (общественное достояние)
• В зависимости от архитектуры:
  • Библиотеки производительности рук ^[53]
  • Интегрированные примитивы производительности Intel
  • Библиотека математического ядра Intel
• Доступно множество других реализаций ^[54] для центральных и графических процессоров, например PocketFFT для C++.

Другие ссылки:

• Алгоритм Одлыцко – Шенхаге применяет БПФ к конечным рядам Дирихле.
• Алгоритм Шёнхаге – Штрассена - асимптотически быстрый алгоритм умножения больших целых чисел.
• Диаграмма «бабочка» - диаграмма, используемая для описания БПФ.
• Спектральная музыка (включает применение анализа ДПФ к музыкальной композиции)
• Анализатор спектра - любое из нескольких устройств, выполняющих анализ спектра, часто с помощью ДПФ.
• Временная последовательность
• Быстрое преобразование Уолша – Адамара
• Обобщенный распределительный закон
• Спектральный анализ методом наименьших квадратов
• Многомерное преобразование
• Многомерная дискретная свертка
• Телескоп быстрого преобразования Фурье

Рекомендации

1. Хайдеман, Майкл Т.; Джонсон, Дон Х.; Буррус, Чарльз Сидни (1984). «Гаусс и история быстрого преобразования Фурье» (PDF) . Журнал IEEE ASSP . 1 (4): 14–21. CiteSeerX  10.1.1.309.181 . дои : 10.1109/MASSP.1984.1162257. S2CID  10032502. Архивировано (PDF) из оригинала 19 марта 2013 г.
2. Ван Лоан, Чарльз (1992). Вычислительные основы для быстрого преобразования Фурье . СИАМ .
3. Стрэнг, Гилберт (май – июнь 1994 г.). «Вейвлеты». Американский учёный . 82 (3): 250–255. JSTOR  29775194.
4. Кент, Рэй Д.; Прочтите, Чарльз (2002). Акустический анализ речи . Сингулярное/Томсоновское обучение. ISBN 0-7693-0112-6.
5. Донгарра, Джек; Салливан, Фрэнсис (январь 2000 г.). «Введение приглашенных редакторов в 10 лучших алгоритмов». Вычисления в науке и технике . 2 (1): 22–23. Бибкод : 2000CSE.....2a..22D. doi : 10.1109/MCISE.2000.814652. ISSN  1521-9615.
6. Гаусс, Карл Фридрих (1866). «Теория интерполяции методо нова трактата» [Теория нового метода интерполяции]. Нахласс (Неопубликованная рукопись). Верке (на латыни и немецком языке). Том. 3. Геттинген, Германия: Königlichen Gesellschaft der Wissenschaften zu Göttingen. стр. 265–303.
7. Хайдеман, Майкл Т.; Джонсон, Дон Х.; Буррус, Чарльз Сидни (1 сентября 1985 г.). «Гаусс и история быстрого преобразования Фурье». Архив истории точных наук . 34 (3): 265–277. CiteSeerX 10.1.1.309.181 . дои : 10.1007/BF00348431. ISSN  0003-9519. S2CID  122847826. 
8. Йейтс, Фрэнк (1937). «Планирование и анализ факторных экспериментов». Техническое сообщение № 35 Бюро почв Содружества . 142 (3585): 90–92. Бибкод : 1938Natur.142...90F. дои : 10.1038/142090a0. S2CID  23501205.
9. Дэниэлсон, Гордон С .; Ланцос, Корнелиус (1942). «Некоторые улучшения в практическом анализе Фурье и их применении к рассеянию рентгеновских лучей жидкостями». Журнал Института Франклина . 233 (4): 365–380. дои : 10.1016/S0016-0032(42)90767-1.
10. Ланчос, Корнелиус (1956). Прикладной анализ . Прентис-Холл .
11. Кули, Джеймс В .; Льюис, Питер AW; Уэлч, Питер Д. (июнь 1967 г.). «Исторические заметки о быстром преобразовании Фурье». Транзакции IEEE по аудио и электроакустике . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . дои : 10.1109/ТАУ.1967.1161903. ISSN  0018-9278. 
12. Кули, Джеймс В .; Тьюки, Джон В. (1965). «Алгоритм машинного вычисления комплексных рядов Фурье». Математика вычислений . 19 (90): 297–301. дои : 10.1090/S0025-5718-1965-0178586-1 . ISSN  0025-5718.
13. Кули, Джеймс В. (1987). Повторное открытие алгоритма быстрого преобразования Фурье (PDF) . Том. III. Вена, Австрия. стр. 33–45. Архивировано (PDF) из оригинала 20 августа 2016 г. {{cite book}}: |work=игнорируется ( помощь )CS1 maint: location missing publisher (link)
14. Гарвин, Ричард (июнь 1969 г.). «Быстрое преобразование Фурье как пример трудности широкого использования нового метода» (PDF) . Транзакции IEEE по аудио и электроакустике . АУ-17 (2): 68–72. Архивировано (PDF) из оригинала 17 мая 2006 г.
15. Рокмор, Дэниел Н. (январь 2000 г.). «БПФ: алгоритм, который может использовать вся семья». Вычисления в науке и технике . 2 (1): 60–64. Бибкод : 2000CSE.....2a..60R. CiteSeerX 10.1.1.17.228 . дои : 10.1109/5992.814659. ISSN  1521-9615. S2CID  14978667. 
16. Фриго, Маттео; Джонсон, Стивен Г. (январь 2007 г.) [19 декабря 2006 г.]. «Модифицированное БПФ с разделенным основанием с меньшим количеством арифметических операций». Транзакции IEEE по обработке сигналов . 55 (1): 111–119. Бибкод : 2007ITSP...55..111J. CiteSeerX 10.1.1.582.5497 . дои : 10.1109/tsp.2006.882087. S2CID  14772428. 
17. Фриго, Маттео; Джонсон, Стивен Г. (2005). «Проектирование и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. Бибкод : 2005IEEP..93..216F. CiteSeerX 10.1.1.66.3097 . doi : 10.1109/jproc.2004.840301. S2CID  6644892. Архивировано (PDF) из оригинала 7 февраля 2005 г. 
18. Джентльмен, В. Морвен; Санде, Г. (1966). «Быстрое преобразование Фурье — для развлечения и выгоды». Труды АФИПС . 29 : 563–578. дои : 10.1145/1464291.1464352 . S2CID  207170956.
19. Гаусс, Карл Фридрих (1866) [1805]. Теория интерполяции методом новых трактатов. Верке (на латыни и немецком языке). Том. 3. Геттинген, Германия: Königliche Gesellschaft der Wissenschaften. стр. 265–327.
20. Бреннер, Норман М.; Рейдер, Чарльз М. (1976). «Новый принцип быстрого преобразования Фурье». Транзакции IEEE по акустике, речи и обработке сигналов . 24 (3): 264–266. дои :10.1109/ТАССП.1976.1162805.
21. Виноград, Шмуэль (1978). «О вычислении дискретного преобразования Фурье». Математика вычислений . 32 (141): 175–199. дои : 10.1090/S0025-5718-1978-0468306-4. JSTOR  2006266. PMC 430186 . ПМИД  16592303. 
22. Виноград, Шмуэль (1979). «О мультипликативной сложности дискретного преобразования Фурье». Достижения в математике . 32 (2): 83–117. дои : 10.1016/0001-8708(79)90037-9.
23. Соренсен, Хенрик В.; Джонс, Дуглас Л .; Хайдеман, Майкл Т.; Буррус, Чарльз Сидни (1987). «Алгоритмы быстрого преобразования Фурье с действительными значениями». Транзакции IEEE по акустике, речи и обработке сигналов . 35 (6): 849–863. CiteSeerX 10.1.1.205.4523 . дои :10.1109/ТАССП.1987.1165220. 
24. Соренсен, Хенрик В.; Джонс, Дуглас Л .; Хайдеман, Майкл Т.; Буррус, Чарльз Сидни (1987). «Исправления к «Алгоритмам быстрого преобразования Фурье с действительными значениями»". IEEE Transactions on Acoustics, Speech and Signal Processing . 35 (9): 1353. doi : 10.1109/TASSP.1987.1165284.
25. Хайдеман, Майкл Т.; Буррус, Чарльз Сидни (1986). «О количестве умножений, необходимых для вычисления ДПФ длины 2 ⁿ ». Транзакции IEEE по акустике, речи и обработке сигналов . 34 (1): 91–95. дои :10.1109/ТАССП.1986.1164785.
26. Дюамель, Пьер (1990). «Алгоритмы, соответствующие нижним оценкам мультипликативной сложности ДПФ длины 2 ⁿ , и их связь с практическими алгоритмами». Транзакции IEEE по акустике, речи и обработке сигналов . 38 (9): 1504–1511. дои : 10.1109/29.60070.
27. Моргенштерн, Жак (1973). «Обратите внимание на нижнюю границу линейной сложности быстрого преобразования Фурье». Журнал АКМ . 20 (2): 305–306. дои : 10.1145/321752.321761 . S2CID  2790142.
28. Пан, Виктор Я. (02 января 1986 г.). «Компромисс между аддитивной сложностью и асинхронностью линейных и билинейных алгоритмов». Письма об обработке информации . 22 (1): 11–14. дои : 10.1016/0020-0190(86)90035-9 . Проверено 31 октября 2017 г.
29. Пападимитриу, Христос Х. (1979). «Оптимальность быстрого преобразования Фурье». Журнал АКМ . 26 : 95–102. дои : 10.1145/322108.322118 . S2CID  850634.
30. Ланди, Томас Дж.; Ван Баскирк, Джеймс (2007). «Новый матричный подход к реальным БПФ и сверткам длиной 2 ^k ». Вычисление . 80 (1): 23–45. дои : 10.1007/s00607-007-0222-6. S2CID  27296044.
31. Хейнал, Стив; Хайнал, Хайди (2011). «Создание и поиск семейств алгоритмов БПФ» (PDF) . Журнал по выполнимости, логическому моделированию и вычислениям . 7 (4): 145–187. arXiv : 1103.5740 . Бибкод : 2011arXiv1103.5740H. дои : 10.3233/SAT190084. S2CID  173109. Архивировано из оригинала (PDF) 26 апреля 2012 г.
32. Дюамель, Пьер; Веттерли, Мартин (1990). «Быстрые преобразования Фурье: обзор учебного пособия и современное состояние». Обработка сигнала . 19 (4): 259–299. дои : 10.1016/0165-1684(90)90158-U.
33. Эдельман, Алан; Маккоркодейл, Питер; Толедо, Сиван (1999). «Будущее быстрое преобразование Фурье?» (PDF) . Журнал SIAM по научным вычислениям . 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339 . дои : 10.1137/S1064827597316266. Архивировано (PDF) из оригинала 5 июля 2017 г. 
34. Го, Хайтао; Буррус, Чарльз Сидни (1996). Унсер, Майкл А.; Альдроуби, Акрам; Лейн, Эндрю Ф. (ред.). «Быстрое приближенное преобразование Фурье с помощью вейвлет-преобразования». Труды SPIE . Вейвлет-приложения в обработке сигналов и изображений IV. 2825 : 250–259. Бибкод : 1996SPIE.2825..250G. CiteSeerX 10.1.1.54.3984 . дои : 10.1117/12.255236. S2CID  120514955. 
35. Шентов, Огнян В.; Митра, Санджит К.; Хойте, Ульрих; Хоссен, Абдул Н. (1995). «Поддиапазон DFT. I. Определение, интерпретации и расширения». Обработка сигнала . 41 (3): 261–277. дои : 10.1016/0165-1684(94)00103-7.
36. Хассания, Хайсам; Индик, Петр ; Катаби, Дина; Прайс, Эрик (январь 2012 г.). «Простой и практичный алгоритм разреженного преобразования Фурье» (PDF) . Симпозиум ACM-SIAM по дискретным алгоритмам . Архивировано (PDF) из оригинала 4 марта 2012 г.(Примечание. См. также веб-страницу sFFT.)
37. Шацман, Джеймс К. (1996). «Точность дискретного преобразования Фурье и быстрого преобразования Фурье». Журнал SIAM по научным вычислениям . 17 (5): 1150–1166. Бибкод : 1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184 . дои : 10.1137/s1064827593247023. 
38. Уэлч, Питер Д. (1969). «Анализ ошибок быстрого преобразования Фурье с фиксированной точкой». Транзакции IEEE по аудио и электроакустике . 17 (2): 151–157. дои : 10.1109/ТАУ.1969.1162035.
39. Эргюн, Фунда (1995). «Тестирование многомерных линейных функций». Материалы двадцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '95 . Киото, Япония. стр. 407–416. дои : 10.1145/225058.225167. ISBN 978-0897917186. S2CID  15512806.{{cite book}}: CS1 maint: location missing publisher (link)
40. Нуссбаумер, Анри Дж. (1977). «Цифровая фильтрация с использованием полиномиальных преобразований». Электронные письма . 13 (13): 386–387. Бибкод : 1977ElL....13..386N. дои : 10.1049/эл: 19770280.
41. Моленкамп, Мартин Дж. (1999). «Быстрое преобразование сферических гармоник» (PDF) . Журнал анализа и приложений Фурье . 5 (2–3): 159–184. CiteSeerX 10.1.1.135.9830 . дои : 10.1007/BF01261607. S2CID  119482349. Архивировано (PDF) из оригинала 6 мая 2017 г. Проверено 11 января 2018 г. 
42. "Библиотека libftsh". Архивировано из оригинала 23 июня 2010 г. Проверено 9 января 2007 г.
43. Рохлин, Владимир; Тайгерт, Марк (2006). «Быстрые алгоритмы сферических гармонических разложений» (PDF) . Журнал SIAM по научным вычислениям . 27 (6): 1903–1928. Бибкод : 2006ГАК...27.1903Р. CiteSeerX 10.1.1.125.7415 . дои : 10.1137/050623073. Архивировано (PDF) из оригинала 17 декабря 2014 г. Проверено 18 сентября 2014 г. [1]
44. Поттс, Дэниел; Стейдл, Габриэле ; Таше, Манфред (2001). «Быстрое преобразование Фурье для неравнораспределенных данных: учебное пособие» (PDF) . В Бенедетто, Джей-Джей; Феррейра, П. (ред.). Современная теория выборки: математика и приложения . Биркхойзер . Архивировано (PDF) из оригинала 26 сентября 2007 г.
45. Берджесс, Ричард Джеймс (2014). История музыкального производства. Издательство Оксфордского университета. ISBN 978-0199357178. Проверено 1 августа 2019 г.
46. Чу, Элеонора; Джордж, Алан (11 ноября 1999 г.) [11 ноября 1999 г.]. «Глава 16». Внутри черного ящика БПФ: последовательные и параллельные алгоритмы быстрого преобразования Фурье . ЦРК Пресс . стр. 153–168. ISBN 978-1-42004996-1.
47. Фернандес-де-Коссио Диас, Хорхе; Фернандес-де-Коссио, Хорхе (8 августа 2012 г.). «Расчет распределения центра масс изотопного пика с помощью преобразования Фурье». Аналитическая химия . 84 (16): 7052–7056. дои : 10.1021/ac301296a. ISSN  0003-2700. ПМИД  22873736.
48. Миненна, Марчелло (октябрь 2008 г.). «Пересмотренный и стабильный метод преобразования Фурье для моделей диффузии аффинного скачка». Журнал банковского дела и финансов . 32 (10): 2064–2075. doi :10.1016/j.jbankfin.2007.05.019.
49. Кормен, Томас Х.; Никол, Дэвид М. (1998). «Выполнение внеядерного БПФ в параллельных дисковых системах». Параллельные вычисления . 24 (1): 5–20. CiteSeerX 10.1.1.44.8212 . дои : 10.1016/S0167-8191(97)00114-2. S2CID  14996854. 
50. Датт, Алок; Рохлин, Владимир (1 ноября 1993 г.). «Быстрое преобразование Фурье для неравнораспределенных данных». Журнал SIAM по научным вычислениям . 14 (6): 1368–1393. Бибкод : 1993SJSC...14.1368D. дои : 10.1137/0914081. ISSN  1064-8275.
51. Рокмор, Дэниел Н. (2004). «Последний прогресс и приложения в групповом БПФ». В Бирнсе, Джим (ред.). Вычислительная некоммутативная алгебра и ее приложения . Серия НАТО по науке II: Математика, физика и химия. Том. 136. Спрингер Нидерланды. стр. 227–254. CiteSeerX 10.1.1.324.4700 . дои : 10.1007/1-4020-2307-3_9. ISBN  978-1-4020-1982-1. S2CID  1412268.
52. Ре, Асака; Казумицу, Сакаи; Рёко, Яхаги (2020). «Квантовая схема быстрого преобразования Фурье». Квантовая обработка информации . 19 (277): 277. arXiv : 1911.03055 . Бибкод : 2020QuIP...19..277A. дои : 10.1007/s11128-020-02776-5. S2CID  207847474.
53. "Библиотеки производительности рук" . Рука . 2020 . Проверено 16 декабря 2020 г.
54. «Полный список библиотек БПФ C/C++» . Сообщество ВКВ . 05.04.2020 . Проверено 03 марта 2021 г.

дальнейшее чтение

• Бригам, Э. Оран (2002). Быстрое преобразование Фурье . Нью-Йорк: Прентис-Холл .
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Штейн, Клиффорд (2001). «Глава 30: Полиномы и БПФ». Введение в алгоритмы (2-е изд.). MIT Press / МакГроу-Хилл . ISBN 0-262-03293-7.
• Эллиотт, Дуглас Ф.; Рао, К. Рамамохан (1982). Быстрые преобразования: алгоритмы, анализ, приложения . Нью-Йорк, США: Академическая пресса .
• Го, Хайтао; Ситтон, Гэри А.; Буррус, Чарльз Сидни (1994). «Быстрое дискретное преобразование Фурье». Труды ICASSP '94. Международная конференция IEEE по акустике, речи и обработке сигналов . Том. 3. С. 445–448. дои : 10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID  42639206.
• Джонсон, Стивен Г.; Фриго, Маттео (2007). «Модифицированное БПФ с разделением системы счисления с меньшим количеством арифметических операций» (PDF) . Транзакции IEEE по обработке сигналов . 55 (1): 111–119. Бибкод : 2007ITSP...55..111J. CiteSeerX  10.1.1.582.5497 . дои : 10.1109/tsp.2006.882087. S2CID  14772428. Архивировано (PDF) из оригинала 26 мая 2005 г.
• Пресс, Уильям Х.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (2007). «Глава 12. Быстрое преобразование Фурье». Численные рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк, США: Издательство Кембриджского университета . ISBN 978-0-521-88068-8.
• Синглтон, Ричард Коллом (июнь 1969 г.). «Краткая библиография по быстрому преобразованию Фурье». Специальный выпуск по быстрому преобразованию Фурье . Том. АУ-17. Группа IEEE по аудио и электроакустике. стр. 166–169. дои : 10.1109/ТАУ.1969.1162029.(Примечание. Содержит обширную библиографию.)
• Елена Престини: «Эволюция прикладного гармонического анализа», Springer, ISBN 978-0-8176-4125-2 (2004), раздел 3.10 «Гаусс и астероиды: история БПФ».

Внешние ссылки

• Быстрое преобразование Фурье для полиномиального умножения – быстрый алгоритм Фурье
• Быстрые преобразования Фурье , онлайн-книга Connexions под редакцией Чарльза Сидни Берруса, с главами Чарльза Сидни Бурруса, Ивана Селесника, Маркуса Пюшеля, Маттео Фриго и Стивена Дж. Джонсона (2008)
• Быстрое преобразование Фурье — БПФ — программирование БПФ на C++ — алгоритм Кули-Тьюки
• Онлайн-документация, ссылки, книги и код
• Шри Веларатна, «Тридцать лет анализаторов БПФ. Архивировано 12 января 2014 г. в Wayback Machine », Звук и вибрация (январь 1997 г., выпуск, посвященный 30-летию) - исторический обзор аппаратных устройств БПФ.
• ALGLIB FFT Code - многоязычная (VBA, C++, Pascal и т. д.) библиотека численного анализа и обработки данных, имеющая двойную лицензию GPL.
• SFFT: разреженное быстрое преобразование Фурье - алгоритм разреженного (сублинейного по времени) БПФ MIT, sFFT и его реализация.
• VB6 FFT - реализация библиотеки, оптимизированная для VB6, с исходным кодом.
• Интерактивное руководство по БПФ – наглядное интерактивное введение в преобразования Фурье и методы БПФ.