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

Быстрое преобразование Фурье (БПФ, FFT) — алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем <math>O(N^2)</math>, требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющий сложность <math>O(N\log(N))</math>.

Основной алгоритм

Покажем, как выполнить дискретное преобразование Фурье за <math>O(N(p_1+\cdots+p_n))</math> действий при <math>N=p_1p_2\cdots p_n</math>. В частности, при <math>N=2^n</math> понадобится <math>O(N\log(N))</math> действий.

Дискретное преобразование Фурье преобразует набор чисел <math>a_0, \dots, a_{n-1}</math> в набор чисел <math>b_0, \dots, b_{n-1}</math>, такой, что <math>b_i=\sum_{j=0}^{n-1}a_j\varepsilon^{ij}</math>, где <math>\varepsilon^n=1</math> и <math>\varepsilon^k\neq 1</math> при <math>0<k<n</math>. Алгоритм быстрого преобразования Фурье применим к любым коммутативным ассоциативным кольцам с единицей. Чаще всего этот алгоритм применяют к полю комплексных чисел (c <math>\varepsilon=e^{2\pi i/n}</math>) и к кольцам вычетов (коим, в частности, является компьютерный целый тип).

Основной шаг алгоритма состоит в сведении задачи для <math>N</math> чисел к задаче для <math>p=N/q</math> числам, где <math>q</math> — делитель <math>N</math>. Пусть мы уже умеем решать задачу для <math>N/q</math> чисел. Применим преобразование Фурье к наборам <math>a_i,a_{q+i}, \dots, a_{q(p-1)+i}</math> для <math>i=0,1,\dots,q-1</math>. Покажем теперь, как за <math>O(Np)</math> действий решить исходную задачу. Заметим, что <math>b_i=\sum_{j=0}^{q-1} \varepsilon^{ij} (\sum_{k=0}^{p-1}a_{kq+j}\varepsilon^{kiq})</math>. Выражения в скобках нам уже известны — это <math>i\pmod p</math>-тое число после преобразования Фурье <math>j</math>-той группы. Таким образом, для вычисления каждого <math>b_i</math> нужно <math>O(q)</math> действий, а для вычисления всех <math>b_i</math> — <math>O(Nq)</math> действий, что и требовалось получить.

Обратное преобразование Фурье

Для обратного преобразования Фурье можно применять алгоритм прямого преобразования Фурье — нужно лишь использовать <math>\varepsilon^{-1}</math> вместо <math>\varepsilon</math> (или применить операцию комплексного сопряжения в начале к входным данным, а затем к результату, полученному после прямого преобразования Фурье) и окончательный результат поделить на <math>N</math>.

Общий случай

Общий случай может быть сведён к предыдущему. Пусть <math>4N>2^k\ge2N</math>. Заметим, что <math>b_i=\varepsilon^{-i^2/2}\sum_{j=0}^{N-1}\varepsilon^{(i+j)^2/2}\varepsilon^{-j^2/2}a_j</math>. Обозначим <math>\bar{a}_i=\varepsilon^{-i^2/2}a_i, \bar{b}_i=\varepsilon^{i^2/2}b_i, c_i=\varepsilon^{(2N-2-i)^2/2}</math>. Тогда <math>\bar{b}_i=\sum_{j=0}^{2N-2-i}\bar{a}_jc_{2N-2-i-j}</math>, если положить <math>\bar{a}_i=0</math> при <math>i\ge N</math>.

Таким образом задача сведена к вычислению свёртки, но это можно сделать с помощью трёх преобразований Фурье для <math>2^k</math> элементов. Выполняем прямое преобразование Фурье для <math>\{\bar{a}_i\}_{i=0}^{i=2^k-1}</math> и <math>\{c_i\}_{i=0}^{i=2^k-1}</math>, перемножаем поэлементно результаты и выполняем обратное преобразование Фурье.

Вычисления всех <math>\bar{a}_i</math> и <math>c_i</math> требуют <math>O(N)</math> действий, три преобразования Фурье требуют <math>O(N\log(N))</math> действий, перемножение результатов преобразований Фурье требует <math>O(N)</math> действий, вычисление всех <math>b_i</math> зная значения свертки требует <math>O(N)</math> действий. Итого для дискретного преобразования Фурье требуется <math>O(N\log(N))</math> действий для любого <math>N</math>.

Этот алгоритм быстрого преобразования Фурье может работать над кольцом только когда известны первообразные корни из единицы степеней <math>2N</math> и <math>2^k</math>.

