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

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

A быстрое преобразование Фурье (БПФ ): алгоритм , который вычисляет дискретное преобразование Фурье (ДПФ) отслеживает или ее обратное (IDFT). Анализ Фурье преобразует сигнал из его исходной области в представление в частотной области и наоборот. ДПФ получается разложением обеспечивать значения на компоненты с разными частотами. Эта операция полезна во многих областях, но вычисление ее непосредственно из определения часто медленно, чтобы быть практичным. БПФ быстро вычисляет такие преобразования путем преобразования фактори матрицы ДПФ в произведение разреженных (в основном нулевых) множителей. В результате ему удается уменьшить сложность вычислений ДПФ из $O\; (N\; 2)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (N\; ^\; \{2\}\; \backslash \; right)\}$, который возникает, если просто применить определение ДПФ к $O\; (N\; log\; \; N)\; \{\backslash \; displaystyle\; O\; (N\; \backslash \; log\; N)\}$, где $N\; \{\backslash \; displaystyle\; N\}$- размер данных. Разница в скорости может быть огромной, особенно для длинных наборов данных, где N может исчисляться тысячами или миллионами. При наличии ошибки округления многие алгоритмы БПФ намного точнее, чем прямая или косвенная оценка ДПФ. Существует множество различных алгоритмов БПФ, основанных на широком спектре опубликованных теорий, от простых арифметики комплексных чисел до теории групп и теории чисел.

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

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

Содержание

• 1 История
• 2
• 3 Алгоритмы
  • 3.1 Алгоритмы Кули - Тьюки
  • 3.2 Другие алгоритмы БПФ
• 4 Алгоритмы БПФ, специализированные для реальных или симметричных данных
• 5 Вычислительные проблемы
  • 5.1 Границы сложности и количества операций
  • 5.2 Приближения
  • 5.3 Точность
• 6 Многомерные БПФ
• 7 Другие обобщения
• 8 Приложения
• 9 Области исследований
• 10 Язык ссылка
• 11 См. также
• 12 Ссылки
• 13 Дополнительная литература
• 14 Внешние ссылки

История

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

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

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

Определение

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

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; xne\; -\; i\; 2\; \pi \; kn\; /\; N\; k\; =\; 0,\dots ,\; N\; -\; 1,\; \{\backslash \; displaystyle\; X\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{n\; =\; 0\}\; ^\; \{N-1\}\; x\_\; \{n\}\; e\; ^\; \{-\; i2\; \backslash \; pi\; kn\; /\; N\}\; \backslash \; qquad\; k\; =\; 0,\; \backslash \; ldots,\; N-1,\}$

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

Непосредственная оценка этого определения требует $O\; (N\; 2)\; \{\backslash \; displaystyle\; O\; \backslash \; left\; (N\; ^\; \{2\}\; \backslash \; right)\}$: операций имеется N выходов X k, и каждый выход требует суммы N условий. БПФ - это любой метод вычисления одних и тех же результатов в операциях $O\; (N\; log\; \; N)\; \{\backslash \; displaystyle\; O\; (N\; \backslash \; log\; N)\}$. Все известные алгоритмы БПФ требуют операций Θ $(N\; log\; \; N)\; \{\backslash \; displaystyle\; (N\; \backslash \; log\; N)\}$, хотя нет никаких доказательств того, что более низкая оценка сложности невозможна.

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

Алгоритмы

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

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

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

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

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

Существуют алгоритмы БПФ, отличные от Кули - Тьюки. Корнелиус Ланцош провел новаторскую работу по БПФ и БПФ (метод) с Г. К. Дэниэлсон (1940).

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

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

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

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

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

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

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

$XN\; -\; k\; =\; X\; k\; \ast \; \{\backslash \; displaystyle\; X\_\; \{Nk\}\; =\; X\_\; \{k\}\; ^\; \{*\}\}$

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

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

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

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

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

Нерешенная проблема в информатике :. Какова нижняя граница сложности алгоритмов быстрого преобразования Фурье? Могут ли они быть быстрее, чем $O\; (N\; log\; \; N)\; \{\backslash \; displaystyle\; O\; (N\; \backslash \; log\; N)\}$?(более нерешенные проблемы в информатике)

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

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

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

Третья проблема - минимизировать общее количество действительных умножений и сложений, иногда называемое «арифметической сложностью» (хотя в данном контексте это точное количество, а не рассматриваемая асимптотическая сложность). Опять же, точная нижняя граница не доказана. Однако с 1968 года самый низкий опубликованный счет для степени двойки N долгое время достигался с помощью алгоритма БПФ с разделением оснований, который требует $4\; N\; log\; 2\; \; (N)\; -\; 6\; N\; +\; 8\; \{\backslash \; displaystyle\; 4N\; \backslash \; log\; \_\; \{2\}\; (N)\; -6N\; +\; 8\}$вещественное умножение и сложение для N>1. Это было недавно уменьшено до $\sim \; 34\; 9\; N\; log\; 2\; \; N\; \{\backslash \; displaystyle\; \backslash \; sim\; \{\backslash \; frac\; \{34\}\; \{9\}\}\; N\; \backslash \; 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 с точностью до нескольких после запятой).

Точность

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

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

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

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

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

$X\; k\; =\; \sum \; n\; =\; 0\; N\; -\; 1\; е\; -\; 2\; \pi \; ik\; \cdot \; (N\; /\; N)\; xn\; \{\backslash \; displaystyle\; X\; \_\; \{\backslash \; mathbf\; \{k\}\}\; =\; \backslash \; sum\; \_\; \{\backslash \; mathbf\; \{n\}\; =\; 0\}\; ^\; \{\backslash \; mathbf\; \{N\}\; -1\}\; e\; ^\; \{-2\; \backslash \; pi\; i\; \backslash \; mathbf\; \{\; k\}\; \backslash \; cdot\; (\backslash \; mathbf\; \{n\}\; /\; \backslash \; mathbf\; \{N\})\}\; x\; \_\; \{\backslash \; mathbf\; \{n\}\}\}$

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

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

