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

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

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

Быстрые преобразования Фурье широко используются в приложениях в инженерии, музыке, науке и математике. Основные идеи были популяризированы в 1965 году, но некоторые алгоритмы были получены еще в 1805 году. В 1994 году Гилберт Стрэнг описал БПФ как «самый важный числовой алгоритм нашей жизни», и он был включен в 10 лучших алгоритмов 20-го века. по IEEE журнала вычислений в науке и инженерии .

Наиболее известные алгоритмы БПФ зависят от разложения из N , но есть с FFTs O ( N  журнал  N ) сложности для всех N , даже для простого  N . Многие алгоритмы БПФ зависят только от того факта, что они являются Nпримитивным корнем из единицы , и поэтому могут применяться к аналогичным преобразованиям над любым конечным полем , таким как теоретико-числовые преобразования . Поскольку обратное ДПФ такое же, как ДПФ, но с противоположным знаком в экспоненте и коэффициентом 1 / N , любой алгоритм БПФ может быть легко адаптирован для него.

История

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

Между 1805 и 1965 годами некоторые версии БПФ были опубликованы другими авторами. Фрэнк Йейтс в 1932 году опубликовал свою версию, названную алгоритмом взаимодействия , которая обеспечивала эффективное вычисление преобразований Адамара и Уолша . Алгоритм Йейтса до сих пор используется в области статистического дизайна и анализа экспериментов. В 1942 году Дж. К. Дэниэлсон и Корнелиус Ланцос опубликовали свою версию вычисления ДПФ для рентгеновской кристаллографии - области, в которой вычисление преобразований Фурье представляло собой серьезное узкое место. В то время как многие методы в прошлом были сосредоточены на уменьшении постоянного множителя для вычислений за счет использования преимущества «симметрии», Дэниэлсон и Ланцош поняли, что можно использовать «периодичность» и применить «трюк удвоения» для «удвоения [N] с помощью только трудозатрат чуть больше, чем вдвое », хотя, как и Гаусс, они не анализировали, что это привело к масштабированию.

Джеймс Кули и Джон Тьюки независимо друг от друга заново открыли эти более ранние алгоритмы и в 1965 году опубликовали более общее БПФ , которое применимо, когда N составное и не обязательно в степени 2, а также анализ масштабирования. Тьюки придумал эту идею во время заседания Научно-консультативного комитета президента Кеннеди, где обсуждалась тема обнаружения ядерных испытаний Советским Союзом путем установки датчиков, окружающих страну извне. Для анализа выходных данных этих датчиков потребуется алгоритм БПФ. В беседе с Тьюки Ричард Гарвин признал общую применимость алгоритма не только к проблемам национальной безопасности, но и к широкому кругу проблем, включая одну, представляющую для него непосредственный интерес, определение периодичности ориентации спина в трехмерном кристалле. гелия-3. Гарвин передал идею Тьюки Кули (оба работали в лаборатории IBM Watson ) для реализации. Кули и Тьюки опубликовали статью за относительно короткий срок - шесть месяцев. Поскольку Тьюки не работал в IBM, патентоспособность идеи была поставлена ​​под сомнение, и алгоритм стал общественным достоянием, что в результате компьютерной революции следующего десятилетия сделало БПФ одним из незаменимых алгоритмов в цифровой обработке сигналов.

Определение

Пусть ,…, быть комплексными числами . ДПФ определяется по формуле

где - примитивный корень N- й степени из 1.

Оценка этого определения напрямую требует операций: имеется N выходов X k , и каждый выход требует суммы N членов. БПФ - это любой метод вычисления одних и тех же результатов в операциях. Все известные алгоритмы БПФ требуют операций , хотя нет никаких известных доказательств того, что более низкая оценка сложности невозможна.

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

Алгоритмы

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

