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

Ответить
SoftCat
Сообщения: 27
Зарегистрирован: 08 фев 2018, 19:27

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

Сообщение SoftCat » 28 июн 2019, 16:22

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

kaa
Сообщения: 25
Зарегистрирован: 17 мар 2019, 20:03

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

Сообщение kaa » 28 июн 2019, 16:47

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

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 892
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

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.

SoftCat
Сообщения: 27
Зарегистрирован: 08 фев 2018, 19:27

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

Сообщение SoftCat » 29 июн 2019, 01:29

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

Ответить

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и 1 гость