Алгоритм ускоренного преобразования фурье на 2**N - 1 точек Опции

[Костян]

Подскажите, существует ли ускоренный алгоритм преобразования фурье на 2**N - 1 точек (например 255 или 511 точек) ?

[thermit]

Костян:
Возмите длину сигнала x и y равной 15. И рассчитайте fft-15.
Дополните нулями x и y до длины 16 и рассчитайте fft-16. Сравните результат.

Ну и что? Ну разные. Дык, иначе и быть не может.
Речь шла несколько о другом.
Скажем, нужна циклическая свертка 2-х последовательностей x и y длиной 255.
1-й плавающий на поверхности вариант

Код

c=ifft(fft(x).*fft(y));

в этом случае нужно вычислять бпф на 255 точек.

2-й вариант - циклическая свертка через апериодическую

Код

xx=[x zeros(1,257)];
yy=[y zeros(1,257)];
c=ifft(fft(xx).*fft(yy));
c=c(1:255)+c(256:510);

Здесь нужно вычисление бпф на 512 точек и еще суммирование результата.

Вариант 2 будет не медленнее варианта 1. А в случае длин 511 - еще и быстрее.
Все зависит от разложения длины на сомножители.
255=3*5*17, еще куде ни шло.
Но 511=7*73...
Так, что стоит ли копья ломать о дпф неудобных длин?

ps

Алгоритм Виноградова просматриваю, возможно он поможет.

Не поможет. Возможно поможет алгоритм Винограда.

Сообщение отредактировал thermit - Jan 17 2013, 09:01