Быстрое преобразование Фурье ( БПФ ) представляет собой алгоритм , который вычисляет дискретное преобразование Фурье (ДПФ) последовательности, или его обратного (IDFT). Анализ Фурье преобразует сигнал из его исходной области (часто во времени или пространстве) в представление в частотной области и наоборот. ДПФ получается путем разложения последовательности значений на компоненты с разными частотами. [1] Эта операция полезна во многих областях, но вычисление ее непосредственно из определения часто слишком медленно, чтобы быть практичным. БПФ быстро вычисляет такие преобразования с помощью факторизующим на матрицу ДПФв продукт редких (в основном нулевых) факторов. [2] В результате удается снизить сложность вычисления ДПФ из, который возникает, если просто применить определение ДПФ к , где это размер данных. Разница в скорости может быть огромной, особенно для длинных наборов данных, где N может быть в тысячах или миллионах. При наличии ошибки округления многие алгоритмы БПФ намного точнее, чем прямая или косвенная оценка определения ДПФ. Существует множество различных алгоритмов БПФ, основанных на широком диапазоне опубликованных теорий, от простой арифметики комплексных чисел до теории групп и теории чисел .
Быстрые преобразования Фурье широко используются в приложениях в инженерии, музыке, науке и математике. Основные идеи были популяризированы в 1965 году, но некоторые алгоритмы были получены еще в 1805 году. [1] В 1994 году Гилберт Стрэнг описал БПФ как «самый важный числовой алгоритм нашей жизни», [3] [4] и это был включен в 10 лучших алгоритмов 20-го века по версии журнала IEEE Computing in Science & Engineering . [5]
Наиболее известные алгоритмы БПФ зависят от разложения из N , но есть с FFTs O ( N журнал N ) сложности для всех N , даже для простого N . Многие алгоритмы БПФ зависят только от того, чтоявляется N -м примитивным корнем из единицы и, таким образом, может применяться к аналогичным преобразованиям над любым конечным полем , таким как теоретико-числовые преобразования . Поскольку обратное ДПФ такое же, как ДПФ, но с противоположным знаком в экспоненте и коэффициентом 1 / N , любой алгоритм БПФ может быть легко адаптирован для него.
История
Развитие быстрых алгоритмов для ДПФ можно проследить до неопубликованной работы Карла Фридриха Гаусса в 1805 году, когда ему потребовалась интерполяция орбиты астероидов Паллада и Юнона по выборочным наблюдениям. [6] [7] Его метод был очень похож на метод, опубликованный в 1965 году Джеймсом Кули и Джоном Тьюки , которым обычно приписывают изобретение современного универсального алгоритма БПФ. Хотя работа Гаусса предшествовала даже результатам Жозефа Фурье в 1822 году, он не анализировал время вычислений и в конечном итоге использовал другие методы для достижения своей цели.
Между 1805 и 1965 годами некоторые версии БПФ были опубликованы другими авторами. Фрэнк Йейтс в 1932 году опубликовал свою версию, названную алгоритмом взаимодействия , которая обеспечивала эффективное вычисление преобразований Адамара и Уолша . [8] Алгоритм Йейтса до сих пор используется в области статистического проектирования и анализа экспериментов. В 1942 году Г. К. Дэниэлсон и Корнелиус Ланцос опубликовали свою версию вычисления ДПФ для рентгеновской кристаллографии - области, в которой вычисление преобразований Фурье представляло собой серьезное узкое место. [9] [10] Хотя в прошлом многие методы были сосредоточены на уменьшении постоянного коэффициента для вычисление с использованием преимущества «симметрии», Дэниэлсон и Ланцош поняли, что можно использовать «периодичность» и применить «трюк удвоения», чтобы «удвоить [N] с лишь немногим более чем удвоением трудозатрат», хотя, как и Гаусс, они не сделали проанализировать, что это привело к масштабирование. [11]
Джеймс Кули и Джон Тьюки независимо друг от друга заново открыли эти более ранние алгоритмы [7] и опубликовали в 1965 году более общий БПФ, который применим, когда N является составным и не обязательно является степенью двойки, а также анализируетмасштабирование. [12] Тьюки придумал эту идею во время встречи Научно-консультативного комитета президента Кеннеди, где обсуждалась тема обнаружения ядерных испытаний Советским Союзом путем установки датчиков, окружающих страну извне. Для анализа выходных данных этих датчиков потребуется алгоритм БПФ. В беседе с Тьюки Ричард Гарвин признал общую применимость алгоритма не только к проблемам национальной безопасности, но и к широкому кругу проблем, включая одну, представляющую для него непосредственный интерес, определение периодичности ориентации спина в трехмерном кристалле. гелия-3. [13] Гарвин передал идею Тьюки Кули (оба работали в лаборатории IBM Watson ) для реализации. [14] Кули и Тьюки опубликовали статью за относительно короткий срок - шесть месяцев. [15] Поскольку Тьюки не работал в IBM, патентоспособность идеи была поставлена под сомнение, и алгоритм стал общественным достоянием, что в результате компьютерной революции следующего десятилетия сделало БПФ одним из незаменимых алгоритмов в цифровой обработке сигналов.
Определение
Позволять ,…, быть комплексными числами . ДПФ определяется по формуле
где является примитивным корнем N- й степени из 1.
Для непосредственной оценки этого определения требуется операций: имеется N выходов X k , и для каждого выхода требуется сумма N членов. БПФ - это любой метод вычисления одних и тех же результатов воперации. Все известные алгоритмы БПФ требуют Θ ( N бревно N ) {\ Displaystyle \ Theta (N \ log N)} операций , хотя нет никаких известных доказательств того, что более низкая оценка сложности невозможна. [16]
Чтобы проиллюстрировать экономию при использовании БПФ, рассмотрим подсчет комплексных умножений и сложений для 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) [17], но общее улучшение от к останки.
Алгоритмы
Алгоритм Кули-Тьюки
Безусловно, наиболее часто используемым БПФ является алгоритм Кули – Тьюки. Это алгоритм «разделяй и властвуй», который рекурсивно разбивает ДПФ любого составного размера. на множество меньших ДПФ размеров а также , вместе с умножения на комплексные корни из единицы традиционно называют множителями (по Джентльмену и Санде, 1966 [18] ).
Этот метод (и общая идея БПФ) был популяризирован публикацией Кули и Тьюки в 1965 году [12], но позже было обнаружено [1], что эти два автора независимо друг от друга заново изобрели алгоритм, известный Карлу Фридриху Гауссу. около 1805 г. [19] (впоследствии переоткрывалась несколько раз в ограниченных формах).
Наиболее известное использование алгоритма Кули-Тьюки состоит в том, чтобы разделить преобразование на две части размером N / 2 на каждом шаге, и поэтому оно ограничено величиной степени двойки, но в целом может использоваться любая факторизация (как было известно как Гауссу, так и Кули / Тьюки [1] ). Они называются случаями с основанием 2 и смешанным основанием соответственно (и другие варианты, такие как БПФ с разделенным основанием, также имеют свои собственные имена). Хотя основная идея является рекурсивной, большинство традиционных реализаций изменяют алгоритм, чтобы избежать явной рекурсии. Кроме того, поскольку алгоритм Кули – Тьюки разбивает ДПФ на более мелкие ДПФ, его можно произвольно комбинировать с любым другим алгоритмом ДПФ, например описанным ниже.
Другие алгоритмы БПФ
Существуют и другие алгоритмы БПФ, кроме Кули – Тьюки.
Для N = N 1 N 2 с взаимно простыми числами N 1 и N 2 можно использовать алгоритм простых множителей (Гуда – Томаса) (PFA), основанный на китайской теореме об остатках , чтобы факторизовать ДПФ аналогично Кули – Тьюки, но без факторы вращения. Алгоритм Рейдера – Бреннера (1976) [20] представляет собой факторизацию, подобную Кули – Тьюки, но с чисто мнимыми вращающимися множителями, сокращающими умножения за счет увеличения числа сложений и снижения числовой стабильности ; Позже его заменил вариант Кули-Тьюки с разделенным основанием (который обеспечивает такое же количество умножений, но с меньшим количеством сложений и без потери точности). Алгоритмы, рекурсивно разлагающие ДПФ на более мелкие операции, отличные от ДПФ, включают алгоритмы Брууна и QFT . ( Алгоритмы Райдера – Бреннера [20] и QFT были предложены для размеров степени двойки, но не исключено, что они могут быть адаптированы к общему составному N. Алгоритм Брууна применим к произвольным четным составным размерам.) Алгоритм Брууна , в частности , основан на интерпретации БПФ как рекурсивной факторизации полинома z N - 1, здесь в полиномы с действительными коэффициентами вида z M - 1 и z 2 M + az M + 1.
Другая полиномиальная точка зрения используется алгоритмом Винограда БПФ [21] [22], который разлагает 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). [23] [24] Один из подходов состоит в использовании обычного алгоритма (например, Кули-Тьюки) и удалении избыточных частей вычислений, что позволяет примерно в два раза экономить время и память. В качестве альтернативы можно выразить ДПФ с реальным входом четной длины как комплексное ДПФ половинной длины (действительная и мнимая части которого являются четными / нечетными элементами исходных реальных данных), за которым следует O ( N ) пост- технологические операции.
Когда-то считалось, что ДПФ с реальным входом можно более эффективно вычислять с помощью дискретного преобразования Хартли (DHT), но впоследствии утверждалось, что обычно можно найти специализированный алгоритм ДПФ с реальным входом (БПФ), который требует меньше операций, чем соответствующий алгоритм DHT (FHT) для того же количества входов. [23] Алгоритм Брууна (см. Выше) - еще один метод, который изначально был предложен для использования реальных входных данных, но он не оказался популярным.
Есть еще FFT специализации для случаев реальных данных , которые имеют четную / нечетную симметрию, и в этом случае можно получить еще фактор примерно два во время и памяти , и ДПФ становится дискретным косинусным / синус преобразование (ы) ( ДКП / часа ). Вместо того, чтобы напрямую изменять алгоритм БПФ для этих случаев, DCT / DST также могут быть вычислены с помощью БПФ реальных данных в сочетании с O ( N ) предварительной и последующей обработкой.
Вычислительные проблемы
Границы сложности и количества операций
Какова нижняя граница сложности алгоритмов быстрого преобразования Фурье? Могут ли они быть быстрее, чем?
Фундаментальный вопрос, давно представляющий теоретический интерес, - это доказательство нижних оценок сложности и точного количества операций быстрого преобразования Фурье, и многие нерешенные проблемы остаются. Строго не доказано, действительно ли для ДПФ требуется Ω ( N log N ) (т. Е. Порядок N log N или больше) операций, даже для простого случая степени двух размеров, хотя не известны алгоритмы с меньшей сложностью. В частности, в центре внимания таких вопросов обычно находится подсчет арифметических операций, хотя фактическая производительность на современных компьютерах определяется многими другими факторами, такими как оптимизация кэша или конвейера ЦП .
Следуя работе Шмуэля Винограда (1978), [21], известна точная нижняя граница Θ ( N ) для числа действительных умножений, необходимых для БПФ. Можно показать, что только иррациональные действительные умножения необходимы для вычисления ДПФ длины степени двойки . Более того, известны явные алгоритмы, позволяющие достичь этого подсчета (Heideman & Burrus , 1986; [25] Duhamel, 1990 [26] ). Однако эти алгоритмы требуют слишком большого количества дополнений, чтобы быть практичными, по крайней мере, на современных компьютерах с аппаратными умножителями (Duhamel, 1990; [26] Frigo & Johnson , 2005). [17]
Точная нижняя граница количества требуемых дополнений неизвестна, хотя нижние оценки были доказаны при некоторых ограничительных предположениях относительно алгоритмов. В 1973 году Моргенштерн [27] доказал нижнюю границу Ω ( N log N ) для суммирования для алгоритмов, в которых мультипликативные константы имеют ограниченные величины (что верно для большинства, но не для всех алгоритмов БПФ). Пан (1986) [28] доказал нижнюю границу Ω ( N log N ), предполагающую оценку меры «асинхронности» алгоритма БПФ, но общность этого предположения неясна. Для случая включения питания из-двух N , Пападимитий (1979) [29] утверждал , что числасложения комплексных чисел, достигаемого алгоритмами Кули – Тьюки, является оптимальным при определенных предположениях о графике алгоритма (его предположения подразумевают, среди прочего, что никакие аддитивные тождества в корнях из единицы не используются). (Этот аргумент подразумевает, что по крайней мере требуются реальные добавления, хотя это не является жесткой границей, потому что дополнительные добавления требуются как часть умножения комплексных чисел.) До сих пор ни один опубликованный алгоритм БПФ не достиг менее чем комплексно-количество дополнений (или их эквивалент) для включения питания из-двух N .
Третья проблема - свести к минимуму общее количество действительных умножений и сложений, иногда называемое «арифметической сложностью» (хотя в этом контексте рассматривается точный подсчет, а не асимптотическая сложность). Опять же, точная нижняя граница не доказана. Однако с 1968 года самый низкий опубликованный счет для степени двойки N долгое время достигался алгоритмом БПФ с разделенным основанием , который требуетдействительные умножения и сложения для N > 1. Это недавно было сокращено до(Джонсон и Фриго, 2007; [16] Ланди и Ван Бускерк, 2007 [30] ). Несколько большее количество (но все же лучше, чем разделение системы счисления для N ≥ 256) оказалось доказуемо оптимальным для N ≤ 512 при дополнительных ограничениях на возможные алгоритмы (потоковые графы, подобные разделению системы счисления, с мультипликативными коэффициентами единичного модуля), путем сокращения к задаче выполнимости по модулю теорий, решаемой грубой силой (Haynal & Haynal, 2011). [31]
Большинство попыток снизить или доказать сложность алгоритмов БПФ были сосредоточены на обычном случае сложных данных, потому что он самый простой. Однако БПФ со сложными данными настолько тесно связаны с алгоритмами для решения связанных проблем, таких как БПФ с реальными данными, дискретные косинусные преобразования , дискретные преобразования Хартли и т. Д., Что любое улучшение в одном из них немедленно приведет к улучшениям в других ( Дюамель и Веттерли, 1990). [32]
Приближения
Все описанные выше алгоритмы БПФ точно вычисляют ДПФ (т. Е. Игнорируя ошибки с плавающей запятой ). Однако было предложено несколько алгоритмов «БПФ», которые вычисляют ДПФ приблизительно с ошибкой, которая может быть сделана сколь угодно малой за счет увеличения объема вычислений. Такие алгоритмы обменивают ошибку аппроксимации на увеличенную скорость или другие свойства. Например, приближенный алгоритм БПФ Эдельмана и др. (1999) [33] достигает более низких требований к связи для параллельных вычислений с помощью быстрого многополюсного метода . Вейвлет основанное на приблизительную FFT Го и Burrus (1996) [34] принимает редкие входы / выходы (время / частота локализации) во внимание более эффективно , чем это возможно с точным FFT. Другой алгоритм для приближенного вычисления подмножества выходных данных ДПФ принадлежит Шентову и др. (1995). [35] Алгоритм Эдельмана одинаково хорошо работает как для разреженных, так и для неразреженных данных, поскольку он основан на сжимаемости (дефицит ранга) самой матрицы Фурье, а не на сжимаемости (разреженности) данных. И наоборот, если данные являются разреженными, то есть если только K из N коэффициентов Фурье отличны от нуля, то сложность может быть уменьшена до O ( K log ( N ) log ( N / K )), и это было продемонстрировано для приводят к практическому ускорению по сравнению с обычным БПФ для N / K > 32 в примере с большим N ( N = 2 22 ) с использованием вероятностного приближенного алгоритма (который оценивает наибольшие коэффициенты K с точностью до нескольких десятичных знаков). [36]
Точность
Алгоритмы БПФ имеют ошибки, когда используется арифметика с плавающей запятой конечной точности, но эти ошибки обычно довольно малы; большинство алгоритмов БПФ, например, Кули – Тьюки, обладают превосходными числовыми свойствами как следствие структуры попарного суммирования алгоритмов. Верхняя граница относительной ошибки для алгоритма Кули – Тьюки составляет O ( ε log N ), по сравнению с O ( εN 3/2 ) для простой формулы ДПФ, [18] где ε - машинная относительная точность с плавающей запятой. Фактически, среднеквадратичные (среднеквадратичные) ошибки намного лучше этих верхних оценок, составляя только O ( ε √ log N ) для Кули – Тьюки и O ( ε √ N ) для наивного ДПФ (Schatzman, 1996). [37] Эти результаты, однако, очень чувствительны к точности коэффициентов поворота, используемых в БПФ (т. Е. Значений тригонометрических функций ), и нередко неосторожные реализации БПФ имеют гораздо худшую точность, например, если они используют неточные тригонометрические рекуррентные формулы. Некоторые БПФ, отличные от Кули – Тьюки, такие как алгоритм Рейдера – Бреннера, по своей сути менее стабильны.
В арифметике с фиксированной точкой ошибки конечной точности, накопленные алгоритмами БПФ, хуже, среднеквадратичные ошибки растут как O ( √ N ) для алгоритма Кули – Тьюки (Welch, 1969). [38] Достижение этой точности требует особого внимания к масштабированию, чтобы минимизировать потерю точности, а алгоритмы БПФ с фиксированной точкой включают изменение масштаба на каждом промежуточном этапе декомпозиции, например, Кули – Тьюки.
Чтобы проверить правильность реализации БПФ, можно получить строгие гарантии за время O ( N log N ) с помощью простой процедуры проверки линейности, импульсной характеристики и свойств сдвига во времени преобразования на случайных входных данных (Ergün, 1995). . [39]
Многомерные БПФ
Как определено в многомерном ДПФ статье многомерного ДПФ
преобразует массив 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 and Johnson, 2005). [17] Тем не менее, это остается простой вариацией алгоритма строка-столбец, которая в конечном итоге требует только одномерного алгоритма БПФ в качестве базового случая и по-прежнему имеет сложность O ( N log N ). Еще один вариант заключается в выполнении транспонирования матриц между преобразованиями последующих измерений, так что преобразования работают с непрерывными данными; это особенно важно для внепрограммной и распределенной памяти, когда доступ к несмежным данным занимает очень много времени.
Существуют и другие многомерные алгоритмы БПФ, отличные от алгоритма строка-столбец, хотя все они имеют сложность O ( N log N ). Возможно, самым простым БПФ без столбцов и без столбцов является алгоритм БПФ с векторным основанием , который является обобщением обычного алгоритма Кули – Тьюки, в котором размерности преобразования делятся на векторкорней на каждом шагу. (Это также может иметь преимущества кэширования.) В простейшем случае векторной системы счисления все корни равны (например, vector-radix-2 делит все измерения на два), но в этом нет необходимости. Векторный основание системы счисления только с одним неединичным основанием системы счисления за раз, т. Е., по сути, является алгоритмом строка-столбец. Другие, более сложные методы включают алгоритмы полиномиального преобразования, разработанные Nussbaumer (1977), [40], которые рассматривают преобразование в терминах сверток и полиномиальных произведений. См. Duhamel и Vetterli (1990) [32] для получения дополнительной информации и ссылок.
Другие обобщения
O ( N 5/2 лог - Н ) обобщение сферических гармоник на сфере S 2 с Н 2 узлов был описан Mohlenkamp, [41] вместе с алгоритмом предположил (но не доказано) , чтобы иметь O ( N 2 журнала 2 ( N )) сложность; Mohlenkamp также предоставляет реализацию в библиотеке libftsh. [42] Алгоритм сферической гармоники со сложностью O ( N 2 log N ) описан Рохлиным и Тигертом. [43]
Быстрый алгоритм складывания аналогичен FFT, за исключением того, что она работает над серией Binned сигналов , а не ряд действительных или комплексных значений скалярных. Вращение (которое в БПФ - это умножение на комплексный вектор) - это круговой сдвиг формы сигнала компонента.
Различные группы также опубликовали алгоритмы «БПФ» для данных с неравномерным интервалом, как описано в Potts et al. (2001). [44] Такие алгоритмы не вычисляют строго ДПФ (которое определено только для данных с равными интервалами), а скорее их аппроксимацию ( неравномерное дискретное преобразование Фурье , или НДПФ, которое само часто вычисляется только приблизительно). В более общем плане существуют различные другие методы спектральной оценки .
Приложения
БПФ используется в программном обеспечении цифровой записи, дискретизации, аддитивного синтеза и коррекции высоты тона . [45]
Важность БПФ проистекает из того факта, что он сделал работу в частотной области в равной степени вычислительно выполнимой, как работу во временной или пространственной области. Некоторые из важных приложений БПФ включают: [15] [46]
- быстрое целочисленное и полиномиальное умножение,
- эффективное матрично-векторное умножение для теплицевых , циркулянтных и других структурированных матриц,
- алгоритмы фильтрации (см. методы перекрытия – добавления и перекрытия – сохранения ),
- быстрые алгоритмы дискретного косинусного или синусоидального преобразования (например, быстрый DCT, используемый для кодирования и декодирования JPEG и MPEG / MP3 ),
- быстрое чебышевское приближение ,
- решение разностных уравнений ,
- расчет изотопных распределений . [47]
- модуляция и демодуляция сложных символов данных с использованием мультиплексирования с ортогональным частотным разделением (OFDM) для 5G, LTE, Wi-Fi, DSL и других современных систем связи.
Области исследований
- Большие БПФ
- С ростом объема больших данных в таких областях, как астрономия, возникла потребность в 512K FFT для определенных расчетов интерферометрии. Данные, собираемые такими проектами, как WMAP и LIGO, требуют БПФ в десятки миллиардов точек. Поскольку этот размер не помещается в основную память, активно исследуются так называемые БПФ вне ядра. [48]
- Приблизительное БПФ
- Для таких приложений, как МРТ, необходимо вычислять ДПФ для неравномерно расположенных точек сетки и / или частот. Подходы на основе многополюсников могут вычислять приблизительные величины с коэффициентом увеличения времени выполнения. [49]
- Групповые БПФ
- БПФ также можно объяснить и интерпретировать с помощью теории представления групп, допускающей дальнейшее обобщение. Функция на любой компактной группе, в том числе нециклической, имеет разложение по базису из неприводимых матричных элементов. Остается активной областью исследований, чтобы найти эффективный алгоритм для выполнения этой смены базиса. Приложения, включая эффективное расширение сферических гармоник , анализ некоторых марковских процессов , робототехнику и т. Д. [50]
- Квантовые БПФ
- В быстром алгоритме Шора для целочисленной факторизации на квантовом компьютере есть подпрограмма для вычисления ДПФ двоичного вектора. Это реализовано в виде последовательности 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 (общественное достояние)
- Зависит от архитектуры:
- Библиотеки производительности Arm [51]
- Интегрированные примитивы производительности Intel
- Библиотека ядра Intel Math
- Доступно гораздо больше реализаций [52] для CPU и GPU, таких как PocketFFT для C ++.
Другие ссылки:
- Алгоритм Одлизко – Шёнхаге применяет БПФ к конечным рядам Дирихле.
- Алгоритм Шёнхаге – Штрассена - асимптотически быстрый алгоритм умножения для больших целых чисел
- Диаграмма бабочки - диаграмма, используемая для описания БПФ
- Спектральная музыка (включает применение анализа DFT к музыкальной композиции)
- Анализатор спектра - любое из нескольких устройств, выполняющих анализ спектра, часто с помощью DFT.
- Временная последовательность
- Быстрое преобразование Уолша-Адамара
- Обобщенный распределительный закон
- Спектральный анализ методом наименьших квадратов
- Многомерное преобразование
- Многомерная дискретная свертка
Рекомендации
- ^ a b c d Хайдеман, Майкл Т .; Джонсон, Дон Х .; Буррус, Чарльз Сидни (1984). «Гаусс и история быстрого преобразования Фурье» (PDF) . Журнал IEEE ASSP . 1 (4): 14–21. CiteSeerX 10.1.1.309.181 . DOI : 10,1109 / MASSP.1984.1162257 . S2CID 10032502 .
- ^ Ван Лоан, Чарльз (1992). Вычислительные рамки для быстрого преобразования Фурье . СИАМ .
- ^ Стрэнг, Гилберт (май – июнь 1994 г.). «Вейвлеты». Американский ученый . 82 (3): 250–255. JSTOR 29775194 .
- ^ Kent, Ray D .; Прочтите, Чарльз (2002). Акустический анализ речи . ISBN 0-7693-0112-6.
- ^ Донгарра, Джек; Салливан, Фрэнсис (январь 2000 г.). «Приглашенные редакторы. Введение в 10 лучших алгоритмов». Вычислительная техника в науке и технике . 2 (1): 22–23. Bibcode : 2000CSE ..... 2a..22D . DOI : 10,1109 / MCISE.2000.814652 . ISSN 1521-9615 .
- ^ Гаусс, Карл Фридрих (1866). "Theoria interpolationis methoddo nova tractata" [Теория относительно нового метода интерполяции]. Нахласс (Неопубликованная рукопись). Верке (на латинском и немецком языках). 3 . Геттинген, Германия: Königlichen Gesellschaft der Wissenschaften zu Göttingen. С. 265–303.
- ^ а б Хайдеман, Майкл Т .; Джонсон, Дон Х .; Буррус, Чарльз Сидни (1 сентября 1985 г.). «Гаусс и история быстрого преобразования Фурье». Архив истории точных наук . 34 (3): 265–277. CiteSeerX 10.1.1.309.181 . DOI : 10.1007 / BF00348431 . ISSN 0003-9519 . S2CID 122847826 .
- ^ Йетс, Франк (1937). «Планирование и анализ факторных экспериментов». Техническое сообщение № 35 Бюро почв Содружества . 142 (3585): 90–92. Bibcode : 1938Natur.142 ... 90F . DOI : 10.1038 / 142090a0 . S2CID 23501205 .
- ^ Дэниэлсон, Гордон С .; Ланцош, Корнелиус (1942). «Некоторые улучшения в практическом анализе Фурье и их применение к рассеянию рентгеновских лучей на жидкостях». Журнал Института Франклина . 233 (4): 365–380. DOI : 10.1016 / S0016-0032 (42) 90767-1 .
- ^ Ланцош, Корнелиус (1956). Прикладной анализ . Прентис-Холл .
- ^ Кули, Джеймс У .; Льюис, Питер А.В.; Уэлч, Питер Д. (июнь 1967). «Исторические заметки о быстром преобразовании Фурье». IEEE Transactions по аудио и электроакустике . 15 (2): 76–79. CiteSeerX 10.1.1.467.7209 . DOI : 10.1109 / TAU.1967.1161903 . ISSN 0018-9278 .
- ^ а б Кули, Джеймс У .; Тьюки, Джон В. (1965). «Алгоритм машинного вычисления сложных рядов Фурье» . Математика вычислений . 19 (90): 297–301. DOI : 10.1090 / S0025-5718-1965-0178586-1 . ISSN 0025-5718 .
- ^ Кули, Джеймс У. (1987). Повторное открытие алгоритма быстрого преобразования Фурье (PDF) . Microchimica Acta . III . Вена, Австрия. С. 33–45.
- ^ Гарвин, Ричард (июнь 1969). «Быстрое преобразование Фурье как пример трудности широкого использования новой техники» (PDF) . IEEE Transactions по аудио и электроакустике . AU-17 (2): 68–72.
- ^ а б Рокмор, Дэниел Н. (январь 2000 г.). «БПФ: алгоритм, который может использовать вся семья». Вычислительная техника в науке и технике . 2 (1): 60–64. Bibcode : 2000CSE ..... 2a..60R . CiteSeerX 10.1.1.17.228 . DOI : 10.1109 / 5992.814659 . ISSN 1521-9615 .
- ^ а б Фриго, Маттео; Джонсон, Стивен Г. (январь 2007 г.) [2006-12-19]. «Модифицированное БПФ с разделенным основанием с меньшим количеством арифметических операций». Транзакции IEEE по обработке сигналов . 55 (1): 111–119. Bibcode : 2007ITSP ... 55..111J . CiteSeerX 10.1.1.582.5497 . DOI : 10.1109 / tsp.2006.882087 . S2CID 14772428 .
- ^ а б в Фриго, Маттео; Джонсон, Стивен Г. (2005). «Дизайн и реализация FFTW3» (PDF) . Труды IEEE . 93 (2): 216–231. CiteSeerX 10.1.1.66.3097 . DOI : 10,1109 / jproc.2004.840301 . S2CID 6644892 .
- ^ а б Джентльмен, В. Морвен; Санде, Г. (1966). «Быстрые преобразования Фурье - для удовольствия и выгоды». Труды AFIPS . 29 : 563–578. DOI : 10.1145 / 1464291.1464352 . S2CID 207170956 .
- ^ Гаусс, Карл Фридрих (1866) [1805]. Theoria interpolationis methoddo nova tractata . Верке (на латинском и немецком языках). 3 . Геттинген, Германия: Königliche Gesellschaft der Wissenschaften. С. 265–327.
- ^ а б Бреннер, Норман М .; Рейдер, Чарльз М. (1976). «Новый принцип быстрого преобразования Фурье». Транзакции IEEE по акустике, речи и обработке сигналов . 24 (3): 264–266. DOI : 10,1109 / TASSP.1976.1162805 .
- ^ а б Виноград, Шмуэль (1978). «О вычислении дискретного преобразования Фурье» . Математика вычислений . 32 (141): 175–199. DOI : 10.1090 / S0025-5718-1978-0468306-4 . JSTOR 2006 266 . PMC 430186 . PMID 16592303 .
- ^ Виноград, Шмуэль (1979). «О мультипликативной сложности дискретного преобразования Фурье» . Успехи в математике . 32 (2): 83–117. DOI : 10.1016 / 0001-8708 (79) 90037-9 .
- ^ а б Соренсен, Хенрик В .; Джонс, Дуглас Л .; Хайдеман, Майкл Т .; Буррус, Чарльз Сидни (1987). «Действительные алгоритмы быстрого преобразования Фурье». Транзакции IEEE по акустике, речи и обработке сигналов . 35 (6): 849–863. CiteSeerX 10.1.1.205.4523 . DOI : 10,1109 / TASSP.1987.1165220 .
- ^ Соренсен, Хенрик В .; Джонс, Дуглас Л .; Хайдеман, Майкл Т .; Буррус, Чарльз Сидни (1987). «Поправки к« алгоритмам быстрого вещественного преобразования Фурье » ». Транзакции IEEE по акустике, речи и обработке сигналов . 35 (9): 1353. DOI : 10,1109 / TASSP.1987.1165284 .
- ^ Хайдеман, Майкл Т .; Буррус, Чарльз Сидни (1986). «О количестве умножений, необходимых для вычисления ДПФ длины 2 n ». Транзакции IEEE по акустике, речи и обработке сигналов . 34 (1): 91–95. DOI : 10,1109 / TASSP.1986.1164785 .
- ^ а б Дюамель, Пьер (1990). «Алгоритмы, удовлетворяющие нижним границам мультипликативной сложности ДПФ длины 2 n и их связь с практическими алгоритмами». Транзакции IEEE по акустике, речи и обработке сигналов . 38 (9): 1504–1511. DOI : 10.1109 / 29.60070 .
- ^ Моргенштерн, Жак (1973). «Замечание о нижней оценке линейной сложности быстрого преобразования Фурье». Журнал ACM . 20 (2): 305–306. DOI : 10.1145 / 321752.321761 . S2CID 2790142 .
- ^ Пан, Виктор Я. (1986-01-02). «Компромисс между аддитивной сложностью и асинхронностью линейных и билинейных алгоритмов» . Письма об обработке информации . 22 (1): 11–14. DOI : 10.1016 / 0020-0190 (86) 90035-9 . Проверено 31 октября 2017 .
- ^ Пападимитриу, Христос Х. (1979). «Оптимальность быстрого преобразования Фурье». Журнал ACM . 26 : 95–102. DOI : 10.1145 / 322108.322118 . S2CID 850634 .
- ^ Ланди, Томас Дж .; Ван Бускерк, Джеймс (2007). «Новый матричный подход к реальным БПФ и сверткам длиной 2 k ». Вычислительная техника . 80 (1): 23–45. DOI : 10.1007 / s00607-007-0222-6 . S2CID 27296044 .
- ^ Хайнал, Стив; Хайнал, Хайди (2011). «Генерация и поиск семейств алгоритмов БПФ» (PDF) . Журнал по выполнимости, логическому моделированию и вычислениям . 7 (4): 145–187. arXiv : 1103,5740 . Bibcode : 2011arXiv1103.5740H . DOI : 10.3233 / SAT190084 . S2CID 173109 . Архивировано из оригинального (PDF) 26 апреля 2012 года.
- ^ а б Дюамель, Пьер; Веттерли, Мартин (1990). «Быстрые преобразования Фурье: учебное пособие и современное состояние» . Обработка сигналов . 19 (4): 259–299. DOI : 10.1016 / 0165-1684 (90) 90158-U .
- ^ Эдельман, Алан; Маккоркодейл, Питер; Толедо, Сиван (1999). "Будущее быстрое преобразование Фурье?" (PDF) . Журнал СИАМ по научным вычислениям . 20 (3): 1094–1114. CiteSeerX 10.1.1.54.9339 . DOI : 10,1137 / S1064827597316266 .
- ^ Го, Хайтао; Буррус, Чарльз Сидни (1996). «Быстрое приближенное преобразование Фурье с помощью вейвлет-преобразования». Труды SPIE . Применение вейвлетов в обработке сигналов и изображений IV. 2825 : 250–259. Bibcode : 1996SPIE.2825..250G . CiteSeerX 10.1.1.54.3984 . DOI : 10.1117 / 12.255236 . S2CID 120514955 .
- ^ Шентов, Огнян В .; Mitra, Sanjit K .; Heute, Ульрих; Хоссен, Абдул Н. (1995). «Подполосное ДПФ. I. Определение, интерпретация и расширения». Обработка сигналов . 41 (3): 261–277. DOI : 10.1016 / 0165-1684 (94) 00103-7 .
- ^ Hassanieh, Haitham; Индик, Петр ; Катаби, Дина; Прайс, Эрик (январь 2012 г.). «Простой и практичный алгоритм разреженного преобразования Фурье» (PDF) . Симпозиум ACM-SIAM по дискретным алгоритмам .(NB. См. Также веб-страницу sFFT .)
- ^ Шацман, Джеймс К. (1996). «Точность дискретного преобразования Фурье и быстрого преобразования Фурье» . Журнал СИАМ по научным вычислениям . 17 (5): 1150–1166. CiteSeerX 10.1.1.495.9184 . DOI : 10.1137 / s1064827593247023 .
- ^ Уэлч, Питер Д. (1969). «Анализ ошибок быстрого преобразования Фурье с фиксированной точкой». IEEE Transactions по аудио и электроакустике . 17 (2): 151–157. DOI : 10.1109 / TAU.1969.1162035 .
- ^ Эргюн, Фунда (1995). Тестирование многомерных линейных функций: преодоление узкого места генератора . Материалы 27-го симпозиума ACM по теории вычислений . Киото, Япония. С. 407–416. DOI : 10.1145 / 225058.225167 . ISBN 978-0897917186. S2CID 15512806 .
- ^ Нуссбаумер, Анри Дж. (1977). «Цифровая фильтрация с использованием полиномиальных преобразований». Письма об электронике . 13 (13): 386–387. DOI : 10.1049 / эл: 19770280 .
- ^ Моленкамп, Мартин Дж. (1999). «Быстрое преобразование сферических гармоник» (PDF) . Журнал анализа и приложений Фурье . 5 (2–3): 159–184. CiteSeerX 10.1.1.135.9830 . DOI : 10.1007 / BF01261607 . S2CID 119482349 . Проверено 11 января 2018 .
- ^ "Библиотека libftsh" . Архивировано из оригинала на 2010-06-23 . Проверено 9 января 2007 .
- ^ Рохлин, Владимир; Тигерт, Марк (2006). "Быстрые алгоритмы расширения сферических гармоник" (PDF) . Журнал СИАМ по научным вычислениям . 27 (6): 1903–1928. CiteSeerX 10.1.1.125.7415 . DOI : 10.1137 / 050623073 . Проверено 18 сентября 2014 . [1]
- ^ Поттс, Дэниел; Стейдл, Габриэле ; Таше, Манфред (2001). «Быстрые преобразования Фурье для данных без интервалов: учебное пособие» (PDF) . В Бенедетто, JJ; Феррейра П. (ред.). Современная теория выборки: математика и приложения . Birkhäuser .
- ^ Берджесс, Ричард Джеймс (2014). История музыкального производства . Издательство Оксфордского университета. ISBN 978-0199357178. Проверено 1 августа 2019 .
- ^ Чу, Элеонора; Джордж, Алан (1999-11-11) [1999-11-11]. «Глава 16». Внутри черного ящика БПФ: последовательные и параллельные алгоритмы быстрого преобразования Фурье . CRC Press . С. 153–168. ISBN 978-1-42004996-1.
- ^ Фернандес-де-Коссио Диас, Хорхе; Фернандес-де-Коссио, Хорхе (2012-08-08). «Вычисление распределения изотопических пиков в центре масс с помощью преобразования Фурье». Аналитическая химия . 84 (16): 7052–7056. DOI : 10.1021 / ac301296a . ISSN 0003-2700 . PMID 22873736 .
- ^ Cormen, Thomas H .; Николь, Дэвид М. (1998). «Выполнение БПФ вне ядра в параллельных дисковых системах» (PDF) . Параллельные вычисления . 24 (1): 5–20. CiteSeerX 10.1.1.44.8212 . DOI : 10.1016 / S0167-8191 (97) 00114-2 .[ постоянная мертвая ссылка ]
- ^ Датт, Алок; Рохлин, Владимир (1993-11-01). «Быстрые преобразования Фурье для данных без интервалов». Журнал СИАМ по научным вычислениям . 14 (6): 1368–1393. DOI : 10.1137 / 0914081 . ISSN 1064-8275 .
- ^ Рокмор, Дэниел Н. (2004). «Последние достижения и применения в групповых БПФ». В Бирнсе, Джиме (ред.). Вычислительная некоммутативная алгебра и приложения . Наука НАТО II: математика, физика и химия. 136 . Springer Нидерланды. С. 227–254. CiteSeerX 10.1.1.324.4700 . DOI : 10.1007 / 1-4020-2307-3_9 . ISBN 978-1-4020-1982-1. S2CID 1412268 .
- ^ «Библиотеки производительности Arm» . Arm . 2020 . Проверено 16 декабря 2020 .
- ^ «Полный список библиотек C / C ++ FFT» . Сообщество VCV . 2020-04-05 . Источник 2021-03-03 .
дальнейшее чтение
- Бригам, Э. Оран (2002). «Быстрое преобразование Фурье». Нью-Йорк, США: Прентис-Холл . Цитировать журнал требует
|journal=
( помощь ) - Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (2001). «Глава 30: Полиномы и БПФ». Введение в алгоритмы (2-е изд.). MIT Press / McGraw-Hill . ISBN 0-262-03293-7.
- Эллиотт, Дуглас Ф .; Рао, К. Рамамохан (1982). Быстрые преобразования: алгоритмы, анализы, приложения . Нью-Йорк, США: Academic Press .
- Го, Хайтао; Ситтон, Гэри А .; Буррус, Чарльз Сидни (1994). «Быстрое дискретное преобразование Фурье». Материалы ICASSP '94. Международная конференция IEEE по акустике, обработке речи и сигналов . Труды конференции IEEE по акустике, речи и обработке сигналов (ICASSP) . 3 . С. 445–448. DOI : 10.1109 / ICASSP.1994.389994 . ISBN 978-0-7803-1775-8. S2CID 42639206 .
- Джонсон, Стивен Дж .; Фриго, Маттео (2007). «Модифицированное БПФ с разделенным основанием с меньшим количеством арифметических операций» (PDF) . Транзакции IEEE по обработке сигналов . 55 (1): 111–119. Bibcode : 2007ITSP ... 55..111J . CiteSeerX 10.1.1.582.5497 . DOI : 10.1109 / tsp.2006.882087 . S2CID 14772428 .
- Press, William H .; Teukolsky, Saul A .; Веттерлинг, Уильям Т .; Фланнери, Брайан П. (2007). «Глава 12. Быстрое преобразование Фурье» . Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк, США: Издательство Кембриджского университета . ISBN 978-0-521-88068-8.
- Синглтон, Ричард Коллом (июнь 1969). «Краткая библиография по быстрому преобразованию Фурье». Специальный выпуск о быстром преобразовании Фурье . IEEE Transactions по аудио и электроакустике . AU-17. IEEE Audio and Electroacoustics Group. С. 166–169. DOI : 10.1109 / TAU.1969.1162029 . (NB. Содержит обширную библиографию.)
- Елена Престини: «Эволюция прикладного гармонического анализа», Springer, ISBN 978-0-8176-4125-2 (2004), раздел 3.10 «Гаусс и астероиды: история БПФ».
Внешние ссылки
- Быстрое преобразование Фурье для полиномиального умножения - быстрый алгоритм Фурье
- Быстрое преобразование Фурье , наставничества онлайн книгередакцией Чарльза Сидни Burrus, с главами Чарльза Сидни Burrus, Иван Selesnick, Маркус Pueschel, Маттео Фриго и Стивен Г. Джонсон (2008)
- Быстрое преобразование Фурье - БПФ - программирование БПФ на C ++ - алгоритм Кули – Тьюки
- Электронная документация, ссылки, книга и код
- Шри Веларатна, « Тридцать лет анализаторам БПФ », Звук и вибрация (январь 1997 г., юбилейный выпуск, посвященный 30-летию) - исторический обзор аппаратных устройств БПФ.
- ALGLIB FFT Code - многоязычная (VBA, C ++, Pascal и т. Д.) Библиотека численного анализа и обработки данных с двойной лицензией / GPL
- SFFT: разреженное быстрое преобразование Фурье - алгоритм быстрого преобразования Фурье (сублинейное время) MIT, sFFT и реализация
- VB6 FFT - оптимизированная реализация библиотеки VB6 с исходным кодом
- Интерактивное руководство по БПФ - визуальное интерактивное введение в преобразования Фурье и методы БПФ