[Костян 0]

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

[Serg76 0]

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

[Костян 0]

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

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

[Serg76 0]

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

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

[thermit 1]

Костян:

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

 

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

 

[Костян 0]

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

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

 

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

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

 

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

[Serg76 0]

Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

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

[Костян 0]

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

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

[Serg76 0]

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

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

что Вы получите ожидаемый результат. в чистом виде применение данных алгоритмов

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

но в них не учитываются "накладные" расходы для хранения промежуточных результатов,

переиндексация и др., которые тоже потребляют машинное время и причем немалое. в свое

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

но результаты оказались плачевными :(. "быстрый" фильтр по скорости оказался на порядок

хуже, нежели классическая реализация. так что хорошо еще раз все взвесьте.

[Костян 0]

на самом деле применение данных алгоритмов совсем не означает,

...

но в них не учитываются "накладные" расходы для хранения промежуточных результатов,

переиндексация

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

 

[thermit 1]

Костян:

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

 

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

 

  x=[-1 -5 4 9 -8];% длина 5
  y=[5 -9 8 4 -1 4 -6 -2 9 1 -5]; %длина 11
%Результат свертки x и y имеет длину 15
%Через FFT-15
  z=ifft(fft([x zeros(1,10)]).*fft([y zeros(1,4)]));
%Через FFT-16
zz=ifft(fft([x zeros(1,11)]).*fft([y zeros(1,5)]));

 

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

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

 

 

[eugen_pcad_ru 0]

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

Но я бы постарался свести к алгоритму бабочкой как наиболее рааспространенному.

[Гость TSerg]

Можно тут взглянуть

http://exfile.ru/396643

[Костян 0]

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

 

  x=[-1 -5 4 9 -8];% длина 5
  y=[5 -9 8 4 -1 4 -6 -2 9 1 -5]; %длина 11
%Результат свертки x и y имеет длину 15
%Через FFT-15
  z=ifft(fft([x zeros(1,10)]).*fft([y zeros(1,4)]));
%Через FFT-16
zz=ifft(fft([x zeros(1,11)]).*fft([y zeros(1,5)]));

Возмите длину сигнала x и y равной 15. И рассчитайте fft-15.

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

 

[thermit 1]

Костян:

Возмите длину сигнала 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

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

 

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

Изменено 17 января, 2013 пользователем thermit