3
$\begingroup$

In my journey about learning what / why / how of DFT, I tried to implement a DFT on MATLAB and then I compared its output with fft output and then I noticed it was different, does DFT produces a different output from fft?

enter image description here

% it creates a simple gray image (4x4)
I = [255, 255, 30, 100 
    255, 50, 90, 20 
    70, 70, 20, 10 
    100, 20, 10, 0];
% it converts it to grayscale
I = mat2gray(I);
% shows it 
imshow(I);

IDFT = [];

% DFT
N1 = 4;
N2 = 4;
e = exp(1);

for w1=1:(N1)
  for w2=1:(N2)
      % X(w1, w2)
      DFT = 0;
        for n1=1:(N1)
            for n2=1:(N2)
                Intensity = I(n1,n2);
                FirstDimension = e ^ (-1i*( (2*pi/N1) * w1 * n1));
                SecondDimension = e ^ (-1i*( (2*pi/N2) * w2 * n2));
                DFT = DFT + (Intensity * FirstDimension * SecondDimension);
            end
        end
       IDFT(w1, w2) = DFT;
  end
end

IDFT
fft(I)
$\endgroup$
  • $\begingroup$ What do you mean with FDFT ? $\endgroup$ – Gilles Oct 30 '16 at 11:22
  • $\begingroup$ Fast Fourier Transform $\endgroup$ – leandro moreira Oct 30 '16 at 11:52
6
$\begingroup$

Yes it does but your DFT implementation is wrong. w1,w2,n1 and n2 should be in the range of $0, \ldots, N-1$. Also you should be comparing against MATLAB's fft2 function.

Here is a correct implementation. I've replace w1,w2 with u,v and n1,n2 with x,y to follow conventions. I've done some algebraic simplification.

I = [255, 255, 30, 100 
    255, 50, 90, 20 
    70, 70, 20, 10 
    100, 20, 10, 0];

% it converts it to grayscale
I = mat2gray(I);

% DFT
N = size(I,1);
IDFT = 1i*zeros(N,N);
for u=0:N-1
  for v=0:N-1
      DFT = 0;
      for x=0:N-1
          for y=0:N-1
              DFT = DFT + I(x+1,y+1)*exp(-1i*2*pi*(u*x+v*y)/N);
          end
      end
      IDFT(u+1, v+1) = DFT;
    end
end

IDFT
fft2(I)

IDFT =
5.3137 + 0.0000i   2.0784 - 1.0392i   1.1961 - 0.0000i   2.0784 + 1.0392i
1.8431 - 1.1176i   0.6471 - 0.6667i  -0.3137 - 0.7255i   0.7255 + 0.0784i
1.0392 - 0.0000i   0.0784 - 0.6471i  -1.6667 - 0.0000i   0.0784 + 0.6471i
1.8431 + 1.1176i   0.7255 - 0.0784i  -0.3137 + 0.7255i   0.6471 + 0.6667i


MATLAB_fft =
5.3137 + 0.0000i   2.0784 - 1.0392i   1.1961 + 0.0000i   2.0784 + 1.0392i
1.8431 - 1.1176i   0.6471 - 0.6667i  -0.3137 - 0.7255i   0.7255 + 0.0784i
1.0392 + 0.0000i   0.0784 - 0.6471i  -1.6667 + 0.0000i   0.0784 + 0.6471i
1.8431 + 1.1176i   0.7255 - 0.0784i  -0.3137 + 0.7255i   0.6471 + 0.6667i 
$\endgroup$
4
$\begingroup$

FFT is a an efficient algorithm to compute the result of DFT (Discrete Fourier Transform) whereas DFT is a discrete time transform.This is in line with the sense of sorting (say default being Bubble Sort) being an algorithm and the quicksort being a particular efficient method to implement sorting, whose output will be the same with that of bubble sort, but will be much more efficient due to a completely different architecture being used.

a 1D FFT will be much faster with $O(N \text{log}N)$ complexity compared to a direct for loop implementation of a 1D DFT which has $O(N^2)$ complexity...

Their output will be exactly the same except for roundoff and approximation errors involved in the arithmetic operations. Any discrepiency is a direct consequence of your coding error.

$\endgroup$
  • 2
    $\begingroup$ Right. In fact I'd go further: both sorting and DFT aren't really defined by any particular algorithm at all, but by mathematical properties that the results should fulfill. (Sorting is defined so each result entry should be less than its successor; Fourier transform is a mapping into the eigenbasis of differential operators on the $L^2$ Hilbert space, and DFT the uniform-discretised approximation.) Only particular algorithms, be it bubble sort, quicksort, naïve-for-loop-over-frequency-integral-kernels or FFT actually tell you how to obtain a result that fulfills those properties. $\endgroup$ – leftaroundabout Oct 30 '16 at 20:08
2
$\begingroup$

The FFT is an efficient DFT algorithm, so in the limit of infinite precision arithmetic, they will give the same output, albeit the direct DFT implementation will be much slower.

However, the DFT algorithm involves the summation of trigonometric polynomials, which are very numerically unstable, so in general the FFT will have less roundoff error because fewer operations are being undertaken and you can take advantage of symmetry to cancel out some of the errors

$\endgroup$
  • 1
    $\begingroup$ if you have an accumulator that has double-width of the two values (the signal and the "twiddle factor") then the naive implementation of the DFT has less roundoff error than the FFT. this is because there is no roundoff until the entire summation is complete. but if the accumulator has the same width as the two values going into the multiply-accumulate operation, then the FFT is better than the naive DFT. $\endgroup$ – robert bristow-johnson Oct 30 '16 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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