Основные алгоритмы компьютерной графики   КГ   ДМ   ТПОИ   Теория сигналов  

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

Мирослав Войнаровский

    Вводная информация

  1. Непрерывные преобразования Фурье и Лапласа
  2. Дискретные преобразования сигналов
  3. Свойства преобразований Фурье
  4. Технология БПФ

  5. Физический смысл БПФ
  6. Определения
  7. Теоремы быстрого преобразования Фурье (FFT)
  8. Основные формулы алгоритма БПФ
  9. Что такое зеркальный эффект
  10. Что такое эффект размазывания
  11. Неоднозначность представления суммой гармоник
  12. Доказательство зеркального эффекта
  13. Исправление зеркального эффекта
  14. БПФ для произвольного N
  15. Листинг программы на C++ (N - степень 2)
  16. Листинг программы на C++ (N - четное)
  17. Листинг программы на C++ (N - любое)
  18. Преобразование БПФ для N=PQ
  19. Логарифмический алгоритм БПФ для произвольного N
  20. Пояснения и оптимизация алгоритма БПФ
  21. Практические советы и замечания к выполнению БПФ
  22. Преобразование Фурье в среде MathCAD
  23. Преобразование Фурье в среде Maple
Быстрое преобразование Фурье, БПФ, Fast Furier Transform, FFT - алгоритм вычисления преобразования Фурье для дискретного случая. В отличие от простейшего алгоритма, который имеет сложность порядка O(N2), БПФ имеет сложность всего лишь O(Nlog2N). Алгоритм БПФ был впервые опубликован в 1965 году в статье Кули (Cooly) и Тьюки (Tukey).

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

Если у вас нет времени и желания разбираться с теорией, то можете сразу скопировать текст программы на C++. Здесь находится заголовочный файл fft.h и исходник fft.cpp для быстрого преобразования Фурье для числа отсчетов, равного степени двойки. Вызывать надо функцию fft. А здесь находится заголовочный файл и исходник для произвольного (!) числа отсчетов. Он чуть медленнее, но скорость там тоже порядка Nlog2N. Вызывать надо функцию universal_fft.

Определения

Определение 1

Дана конечная последовательность x0, x1, x2,...,xN-1 (в общем случае комплексных). Дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности X0, X1, X2,...,XN-1 элементы которой вычисляются по формуле:

    (1).

Определение 2

Дана конечная последовательность X0, X1, X2,...,XN-1 (в общем случае комплексных). Обратное дискретное преобразование Фурье (ДПФ) заключается в поиске другой последовательности x0, x1, x2,...,xN-1 элементы которой вычисляются по формуле:

    (2).

Основным свойством этих преобразований (которое доказывается в соответствующих разделах математики) является тот факт, что из последовательности {x} получается (при прямом преобразовании) последовательность {X}, а если потом применить к {X} обратное преобразование, то снова получится исходная последовательность {x}.

Определение 3

Величина

называется поворачивающим множителем.

Рассмотрим ряд свойств поворачивающих множителей, которые нам понадобятся в дальнейшем.

Верхняя цифра в поворачивающем множителе не является индексом, это - степень. Поэтому, когда она равна единице, мы не будем ее писать:

Прямое преобразование Фурье можно выразить через поворачивающие множители. В результате формула (1) примет вид:

    (3).

Эти коэффициенты действительно оправдывают свое название. Нарисуем на комплексной плоскости любое комплексное число, в виде вектора, исходящего из начала координат. Представим это комплексное число в показательной форме: re, где r - модуль числа, а φ - аргумент. Модуль соответствует длине вектора, а аргумент - углу поворота:

Теперь возьмем какой-нибудь поворачивающий множитель . Его модуль равен единице, а фаза - 2π/N. Как известно, при умножении комплексных чисел, представленных в показательной форме, их модули перемножаются, а аргументы суммируются. Тогда умножение исходного числа на поворачивающий множитель не изменит длину вектора, но изменит его угол. То есть, произойдет поворот вектора на угол 2π/N (см. предыдущий рисунок).

Если теперь посмотреть на формулу (3), то станет ясен геометрический смысл преобразования Фурье: он состоит в том, чтобы представить N комплексных чисел-векторов из набора {x}, каждое в виде суммы векторов из набора {X}, повернутых на углы, кратные 2π/N.

Основные алгоритмы компьютерной графики   КГ   ДМ   ТПОИ   Теория сигналов  
Знаете ли Вы, что наблюдатели - это операции, которые используют в качестве аргумента объекты соответствующего им типа и возвращают элемент другого типа, они используются для получения информации об объекте. Сюда относятся, например, операции типа size.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
  27.04.2016 - 07:59: СОВЕСТЬ - Conscience -> Проблема государственного терроризма - Карим_Хайдаров.
25.04.2016 - 07:47: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
24.04.2016 - 21:11: АСТРОФИЗИКА - Astrophysics -> Комета 67Р/Чурюмова-Герасименко и проблема ее происхождения - Евгений_Дмитриев.
20.04.2016 - 12:33: ЭКОЛОГИЯ - Ecology -> ЭКОЛОГИЯ ДЛЯ ВСЕХ - Карим_Хайдаров.
17.04.2016 - 22:31: СОВЕСТЬ - Conscience -> РУССКИЙ МИР - Карим_Хайдаров.
09.04.2016 - 06:59: АСТРОФИЗИКА - Astrophysics -> Сезонные колебания уровня вод морей и океанов - Юсуп_Хизиров.
28.03.2016 - 16:42: СОВЕСТЬ - Conscience -> ПРАВОСУДИЯ.НЕТ - Карим_Хайдаров.
17.03.2016 - 11:20: СЕЙСМОЛОГИЯ - Seismology -> Запасы воды под Землёй - Карим_Хайдаров.
15.03.2016 - 16:15: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> ВЫМИРАНИЕ ДИНОЗАВРОВ на www.nkj.ru - Карим_Хайдаров.
23.02.2016 - 20:34: Беседка - Chatter -> Приливы и отливы - Юсуп_Хизиров.
19.02.2016 - 05:38: ФИЗИКА ЭФИРА - Aether Physics -> Скорость распространения гравитации - Карим_Хайдаров.
Боровское исследовательское учреждение - Bourabai Research Bourabai Research Institution