Чем БПФ отличаются от ДПФ и как их реализовать в C ++?

Question

После некоторого изучения я создал небольшое приложение, которое вычисляет ДПФ (дискретные преобразования Фурье) по некоторому входу.Он работает достаточно хорошо, но довольно медленно.

Я читал, что БПФ (быстрые преобразования Фурье) позволяют проводить более быстрые вычисления, но чем они отличаются?И что более важно, как бы я реализовал их в C ++?

Answer 1

Если вам не нужно реализовывать алгоритм вручную, вы можете взглянуть на Самое быстрое преобразование Фурье на Западе

Даже несмотря на то, что он разработан на C, он официально работает на C ++ (из FAQ )

Вопрос 2.9. Могу ли я позвонить FFTW из C ++?

Определенно. FFTW должен скомпилировать и / или ссылка под любым компилятором C ++. Более того, вполне вероятно, что C ++ шаблон класса бит-совместимый с FFTW формат комплексного числа (см. FFTW руководство для более подробной информации).

Answer 2

БПФ имеет n * log (n) конкуренцию по сравнению с ДПФ, у которого n ^ 2.

Существует много литературы по этому вопросу, и я настоятельно рекомендую вам сначала проверить это, потому что такая широкая тема не может быть полностью объяснена здесь. http://en.wikipedia.org/wiki/Fast_Fourier_transform (проверьте внешние ссылки)

Если вам нужна библиотека, я советую вам использовать, например, существующую. http://www.fftw.org/ В этой библиотеке эффективно реализована БПФ, а также она используется в программном обеспечении пропариатерии (например, MATLAB)

Answer 3

Результаты правильно реализованного БПФ по существу идентичны результатам правильно реализованного БПФ (они отличаются только ошибками округления). Как уже отмечали другие, главное отличие заключается в производительности. DFT имеет O (n ^ 2) операций, в то время как FFT имеет O (nlogn) операций.

Лучшая, самая читаемая публикация, которую я когда-либо нашел (к которой я все еще обращаюсь), это Быстрое преобразование Фурье и его приложения Э. Бригама. Первые несколько глав дают очень подробный обзор непрерывных и дискретных форм преобразования Фурье. Затем он использует это для разработки быстрой версии DFT, основанной на алгоритме Кули-Тьюки для оснований radix-2 (n - степень 2) и случаев смешанного радиуса (хотя последний является несколько более мелкий трактат, чем прежний).

Базовый подход в алгоритме radix-2 для выполнения операции линейного времени на входе X и рекурсивного разбиения результата пополам и выполнения аналогичной операции линейного времени на двух половинах. Случай смешанного радиуса аналогичен, хотя вам нужно каждый раз делить X на равные части, поэтому полезно, если n не имеет больших простых множителей.

Answer 4

Книга Стивена Смита Руководство ученого и инженера по цифровой обработке сигналов , в частности Глава 8 по DFT и Глава 12 по FFT , делает многое лучшая работа по объяснению двух преобразований, которые я когда-либо мог.

Кстати, вся книга доступна бесплатно (ссылка выше), и это очень хорошее введение в обработку сигналов.

Что касается запроса кода C ++, я использовал только самое быстрое преобразование Фурье на Западе (уже цитируемое superexsl) или библиотеки DSP, такие как библиотеки TI или Analog Devices.

Answer 5

Я нашел это хорошее объяснение с некоторыми описанными алгоритмами.

FastFourierTransform

О реализации,

• сначала я бы удостоверился, что ваша реализация возвращает правильные результаты (сравните вывод из matlab или octave - со встроенными преобразователями Фурье)
• оптимизировать при необходимости, использовать профилировщики
• не используйте ненужные для циклов