А если количество точек не равно 2^k
А если количество точек не равно 2^k
Можно ли собрать из нескольких БПФ такое преобразование, которое работало бы с выборкой, размер которой не является степенью двойки? Важен обязательно быстрый алгоритм, а не просто ДПФ.
Re: А если количество точек не равно 2^k
Алгоритм Винограда или в некоторых случаях скользящие алгоритмы (что то вроде Герцеля) иногда подходят.
Вот статья от которой можно начать поиск:
https://www.researchgate.net/profile/Ol ... 5dd4ec.pdf
Вот статья от которой можно начать поиск:
https://www.researchgate.net/profile/Ol ... 5dd4ec.pdf
- Бахурин Сергей
- Администратор
- Сообщения: 1116
- Зарегистрирован: 05 окт 2010, 19:55
- Контактная информация:
Re: А если количество точек не равно 2^k
Да можно построить хороший БПФ алгоритм для составной длины. Если длина 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.
Написано в книге Г. Нуссбаумер. Быстрое преобразование Фурье и алгоритмы вычисления сверток
Кстати если посмотрите, то именно такой подход реализуется во многих библиотеках 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
kaa и Бахурин Сергей, спасибо Вам большое за ответы и ссылки!