ДПФ И БПФ, когда что применять... Опции

[TigerSHARC]

Здравствуйте!
Интересно, в каких случая удобно применять БПФ, а в каких прямое ДПФ??? Что требует меньше процессорного времени и при каких условиях?
Есть универсальные критерии применяемости для этих алгоримтов???

[eugen_pcad_ru]

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

P.S.: Усеченные алгоритмы - совсем другая песня, про нее можно писать много и лучше отдельно

[EvgenyV]

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

А не подскажете как как в режиме реального времени вычислять спектр с помощью ДПФ. Я считал что БПФ - это всего лишь частный случай ДПФ. Различие всего лишь в длине обрабатываемой последовательности N. Для FFT N является степенью двойки, а для ДПФ любая. И там и там надо где-то иметь уже накопленные N символов.
Или я чего-то не понимаю?

[fontp]

А не подскажете как как в режиме реального времени вычислять спектр с помощью ДПФ. Я считал что БПФ - это всего лишь частный случай ДПФ. Различие всего лишь в длине обрабатываемой последовательности N. Для FFT N является степенью двойки, а для ДПФ любая. И там и там надо где-то иметь уже накопленные N символов.
Или я чего-то не понимаю?

БПФ и есть быстрая реалиация ДПФ (даже не частный случай). БПФ существует не только для степени двойки. БПФ существует для любого N составленого из большого числа множителей (http://sonder.ru/content/view/480/32/).

Просто в практических приложениях часто все гармоники не нужны. Мы заранее знаем область своего интереса. Для обычного ДПФ эффективность вычислений при этом повышается пропорционально. А для быстрых преобразований (БПФ) усечённые алгоритмы хоть тоже существуют, но выигрыш их по производительности мал и проявляется только при значительном уменьшении числа гармоник: в двое, в четверо,... в 128 раз. Ничего выиграть в БПФ от ненужности вычислять 35% гармоник нельзя

Короче, отвечая на первоначальный вопрос можно сказать так: ДПФ используется только когда

- или число гармоник мало, поскольку мало число входных отсчётов N
- или число гармоник мало, поскольку нас интересуют не все гармоники N, а только некоторые

Во всех остальных случаях БПФ предпочтителен. Поскольку в ошибках округления он уступает не очень, а для случая простого N тоже есть способы перейти к составному. В конце концов просто добавить несколько нулевых отсчётов...

[Oldring]

БПФ существует для любого N составленого из большого числа множителей (http://sonder.ru/content/view/480/32/).

Под термином "БПФ" традиционно понимают алгоритм Кули-Тьюки. Он существует только для степеней двойки. Если же рассматривать быстрые алгоритмы дискретного преобразования Фурье вообще, то возможность разложения N на множители не обязательна. Например, алгоритм Рейдера работает только для простых N, сводя преобразования Фурье к циклической свертке длиной N-1 и некоторому количеству сложений.

[fontp]

Под термином "БПФ" традиционно понимают алгоритм Кули-Тьюки. Он существует только для степеней двойки.

Странная традиция. Алгоритмы Гуда_Томаса, Винограда, Рейдера значит уже не БПФ, ага ))
Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток
Да и по прошлой ссылке ясно написано: "алгоритм БПФ для составных множителей". Вы конечно туда не ходили...

"Традицию" можно оправдать только в качестве прикладной унификации

[Oldring]

Странная традиция. Алгоритмы Гуда_Томаса, Винограда, Рейдера значит уже не БПФ, ага ))

Про эти алгоритмы знают уже далеко не все. Поэтому когда написано "БПФ", можно подразумевать, что автор имел в виду Кули-Тьюки.

[fontp]

Про эти алгоритмы знают уже далеко не все. Поэтому когда написано "БПФ", можно подразумевать, что автор имел в виду Кули-Тьюки.

Это так.
Но это не важно.
Большое к-во множителей в N (в том числе кратных двоек) даёт возможность построить БПФ.
Хотя действительно, даже это не обязательно. Главное чтобы матрица преобразования факторизовалась в произведение прореженых матриц

Походу тут и реализация попалась БПФ для произвольного N.
Enjoy! Только не забывайте, что не все N одинаково полезны ))
http://alglib.sources.ru/fasttransforms/fft.php