1
$\begingroup$

Assume that I have L points and want to calculate its Fourier transform with N points (N is much larger than L, link N=256, while L=10), I am think if there is way to calculate it with lowest complexity.

At first, I try to calculate it by the definition Fourier transform, according to the definition, the complexity cost should be 2NL.

Then I try to calculate with fast Fourier transform (FFT). As far as I understand, I should make N points input (L points with N-L zeros) to produce N points output. In this case, the complexity should still be the NlogN+N, it is small than 2NL.

Thinking that L is much smaller that N, the result is unaccepted that it takes the same computational cost with N points input. I wonder do you guys have better idea?

$\endgroup$

closed as unclear what you're asking by Stanley Pawlukiewicz, Marcus Müller, MBaz, lennon310, Matt L. Aug 1 '18 at 13:45

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ It’s unclear what you are asking. Do you want to speed up zero padding? $\endgroup$ – Stanley Pawlukiewicz Jul 31 '18 at 12:48
  • $\begingroup$ Yes, I want to know if there is way to speed up zero padding. $\endgroup$ – 吴世娟 Jul 31 '18 at 12:56
  • $\begingroup$ @吴世娟 no. Zero padding is only limited by the speed at which you can set memory to 0. How could you speed that up? Makes no sense. $\endgroup$ – Marcus Müller Jul 31 '18 at 14:04
  • $\begingroup$ I am not sure if I state it clear. I want to reduce the computational complexity . $\endgroup$ – 吴世娟 Jul 31 '18 at 14:09
  • $\begingroup$ e.g. compute efficiently the N-point FFT from the L-point FFT of the non-zero elements $\endgroup$ – 吴世娟 Jul 31 '18 at 14:17
0
$\begingroup$

The classic complexity measures are much less relevant today than they were in the days of fixed point ALU's taking 40 cycles to do a floating point multiply.

The answer to your question is maybe. One can decompose an FFT in terms of smaller FFTs,

based on

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 at

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

and coppying the matlab code from there:

for a 96 point FFT, I formed a 32 X 3 matrix

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')

You need to exploit the zero padding when you form the 2D Matrix. When you do the column FFT operation, simplify by noting the zero elements.

As a simple example, let's say we have 3 data points we want to zero pad for a 16 point DFT. A direct DFT is complexity $16^2$. We need to choose M and N, so that M*N=16. I want all the non zero data in the first row, so M=N=4 , so read in as rows is: $$ X=\left| \begin{array}{cccc} x[0] & x[1] & x[2] & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{array}\right| $$ the next step is to do DFTs on the column, normally $ 4 \times 4^2$ complexity. The last column are zeros, and the DFT of a column is zero, so our complexity is now $ 3\times 4^2$. Im reusing the same memory, $$ \text{after column DFTs} \; \;X=\left| \begin{array}{cccc} x[0] & x[1] & x[2] & 0 \\ x[0] & x[1] & x[2] & 0 \\ x[0] & x[1] & x[2] & 0 \\ x[0] & x[1] & x[2] & 0 \\ \end{array}\right| $$ There was only one term in each column so I didn't really need to do any multiplies in this step and you don't either. The Twiddle matrix is usually calculated offline in any FFT , and forming it is not usually counted in the Complexity calculation. In most DSP treatments, the top of the array is zero based, but in Matlab is one based. so in MATLAB $$ W_{16}^{ik}= \exp(-\jmath 2\pi\frac{(i-1)(k-1)}{16}) $$ but in most DSP books $$ W_{16}^{ik}= \exp(-\jmath 2\pi\frac{(i)(k)}{16}) $$

In this case the product of the Twiddle matrix with $X$ is: $$ \text{Twiddled X} X=\left| \begin{array}{cccc} x[0] & x[1]1 & x[2]1 & 0 \\ x[0] & x[1]W_{16}^1 & x[2]W_{16}^2 & 0\\ x[0] & x[1]W_{16}^2 & x[2] W_{16}^4 & 0\\ x[0]& x[1]W_{16}^3 & x[2]W_{16}^6 & 0\\ \end{array}\right| \; $$ given $$ \text{Twiddle}\; X=\left| \begin{array}{cccc} 1 & 1 & 1 & 1 \\ 1 & W_{16}^1 & W_{16}^2 & W_{16}^3 \\ 1 & W_{16}^2 & W_{16}^4 & W_{16}^6\\ 1 & W_{16}^3 & W_{16}^6 & W_{16}^{9} \\ \end{array}\right| \; $$ at this step 9 Complex products

The rest should be obvious (and is left as an exercise) Use the Matlab code as a template but do the short cuts when you can.

$\endgroup$
  • $\begingroup$ Hello, I simulate the code and it seems that it performs the same as DFT. But I can not understand the how this works. Could you please explain to me and help me to analyze the complexity if I use 10 points to transform into 256 DFT points? $\endgroup$ – 吴世娟 Aug 1 '18 at 14:46
  • $\begingroup$ Look at Rabiner and Gold for understanding. Im not going to reproduce 5 pages of text here. Ill add to my answer. $\endgroup$ – Stanley Pawlukiewicz Aug 1 '18 at 14:58

Not the answer you're looking for? Browse other questions tagged or ask your own question.