Безусловно, наиболее часто используемым БПФ является алгоритм Кули – Тьюки. Это алгоритм «разделяй и властвуй», который рекурсивно разбивает ДПФ любого составного размера на множество меньших ДПФ размеров и , наряду с умножением на комплексные корни из единицы, традиционно называемые множителями (по Gentleman and Sande, 1966).

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

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

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

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

Для N = N 1 N 2 с взаимно простыми числами N 1 и N 2 можно использовать алгоритм простых множителей (Гуда – Томаса) (PFA), основанный на китайской теореме об остатках , чтобы факторизовать ДПФ аналогично Кули – Тьюки, но без факторы вращения. Алгоритм Рейдера – Бреннера (1976) представляет собой факторизацию, подобную Кули – Тьюки, но с чисто мнимыми множителями, сокращающими умножения за счет увеличения числа сложений и снижения числовой стабильности ; Позднее он был заменен вариантом Кули – Тьюки с разделенным основанием (который обеспечивает такое же количество умножений, но с меньшим количеством сложений и без потери точности). Алгоритмы, рекурсивно разлагающие ДПФ на более мелкие операции, отличные от ДПФ, включают алгоритмы Брууна и QFT . (Алгоритмы Райдера – Бреннера и QFT были предложены для размеров степени двойки, но не исключено, что они могут быть адаптированы к общему составному N. Алгоритм Брууна применяется к произвольным четным составным размерам.) Алгоритм Брууна , в частности, основан на об интерпретации БПФ как рекурсивной факторизации полинома z N  - 1, здесь в полиномы с действительными коэффициентами вида z M  - 1 и z 2 M  +  az M  + 1.

Другая полиномиальная точка зрения используется алгоритмом БПФ Винограда, который разлагает z N  - 1 на циклотомические полиномы - они часто имеют коэффициенты 1, 0 или -1, и поэтому требуют небольшого (если есть) умножения, поэтому Виноград может использоваться для получить БПФ с минимальным умножением и часто используется для поиска эффективных алгоритмов для малых факторов. Действительно, Виноград показал, что ДПФ может быть вычислено только с помощью O ( N ) иррациональных умножений, что привело к доказанной достижимой нижней границе числа умножений для величин степени двойки; К сожалению, это происходит за счет гораздо большего количества дополнений, что больше не выгодно для современных процессоров с аппаратными умножителями . В частности, Winograd также использует PFA, а также алгоритм Rader для БПФ простых размеров.

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

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

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

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

и для этой ситуации были разработаны эффективные алгоритмы БПФ (см., например, Соренсен, 1987). Один из подходов состоит в использовании обычного алгоритма (например, Кули – Тьюки) и удалении избыточных частей вычислений, что позволяет примерно вдвое сэкономить время и память. В качестве альтернативы можно выразить ДПФ с реальным входом четной длины как комплексное ДПФ половинной длины (действительная и мнимая части которого являются четными / нечетными элементами исходных реальных данных), за которым следует O ( N ) пост- технологические операции.

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

Есть еще FFT специализации для случаев реальных данных , которые имеют четную / нечетную симметрию, и в этом случае можно получить еще фактор примерно два во время и памяти , и ДПФ становится дискретным косинусным / синус преобразование (ы) ( ДКП / часа ). Вместо того, чтобы напрямую изменять алгоритм БПФ для этих случаев, DCT / DST также могут быть вычислены с помощью БПФ реальных данных в сочетании с O ( N ) предварительной и последующей обработкой.

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

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

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

Какова нижняя граница сложности алгоритмов быстрого преобразования Фурье? Могут ли они быть быстрее чем ?

Фундаментальный вопрос, давно представляющий теоретический интерес, - это доказательство нижних оценок сложности и точного количества операций быстрого преобразования Фурье, и многие нерешенные проблемы остаются. Строго не доказано, действительно ли для ДПФ требуется Ω ( N  log  N ) (т. Е. Порядок N  log  N или больше) операций, даже для простого случая степени двух размеров, хотя не известны алгоритмы с меньшей сложностью. В частности, в центре внимания таких вопросов обычно находится подсчет арифметических операций, хотя фактическая производительность на современных компьютерах определяется многими другими факторами, такими как оптимизация кэша или конвейера ЦП .

