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

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:51, 17 ноября 2016.


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

Наиболее распространённым алгоритмом вычисления быстрого преобразования Фурье является алгоритм Кули-Тьюки[1].

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

Концепция

Данный алгоритм используется для вычисления дискретного преобразования Фурье (ДПФ) и основан на следующих принципах:

  • ДПФ размерности выражается через сумму ДПФ более малых размерностей и .
  • Аналогичным образом и рекурсивно выражаются через ДПФ ещё более малых размерностей.
  • Разложение ДПФ в сумму 2 частей можно организовать таким образом, что первая часть будет представлять собой сумму по чётным индексам, а вторая — по нечётным.

Разбиение

Пусть — вектор, для которого необходимо вычислить ДПФ. Тогда его Фурье-образ можно представить в виде последовательности , где — Фурье-образ -ой компоненты.

Тогда, воспользовавшись приведёнными выше концепциями, Фурье-образ приводится к следующему виду:

,


где — сумма по чётным индексам;
сумма по нечётным индексам.

В силу периодичности ДПФ:

,

откуда:

.

Таким образом, все компоненты ДПФ можно рекурсивно раскладывать по уменьшению размерности до Фурье-образов 2 точек, которые определяются по формулам:

,

Связь между начальным и конечным положением элементов

Пусть имеется элементов последовательности и надо получить последовательность . Для этого делится по индексам на две последовательности — с чётными индексами и нечётными индексами, каждая из которых затем рекурсивно таки же образом делится на более короткие последовательности, пока все полученные последовательности не будут иметь длину не более 2.

Пример деления последовательности для приведён на рис. 1.

Рис. 1. Процесс деления для последовательности из 16 элементов.

Итого алгоритм деления выполняется за итераций.

Рассмотрим двоичное представление номеров элементов и занимаемых ими мест.

Элемент с номером (двоичное ) после всех перестановок занимает позицию , элемент — позицию , элемент — позицию , элемент — позицию и так далее.

Можно заметить закономерную связь между двоичными представлениями индекса (начального положения) и двоичным представлением конечного положения.

TemplateTheoremIcon.svg Теорема Теорема

При делении последовательности длины на последовательности длины не более 2 двоичное представление конечной позиции любого элемента получается из двоичного представления начальной позиции этого элемента перестановкой битов в обратном порядке и наоборот.

Доказательство
На первом шаге чётные элементы с номером переместились в позицию , а нечетные — из позиции в позицию .

Таким образом, новая позиция вычисляется из старой позиции с помощью функции , где операция означает взятие целой части числа , а — дробной.

Рис. 2. Циклический сдвиг вправо.
Рис. 3. Циклический сдвиг на -ом шаге.

Назовём данную операцию циклическим сдвигом вправо, исходя из того, что в двоичном представлении числа при применении данной операции все биты, кроме младшего (самого правого), перемещаются на 1 позицию вправо, младший бит перемещается на освободившееся место самого старшего (самого левого) бита (рис. 2).

Дальнейшие разбиения выполняются аналогично.

На каждом следующем шаге количество последовательностей удваивается, а число элементов в каждой из них уменьшается вдвое, и операции подвергаются уже не все биты, а только несколько младших (правых). Так, на -ом шаге остаются нетронутыми старшие битов (рис. 3.).

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

Именно такое перемещение — из разряда в разряд завершает перестановку в зеркальное перемещение битов. Что и требовалось доказать.

См. также

Примечания

  1. Быстрое преобразование Фурье [Электронный ресурс] : Материал из Википедии — свободной энциклопедии : Версия 76171255, сохранённая в 08:16 UTC 2 февраля 2016 / Авторы Википедии // Википедия, свободная энциклопедия. — Электрон. дан. — Сан-Франциско: Фонд Викимедиа, 2016. — Режим доступа: http://ru.wikipedia.org/?oldid=76171255