Вывод преобразования из ДПФ

Наиболее распространенным алгоритмом БПФ является алгоритм Кули-Тьюки (Cooley–Tukey), при котором ДПФ от <math>N=N_1 N_2</math> выражается как сумма ДПФ более малых размерностей <math>N_1</math> и <math>N_2</math> рекурсивно для того, чтобы достичь сложность <math>O(N\log(N))</math>. В вычислительной технике наиболее часто используется рекурсивное разложение ДПФ надвое, то есть с основанием 2, (хотя может быть использовано любое основание), а количество входных отсчетов является степенью двойки. Для случаев, когда ДПФ считается от количества отсчетов, являющихся простыми числами могут быть использованы алгоритмы Блуштайна и Рейдера.

Ниже рассмотрим наиболее простой способ вычисления БПФ по алгоритму Кули-Тьюки с основанием 2.

Дискретное преобразование Фурье для вектора <math> \vec x </math>, состоящего из N элементов, имеет вид:

<math> \vec X = \hat A \vec x </math>

элементы матрицы <math> \hat A </math> имеют вид: <math> a_{N}^{mn} = e^ { -\frac{2\pi i}{N} mn} </math>.

Взяв за основание 2, ДПФ можно выразить как сумму 2 частей: сумму четных индексов <math>m={2n}</math> и сумму нечетных индексов <math>m={2n+1}</math>:

<math> X_m=\sum_{n=0}^{N-1} x_n a_{N}^{mn} = \sum_{n=0}^{N/2-1}x_{2n} a_{N}^{2nm} + \sum_{n=0}^{N/2-1}x_{2n+1} a_{N}^{(2n+1)m}</math>

Коэффициенты <math> a_{N}^{2nm} </math> и <math> a_{N}^{(2n+1)m} </math> можно переписать следующим образом:

<math> a_{N}^{2nm} = e^\left( -2\pi i \frac{2mn}{N} \right) = e^ \left( -2\pi i \frac{mn}{N/2} \right) = a_{N/2}^{nm} </math>

<math> a_{N}^{(2n+1)m} = e^ \left( -2\pi i \frac{m}{N} \right) a_{N/2}^{nm} </math>

В результате получаем:

<math> X_m=\sum_{n=0}^{N/2-1} x_{2n} a_{N/2}^{nm} + e^ { -\frac{2\pi i}{N} m} \sum_{n=0}^{N/2-1} x_{2n+1} a_{N/2}^{nm} </math>

Вычисление данного выражения можно упростить используя:

1. свойство периодичности ДПФ:

<math> a_{N/2}^{(m+\frac{N}{2})n} = a_{N/2}^{nm} </math>,

2. коэффициент поворота БПФ удовлетворяет следующему равенству:

<math>

\begin{matrix} e^{\frac{-2\pi i}{N} (m + N/2)} & = & e^{\frac{-2\pi i m}{N} - {\pi i}} \\ & = & e^{-\pi i} e^{\frac{-2\pi i m}{N}} \\ & = & -e^{\frac{-2\pi i m}{N}} \end{matrix} </math> В результате упрощений, обозначив ДПФ четных индексов <math>x_{2m}</math> через <math>E_k</math> (англ., even — четный) и ДПФ нечетных индексов <math>x_{2m + 1}</math> через <math>O_k</math> (англ., odd — нечетный), для <math>0 \leq m < \frac{N}{2}</math> получаем:

<math>

\begin{matrix} X_m & = & E_m + e^{-\frac{2\pi i}{N}m} O_m \\ X_{m+\frac{N}{2}} & = & E_m - e^{-\frac{2\pi i}{N}m} O_m \end{matrix} </math>

Данная запись является базой алгоритма Кули-Тьюки с основанием 2 для вычисления БПФ. То есть ДПФ от вектора, состоящего из N отсчетов, приведено к линейной композиции двух ДПФ от <math>\frac N2</math> отсчетов, и если для первоначальной задачи требовалось <math>N^2</math> операций, то для полученной композиции — <math>\frac{N^2}{2} </math> (за счет повторного использования промежуточных результатов вычислений <math>E_m</math> и <math>O_m</math>). Если N является степенью двух, то это разделение можно продолжать рекурсивно до тех пор, пока не дойдем до двухточечного преобразования Фурье, которое вычисляется по следующим формулам:

<math>

\begin{cases} X_0=x_0+x_1\\ X_1=x_0-x_1 \end{cases} </math> При рекурсивном делении ДПФ от <math>N</math> входных значений на сумму 2 ДПФ по <math>N/2</math> входных значений сложность алгоритма становится равной <math>O(N\log(N))</math>.

