fft/ifft для последовательности длиной 768 (=512+256) Опции

[PriBoris]

Какой эффективный алгоритм для длин такого типа (2^n+2^(n-1)) выбрать ?
Вопрос возник при попытке реализации фильтрации с помощью быстрой линейной свёртки. Длина фильтра почти 256 точек, данные поступают в реальном времени блоками по 512.

Сообщение отредактировал PriBoris - Jul 27 2010, 08:49

[thermit]

Никаких 512-и быть тут не может, т к результат свертки 2-х последовательностей длин 512 и 256 будет иметь длину 767. Т е размер дпф должен иметь длину минимум 767. Ближайшая внятная размерность 768. Что касается 1024-х точек - уверен, что дпф на 768 точек будет быстрее. Это справедливо, если нет аппаратной поддержки перестановок. (Например, если есть аппаратная поддержка битреверсной адресации, которая используется в алгоритме к-т по основанию 2, то есть выигрыш в числе операций). Так что не парьтесь, Вы на правильном пути.

ps
Можно манипулировать дпф сигнала используя окна без умножения на дпф фильтра, как пытались посоветовать некоторые товарищи. Но это будет совсем другая история, и размер 512 тут далеко не оптимален... Хотя, все зависит от требований к точности.

[DRUID3]

Никаких 512-и быть тут не может, т к результат свертки 2-х последовательностей длин 512 и 256 будет иметь длину 767. Т е размер дпф должен иметь длину минимум 767.

Согласно самому определению свертки двух конечных рядов во временном представлении - да. Но товарищу нужно наложить фильтр. Просто фильтр наложить!!! И хрен он его наложит на бесконечный ряд согласно этому определению. Классическая длинна блока, классический алгоритм БПФ, делается в течении дня вместе с тестами... Зачем вся эта ерунда!!!??? Разрабатывать БПФ странной длинны... Добавляется Х.з. сколько операций. В крайнем случае фильтр можно немного "предисказить" для улучшения результата. Хотя - мне за это не платят, так что чего это я ...

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

КАроче - школота и дилетанты.