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

[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 тоже есть способы перейти к составному. В конце концов просто добавить несколько нулевых отсчётов...