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

Алгоритм дискретного преобразования Фурье 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]} и он был включен в Топ-10 алгоритмов 20-го века журналом IEEE Computing in Science & Engineering . ^[5]

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

История

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

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

Джеймс Кули и Джон Тьюки независимо друг от друга заново открыли эти более ранние алгоритмы ^[7] и опубликовали более общее БПФ в 1965 году, которое применимо, когда n является составным и не обязательно степенью 2, а также проанализировали масштабирование . ^[12] Тьюки выдвинул идею во время заседания Научного консультативного комитета президента Кеннеди , где темой обсуждения было обнаружение ядерных испытаний Советского Союза путем установки датчиков, чтобы окружить страну снаружи. Для анализа выходных данных этих датчиков потребовался бы алгоритм БПФ. В обсуждении с Тьюки Ричард Гарвин признал общую применимость алгоритма не только к проблемам национальной безопасности, но и к широкому кругу проблем, включая одну, которая представляла для него непосредственный интерес, определение периодичности ориентаций спинов в трехмерном кристалле гелия-3. ^[13] Гарвин передал идею Тьюки Кули (оба работали в лабораториях Уотсона IBM ) для реализации. ^[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}$

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

Алгоритм Рейдера , использующий существование генератора для мультипликативной группы по модулю простого числа n , выражает ДПФ простого размера n как циклическую свертку (составного) размера n – 1 , которая затем может быть вычислена парой обычных БПФ с помощью теоремы о свертке (хотя Виноград использует другие методы свертки). Другое БПФ простого размера принадлежит LI Bluestein и иногда называется алгоритмом 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}^{*}}$

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

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

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

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

Ограничения по сложности и количеству операций

Нерешенная проблема в информатике :

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

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

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

После работы Шмуэля Винограда (1978), ^[21] известна точная нижняя граница для числа действительных умножений, требуемых БПФ. Можно показать, что для вычисления ДПФ длины степени двойки требуются только иррациональные действительные умножения . Более того, известны явные алгоритмы, которые достигают этого числа (Heideman & Burrus , 1986; ^[25] Duhamel, 1990 ^[26] ). Однако эти алгоритмы требуют слишком много сложений, чтобы быть практичными, по крайней мере, на современных компьютерах с аппаратными умножителями (Duhamel, 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 долгое время достигалось алгоритмом FFT с разделенным основанием , который требует действительных умножений и сложений для n > 1. Недавно это было сокращено до (Johnson and Frigo, 2007; ^[16] Lundy and Van Buskirk, 2007 ^[30] ). Было показано , что немного большее количество (но все же лучше, чем разделенное основание для n ≥ 256 ) является доказуемо оптимальным для n ≤ 512 при дополнительных ограничениях на возможные алгоритмы (поточные графы, подобные разделенному основанию, с единичными модулями мультипликативных множителей) путем сведения к проблеме выполнимости по модулю теорий, решаемой методом грубой силы (Хайнал и Хайнал, 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}})}$

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

Эта композиционная точка зрения немедленно обеспечивает простейший и наиболее распространенный многомерный алгоритм DFT, известный как алгоритм строка-столбец (после двумерного случая, ниже). То есть, просто выполняется последовательность из d одномерных FFT (любым из вышеприведенных алгоритмов): сначала вы преобразуете по измерению n ₁ ​​, затем по измерению n ₂ и так далее (на самом деле, любой порядок работает). Легко показать, что этот метод имеет обычную сложность, где — общее количество преобразованных точек данных. В частности, есть n / n ₁ преобразований размера n ₁ и т. д., поэтому сложность последовательности FFT равна: ${\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 и 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)}$

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

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

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

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

Приложения

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

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

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

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

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

Большие БПФ

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

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

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

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

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

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

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

Ссылка на язык

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

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

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

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

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

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

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

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

Ссылки

1. Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1984). «Gauss and the history of the fast Fourier transform» (PDF) . IEEE ASSP Magazine . 1 (4): 14–21. CiteSeerX  10.1.1.309.181 . doi :10.1109/MASSP.1984.1162257. S2CID  10032502. Архивировано (PDF) из оригинала 2013-03-19.
2. Ван Лоан, Чарльз (1992). Вычислительные структуры для быстрого преобразования Фурье . SIAM .
3. Стрэнг, Гилберт (май–июнь 1994 г.). «Вейвлеты». American Scientist . 82 (3): 250–255. JSTOR  29775194.
4. Кент, Рэй Д.; Рид, Чарльз (2002). Акустический анализ речи . Singular/Thomson Learning. ISBN 0-7693-0112-6.
5. Донгарра, Джек; Салливан, Фрэнсис (январь 2000 г.). «Введение в 10 лучших алгоритмов от приглашенных редакторов». Computing in Science & Engineering . 2 (1): 22–23. Bibcode : 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. Heideman, Michael T.; Johnson, Don H.; Burrus, Charles Sidney (1985-09-01). «Гаусс и история быстрого преобразования Фурье». Архив History of Exact Sciences . 34 (3): 265–277. CiteSeerX 10.1.1.309.181 . doi :10.1007/BF00348431. ISSN  0003-9519. S2CID  122847826. 
8. Йейтс, Фрэнк (1937). «Проектирование и анализ факторных экспериментов». Техническое сообщение № 35 Бюро почв Содружества . 142 (3585): 90–92. Bibcode : 1938Natur.142...90F. doi : 10.1038/142090a0. S2CID  23501205.
9. Даниельсон, Гордон К.; Ланцош , Корнелиус (1942). «Некоторые улучшения в практическом анализе Фурье и их применение к рассеянию рентгеновских лучей жидкостями». Журнал Института Франклина . 233 (4): 365–380. doi :10.1016/S0016-0032(42)90767-1.
10. Ланцос, Корнелиус (1956). Прикладной анализ . Prentice–Hall .
11. Кули, Джеймс У .; Льюис, Питер AW; Уэлч, Питер Д. (июнь 1967 г.). «Исторические заметки о быстром преобразовании Фурье». Труды IEEE по аудио и электроакустике . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . doi :10.1109/TAU.1967.1161903. ISSN  0018-9278. 
12. Cooley, James W. ; Tukey, John W. (1965). «Алгоритм для машинного вычисления комплексных рядов Фурье». Mathematics of Computation . 19 (90): 297–301. doi : 10.1090/S0025-5718-1965-0178586-1 . ISSN  0025-5718.
13. Кули, Джеймс У. (1987). «Повторное открытие алгоритма быстрого преобразования Фурье» (PDF) . Microchimica Acta . Т. III. Вена, Австрия. стр. 33–45. Архивировано (PDF) из оригинала 2016-08-20.{{cite book}}: CS1 maint: location missing publisher (link)
14. Гарвин, Ричард (июнь 1969). «Быстрое преобразование Фурье как пример трудностей в получении широкого использования новой техники» (PDF) . Труды IEEE по аудио и электроакустике . AU-17 (2): 68–72. Архивировано (PDF) из оригинала 2006-05-17.
15. Rockmore, Daniel N. (январь 2000 г.). «БПФ: алгоритм, который может использовать вся семья». Computing in Science & Engineering . 2 (1): 60–64. Bibcode : 2000CSE.....2a..60R. CiteSeerX 10.1.1.17.228 . doi : 10.1109/5992.814659. ISSN  1521-9615. S2CID  14978667. 
16. Frigo, Matteo; Johnson, Steven G. (январь 2007 г.) [2006-12-19]. "Модифицированное быстрое преобразование Фурье с разделением по основанию и меньшим количеством арифметических операций". IEEE Transactions on Signal Processing . 55 (1): 111–119. Bibcode : 2007ITSP...55..111J. CiteSeerX 10.1.1.582.5497 . doi : 10.1109/tsp.2006.882087. S2CID  14772428. 
17. Frigo, Matteo; Johnson, Steven G. (2005). "The Design and Implementation of FFTW3" (PDF) . Proceedings of the IEEE . 93 (2): 216–231. Bibcode :2005IEEEP..93..216F. CiteSeerX 10.1.1.66.3097 . doi :10.1109/jproc.2004.840301. S2CID  6644892. Архивировано (PDF) из оригинала 2005-02-07. 
18. Gentleman, W. Morven; Sande, G. (1966). «Быстрые преобразования Фурье — ради удовольствия и выгоды». Труды AFIPS . 29 : 563–578. doi : 10.1145/1464291.1464352 . S2CID  207170956.
19. Гаусс, Карл Фридрих (1866) [1805]. Теория интерполяции методом новых трактатов. Верке (на латыни и немецком языке). Том. 3. Геттинген, Германия: Königliche Gesellschaft der Wissenschaften. стр. 265–327.
20. Бреннер, Норман М.; Рейдер, Чарльз М. (1976). «Новый принцип быстрого преобразования Фурье». Труды IEEE по акустике, речи и обработке сигналов . 24 (3): 264–266. doi :10.1109/TASSP.1976.1162805.
21. Виноград, Шмуэль (1978). «О вычислении дискретного преобразования Фурье». Математика вычислений . 32 (141): 175–199. doi :10.1090/S0025-5718-1978-0468306-4. JSTOR 2006266.  PMC 430186. PMID 16592303  . 
22. Виноград, Шмуэль (1979). «О мультипликативной сложности дискретного преобразования Фурье». Успехи математики . 32 (2): 83–117. doi :10.1016/0001-8708(79)90037-9.
23. Sorensen, Henrik V.; Jones, Douglas L .; Heideman, Michael T.; Burrus, Charles Sidney (1987). «Алгоритмы быстрого преобразования Фурье с действительными значениями». IEEE Transactions on Acoustics, Speech, and Signal Processing . 35 (6): 849–863. CiteSeerX 10.1.1.205.4523 . doi :10.1109/TASSP.1987.1165220. 
24. Соренсен, Хенрик В.; Джонс, Дуглас Л .; Хайдеман, Майкл Т.; Беррус, Чарльз Сидни (1987). «Исправления к «Алгоритмам быстрого преобразования Фурье с действительными значениями»". Труды IEEE по акустике, речи и обработке сигналов . 35 (9): 1353. doi :10.1109/TASSP.1987.1165284.
25. Хайдеман, Майкл Т.; Беррус, Чарльз Сидни (1986). «О количестве умножений, необходимых для вычисления ДПФ длины 2 ⁿ ». Труды IEEE по акустике, речи и обработке сигналов . 34 (1): 91–95. doi :10.1109/TASSP.1986.1164785.
26. Duhamel, Pierre (1990). «Алгоритмы, соответствующие нижним границам мультипликативной сложности ДПФ длины 2 ⁿ и их связь с практическими алгоритмами». Труды IEEE по акустике, речи и обработке сигналов . 38 (9): 1504–1511. doi :10.1109/29.60070.
27. Моргенштерн, Жак (1973). «Заметка о нижней границе линейной сложности быстрого преобразования Фурье». Журнал ACM . 20 (2): 305–306. doi : 10.1145/321752.321761 . S2CID  2790142.
28. Пан, Виктор Я. (1986-01-02). «Компромисс между аддитивной сложностью и асинхронностью линейных и билинейных алгоритмов». Information Processing Letters . 22 (1): 11–14. doi :10.1016/0020-0190(86)90035-9 . Получено 2017-10-31 .
29. Пападимитриу, Христос Х. (1979). «Оптимальность быстрого преобразования Фурье». Журнал ACM . 26 : 95–102. doi : 10.1145/322108.322118 . S2CID  850634.
30. Ланди, Томас Дж.; Ван Баскирк, Джеймс (2007). «Новый матричный подход к реальным БПФ и сверткам длины 2k ^» . Вычислительная техника . 80 (1): 23–45. doi :10.1007/s00607-007-0222-6. S2CID  27296044.
31. Хайнал, Стив; Хайнал, Хайди (2011). «Создание и поиск семейств алгоритмов БПФ» (PDF) . Журнал по выполнимости, булевому моделированию и вычислениям . 7 (4): 145–187. arXiv : 1103.5740 . Bibcode : 2011arXiv1103.5740H. doi : 10.3233/SAT190084. S2CID  173109. Архивировано из оригинала (PDF) 2012-04-26.
32. Дюамель, Пьер; Веттерли, Мартин (1990). «Быстрые преобразования Фурье: обзор учебника и современное состояние». Обработка сигналов . 19 (4): 259–299. Bibcode : 1990SigPr..19..259D. doi : 10.1016/0165-1684(90)90158-U.
33. Эдельман, Алан; Маккоркодейл, Питер; Толедо, Сиван (1999). «Будущее быстрого преобразования Фурье?» (PDF) . Журнал SIAM по научным вычислениям . 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339 . doi :10.1137/S1064827597316266. Архивировано (PDF) из оригинала 05.07.2017. 
34. Guo, Haitao; Burrus, Charles Sidney (1996). "Быстрое приближенное преобразование Фурье с помощью вейвлет-преобразования". В Unser, Michael A.; Aldroubi, Akram; Laine, Andrew F. (ред.). Wavelet Applications in Signal and Image Processing IV . Proceedings of SPIE . Vol. 2825. pp. 250–259. Bibcode : 1996SPIE.2825..250G. CiteSeerX 10.1.1.54.3984 . doi : 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) из оригинала 2012-03-04.(Примечание. См. также веб-страницу sFFT.)
37. Schatzman, James C. (1996). «Точность дискретного преобразования Фурье и быстрого преобразования Фурье». SIAM Journal on Scientific Computing . 17 (5): 1150–1166. Bibcode : 1996SJSC...17.1150S. CiteSeerX 10.1.1.495.9184 . doi : 10.1137/s1064827593247023. 
38. Уэлч, Питер Д. (1969). «Анализ ошибок быстрого преобразования Фурье с фиксированной точкой». Труды IEEE по аудио и электроакустике . 17 (2): 151–157. doi :10.1109/TAU.1969.1162035.
39. Эргюн, Фунда (1995). "Тестирование многомерных линейных функций". Труды двадцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '95 . Киото, Япония. стр. 407–416. doi :10.1145/225058.225167. ISBN 978-0897917186. S2CID  15512806.{{cite book}}: CS1 maint: location missing publisher (link)
40. Нуссбаумер, Анри Дж. (1977). «Цифровая фильтрация с использованием полиномиальных преобразований». Electronics Letters . 13 (13): 386–387. Bibcode : 1977ElL....13..386N. doi : 10.1049/el:19770280.
41. Mohlenkamp, ​​Martin J. (1999). "Быстрое преобразование для сферических гармоник" (PDF) . Journal of Fourier Analysis and Applications . 5 (2–3): 159–184. Bibcode :1999JFAA....5..159M. CiteSeerX 10.1.1.135.9830 . doi :10.1007/BF01261607. S2CID  119482349. Архивировано (PDF) из оригинала 2017-05-06 . Получено 2018-01-11 . 
42. "libftsh library". Архивировано из оригинала 2010-06-23 . Получено 2007-01-09 .
43. Рохлин, Владимир; Тайгерт, Марк (2006). "Быстрые алгоритмы для сферических гармонических разложений" (PDF) . SIAM Journal on Scientific Computing . 27 (6): 1903–1928. Bibcode :2006SJSC...27.1903R. CiteSeerX 10.1.1.125.7415 . doi :10.1137/050623073. Архивировано (PDF) из оригинала 2014-12-17 . Получено 2014-09-18 . [1]
44. Поттс, Дэниел; Штайдл, Габриэле ; Таше, Манфред (2001). "Быстрые преобразования Фурье для неравноширинных данных: учебное пособие" (PDF) . В Benedetto, JJ; Ferreira, P. (ред.). Современная теория выборки: математика и приложения . Биркхойзер . Архивировано (PDF) из оригинала 26.09.2007.
45. Берджесс, Ричард Джеймс (2014). История музыкального производства. Oxford University Press. ISBN 978-0199357178. Получено 1 августа 2019 г. .
46. Чу, Элеанор; Джордж, Алан (11.11.1999) [11.11.1999]. "Глава 16". Внутри черного ящика БПФ: последовательные и параллельные алгоритмы быстрого преобразования Фурье . CRC Press . стр. 153–168. ISBN 978-1-42004996-1.
47. Фернандес-де-Коссио Диас, Хорхе; Фернандес-де-Коссио, Хорхе (2012-08-08). "Вычисление распределения изотопных пиков по центру и массе с помощью преобразования Фурье". Аналитическая химия . 84 (16): 7052–7056. doi :10.1021/ac301296a. ISSN  0003-2700. PMID  22873736.
48. Миненна, Марчелло (октябрь 2008 г.). «Пересмотренный и стабильный метод преобразования Фурье для моделей аффинной скачкообразной диффузии». Журнал банковского дела и финансов . 32 (10): 2064–2075. doi :10.1016/j.jbankfin.2007.05.019.
49. Cormen, Thomas H.; Nicol, David M. (1998). «Выполнение FFT вне ядра на параллельных дисковых системах». Параллельные вычисления . 24 (1): 5–20. CiteSeerX 10.1.1.44.8212 . doi :10.1016/S0167-8191(97)00114-2. S2CID  14996854. 
50. Датт, Алок; Рохлин, Владимир (1 ноября 1993 г.). «Быстрые преобразования Фурье для неэквиспек-тированных данных». Журнал SIAM по научным вычислениям . 14 (6): 1368–1393. Bibcode : 1993SJSC...14.1368D. doi : 10.1137/0914081. ISSN  1064-8275.
51. Рокмор, Дэниел Н. (2004). "Последние достижения и приложения в групповых БПФ". В Бирнс, Джим (ред.). Вычислительная некоммутативная алгебра и приложения . NATO Science Series II: Mathematics, Physics and Chemistry. Vol. 136. Springer Netherlands. pp. 227–254. CiteSeerX 10.1.1.324.4700 . doi :10.1007/1-4020-2307-3_9. ISBN  978-1-4020-1982-1. S2CID  1412268.
52. Рё, Асака; Казумицу, Сакаи; Рёко, Яхаги (2020). «Квантовая схема для быстрого преобразования Фурье». Квантовая обработка информации . 19 (277): 277. arXiv : 1911.03055 . Bibcode : 2020QuIP...19..277A. doi : 10.1007/s11128-020-02776-5. S2CID  207847474.
53. "Arm Performance Libraries". Arm . 2020 . Получено 2020-12-16 .
54. "Полный список библиотек C/C++ FFT". Сообщество VCV . 2020-04-05 . Получено 2021-03-03 .

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

