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

[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 раз.

[AndrewN]

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

За счёт какого-такого вычислительного свойства? Все, абсолютно все, разновидности цифровых алгоритмов вычисления ДПФ привносят совершенно одинаковую погрешность в результат. И было бы странно, если бы погрешности менялись от алгоритма к алгоритму. ДПФ - это умножение (N,N) матрицы на вектор длиной N, что соответственно требует N скалярных произведений. Скалярное произведение длины N имеет совершенно определённую оценку погрешности.

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

А "в случае жестокого ограничения разрядности" точности, как таковой, вообще не остаётся...

И почему только К-Т "потянет вычисление сразу двух реальных выборок"? Любой другой (быстрый/небыстрый) алгоритм ДПФ сделает тоже самое.

Писать ГОСТЫ на ДПФ - отличный способ делать деньги из ничего. Интересно, кто этим занимается?..

[SPACUM]

<А "в случае жестокого ограничения разрядности" точности, как таковой, вообще не остаётся...>

Не настаиваю, у всех по-разному. Но какую-то разрядность применить придется (наши процессоры не резиновые). Все-таки думаю что-нибудь останется и для 16 бит в современных DSP и для 24 бит при вычислениях с плавающей точкой и для 32 бит (около -160 dB). И 8 бит примнеяется для Гигагерцовых АЦП + программируемая логика. Методы не при чем, разрядность вычислений рождает погрешность. А Винограда Я очень даже люблю и всем советую, но только для выборок кратных 10 (для них и погрешность будет около -148 dB).


<Писать ГОСТЫ на ДПФ - отличный способ делать деньги из ничего. Интересно, кто этим занимается?..>

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

С остальными замечаниями согласен.