См. также

• Бабочка (БПФ)

Ссылки

• Захаров С. И. Повышение эффективности вибродиагностики механизмов с помощью экспертных систем. М: Машиностроение//Вестник машиностроения, 2008, № 6, стр.31-32.
• [www.dsplib.ru/content/thintime/thintime.html БПФ по основанию 2 с прореживанием по времени] (рус.). Проверено 15 ноября 2010. [www.webcitation.org/65EOWMM4R Архивировано из первоисточника 5 февраля 2012].
• [www.dsplib.ru/content/thinfreq/thinfreq.html БПФ по основанию 2 с прореживанием по частоте] (рус.). Проверено 15 ноября 2010. [www.webcitation.org/65EOYGVTp Архивировано из первоисточника 5 февраля 2012].
• [www.dsplib.ru/content/polyphasefft/polyphase.html Полифазное БПФ] (рус.). Проверено 15 ноября 2010. [www.webcitation.org/65EOZJ6qz Архивировано из первоисточника 5 февраля 2012].

Отрывок, характеризующий Быстрое преобразование Фурье

Ветер стих, черные тучи низко нависли над местом сражения, сливаясь на горизонте с пороховым дымом. Становилось темно, и тем яснее обозначалось в двух местах зарево пожаров. Канонада стала слабее, но трескотня ружей сзади и справа слышалась еще чаще и ближе. Как только Тушин с своими орудиями, объезжая и наезжая на раненых, вышел из под огня и спустился в овраг, его встретило начальство и адъютанты, в числе которых были и штаб офицер и Жерков, два раза посланный и ни разу не доехавший до батареи Тушина. Все они, перебивая один другого, отдавали и передавали приказания, как и куда итти, и делали ему упреки и замечания. Тушин ничем не распоряжался и молча, боясь говорить, потому что при каждом слове он готов был, сам не зная отчего, заплакать, ехал сзади на своей артиллерийской кляче. Хотя раненых велено было бросать, много из них тащилось за войсками и просилось на орудия. Тот самый молодцоватый пехотный офицер, который перед сражением выскочил из шалаша Тушина, был, с пулей в животе, положен на лафет Матвевны. Под горой бледный гусарский юнкер, одною рукой поддерживая другую, подошел к Тушину и попросился сесть.
– Капитан, ради Бога, я контужен в руку, – сказал он робко. – Ради Бога, я не могу итти. Ради Бога!
Видно было, что юнкер этот уже не раз просился где нибудь сесть и везде получал отказы. Он просил нерешительным и жалким голосом.
– Прикажите посадить, ради Бога.
– Посадите, посадите, – сказал Тушин. – Подложи шинель, ты, дядя, – обратился он к своему любимому солдату. – А где офицер раненый?
– Сложили, кончился, – ответил кто то.
– Посадите. Садитесь, милый, садитесь. Подстели шинель, Антонов.
Юнкер был Ростов. Он держал одною рукой другую, был бледен, и нижняя челюсть тряслась от лихорадочной дрожи. Его посадили на Матвевну, на то самое орудие, с которого сложили мертвого офицера. На подложенной шинели была кровь, в которой запачкались рейтузы и руки Ростова.
– Что, вы ранены, голубчик? – сказал Тушин, подходя к орудию, на котором сидел Ростов.
– Нет, контужен.
– Отчего же кровь то на станине? – спросил Тушин.
– Это офицер, ваше благородие, окровянил, – отвечал солдат артиллерист, обтирая кровь рукавом шинели и как будто извиняясь за нечистоту, в которой находилось орудие.
Насилу, с помощью пехоты, вывезли орудия в гору, и достигши деревни Гунтерсдорф, остановились. Стало уже так темно, что в десяти шагах нельзя было различить мундиров солдат, и перестрелка стала стихать. Вдруг близко с правой стороны послышались опять крики и пальба. От выстрелов уже блестело в темноте. Это была последняя атака французов, на которую отвечали солдаты, засевшие в дома деревни. Опять всё бросилось из деревни, но орудия Тушина не могли двинуться, и артиллеристы, Тушин и юнкер, молча переглядывались, ожидая своей участи. Перестрелка стала стихать, и из боковой улицы высыпали оживленные говором солдаты.
– Цел, Петров? – спрашивал один.
– Задали, брат, жару. Теперь не сунутся, – говорил другой.
– Ничего не видать. Как они в своих то зажарили! Не видать; темь, братцы. Нет ли напиться?
Французы последний раз были отбиты. И опять, в совершенном мраке, орудия Тушина, как рамой окруженные гудевшею пехотой, двинулись куда то вперед.
В темноте как будто текла невидимая, мрачная река, всё в одном направлении, гудя шопотом, говором и звуками копыт и колес. В общем гуле из за всех других звуков яснее всех были стоны и голоса раненых во мраке ночи. Их стоны, казалось, наполняли собой весь этот мрак, окружавший войска. Их стоны и мрак этой ночи – это было одно и то же. Через несколько времени в движущейся толпе произошло волнение. Кто то проехал со свитой на белой лошади и что то сказал, проезжая. Что сказал? Куда теперь? Стоять, что ль? Благодарил, что ли? – послышались жадные расспросы со всех сторон, и вся движущаяся масса стала напирать сама на себя (видно, передние остановились), и пронесся слух, что велено остановиться. Все остановились, как шли, на середине грязной дороги.
Засветились огни, и слышнее стал говор. Капитан Тушин, распорядившись по роте, послал одного из солдат отыскивать перевязочный пункт или лекаря для юнкера и сел у огня, разложенного на дороге солдатами. Ростов перетащился тоже к огню. Лихорадочная дрожь от боли, холода и сырости трясла всё его тело. Сон непреодолимо клонил его, но он не мог заснуть от мучительной боли в нывшей и не находившей положения руке. Он то закрывал глаза, то взглядывал на огонь, казавшийся ему горячо красным, то на сутуловатую слабую фигуру Тушина, по турецки сидевшего подле него. Большие добрые и умные глаза Тушина с сочувствием и состраданием устремлялись на него. Он видел, что Тушин всею душой хотел и ничем не мог помочь ему.
Со всех сторон слышны были шаги и говор проходивших, проезжавших и кругом размещавшейся пехоты. Звуки голосов, шагов и переставляемых в грязи лошадиных копыт, ближний и дальний треск дров сливались в один колеблющийся гул.
Теперь уже не текла, как прежде, во мраке невидимая река, а будто после бури укладывалось и трепетало мрачное море. Ростов бессмысленно смотрел и слушал, что происходило перед ним и вокруг него. Пехотный солдат подошел к костру, присел на корточки, всунул руки в огонь и отвернул лицо.
– Ничего, ваше благородие? – сказал он, вопросительно обращаясь к Тушину. – Вот отбился от роты, ваше благородие; сам не знаю, где. Беда!
Вместе с солдатом подошел к костру пехотный офицер с подвязанной щекой и, обращаясь к Тушину, просил приказать подвинуть крошечку орудия, чтобы провезти повозку. За ротным командиром набежали на костер два солдата. Они отчаянно ругались и дрались, выдергивая друг у друга какой то сапог.
– Как же, ты поднял! Ишь, ловок, – кричал один хриплым голосом.
Потом подошел худой, бледный солдат с шеей, обвязанной окровавленною подверткой, и сердитым голосом требовал воды у артиллеристов.
– Что ж, умирать, что ли, как собаке? – говорил он.
Тушин велел дать ему воды. Потом подбежал веселый солдат, прося огоньку в пехоту.
– Огоньку горяченького в пехоту! Счастливо оставаться, землячки, благодарим за огонек, мы назад с процентой отдадим, – говорил он, унося куда то в темноту краснеющуюся головешку.
За этим солдатом четыре солдата, неся что то тяжелое на шинели, прошли мимо костра. Один из них споткнулся.
– Ишь, черти, на дороге дрова положили, – проворчал он.
– Кончился, что ж его носить? – сказал один из них.
– Ну, вас!
И они скрылись во мраке с своею ношей.
– Что? болит? – спросил Тушин шопотом у Ростова.
– Болит.
– Ваше благородие, к генералу. Здесь в избе стоят, – сказал фейерверкер, подходя к Тушину.
– Сейчас, голубчик.
Тушин встал и, застегивая шинель и оправляясь, отошел от костра…
Недалеко от костра артиллеристов, в приготовленной для него избе, сидел князь Багратион за обедом, разговаривая с некоторыми начальниками частей, собравшимися у него. Тут был старичок с полузакрытыми глазами, жадно обгладывавший баранью кость, и двадцатидвухлетний безупречный генерал, раскрасневшийся от рюмки водки и обеда, и штаб офицер с именным перстнем, и Жерков, беспокойно оглядывавший всех, и князь Андрей, бледный, с поджатыми губами и лихорадочно блестящими глазами.