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

[PriBoris]

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

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

[thermit]

768 = 3*2^8
последняя стадия по основанию 3, остальные - по основанию 2. или 16.
C перестановками, правда будет возня. Может, действительно проще будет взять на 1к точек?

[Xenia]

Да,я так и хочу сделать. Просто на всякий случай спросил, вдруг есть возможность сэкономить.

Если вы достигните своего желания получить FFT на 768-точечном массиве, то у вас получится циклическая свертка. А вам оно надо? В большинстве практических случаев нужна простая свертка, а не циклическая, поскольку образ, находящийся в массиве 768, вряд ли периодический.
Дополнение же нулями до 1024 здесь очень удачно еще и тем, что как раз добавляет к исходному массиву данных нулевой кусок той же самой длины, как и длина функции, с которой станут сворачивать. Такое добавление является как раз минимальным для того, чтобы вместо циклической свертки получить нормальную.
Более того, даже если бы ваш массив был длиной 512, что позволило бы легко преобразовать его в FFT-образ, то и в том случае стоило бы подумать о целесообразности дополнения его нулями до 1024, чтобы избавиться от циклической свертки. А у вас длина массива просто идеальна для получения нормальной свертки, т.к. 768+256=1024.