Страница 1 из 1

А если количество точек не равно 2^k

Добавлено: 28 июн 2019, 16:22
SoftCat
Можно ли собрать из нескольких БПФ такое преобразование, которое работало бы с выборкой, размер которой не является степенью двойки? Важен обязательно быстрый алгоритм, а не просто ДПФ.

Re: А если количество точек не равно 2^k

Добавлено: 28 июн 2019, 16:47
kaa
Алгоритм Винограда или в некоторых случаях скользящие алгоритмы (что то вроде Герцеля) иногда подходят.
Вот статья от которой можно начать поиск:
https://www.researchgate.net/profile/Ol ... 5dd4ec.pdf

Re: А если количество точек не равно 2^k

Добавлено: 28 июн 2019, 17:52
Бахурин Сергей
Да можно построить хороший БПФ алгоритм для составной длины. Если длина FFT равна N = M*P то можно сделать такое преобразование путем M преобразований длины P далее умножение на поворотные коэффициенты и потом еще P преобразований длины M.

Написано в книге Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток

Кстати если посмотрите, то именно такой подход реализуется во многих библиотеках FFT (в частности FFTW использует такой подход) Моя библиотека тоже имеет FFT составной алгоритм. Быстродействие немного уступает FFTW но можете посмотреть код (не такой монструозный как FFTW).

Что касается алгоритма Винограда, то он применяется для вычисления как раз составных преобразований длины 3,5,6,7, и т.д. Он непростой для понимания, но описан в статье:

On Computing the Discrete Fourier Transform By S. Winograd
MATHEMATICS OF COMPUTATION, VOLUME 32, NUMBER 141 JANUARY 1978, PAGES 175-19


DSPL как использует алгоритмы Винограда для длины 3,5,7.

Re: А если количество точек не равно 2^k

Добавлено: 29 июн 2019, 01:29
SoftCat
kaa и Бахурин Сергей, спасибо Вам большое за ответы и ссылки!