• Brigham, Elbert Oran (1974). Быстрое преобразование Фурье (Nachdr. ed.). Englewood Cliffs, NJ: Prentice-Hall . ISBN 978-0-13-307496-3.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Глава 30: Полиномы и БПФ". Введение в алгоритмы (2-е изд.). Кембридж (Массачусетс): MIT Press . ISBN 978-0-262-03293-3.
• Эллиотт, Дуглас Ф.; Рао, К. Рамамохан (1982). Быстрые преобразования: алгоритмы, анализы, приложения. Нью-Йорк: Academic Press . ISBN 978-0-12-237080-9.
• Guo, H.; Sitton, GA; Burrus, CS (1994). "Быстрое дискретное преобразование Фурье". Труды ICASSP '94. Международная конференция IEEE по акустике, речи и обработке сигналов. Том iii. IEEE . стр. III/445–III/448. doi :10.1109/ICASSP.1994.389994. ISBN 978-0-7803-1775-8. S2CID  42639206.
• Johnson, Steven G.; Frigo, Matteo (январь 2007 г.). "Модифицированное быстрое преобразование Фурье с разделением по основанию и меньшим количеством арифметических операций" (PDF) . IEEE Transactions on Signal Processing . 55 (1): 111–119. Bibcode :2007ITSP...55..111J. CiteSeerX  10.1.1.582.5497 . doi :10.1109/TSP.2006.882087. ISSN  1053-587X. S2CID  14772428. Архивировано (PDF) из оригинала 2005-05-26.
• Press, William H. ; Teukolsky, Saul A. ; Vetterling, William T.; Flannery, Brian P. (2007). "Глава 12. Быстрое преобразование Фурье". Численные рецепты: искусство научных вычислений (PDF) . Численные рецепты (3-е изд.). Кембридж: Cambridge University Press . стр. 600-639. ISBN 978-0-521-88068-8.
• Синглтон, Р. (июнь 1969 г.). «Краткая библиография по быстрому преобразованию Фурье». IEEE Transactions on Audio and Electroacoustics . 17 (2): 166–169. doi :10.1109/TAU.1969.1162040. ISSN  0018-9278.(Примечание. Содержит обширную библиографию.)
• Престини, Елена (2004). Эволюция прикладного гармонического анализа: модели реального мира. Прикладной и численный гармонический анализ. Бостон; Берлин: Springer Media . Раздел 3.10: Гаусс и астероиды: история БПФ. ISBN 978-0-8176-4125-2.

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

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