Question about the implementation of the FFT function

There is an ambiguity for me in the FFT function implementation. I would like to know why there are two kinds of fft() fills: fft(signal) and fft(signal,L), where L = 2^nextpow2(length(s)). As I found, fft in MATLAB is based on radix-2 algorithm and that's why we should to cut or zero-pad the signal to obtain it's proper length. There also stands, that the fft with the length of 2^N is more efficient and faster than with the other length.

Thus, why MATLAB allows us to define fft(s) (with its original length)? Why it doesn't compute automatically the vector with zero-padding and it doesn't provide us one implementation consistent with theoretical concepts?

I've prepared a short example:

 fs=1000;                                % Sampling frequency
t=0:1/fs:1-1/fs-12/fs;                  % Time vector, N = 988
s=0.5*sin(2*pi*4*t)+1.2*sin(2*pi*13*t); % Signal vector
N=length(s);                            
L=2^nextpow2(N);                        % L=1024
tic
S1=fft(s,L);                            % Signal with zero-padding
toc
tic
S2=fft(s);                              % "Pure" signal without zero-padding
toc                                                            
Sm1=abs(S1)/fs;                         % Magnitude 1 normalization
Sm2=abs(S2)/fs;                         % Magnitude 2 normalization
f1 = (0:L/2-1)*(fs/L);
f2 = (0:N/2-1)*(fs/N);
% plotting the figures
figure(1)
subplot 211
plot(f1,Sm1(1:length(f1)))
title('Magnitude response, length 1024'); 
subplot 212
title('Magnitude response, length 988')
plot(f2,Sm2(1:length(f2)))

I defined here two fft implementations (one with the length of 988 samples, the second with L = 1024 (2^10). I also used tic toc to find the elapsed time, this time changes during the different simulations, but there is almost always the same situation, in which the elapsed time of the computation with the zero-padded fft is longer than without zero-padding.

In addition, when I look at the results of the magnitude response I see that fft with zero-padding fft(s,L) gives more "leaked" results, while the results of fft(s) seems to be more accurate. Ending my long and maybe slightly naive question, I wonder why do we have two implementations. I hope someone had similar considerations and can share his knowledge :) Best regards

Answer 1

[David Goodmanson]

Hi MaryM,

Where did you get the information that Matlab you should zero-pad to get the "proper" length? And that fft with 2^n is more efficient and faster? This is not a rhetorical question. If you could post a reference here where people are recommending this I would be interested in seeing it.

Maybe I am not the ideal person to answer this question because I believe that nowadays the 2^n business is a myth. It's true that when the algorithm was introduced, it was radix 2. But that was 53 years ago. I mean, Lyndon Johnson was president. There has been a lot of progress in the last half century.

I agree that you don't want to do an fft when the number of points (n) is a large prime number, but you don't have to look any further than the wikipedia entry for fft to see that there are plenty efficient algorithms when n is the product of powers of small prime factors.

As you are finding out for yourself, padding out to 2^n points has issues. If there are oscillations that fit perfectly into an existing array, then padding with zeros messes up the periodicity and introduces extraneous peaks in the frequency domain. For example, for

x = 0:999;  y = cos(2*pi*x/50);  % 1000 points

then fft(y) gives two sharp peaks in the frequency domain as it should, and fft(y,1024) gives a mess.

Well, there are many situations where zeropadding has only a small effect, so it would be worth it to go to 2^n for the speed advantage, right? Here is an example:

n1 = 1000;  n2 = 1024;
r1 = rand(1,n1);  r2 = rand(1,n2);
N =1e6;

% 1000 points
tic; for k = 1:N; y = fft(r1); end; toc
% Elapsed time is 9.487246 seconds.

% zerofill to 1024
tic; for k = 1:N; y = fft(r1,n2); end; toc
% Elapsed time is 10.844286 seconds.

% straight 1024
tic; for k = 1:N; y = fft(r2); end;  toc
% Elapsed time is 9.113331 seconds.

Comparing the first two cases, speeding up with 1024 points and zerofill is actually slower.

The zerofill overhead time certainly counts, it's a fair comparison with the first case, but the third case shows that a straight fft on 1024 points is slightly faster than for 1000 points. So let's go to a really large number of points, where the fft on 2^n points can really show its stuff:

In this situation, 2^23 is about 84% as large as 1e7. So if we try an fft on these two, 2^23 should be much faster.

n1 = 2^23; n2 = 1e7;
r1 = rand(1,n1);  r2 = rand(1,n2);
N =20;

% 2^23
tic; for k = 1:N; y = fft(r1); end; toc    
% Elapsed time is 10.374116 seconds.

% 10^7
tic; for k = 1:N; y = fft(r2); end; toc
% Elapsed time is 6.346971 seconds.

2^n is not faster, it's slower. By a lot.**

So I would say that unless your sample length is 2^n already or is a large prime number, stay away from 2^n.

** I believe this may have something to do with machine-dependent microprocessor caching, but I think my PC is pretty typical.