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

Неужели так критично по скорости, что нельзя добавить один отсчет и использовать известные алгоритмы?

не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.

У Блейхута не смотрели? Там есть целая глава по коротким сверткам.

Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.

Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.


Спасибо. Интересная книжка. Блейхута знал по теории кодирования. Алгоритм Виноградова просматриваю, возможно он поможет. Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

Пока лишь в голове держу вариант БПФ с разными основаниями. Например 255 хорошо разбивается на radix2,radix5 и radix17. 5 куда не шло, но 17 существенно увеличит время рассчета при таком кол-ве точек.

В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.

Спасибо. Догадывался. Посмотрю.

Но будьте осторожны, на самом деле применение данных алгоритмов совсем не означает,
что Вы получите ожидаемый результат. в чистом виде применение данных алгоритмов
имеет выигрыш с точки зрения количества используемых операций сложения/умножения,
но в них не учитываются "накладные" расходы для хранения промежуточных результатов,
переиндексация и др., которые тоже потребляют машинное время и причем немалое. в свое
время тоже пытался реализовать быструю линейную свертку для фильтрации, все получилось,
но результаты оказались плачевными . "быстрый" фильтр по скорости оказался на порядок
хуже, нежели классическая реализация. так что хорошо еще раз все взвесьте.

Это само собой. Цель этой темы выбрать оптимальный алгоритм. Пока я склоняюсь к БПФ, но предположил, что возможно есть что-то более оптимальное.

Чудеса, да и только... И чего это подойдет для линейной, что не подойдет для циклической?



z=
1.0e+002 *

-0.050000000000000
-0.160000000000000
0.570000000000000
-0.350000000000000
-1.080000000000000
1.610000000000000
-0.460000000000000
0.070000000000000
0.210000000000000
-1.400000000000000
0.660000000000000
1.260000000000000
-0.830000000000000
-0.530000000000000
0.400000000000000

zz=
1.0e+002 *

-0.050000000000000
-0.160000000000000
0.570000000000000
-0.350000000000000
-1.080000000000000
1.610000000000000
-0.460000000000000
0.070000000000000
0.210000000000000
-1.400000000000000
0.660000000000000
1.260000000000000
-0.830000000000000
-0.530000000000000
0.400000000000000
-0.000000000000000 %Этот 0 выкидывается, потому как за пределами результата

Какие проблемы?

ps
Впрочем, если охота попреодолевать трудности - флаг в руки...

Когда-то давно читал про это. По моему называется алгоритм винограда.
Но я бы постарался свести к алгоритму бабочкой как наиболее рааспространенному.

Можно тут взглянуть
http://exfile.ru/396643

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

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

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

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

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

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

ps


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

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