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

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

Дискретный анализ Фурье суммы косинусоидальных волн на частотах 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)}$

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

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

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

Этот метод (и общая идея БПФ) был популяризирован публикацией Кули и Тьюки в 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 иг ^{2 М}  +  аз ^М  + 1.

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

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

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

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

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

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

${\displaystyle X_{N-k}=X_{k}^{*}}$

и для этой ситуации были разработаны эффективные алгоритмы БПФ (см., например, Соренсен, 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]${\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]
• модуляция и демодуляция сложных символов данных с использованием мультиплексирования с ортогональным частотным разделением (OFDM) для 5G, LTE, Wi-Fi, DSL и других современных систем связи.

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

Большие БПФ

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

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

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

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

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

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

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

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

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

Алгоритмы, относящиеся к БПФ:

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

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

• ALGLIB - библиотека C ++ и C # с двойной лицензией / GPL (также поддерживающая другие языки) с реальной / сложной реализацией БПФ
• FFTPACK - еще одна библиотека Fortran FFT (общественное достояние)
• Зависит от архитектуры:
  • Библиотеки производительности Arm ^[51]
  • Интегрированные примитивы производительности Intel
  • Библиотека ядра Intel Math
• Доступно гораздо больше реализаций ^[52] для CPU и GPU, таких как PocketFFT для C ++.

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

• Алгоритм Одлызко – Шёнхаге применяет БПФ к конечным рядам Дирихле
• Алгоритм Шёнхаге – Штрассена - асимптотически быстрый алгоритм умножения для больших целых чисел
• Диаграмма бабочки - диаграмма, используемая для описания БПФ
• Спектральная музыка (включает применение анализа 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 Transactions по аудио и электроакустике . AU-17. IEEE Audio and Electroacoustics Group. С. 166–169. DOI : 10.1109 / TAU.1969.1162029 . (NB. Содержит обширную библиографию.)

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

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