# How make FFT when buffer size is not 2^L

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?

• You could have your correction value round up instead of round down. The zero-pad a 512 length or longer FFT as needed. – hotpaw2 Apr 2 '18 at 11:01
• Yes I know, but I have only 500 samples, so to compute FFT of 512, I need to provide in some way 12 samples more. – pajczur Apr 2 '18 at 11:04
• Look up "zero padding" an FFT. – hotpaw2 Apr 2 '18 at 15:40
• I read about "zeros padding", it's easiest solution and it could be OK in some cases, but it only approximates the results. – pajczur Apr 4 '18 at 8:06

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.

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.

• Thanks, it's interesting. I need to study it. Looks like it will help me. – pajczur Apr 2 '18 at 10:39

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

• Hello, I know all of that, I know how to do that in regular DFT calculations, but I don't know how to do that by FFT. Tomorrow I will read your blog, thanks – pajczur Apr 1 '18 at 23:35
• I mean I know I can do DFT on every buffer size input, it's easy. But how to do that with FFT. Even not sure if I can do that with FFT radix-2, or should I use any other method? – pajczur Apr 1 '18 at 23:38
• @pajczur, I can't give you a link off the top of my head, but a little searching should find it for you. It's already been done in libraries, like fftw. Zero padding is not the same thing. Understanding what the DFT means and understanding how an FFT can compute it more efficiently are two independent things. I would say the former should take precedence over the latter. – Cedron Dawg Apr 1 '18 at 23:46