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

[TigerSHARC]

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

[V_G]

Есть мнение, что БПФ становится более эффективным при обработке более 64 отсчетов.
Я ДПФ (вернее, прямые формулы для гармоник) применяю в задаче, где мне нужно рассчитать только амплитуду и фазу первой гармоники.

Сложность БПФ растёт всегда как N*log(N) Cложность усечённого ДПФ как k*N

Я не секу абсолютно всех тонкостей цифровой обработки и не очень знаю, что такое усеченное ДПФ, но речь, очевидно, идет не о сложности программы, а о временнЫх затратах на вычисление, и при классическом ДПФ эти затраты пропорциональны N²

[fontp]

Есть мнение, что БПФ становится более эффективным при обработке более 64 отсчетов.
Я ДПФ (вернее, прямые формулы для гармоник) применяю в задаче, где мне нужно рассчитать только амплитуду и фазу первой гармоники.


Я не секу абсолютно всех тонкостей цифровой обработки и не очень знаю, что такое усеченное ДПФ, но речь, очевидно, идет не о сложности программы, а о временнЫх затратах на вычисление, и при классическом ДПФ эти затраты пропорциональны N²

Усечёнными называют алгоритмы которые вычисляют не все гармоники (все не нужны), а только некоторые.
Очевидно k - это число гармоник которые нужно вычислить. Речь действительно идёт о вычислительных затратах.

Что касается точной границы когда БПФ становится более эффективным... На этот счет бывают разные мнения, это зависит от процессора, его системы комманд. Где то 16-64, но нэ болше... В любом случае более сложная структура алгоритма при малых N обязательно проявит себя и сделает БПФ неэффективным. Сравниваются по числу операций
A*N*log(N) + О(N) и B*k*N + O(N), так эти O(N) и доминируют при малых N и тогда отдают предпочтение более простому алгоритму. Более простой алгоритм - это либо реализация ДПФ суммированием в лоб, либо, как было сказано алгоритм Герцеля. Эти два последних соизмеримы по затратам и опять же преимущество по затратам зависит от процессора. Что лучше : один фильтр второго порядка (но рекурсивный) или два фильтра первого (2 аккумулятора + таблица синусов)? ))