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 тут далеко не оптимален... Хотя, все зависит от требований к точности.

[PriBoris]

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

Под двумя проходами по 512 я имел ввиду :
первый проход : 512 - состоит из второй половины предыдущего блока и из первой половины нового блока данных
второй проход : 512 - состоит из первой и второй половин нового блока данных
то есть на каждый блок данных длиной 512 я прохожусь 2 раза сверткой с длиной 512, и после каждой свертки получаю 256 фильтрованных значений

Сегодня этот вариант реализовал и проверил в процессоре. Выигрыш по сравнению с прамой реализацией FIR составил 6 раз. На данном этапе меня это устраивает. Если в будущем не будет хватать, то буду делать 768-точечное FFT.
Большое спасибо всем откликнувшимся!