В соответствии с работой Шмуэля Винограда (1978), точная нижняя граница Θ ( N ) известна для числа действительных умножений, необходимых для БПФ. Можно показать, что для вычисления ДПФ длины степени двойки требуются только иррациональные действительные умножения . Более того, известны явные алгоритмы, позволяющие достичь этого подсчета (Heideman & Burrus , 1986; Duhamel, 1990). Однако эти алгоритмы требуют слишком большого количества дополнений, чтобы быть практичными, по крайней мере, на современных компьютерах с аппаратными умножителями (Duhamel, 1990; Frigo & Johnson , 2005).

Точная нижняя граница количества требуемых дополнений неизвестна, хотя нижние оценки были доказаны при некоторых ограничительных предположениях относительно алгоритмов. В 1973 году Моргенштерн доказал нижнюю границу Ω ( N  log  N ) для суммирования для алгоритмов, в которых мультипликативные константы имеют ограниченные величины (что верно для большинства, но не для всех алгоритмов БПФ). Пан (1986) доказал нижнюю границу Ω ( N  log  N ), предполагающую оценку меры «асинхронности» алгоритма БПФ, но общность этого предположения неясна. В случае питания от двойки N , Пападимитий (1979) утверждал , что число комплексно-количество дополнений , достигнутых Кули-Тьюки алгоритмов оптимальный при определенных предположениях о графе алгоритма (его предположения подразумевают, среди прочего, что никакие аддитивные тождества в корнях единства не используются). (Этот аргумент будет означать, что требуются по крайней мере реальные сложения, хотя это не является жесткой границей, потому что дополнительные добавления требуются как часть умножения комплексных чисел.) До сих пор ни один опубликованный алгоритм БПФ не достиг меньшего, чем сложения комплексных чисел ( или их эквивалент) для включения питания из-двух  N .

Третья проблема - свести к минимуму общее количество действительных умножений и сложений, иногда называемое «арифметической сложностью» (хотя в этом контексте рассматривается точный подсчет, а не асимптотическая сложность). Опять же, точная нижняя граница не доказана. Однако с 1968 года самый низкий опубликованный счет для степени двойки N долгое время достигался с помощью алгоритма БПФ с разделенным основанием , который требует действительных умножений и сложений для N > 1. Это недавно было сокращено до (Johnson and Frigo, 2007; Ланди и Ван Бускерк, 2007). Несколько большее количество (но все же лучше, чем разделение системы счисления для N ≥ 256) оказалось доказуемо оптимальным для N ≤ 512 при дополнительных ограничениях на возможные алгоритмы (потоковые графы, подобные разделению системы счисления с единичным модулем мультипликативных коэффициентов), путем сокращения к проблеме выполнимости по модулю теорий, решаемой грубой силой (Haynal & Haynal, 2011).

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

Приближения

Все описанные выше алгоритмы БПФ точно вычисляют ДПФ (т. Е. Игнорируя ошибки с плавающей запятой ). Однако было предложено несколько алгоритмов «БПФ», которые вычисляют ДПФ приблизительно с ошибкой, которая может быть сделана сколь угодно малой за счет увеличения объема вычислений. Такие алгоритмы обменивают ошибку аппроксимации на увеличенную скорость или другие свойства. Например, приближенный алгоритм БПФ Эдельмана и др. (1999) достигли более низких требований к связи для параллельных вычислений с помощью быстрого многополюсного метода . Вейвлет основанного на приблизительную FFT Го и Burrus (1996) принимает редкие входы / выходы (время / частота локализации) во внимание более эффективно , чем это возможно с точным FFT. Другой алгоритм для приближенного вычисления подмножества выходных данных ДПФ принадлежит Шентову и др. (1995). Алгоритм Эдельмана одинаково хорошо работает для разреженных и неразреженных данных, поскольку он основан на сжимаемости (дефицит ранга) самой матрицы Фурье, а не на сжимаемости (разреженности) данных. И наоборот, если данные являются разреженными, то есть если только K из N коэффициентов Фурье отличны от нуля, то сложность может быть уменьшена до O ( K  log ( N ) log ( N / K )), и это было продемонстрировано для приводят к практическому ускорению по сравнению с обычным БПФ для N / K  > 32 в примере с большим N ( N  = 2 22 ) с использованием вероятностного приближенного алгоритма (который оценивает наибольшие коэффициенты K с точностью до нескольких десятичных знаков).

