Алгоритм ускоренного преобразования фурье на 2**N - 1 точек Опции

[Костян]

Подскажите, существует ли ускоренный алгоритм преобразования фурье на 2**N - 1 точек (например 255 или 511 точек) ?

[thermit]

Костян:
не в скорости дело, нужна циклическая свертка на такое кол-во отчетов.

Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.

[Костян]

Сделайте на 512. Если результат свертки имеет длину 511, последний отсчет выкидывается, ибо будет равен 0.

Так не получиться. Для линейной свертки бы подошло, а для циклической - нет.

У Блейхута не смотрели? Там есть целая глава по коротким сверткам.

Спасибо. Интересная книжка. Блейхута знал по теории кодирования. Алгоритм Виноградова просматриваю, возможно он поможет. Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

Пока лишь в голове держу вариант БПФ с разными основаниями. Например 255 хорошо разбивается на radix2,radix5 и radix17. 5 куда не шло, но 17 существенно увеличит время рассчета при таком кол-ве точек.

[Serg76]

Но в остальной части главы речь идет только про короткие свертки. 255 - уже далеко не короткая.

В том то и дело, что алгоритм для "длинных" сверток строится на основе секций из коротких сверток.