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

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

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

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

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

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

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

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



Да, почему это "не сможет"? Любой алгоритм сможет. Используется только свойство комплексной сопряженности, а не факторизация. Делается половина последовательности S1+i*S2, а другая S1-i*S2. Всего 2*N элементов, но не обязательно это К-Т.
Так же обстоит дело с возможностью посчитать одну реальную последовательность длины 2*N, как комплексную последовательность длины N. N (как и алгоритм) может быть любым, это длина исходной последовательности должна быть четной

В любом случае, можно сказать, что для четных значений N вычисления можно сделать любым алгоритмом

Кули-Тьюки по основанию 2 пойдет почти во всех случаях, как самый простой и незаморочливый алгоритм.
Изобретательство алгоритмов БПФ в свое время двигалось по бедности и прекратилось с появлением умножителей с аккумулятором, а тем более - с плавающей запятой. Поэтому навскидку, алгоритмы, кроме основания 2,
простому инженеру не нужны.
Игра с производительностью - неблагодарное дело - и чаще всего выигрыш съедается другими накладными расходами типа системные дела. смена контекста и т.п.
Несколько лучше - БПФ по основанию 4, но чаще всего в аппаратных конвейерах, в ПЛИСах, например.
Кули-Тьюки по составному основанию - когда очень нужно конкретное число точек - те же 1000.
Так например, для универсальности сделано в Матлабе.
Алгоритмы Винограда - это для очень специальных процессоров, например, в ASIC, т.к. имеют минимум умножений
и очень заморочливые в плане организации вычислений.
Причем так как сложения,в отличие от умножений, в них делаются безошибочно, то и алгоритм в целом
получается точнее.
Алгоритмы по высоким основаниям (на блоках Винограда, например) имеют-таки большую точность, чем другие,
т.к. количество стадий усечения результатов (которые собственно и вносят ошибки) в несколько раз меньше.
Другое преимущество - если это конвейер, то ему нужно меньше памяти. которая ставится между ступенями.

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

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


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

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

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

Господа, а как вы отнесётесь к такому, недавно прочитанному мной тезису:
"... в пользу алгоритма Кули-Тьюки можно отнести, то, что этот алгоритм позволяет, при несложной модификации, провести ДПФ сразу двух сигналов за один "проход" алгоритма"...

... интересно очень...

Косноязычный тезис, автор которого говорит о двух реальных последовательностях, но в неявном виде
Это уже обсуждалось выше

Так это реально или нет? На практике применяется?

Что? Вычисление дпф 2-х вещественных последовательностей за 1 комплексное бпф?
Да в полный рост.

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

Сообщение отредактировал TigerSHARC - Dec 21 2009, 16:33

Это прямое следствие свойства дпф от вещественной последовательности. А кули там или какие-нить другие тьюки - не имеет значения.
ДПФ вещественной последовательности имеет четную вещественную часть и не четную мнимую.
Ну и плюс свойство линейности ДПФ.

x и y - 2 вещественные последовательности


M=length(x) %или y

xy = complex(x,y);
S = fft(xy);
Xr = [real(S(1)) 0.5.*(real(S(2:M/2)) + real(S(M:-1:M/2+2))) real(S(M/2+1))];
Xi = [0 0.5.*(imag(S(2:M/2)) - imag(S(M:-1:M/2+2))) 0];

Yr = [imag(S(1)) 0.5.*(imag(S(2:M/2)) + imag(S(M:-1:M/2+2))) imag(S(M/2+1))];
Yi = [0 -0.5.*(real(S(2:M/2)) - real(S(M:-1:M/2+2))) 0];

Xr+j*Xi - дпф последовательности x
Yr+j*Yi - дпф последовательности y

Что-то вроде этого...

спасибо!

Но в моих источниках упоминается, что Виноград, к примеру, такого уже не умеет...
так ли это?

Сообщение отредактировал TigerSHARC - Dec 21 2009, 19:31

Если Виноград произвести для последовательности длиной в степень двойки - какие могут быть отличия?

Между прочим в одной из предыдущих тем Я предложил Вам посмотреть все о чем Вы спрашивали на реальном приборе с реальными сигналами. И по этой теме тоже. Предложение закрыто. Может в мае на серийном приборе.