Как эффективно рассчитать только низкие коэффициенты FFT с нулевым дополнением

14

У меня есть алгоритм, который обнуляет последовательность до 4N, выполняет БПФ и использует только точки N самой низкой частоты из сгенерированного 4N.

Похоже, это много потраченной впустую работы, есть идеи, как это можно сделать быстрее?

Марк Боргердинг
источник
@Dilip. Я буду использовать библиотеки FFTW или IMKL. Я мог бы, конечно, использовать свою библиотеку Kissfft, но она начинается с недостатком скорости по сравнению с другими
Марк Боргердинг,
2
Я удалил комментарий, на который вы ответили, так как я хотел сказать, что поочередно, но вместо этого написал по времени. Но посмотрите на диаграмму бабочки здесь. Если вы напишете некоторый код для первых двух этапов для -FFT, чтобы учесть большое количество нулей и пропустить соответствующие умножения, вы можете затем вызвать библиотечную процедуру FFT 4 раза для N -FFT, в которых входные векторы полны". Конечно, вам нужно только N / 4 выходов от каждого вызова подпрограммы. 4N4NN/4
Дилип Сарвате

Ответы:

2

Если у вас есть только несколько лотков, то следующие варианты могут быть очень эффективными для вас:
1. Просто выполняйте DFT на каждой частоте, которая вам нужна.
2. Используйте алгоритм Гёртцела для каждой рассматриваемой частоты.

Иаков
источник
Марк сказал, что ему нужно бункеров из 4 N , поэтому 1) кажется неоправданным вариантом. Алгоритм Гертцеля обладает такими преимуществами, как онлайн-вычисления при получении данных, небольшая память и т. Д., Но для каждого бина требуется 2 N + 4 умножения, в то время как для каждого бина, вычисленного как полиномиальная оценка по правилу Хорнера, требуется только N умножений. Таким образом, 2) также не представляется особенно разумным вариантом. N4N2N+4N
Дилип Сарвате
Вы правы, читая вопрос, я как-то упустил детали. Когда я отвечал, я думал: «Ну и дела, было бы неплохо узнать, сколько ящиков он хочет ...» Думаю, мне следует перечитать вопрос, прежде чем ответить.
Джейкоб
2

Нулевое заполнение до длины 4X, вычисление более длинного БПФ, а затем использование только нижних 1/4 бинов дает результаты, практически идентичные оконной интерполяции Sinc исходной длины БПФ.

Поэтому просто используйте исходную длину FFT и интерполируйте, используя 3-фазное ядро ​​интерполяции Sinc с подходящей шириной окна.

hotpaw2
источник
0

Заполнение нулями во временной области дает вам более высокочастотное решение, но не дает новой информации, поэтому оно обеспечивает по существу интерполяцию в частотной области. В зависимости от характера ваших сигналов и требуемой точности вы можете получить дополнительные частотные точки с регулярным БПФ из N точек и выполнить подходящую интерполяцию (линейная, сплайн, pchip, sinc и т. Д.).

Hilmar
источник
x(z)=i=0N1xizi be a polynomial (possibly with complex coefficients xi) of degree N1. We evaluate it at the N points αn,0nN1 where α=exp(j2π/N) is a N-th root of unity to get N numbers Xn=x(αn). These are values of x(z) at N equally spaced points on the unit circle. What we really want is the values of x(z) at βn,0nN1 where β=exp(j2π/4N), which are N points on the first quadrant of the unit circle. I don't see how linear, spline etc interpolation is going to work. Please explain.
Dilip Sarwate
Sorry, that penultimate sentence in my previous comment should have said fourth quadrant of the unit circle. Since β4=α, every fourth desired value x(β4k) has already been computed by the FFT: x(β4k)=x(αk).
Dilip Sarwate
I suspect it would be difficult to do a decent interpolation faster than doing the larger FFT.
Mark Borgerding
Let's say you have a 128 point FFT and 12800Hz sample rate. A 128 point FFTs gives values at 0Hz, 100Hz, 200 Hz, 300Hz, etc. What the zero padding does is to increase the frequency resolution to 0 Hz, 25Hz,50 Hz, 100Hz etc. This can be viewed as an interpolation problem. To me mathematically precised you need to do circular sinc intperpolation of 128th order. That certainly isn't worth the bother but depending on application and precision required a much lower order interpolation would be good enough
Hilmar