Asked by Lisa Justin
on 22 Feb 2012

How do i calculate DFT in matlab? I do not want FFT.

*No products are associated with this question.*

Answer by Wayne King
on 22 Feb 2012

Accepted answer

Hi Lisa, you had a couple problems with your code:

N= 4; x=1:4; for k=0:3 for n = 0:3; y(n+1) = x(n+1).*exp(-(1j*2*pi*k*n)/N); end xdft(k+1)= sum(y); end

compare to

fft(x)

Lisa Justin
on 22 Feb 2012

Answer by Wayne King
on 22 Feb 2012

FFT() is just an efficient algorithm (actually a family of algorithms) for computing the DFT. The DFT is the mathmatical concept, the FFT is just an algorithm. You can form a matrix to compute the DFT by brute force, but the result will be identical to the output of fft().

Lisa Justin
on 22 Feb 2012

Answer by Wayne King
on 22 Feb 2012

The DFT can be written as a matrix multiplication of a Nx1 vector, your signal, with a NxN matrix -- the DFT matrix. But that will involve N^2 multiplications and N additions. You can see that if your signal gets even reasonably large that is going to be a huge computational effort. The FFT() exploits symmetries in the DFT to reduce the number of computations greatly.

For example, here is the brute force way for N=4

x = (1:4)'; % the signal W = -1j*2*pi/4; W = repmat(W,4,4); k = (0:3)'; k = repmat(k,1,4); n = 0:3; n = repmat(n,4,1); W = exp(W.*k.*n); % W is the DFT matrix, now to get the DFT xdft1 = W*x

% but that is exactly the same as xdft2 = fft(x)

Lisa Justin
on 22 Feb 2012

k = (1:N/2-1);

x=1:1024

for n=0:1024

xl(n+1) = (x.*exp(-i.*2.*pi.*(k./N).*n));

end

xs=sum(xl)

please can you make correction on the loop, it is easier for me to understand. i do not understand repmat on your code. thanks

Answer by Wayne King
on 22 Feb 2012

With all due respect to that author, I think she is overstating her point. The DFT takes a N-point periodic vector (the N-point periodicity is implicit in the DFT) and projects it onto N discrete-time complex exponentials with period N. Those complex exponentials are a basis for vectors (a vector space) with period N.

Now, in reality, the DFT is most often used for sampled data, data sampled from a continuous-time process, which may or may not be periodic, and even if it is periodic, most likely does not have period N.

The problems that motivate using a window with the DFT, come from this "translation". You're taking a process which is continous, may or may not be periodic, and may not have an abrupt on and off transition, and you are creating a N-point vector out of it, which has those qualities.

So I think it is wholly artificial to draw a line between the DFT and FFT.

I think you still have to window in many cases whether you compute the DFT by brute force or use an FFT implementation.

Answer by Elige Grant
on 22 Feb 2012

Here is another (inefficient) way of saying the same thing as Wayne by way of example:

Fs = 100; % samples per second dt = 1/Fs; N = 128; % Number of samples time = (0:1:(N-1))*dt; timedata = sin(2*pi*time);

figure; plot(time,timedata);

df = 1/(N*dt); % frequency increment Nyq = 1/(dt*2); % Nyquist Frequency freq = -Nyq:df:Nyq-df; freqdata = zeros(size(timedata)); for i = 1 : N for j = 1 : N freqdata(i) = freqdata(i) + timedata(j)*exp(-1i*2*pi*freq(i)*time(j)); end end

figure; plot(freq,real(freqdata),freq,imag(freqdata));

And both (actually all 3) implementations should give the same results as FFT. I can't see any reason why they wouldn't work with real data either.

Opportunities for recent engineering grads.

## 0 Comments