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

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

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

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

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

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

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

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

История

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

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

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

Определение

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

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

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

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

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

Алгоритмы

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

Основная статья: Алгоритм БПФ Кули – Тьюки

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

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

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

алгоритмы

Основные статьи: Алгоритм БПФ с простым коэффициентом , Алгоритм БПФ Брууна , Алгоритм БПФ Радера , Chirp Z-преобразование и гексагональное быстрое преобразование Фурье

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

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

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

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

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

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

специализирующиеся на реальных или симметричных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приближения

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

Точность

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

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

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

Значения промежуточных частот могут быть получены различными методами усреднения.

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

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

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

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

${\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 можно рассматривать как $n_{1}\times n_{2}$ матрица , и этот алгоритм соответствует первому выполнению БПФ всех строк (соответственно столбцов), группируя полученные преобразованные строки (соответственно столбцы) вместе как еще $n_{1}\times n_{2}$ матрицу, а затем выполнение БПФ для каждого из столбцов (соответственно строк) этой второй матрицы и аналогичным образом группировку результатов в окончательную матрицу результатов.

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

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

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

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

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

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

Приложения

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

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

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

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

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

Большие БПФ

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

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

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

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

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

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

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

Языковая ссылка

Язык	Команда/Метод	Предварительные условия
Р	статистика::fft(x)	Никто
Сцилаб	ффт(х)	Никто
Октава / MATLAB	ффт(х)	Никто
Питон	fft.fft(x)	тупой или тупой
Математика	Фурье[х]	Никто
Фортран	fftw_one(план,вход,выход)	ФФТВ
Юлия	fft(A [, тускнеет])	ФФТВ
Ржавчина	fft.process(&mut x);	отдыхфффт
Хаскелл	дфт х	ффт

См. также

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

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

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

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

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

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

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

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

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

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

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