$NN\; 1\; O\; (N\; 1\; log\; \; N\; 1)\; +\; \cdots \; +\; NN\; d\; O\; (N\; d\; log\; \; N\; d)\; =\; O\; (N\; [log\; \; N\; 1\; +\; \cdots \; +\; log\; \; N\; d])\; =\; O\; (N\; log\; \; N).\; \{\backslash \; displaystyle\; \{\backslash \; begin\; \{align\}\; \{\backslash \; frac\; \{N\}\; \{N\_\; \{1\}\}\}\; O\; (N\_\; \{1\}\; \backslash \; log\; N\_\; \{1\})\; +\; \backslash \; cdots\; +\; \{\backslash \; frac\; \{N\}\; \{N\_\; \{d\; \}\}\}\; O\; (N\_\; \{d\}\; \backslash \; log\; N\_\; \{d\})\; \backslash \backslash \; [6pt]\; =\; \{\}\; O\; \backslash \; left\; (N\; \backslash \; left\; [\backslash \; log\; N\_\; \{1\}\; +\; \backslash \; cdots\; +\; \backslash \; log\; N\_\; \{d\}\; \backslash \; справа]\; \backslash \; справа)\; =\; O\; (N\; \backslash \; log\; N).\; \backslash \; end\; \{align\}\}\}$

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

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

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

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

Обобщение O (Nlog N) до сферических гармоник на сфере S с N узлами было описано Моленкампом вместе с предполагаемым алгоритмом (но не доказано) имеет сложность O (N журнал (N)); Mohlenkamp также предоставляет возможности в библиотеке libftsh. Алгоритм сферической гармоники со сложностью O (Nlog N) описан Рохлиным и Тигертом.

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

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

Приложения

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

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

• Быстрое умножение больших целых чисел и многочленов
• Эффективное умножение матрицы на вектор для Теплица, циркулянта и других структурированных матриц
• алгоритмы фильтрации (см. методы сложения с перекрытием и сохранение с перекрытием )
• Быстрые алгоритмы для дискретного косинуса или синусоидальное преобразование (например, быстрое DCT, используемое для кодирования и декодирования JPEG и MPEG / MP3 )
• Быстро Чебышёвское приблили
• Решение разностных уравнений
• Вычисление изотопных распределений.

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

Большие БПФ

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

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

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

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

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

квантовых БПФ

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

Справочник по языку

Язык	Команда / метод	Предварительные требования
R	stats :: fft (x)	Нет
Octave / MATLAB	fft (x)	Нет
Python	fft.fft (x)	numpy
Mathematica	Фурье [x]	Нет
Джулия	fft (A [, dims])	FFTW

См. Также

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

• Алгоритм Кули – Тьюки
• Алгоритм БПФ с простым коэффициентом
• Алгоритм БПФ Бруна
• Алгоритм БПФ Рейдера
• Алгоритм БПФ Блюстейна
• алгоритм Герцеля - вычисляет отдельные члены дискретного преобразования Фурье

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

• ALGLIB - библиотека C ++ и C # с реальной / комплексной реализацией БПФ.
• FFTW «Самое быстрое преобразование Фурье на Западе» - библиотека C для дискретного преобразования Фурье (ДПФ) в одном или нескольких измерениях.
• FFTS - Самое быстрое преобразование Фурье на юге.
• FFTPACK - еще одна библиотека Fortran FFT (общественное достояние)
• Intel Интегрированные примитивы производительности
• Intel Math Kernel Library
• - БПФ для CUDA с ускорением на GPU

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

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

Ссылки

Дополнительная литература

• Бригам, Э. Оран (2002). «Быстрое преобразование Фурье». Нью-Йорк, США: Prentice-Hall. Cite journal требует | journal =()
• Cormen, Thomas H. ; Лейзерсон, Чарльз Э. ; Ривест, Рональд Л. ; Стейн, Клиффорд (2001). «Глава 30: Полиномы и БПФ». Введение в алгоритмы (2-е изд.). MIT Press / McGraw-Hill. ISBN 0-262-03293-7.
• Эллиотт, Дуглас Ф.; Рао, К. Рамамохан (1982). Быстрые преобразования: алгоритмы, анализ, приложения. Нью-Йорк, США: Academic Press.
• Guo, Haitao; Sitton, Gary A.; Burrus, Чарльз Сидни (1994). "Быстрое дискретное преобразование Фурье". Труды ICASSP '94. Международная конференция IEEE по акустике, речи и обработке сигналов. Труды конференции IEEE по акустике, речи и обработке сигналов (ICASSP). 3 . Pp. 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.; Теукольский, Саул А.; Веттерлинг, Уильям Т.; Фланнери, Брайан П. (2007). «Глава 12. Быстрое преобразование Фурье». Числовые рецепты: искусство научных вычислений (3-е изд.). Нью-Йорк, США: Cambridge University Press. ISBN 978-0-521-88068-8.
• Синглтон, Ричард Коллом (июнь 1969). «Краткая библиография по быстрому преобразованию Фурье». Специальный выпуск о быстром преобразовании Фурье. Транзакции IEEE по аудио и электроакустике. AU-17. IEEE Audio and Electroacoustics Group. С. 166–169. doi : 10.1109 / TAU.1969.1162029.(NB. Содержит обширную библиографию.)

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

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