Быстрая свертка дискретных сигналов, как? Опции

[phantom]

Надо написать алгоритм КИХ фильтрации. Особенность процесса такова, что сигнал выдается фрагментами (начиная от 64 отсчетов).Светрку реализовили через БПФ в нескольких вариантах (overlap&save, overlap&add), но необходимой производительности достичь не удалось (получается в 2-8раз медленнее чем у существующих программ). Причем у программ-аналогов загрузка процессора практически не зависит от длины импульсной характеристики, а у нас - чем больше длина ИХ, тем больше времени требуется на обработку. Думали может БПФ медленное, заменили на Intel FFT которое в 10 раз быстрее общепринятых алгоритмов, но это существенно не помогло. Осталось попаробовать метод блоков переменной длины, но не совсем понятно как это работает. Что можно было бы сделать?

[phantom]

Ой, какие все пафосные, аж страшно...

Ну а вы оптимизацией подобных вычислительных алгоритмов раньше занимались? Опыт имеется?

Странный подход. Если раньше не занимались - то что, и пробовать нельзя?

За вас в конференции никто это не сделает.

Никто и не просил ДЕЛАТЬ что-либо за меня. Хотелось просто услышать мнения по поводу быстрых алгоритмов свертки и особенностей их применения для данной конкретной задачи, особенности которой в следующем:
а) входной сигнал поступает короткими блоками (64...2048)
б) импульсная характеристика имеет очень большую длину по сравнению с длиной блока (100000...500000)
в) обработка идет в реальном времени, т.е. на выход сигнал нужно выдавать блоками такой же длины, что и входные блоки, причем в ответ на каждый входной блок нужно выдать один выходной до того, как придет следующий входной блок (собственно, этот существенный момент не был упомянут ранее, что возможно и вызвало столь странную реакцию отвечающих). И еще один момент: чем короче блоки, тем чаще они поступают на вход и тем меньше времени на обработку.

Хотите теории - Блейхут, "Быстрый алгоритмы цифровой обрабогтки ".

Не поверите - читал. Очень хорошая и полезная книга. Кстати, после Блейхута были и другие люди, тоже занимавшиеся проблемой быстрых сверток...

Понятно что алгоритмы коротких сверток Винограда им скорее всего не потребуются.

Это вы к чему? Алгоритмы Винограда, как я понимаю, эффективнее для ОЧЕНЬ коротких сверток (пример со сверткой векторов длиной 2 и 3 действительно поучителен), и то еще вопрос, нужно ли стремиться уменьшать количество именно умножений за счет сложений, в то время как бОльшую часть времени занимают операции чтения-записи

есть подозрение, что ребята сами не понимают что делают

прочитав Блейхута они поймут, как использовать FFT для их фильтрации наиболее успешно

...ну и что? Вы что, после каждого приращения буфера на 64 сэмпла делаете новое FFT на 4096(допустим) отсчета?

Нет, делаю одно FFT на 64 отсчета. Алгоритм overlap-discard (то, которое "перекрытие с накоплением" у Блейхута) со сложением в частотной области и обратное FFT на те же 64 отсчета. Поэтому то, что

На 130 000 выигрыш FFT очень ощутим.

меня не сильно волнует.

Вот получили свои 130 000 и сделали один раз FFT...

130000 у меня есть до начала процесса обработки, FFT над ним я делаю один раз и далее все время использую при обработке каждого входного блока. Основная вычислительная работа - это умножение и суммирование в частотной области, время вычисления FFT по сравнению с ним - всего ничего...

[Oldring]

Никто и не просил ДЕЛАТЬ что-либо за меня. Хотелось просто услышать мнения по поводу быстрых алгоритмов свертки и особенностей их применения для данной конкретной задачи, особенности которой в следующем:

По крайней мере после ваших разъяснений относительно того, что вы делаете, вопрос стал чуть меньше похожим на "у меня ничего не работает - почему"? Впрочем, разбираться, что именно вы делаете, всё равно лень. Что за быстрое обновление через каждые 64 точки при длине фильтра 130000. Возможно задача просто вами сильно переусложнена, так как если этот фильтр симметричный, как бывает часто, то только групповое время задержки этого фильтра составляет 65000 отсчетов.

Что касается Блейхута: я и писал, что вам скорее всего он может понадобитья только в качестве смазки для мозгов. Прочитали - вот и здорово. Конечно, книжка довольно старая, тем не менее.