Полная версия этой страницы: Алгоритм ускоренного преобразования фурье на 2**N - 1 точек
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Подскажите, существует ли ускоренный алгоритм преобразования фурье на 2**N - 1 точек (например 255 или 511 точек) ?
Неужели так критично по скорости, что нельзя добавить один отсчет и использовать известные алгоритмы?
QUOTE (Serg76 @ Jan 15 2013, 12:40) 
Неужели так критично по скорости, что нельзя добавить один отсчет и использовать известные алгоритмы?
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.
Цитата(Костян @ Jan 15 2013, 17:51)
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.
У Блейхута не смотрели? Там есть целая глава по коротким сверткам.
Цитата
Костян:
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.
Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.
QUOTE (thermit @ Jan 15 2013, 13:12)
Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.
Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.
QUOTE
У Блейхута не смотрели? Там есть целая глава по коротким сверткам.
Спасибо. Интересная книжка. Блейхута знал по теории кодирования. Алгоритм Виноградова просматриваю, возможно он поможет. Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.
Пока лишь в голове держу вариант БПФ с разными основаниями. Например 255 хорошо разбивается на radix2,radix5 и radix17. 5 куда не шло, но 17 существенно увеличит время рассчета при таком кол-ве точек.
Цитата(Костян @ Jan 15 2013, 18:28)
Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.
В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.
QUOTE (Serg76 @ Jan 15 2013, 13:52)
В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.
Спасибо. Догадывался. Посмотрю.
Цитата(Костян @ Jan 15 2013, 17:54)
Спасибо. Догадывался. Посмотрю.
Но будьте осторожны, на самом деле применение данных алгоритмов совсем не означает,
что Вы получите ожидаемый результат. в чистом виде применение данных алгоритмов
имеет выигрыш с точки зрения количества используемых операций сложения/умножения,
но в них не учитываются "накладные" расходы для хранения промежуточных результатов,
переиндексация и др., которые тоже потребляют машинное время и причем немалое. в свое
время тоже пытался реализовать быструю линейную свертку для фильтрации, все получилось,
но результаты оказались плачевными
. "быстрый" фильтр по скорости оказался на порядокхуже, нежели классическая реализация. так что хорошо еще раз все взвесьте.
QUOTE (Serg76 @ Jan 15 2013, 14:06)
на самом деле применение данных алгоритмов совсем не означает,
...
но в них не учитываются "накладные" расходы для хранения промежуточных результатов,
переиндексация
...
но в них не учитываются "накладные" расходы для хранения промежуточных результатов,
переиндексация
Это само собой. Цель этой темы выбрать оптимальный алгоритм. Пока я склоняюсь к БПФ, но предположил, что возможно есть что-то более оптимальное.
Цитата
Костян:
Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.
Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.
Чудеса, да и только... И чего это подойдет для линейной, что не подойдет для циклической?
Код
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)]));
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
Впрочем, если охота попреодолевать трудности - флаг в руки...
Когда-то давно читал про это. По моему называется алгоритм винограда.
Но я бы постарался свести к алгоритму бабочкой как наиболее рааспространенному.
Но я бы постарался свести к алгоритму бабочкой как наиболее рааспространенному.
Можно тут взглянуть
http://exfile.ru/396643
http://exfile.ru/396643
QUOTE (thermit @ Jan 15 2013, 14:39)
Чудеса, да и только... И чего это подойдет для линейной, что не подойдет для циклической?
CODE
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)]));
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. Сравните результат.
Цитата
Костян:
Возмите длину сигнала x и y равной 15. И рассчитайте fft-15.
Дополните нулями x и y до длины 16 и рассчитайте fft-16. Сравните результат.
Возмите длину сигнала 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);
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, 12:37)
2-й вариант - циклическая свертка через апериодическую
Здесь нужно вычисление бпф на 512 точек и еще суммирование результата.
Код
xx=[x zeros(1,257)];
yy=[y zeros(1,257)];
c=ifft(fft(xx).*fft(yy));
c=c(1:255)+c(256:510);
yy=[y zeros(1,257)];
c=ifft(fft(xx).*fft(yy));
c=c(1:255)+c(256:510);
Здесь нужно вычисление бпф на 512 точек и еще суммирование результата.
Можно даже без суммирования.
Код
xx=[x x zeros(1,2)];
yy=[y zeros(1,257)];
c=ifft(fft(xx).*fft(yy));
c=c(1+255: 255+255);
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.