Точность

Алгоритмы БПФ имеют ошибки, когда используется арифметика с плавающей запятой конечной точности, но эти ошибки обычно довольно малы; большинство алгоритмов БПФ, например, Кули – Тьюки, обладают превосходными числовыми свойствами как следствие структуры попарного суммирования алгоритмов. Верхняя граница относительной ошибки для алгоритма Кули – Тьюки составляет O ( ε log N ) по сравнению с O ( εN 3/2 ) для простой формулы ДПФ, где ε - машинная относительная точность с плавающей запятой. Фактически, среднеквадратичные (среднеквадратичные) ошибки намного лучше этих верхних оценок, составляя только O ( ε log N ) для Кули – Тьюки и O ( ε N ) для наивного ДПФ (Schatzman, 1996). Эти результаты, однако, очень чувствительны к точности коэффициентов вращения, используемых в БПФ (то есть значений тригонометрических функций ), и нередко неосторожные реализации БПФ имеют гораздо худшую точность, например, если они используют неточные тригонометрические рекуррентные формулы. . Некоторые БПФ, отличные от Кули – Тьюки, такие как алгоритм Рейдера – Бреннера, по своей сути менее стабильны.

В арифметике с фиксированной точкой ошибки конечной точности, накопленные алгоритмами БПФ, хуже, среднеквадратичные ошибки растут как O ( N ) для алгоритма Кули – Тьюки (Welch, 1969). Достижение этой точности требует особого внимания к масштабированию, чтобы минимизировать потерю точности, а алгоритмы БПФ с фиксированной точкой включают изменение масштаба на каждом промежуточном этапе декомпозиции, например, Кули – Тьюки.

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

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

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

преобразует массив x n с d -мерным вектором индексов набором из d вложенных суммирований ( для каждого j ), где деление n / N , определенное как , выполняется поэлементно. Эквивалентно, это композиция последовательности из d наборов одномерных ДПФ, выполняемых по одному измерению за раз (в любом порядке).

Эта композиционная точка зрения немедленно обеспечивает простейший и наиболее распространенный алгоритм многомерного ДПФ, известный как алгоритм строки-столбца (после двумерного случая ниже). То есть просто выполняется последовательность из d одномерных БПФ (по любому из вышеперечисленных алгоритмов): сначала вы преобразуете по измерению n 1 , затем по измерению n 2 и так далее (или на самом деле работает любой порядок) . Легко показать, что этот метод имеет обычную сложность O ( N  log  N ), где - общее количество преобразованных точек данных. В частности, существует N / N 1 преобразований размера N 1 и так далее, поэтому сложность последовательности БПФ составляет:

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

В более чем двух измерениях для локальности кэша часто бывает выгодно группировать измерения рекурсивно. Например, трехмерное БПФ может сначала выполнить двумерное БПФ каждого плоского «среза» для каждого фиксированного n 1 , а затем выполнить одномерное БПФ вдоль направления n 1 . Более общо, асимптотически оптимальным кэш-забывает алгоритм состоит рекурсивно деления размеров на две группы , и которые преобразуются рекурсивно (округления , если d не является даже) (см Frigo и Johnson, 2005). Тем не менее, это остается простой вариацией алгоритма строка-столбец, которая в конечном итоге требует только одномерного алгоритма БПФ в качестве базового случая и по-прежнему имеет сложность O ( N  log  N ). Еще один вариант заключается в выполнении перестановок матриц между преобразованиями последующих измерений, так что преобразования работают с непрерывными данными; это особенно важно для внепрограммной и распределенной памяти, когда доступ к несмежным данным занимает очень много времени.

