модификации БПФ, выбор Опции

[TigerSHARC]

В литературе фигурируют несколько вариантов исполнения алгоритма БПФ:
Кули - Тьюки, Винограда, Блюштейна...
Есть ли практический смысл в анализе их реализации и конкретном выборе оптимального алгоритма для конкретной задачи.
Читаю у С.Смита, что все варианты БПФ дают приблизительно одинаковый выигрышь в производительности и, как я понял, особо заморачиваться нестоит...
(тем более, если честь что большинство библиотек для DSP написаны для Кули-Тьюки)

[fontp]

В литературе фигурируют несколько вариантов исполнения алгоритма БПФ:
Кули - Тьюки, Винограда, Блюштейна...
Есть ли практический смысл в анализе их реализации и конкретном выборе оптимального алгоритма для конкретной задачи.
Читаю у С.Смита, что все варианты БПФ дают приблизительно одинаковый выигрышь в производительности и, как я понял, особо заморачиваться нестоит...
(тем более, если честь что большинство библиотек для DSP написаны для Кули-Тьюки)

При программной реализации - да, если только не требуется по каким-то причинам конкретное N, а не ближайшее к нему 2**log(N)
При аппаратной реализации алгоритм Винограда может оказаться более выгодным за счет снижения кол-ва умножений, т.е. при нессиметричности затрат на сложение и умножение Кули-Тьюки не оптимален

Вот что говорится о конкретной реализации для "произвольного N"
http://forum.sources.ru/index.php?showtopic=273153&st=0
* максимум быстродействия для степеней двойки; все дальнейшие случаи сравниваются с этим
* для N вида (2^i)*(3^j)*(5^k) - медленнее раза в полтора; впрочем, это отличие скорее всего будет уменьшено при помощи оптимизации
* для N с простыми множителями, большими пятерки, но значительно меньшими N, раза в три-четыре медленнее, но всё равно N*log(N); это уже не поддается оптимизации
* если само N - простое, то раз в шесть медленнее, но всё равно N*log(N); это тоже не поддается оптимизации

Алгоритм Томаса-Гуда для N составленого из взаимно простых множителей 2.3.5.7... не уступит Кули-Тьюки по быстродействию и структурно более прост. Но это неудобно, составлять N только из простых множителей

[SPACUM]

При аппаратной реализации алгоритм Винограда может оказаться более выгодным за счет снижения кол-ва умножений, т.е. при нессиметричности затрат на сложение и умножение Кули-Тьюки не оптимален

Только для програмной реализации плавающей точки и ненамного, а для фиксированной - медленнее. Аппаратное умножение почти везде очень быстрое. Я всегда рекомендую 1000 - 2000 - 5000 - 10000 точек. Выигрыш по скорости менее, чем в 2 раза, несравним с удобством читать временные и частотные шкалы в круглых и приятных для глаза единицах. Несколько раз встречал явный отказ по причине советских ГОСТов, в которых указана степень двойки. А по поводу российских стандартов только статьи в газетах. Может кто-нибудь знает какой-нибудь РОСТ со свободной длиной выборки для БПФ? Еще неназван самый быстрый алгоритм - для реальных выборок. Впрочем Кули - Тьюки запросто потянет вычисление сразу двух реальных выборок сразу. И, наконец, в случае жестокого ограничения разрядности Кули - Тьюки и реальный дают существенное преимущество по точности по сравнению с Виноградом. У Меня в 5 раз.