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

Если нужны ВСЕ гармоники преобразования практически всегда выгодно использование БПФ
за исключением вырожденых случаев, когда гармоник совсем мало, например 8 ))
Если нужны только отдельные гармоники используют прямое суммирование, ДПФ

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Бывают случаи, что главный период сигнала нельзя разбить точно на 2^n отсчетов,
и тогда частотные бины не ложатся куда надо.
Бывает, интересующие частоты имеют очень большое общее кратное, как в DTMF.
В этих случаях приходится делать прямой ДПФ.

И что же даст? Еще раз для всех. Если вы возьмете сигнал и пропустите его через 2 черных ящика, на одном будет написано БПФ а надругом ДПФ то результат будет одинаковый если разрядность представления сигнала 8 или более бит.

Сообщение отредактировал bahurin - Nov 13 2009, 11:46

Да, это один алгоритм. Различается только реализация.
Так же как и алгоритм Герцеля - всего лишь вычисление отдельной гармоники ДПФ посредством рекурсивного фильтра. Математически это не новые, уникальные сущности, а всё одно и то же

ЗЫ.Не знаю, что хотел сказать анатолий, но упоминание DTMF, намекает на то, что вместо ДПФ он хотел использовать банк фильтров, реализуемых как суммы в ДПФ. Преобразование типа Фурье, но с неортогональными гармониками (на частотах MF). Реализация позволяет частотам съехать с равномерной сетки. Так это уже не ДПФ. В принципе, то же самое можно проделать и с БПФ приближенно: если интересующие нас гармоники не ложатся туда куда надо на бины ДПФ (БПФ), будем добавлять к данным нулей (увеличивать N) пока частоты преобразования не апроксимируют частоты MF с любой наперёд заданной точностью... Для этого не нужно увеличивать размер блока данных, теряя временное разрешение; достаточно увеличивать размерность преобразования
В любом случае всё что считается ДПФ считается и БПФ, поскольку это одно и то же преобразование