Существуют и другие многомерные алгоритмы БПФ, отличные от алгоритма строка-столбец, хотя все они имеют сложность O ( N  log  N ). Возможно, самым простым БПФ без столбцов и без столбцов является алгоритм БПФ с основанием вектора , который является обобщением обычного алгоритма Кули – Тьюки, в котором размерности преобразования делятся на вектор оснований на каждом шаге. (Это также может иметь преимущества кеширования.) В простейшем случае вектор-основание системы счисления равны (например, вектор-основание-основание-2 делит все измерения на два), но в этом нет необходимости. Векторный основание системы счисления с единственным основанием системы счисления, не являющимся единичным, то есть , по сути, представляет собой алгоритм строки-столбца. Другие, более сложные методы включают в себя алгоритмы полиномиального преобразования, разработанные Nussbaumer (1977), которые рассматривают преобразование в терминах сверток и полиномиальных произведений. См. Duhamel and Vetterli (1990) для получения дополнительной информации и ссылок.

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

O ( N 5/2 лог  - Н ) обобщение сферических гармоник на сфере S 2 с N 2 узлов был описан Mohlenkamp, наряду с алгоритмом предположил (но не доказано) , чтобы иметь O ( N 2 журнала 2 ( Н )) сложность; Mohlenkamp также предоставляет реализацию в библиотеке libftsh. Алгоритм сферической гармоники со сложностью O ( N 2 log  N ) описан Рохлиным и Тигертом.

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

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

Приложения

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

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

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

Большие БПФ
С ростом объема больших данных в таких областях, как астрономия, возникла потребность в 512K FFT для определенных расчетов интерферометрии. Данные, собираемые такими проектами, как WMAP и LIGO, требуют БПФ в десятки миллиардов точек. Поскольку этот размер не помещается в основную память, активно исследуются так называемые БПФ вне ядра.
Приблизительное БПФ
Для таких приложений, как МРТ, необходимо вычислять ДПФ для неравномерно расположенных точек сетки и / или частот. Подходы на основе многополюсников могут вычислять приблизительные величины с коэффициентом увеличения времени выполнения.
Групповые БПФ
БПФ также можно объяснить и интерпретировать с помощью теории представления групп, допускающей дальнейшее обобщение. Функция на любой компактной группе, в том числе нециклической, имеет разложение по базису из неприводимых матричных элементов. Остается активной областью исследований, чтобы найти эффективный алгоритм для выполнения этой смены базиса. Приложения, включая эффективное расширение сферических гармоник , анализ определенных марковских процессов , робототехнику и т. Д.
Квантовые БПФ
В быстром алгоритме Шора для целочисленной факторизации на квантовом компьютере есть подпрограмма для вычисления ДПФ двоичного вектора. Это реализовано в виде последовательности 1- или 2-битных квантовых вентилей, теперь известных как квантовое БПФ, которое фактически является БПФ Кули – Тьюки, реализованным как конкретная факторизация матрицы Фурье. Расширение этих идей в настоящее время изучается.

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

Язык Команда / Метод Предварительные условия
р stats :: fft (x) Никто
Октава / MATLAB fft (x) Никто
Python fft.fft (x) тупой
Mathematica Фурье [x] Никто
Фортран fftw_one (план, вход, выход) FFTW
Юлия fft (A [, dims]) FFTW
Ржавчина fft.process (& mut x); Rustfft
Haskell dft x fft

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

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

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

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

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

использованная литература

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

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