Здравствуйте! Я в этих вопросах далеко не специалист и мне требуется помощь. Вопрос у меня следующий - делают ли КИХ фильтры через БПФ что называется в hardware. Я имею ввиду полноценно конвейерный фильтр с прямым ффт, умножителем и обратным ффт. Я так понял что на микроконтроллерах и дсп процессорах - это актуально, а вот так, в хардваре делают? Или юзают tapped-delay line просто?
Заранее спасибо за помощь.
Полная версия этой страницы: hardware FFT-based FIR filter
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
Цитата(Noob @ Jul 17 2013, 17:12) 
Здравствуйте! Я в этих вопросах далеко не специалист и мне требуется помощь. Вопрос у меня следующий - делают ли КИХ фильтры через БПФ что называется в hardware. Я имею ввиду полноценно конвейерный фильтр с прямым ффт, умножителем и обратным ффт. Я так понял что на микроконтроллерах и дсп процессорах - это актуально, а вот так, в хардваре делают? Или юзают tapped-delay line просто?
Заранее спасибо за помощь.
Заранее спасибо за помощь.
посмотрите FPGA технологии и поделки на их основе...
фирмы производители FPGA : xilinx, altera, lattice ...
Да, эта здравая мысль уже посещала мою голову. Покопавшись в мануалах от мегафункции Alter-ы, я не нашел никаког упоминания про FFT-шные КИХ фильтры. Там судя по всему используется что-то иное. В матлабе я тоже нашел fdatool для проектирования КИХ фильтров. Там тоже только обычные фильтры генерируются в HDL. Вы считаете этого достаточно чтобы сделать вывод что фильтры через БПФ в железе не реализуются? Мне просто хотелось бы убедиться что это действительно так. А заодно и услышать компетентное мнение - почему.
Цитата(Noob @ Jul 17 2013, 09:19)
Вы считаете этого достаточно чтобы сделать вывод что фильтры через БПФ в железе не реализуются? Мне просто хотелось бы убедиться что это действительно так. А заодно и услышать компетентное мнение - почему.
Рекомендую для начала почитать теорию FFT, затем теорию расчета линейной свертки через фурье и понять особенности данного вида фильтрации. Затем уже сделать вывод когда его рационально применять и почему.
QUOTE (des00 @ Jul 17 2013, 19:28)
Рекомендую для начала почитать теорию FFT, затем теорию расчета линейной свертки через фурье и понять особенности данного вида фильтрации. Затем уже сделать вывод когда его рационально применять и почему.
..а если в двух словах?
Цитата(Lmx2315 @ Jul 17 2013, 19:58)
..а если в двух словах?
Если в двух словах, то FFT-IFFT фильтрация N отсчетов жрет (KlogN+M)N операций, а линеная свертка F*N (MAC - умножений + сложений). K,M - заависят от реализации, F - длина фильтра. Начиная с некоторого F > (KlogN + M) FFT фильтр становится выгоднее. Вам нужно понять что есть F,K,M в Вашем случае.
Цитата
Если в двух словах, то FFT-IFFT фильтрация N отсчетов жрет (KlogN+M)N операций, а линеная свертка F*N (MAC - умножений + сложений). K,M - заависят от реализации, F - длина фильтра. Начиная с некоторого F > (KlogN + M) FFT фильтр становится выгоднее. Вам нужно понять что есть F,K,M в Вашем случае.
Да, это я понимаю и осознаю. Если делать программными методами - то вопросов тут никаких. Если делать на одном "АЛУ" и с переадресацией памяти - то тоже всё ясно. Операций становится меньше начиная с какого-то порядка фильтра.
Но вопрос мой остается - если делать в "железе" конвейерными методами - разве эта логика с количеством операций работает? Вот например простая схема FIR фильтра
Тут каждый такт будет выдаваться верное значение, схема конвейерная. А вот как я через FFT представляю:
Нажмите для просмотра прикрепленного файла
Тут нужно ждать пока вся последовательность загрузиться в первый БПФ, потом такт на умножение, потом еще столько же на обратный БПФ. Общая Latency большая по сравнению с стандартным методом, с тактовой частотой тоже не видно почему она может стать лучше. В таком разрезе совершенно непонятно зачем юзать ФФТ подход. Или я чего-то не понимаю? Буду рад любым мыслям по этому поводу)
С простым конвейерным фильтром не все так просто - его трудно заставить работать на высокой частоте при большом количестве коэффициентов - проблемы с clock distribution внутри FPGA.
С FFT у Вас все тоже несколько упрощенно - посмотрите про методы overlap-add/overlap-save для реализации непрерывной свертки. Там окна FFT берутся с перекрытием. Но в общем Вы правы- для FFT придется иметь буфер на входе и выходе. В теории длина импульсной харакетристики фильтра не шибко короче длины блока FFT, поэтому проигрыш по задержке относительно невелик.
FFT движки обычно оптимизируются производителями FPGA, поэтому всегда можно найти хороший компромисс между задержкой движка (в минимальном случае это log N) и количеством съеденных движком ресурсов кристалла. В результате может получиться дизайн, способный работать на большей тактовой частоте при той же длине фильтра, хотя с несколько большей latency.
PS Все это абстрактный разговор - все завист от требуемой частоты, количества (и даже значений) коэффициентов и количества доступных ресурсов в FPGA. Например, если тактовая невелика и фильтр короткий, то можно обйтись одним MAC-юнитом, делая свертку последовательно на частоте F*Fin (F -длина фильтра). Приведенный Вами вариант полностью параллелен. Также, всегда есть что-то между этими крайностями.
С FFT у Вас все тоже несколько упрощенно - посмотрите про методы overlap-add/overlap-save для реализации непрерывной свертки. Там окна FFT берутся с перекрытием. Но в общем Вы правы- для FFT придется иметь буфер на входе и выходе. В теории длина импульсной харакетристики фильтра не шибко короче длины блока FFT, поэтому проигрыш по задержке относительно невелик.
FFT движки обычно оптимизируются производителями FPGA, поэтому всегда можно найти хороший компромисс между задержкой движка (в минимальном случае это log N) и количеством съеденных движком ресурсов кристалла. В результате может получиться дизайн, способный работать на большей тактовой частоте при той же длине фильтра, хотя с несколько большей latency.
PS Все это абстрактный разговор - все завист от требуемой частоты, количества (и даже значений) коэффициентов и количества доступных ресурсов в FPGA. Например, если тактовая невелика и фильтр короткий, то можно обйтись одним MAC-юнитом, делая свертку последовательно на частоте F*Fin (F -длина фильтра). Приведенный Вами вариант полностью параллелен. Также, всегда есть что-то между этими крайностями.
Спасибо за ответ. Да, действительно, разговор абстрактный, ибо стоят чисто исследовательские задачи. Но в любом случае хочется грубо структурировать различные подходы по их применимости, чисто для понимания. Из ваших слов я сделал вывод следующий: если нам нужно сделать свертку последовательно - то при большом порядке фильтра действительно эффективно делать через БПФ. Если используется полностью параллельные медоты - эфективность не так очевидна и зависит от внешних факторов (связанных с реализационными аспектами в FPGA, наличием эффективных движков и т п).
Точно, общего рецепта нет. Нужно всегда по задаче смотреть. Всегда есть дилемма площадь-частота. Ну и latency. Часто на высоких частотах на latency можно забить - она не сильно влияет на задержку всей системы (например, делаете модем - так что там latency по сравнению с задержкой декодирования). Иногда задержка будет критична. Также влияет, есть ли на кристалле или под рукой дешевая память.
Вот конкретный аппаратный фильтр на FFT с описанием:
http://opencores.org/project,fft_fir_filter
http://opencores.org/project,fft_fir_filter
Цитата(анатолий @ Jul 20 2013, 22:13)
Вот конкретный аппаратный фильтр на FFT с описанием:
http://opencores.org/project,fft_fir_filter
http://opencores.org/project,fft_fir_filter
Анатолий,посмотрите личку.
Анатолий не отвечает,спрошу у all.
Приглянулся мне метод который применяет Анатолий,написал скрипт для матлаба,а что-то он работает не так.
Может кто глянет опытным глазом.
Приглянулся мне метод который применяет Анатолий,написал скрипт для матлаба,а что-то он работает не так.
Может кто глянет опытным глазом.
Вот казалось бы, известно правильное решение - быстрая свёртка, во всех классических книжках по ЦОС расписанная, но приглядывается почему-то всё время посредственная эвристика.
Цитата(petrov @ Jul 26 2013, 11:24)
Вот казалось бы, известно правильное решение - быстрая свёртка, во всех классических книжках по ЦОС расписанная, но приглядывается почему-то всё время посредственная эвристика.
Так эта штука позволяет неслабо память сэкономить по сравнению с классическим решением.Немаловажный фактор.Если,конечно,нормально заработает.
Есть только 2 способа секционирования апериодической свертки:
Перекрытие с накоплением и перекрытие с суммированием. Все остальное - лженаука.
Перекрытие с накоплением и перекрытие с суммированием. Все остальное - лженаука.
Код
clear all;
N=1024;
h=randn(1,N);
x=randn(1,100*N);
H=fft([h zeros(1,N)]);
%Перекрытие с накоплением
y1=[];
for i=1:N:length(x)-N
X=fft(x(i:i+2*N-1));
Y=H.*X;
z=ifft(Y);
y1=[y1 z(N+1:end)];
end;
%Перекрытие с суммированием
y2=[];
mem=zeros(1,N);
for i=1:N:length(x)-N
X=fft([x(i:i+N-1) zeros(1,N)]);
Y=H.*X;
z=ifft(Y);
y2=[y2 z(1:N)+mem];
mem=z(N+1:end);
end;
%образец
yy=conv(h,x);
yy=yy(N+1:end);
y2=y2(N+1:end);
grid on;
plot(yy);
hold on;
plot(y1,'r');
plot(y2,'g');
N=1024;
h=randn(1,N);
x=randn(1,100*N);
H=fft([h zeros(1,N)]);
%Перекрытие с накоплением
y1=[];
for i=1:N:length(x)-N
X=fft(x(i:i+2*N-1));
Y=H.*X;
z=ifft(Y);
y1=[y1 z(N+1:end)];
end;
%Перекрытие с суммированием
y2=[];
mem=zeros(1,N);
for i=1:N:length(x)-N
X=fft([x(i:i+N-1) zeros(1,N)]);
Y=H.*X;
z=ifft(Y);
y2=[y2 z(1:N)+mem];
mem=z(N+1:end);
end;
%образец
yy=conv(h,x);
yy=yy(N+1:end);
y2=y2(N+1:end);
grid on;
plot(yy);
hold on;
plot(y1,'r');
plot(y2,'g');
Цитата(thermit @ Jul 26 2013, 16:27)
Спасибо!
Да,overlap-add/overlap-save я моделировал,прекрасно работают.
Подвёл тёзка.
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.