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

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

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

Быстрое преобразование Фурье ( БПФ ) представляет собой алгоритм , который вычисляет дискретное преобразование Фурье (ДПФ) последовательности, или его обратного (IDFT). Анализ Фурье преобразует сигнал из его исходной области (часто во времени или пространстве) в представление в частотной области и наоборот. ДПФ получается путем разложения последовательности значений на составляющие с разными частотами. ^[1] Эта операция полезна во многих областях, но вычисление ее непосредственно из определения часто слишком медленно, чтобы быть практичным. БПФ быстро вычисляет такие преобразования с помощью факторизующим на матрицу ДПФв продукт редких (в основном нулевых) факторов. ^[2] В результате ему удается снизить сложность вычисления ДПФ от , которая возникает, если просто применить определение ДПФ, до , где - размер данных. Разница в скорости может быть огромной, особенно для длинных наборов данных, где N может исчисляться тысячами или миллионами. При наличии ошибки округления многие алгоритмы БПФ намного точнее, чем прямая или косвенная оценка определения ДПФ. Существует множество различных алгоритмов БПФ, основанных на широком спектре опубликованных теорий, от простой арифметики комплексных чисел до теории групп и${\ Displaystyle О \ влево (N ^ {2} \ вправо)}$${\ Displaystyle О (Н \ журнал N)}$${\ displaystyle 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 , любой алгоритм БПФ может быть легко адаптирован для него.${\ Displaystyle е ^ {- 2 \ пи я / N}}$

История [ править ]

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

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

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

Определение [ править ]

Пусть x ₀ ,…, x _{N −1} - комплексные числа . ДПФ определяется по формуле

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

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

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

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

Алгоритмы [ править ]

Алгоритм Кули-Тьюки [ править ]

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

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

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

Другие алгоритмы БПФ [ править ]

Есть алгоритмы БПФ, отличные от Кули – Тьюки. Корнелиус Ланцош провел новаторскую работу по БПФ и FFS ( быстрый метод выборки Фурье ) с GC Danielson (1940). ^{[ необходима цитата ]}

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

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

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

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

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

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

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

${\ Displaystyle X_ {Nk} = X_ {k} ^ {*}}$

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

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

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

Вычислительные проблемы [ править ]

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

Нерешенная проблема в информатике : Какова нижняя граница сложности алгоритмов быстрого преобразования Фурье? Могут ли они быть быстрее чем ?${\ Displaystyle О (Н \ журнал N)}$ (больше нерешенных проблем в информатике)

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

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

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

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

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

Приближения [ править ]

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

Многомерные БПФ [ править ]

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

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

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

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

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

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

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

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

Другие обобщения [ править ]

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

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

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

Приложения [ править ]

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

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

• Быстрое целочисленное и полиномиальное умножение
• Эффективное матрично-векторное умножение для теплицевых , циркулянтных и других структурированных матриц
• Алгоритмы фильтрации (см. Методы перекрытия – добавления и перекрытия – сохранения )
• Быстрые алгоритмы дискретного косинусного или синусоидального преобразования (например, быстрое DCT, используемое для кодирования и декодирования JPEG и MPEG / MP3 )
• Быстрое приближение Чебышева
• Решение разностных уравнений
• Расчет изотопных распределений . ^[47]

Области исследований [ править ]

Большие БПФ

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

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

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

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

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

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

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

Ссылка на язык [ править ]

См. Также [ править ]

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

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

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

• ALGLIB - библиотека C ++ и C # с реальной / сложной реализацией БПФ
• FFTPACK - еще одна библиотека Fortran FFT (общественное достояние)
• Интегрированные примитивы производительности Intel
• Библиотека ядра Intel Math
• cuFFT - БПФ для CUDA с ускорением на GPU

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

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

• Бригам, Э. Оран (2002). «Быстрое преобразование Фурье». Нью-Йорк, США: Прентис-Холл . Cite journal requires |journal= (help)
• Кормен, Томас Х .; Лейзерсон, Чарльз Э .; Ривест, Рональд Л .; Стейн, Клиффорд (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 по аудио и электроакустике . AU-17. IEEE Audio and Electroacoustics Group. С. 166–169. DOI : 10.1109 / TAU.1969.1162029 . (NB. Содержит обширную библиографию.)

Внешние ссылки [ править ]

• Быстрый алгоритм Фурье
• Быстрое преобразование Фурье , наставничества онлайн книгередакцией Чарльза Сидни Burrus, с главами Чарльза Сидни Burrus, Иван Selesnick, Маркус Pueschel, Маттео Фриго и Стивен Г. Джонсон (2008)
• Ссылки на код БПФ и информацию в Интернете
• Национальный Тайваньский университет - FFT
• Программирование БПФ на C ++ - алгоритм Кули – Тьюки
• Электронная документация, ссылки, книга и код
• Использование БПФ для построения агрегированных распределений вероятностей
• Шри Веларатна, « Тридцать лет анализаторам БПФ », звук и вибрация (январь 1997 г., юбилейный выпуск, посвященный 30-летию) - исторический обзор аппаратных устройств БПФ.
• Основы БПФ и пример использования мультиинструмента
• Заметки из учебника FFT, PPT, видео в Институте целостных численных методов
• ALGLIB FFT Code GPL Лицензированная многоязычная (VBA, C ++, Pascal и т. Д.) Библиотека численного анализа и обработки данных
• SFFT: разреженное быстрое преобразование Фурье  - алгоритм быстрого преобразования Фурье (сублинейное время) MIT, sFFT и его реализация
• VB6 FFT  - оптимизированная реализация библиотеки VB6 с исходным кодом
• Иллюстрированное быстрое преобразование Фурье  - демонстрационные примеры и калькулятор БПФ
• Дискретное преобразование Фурье (вперед)  - реализация кода FFTPACK в JavaScript от Swarztrauber
• Преобразования Фурье дискретных сигналов (Microlink IT College)
• Interactive FFT Tutorial  - визуальное интерактивное введение в преобразования Фурье и методы БПФ