How make FFT when buffer size is not 2^L

Question

I still try to understand FFT :) I know I can do something like that:

float bufferSize = 500.0f;
int correction = log2(bufferSize);
bufferSize= pow(2, correction);

But then I get buffer size 256. So it doesn't use all samples in the buffer. But I've heard there are some methods to make FFT with buffer size for example 500. And use all possible samples. Could anyone explain me how to do that? Great thanks in advance.

So I need to develop my question :)

I’ve just read Rabiner, Lawrence R., and Bernard Gold. "Theory and application of digital signal processing." Of course not all but the fragment titled “A Unified Approach to the FFT”.

And there is about dividing N-point sequence to make matrix. I even implemented in C++ exact example from that book with N=60 points of sequence. But I am not sure if I understand the idea (maybe it’s because English is not my first language).

Firstly in the book they say to make matrix 60=5 X 12, and further they say to pay attention that we can divide each 12 points to make matrix 3 X 4. But although it is said, the further calculations are only for 5 X 12. Why not 5 X 3 X 4? Is it only for make explanations easier? Or what?

And more important question is what exactly that matrix division give me? Stanley Pawlukiewicz says about my example (when N=500) to make prime factors 2 2 5 5 5. So as I understand it’s 5 dimensional matrix, 2 X 2 X 5 X 5 X 5? Am I right?

But to make DFTs on that matrix I still need to make 500x500=250000 calculations, so it’s like regular DFT, not any FFT. I could imagine I can make 125 X 4 points FFTs (4 is 2 to the power of 2). But if it’s the idea, why we are not talking about matrix 125 X 4, but instead we are talking about matrix 2 X 2 X 5 X 5 X 5?

In which point here is FFT?

Answer 1

The prime factors of 500 are:

2 2 5 5 5

fftw can do this fast.

If you want to roll your own in:

Rabiner, Lawrence R., and Bernard Gold. "Theory and application of digital signal processing." Englewood Cliffs, NJ, Prentice-Hall, Inc., 1975. 777 p. (1975).

there is a section that shows how to do a 1 dimensional dft in two dimensions.

see my answer

Combine FFT's of shorter length than sample data to get spectrum of all data

pasting the Matlab code from there to here, and taking M=20 N=25 for your problem.

clear all
M=3;
N=32;
x=linspace(0,10,M*N);
X=reshape(x,N,M).'; % read in as rows
Twiddle=zeros(size(X));
for i=1:M
for k=1:N
Twiddle(i,k)=exp(-1j*2*pi*(i-1)(k-1)/(NM));
end
end
X=fft(X) % fft on each column
X=X.*Twiddle;% element by element product
X=fft(X.').' ; %fft on each row
y=reshape(X,N*M,1); % read out as columns
figure(1)
plot(abs(y),'linewidth',2)
title('Composite DFT')
figure(2)
plot(abs(fft(x)),'linewidth',2)
title('Direct DFT')
figure(3)
plot(x,'linewidth',2)
title('time series')

FFTW is probably faster.

Answer 2

The FFT is just a fast version of the Discrete Fourier Transform (DFT). The FFT can work on other sizes than powers of two, depending on the implementation. A brute force DFT can always be done if you are coding it yourself.

You can find some very inefficient, but explicit, DFT bin value calculation routines in C in the sample code of my blog article DFT Bin Value Formulas for Pure Real Tones.

Hope this helps,

Ced