MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

DFT

Asked by Lisa Justin on 22 Feb 2012
Latest activity Edited by Cedric Wannaz on 21 Oct 2013

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

Products

No products are associated with this question.

Answer by Wayne King on 22 Feb 2012

```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

thanks, i will check

Lisa Justin on 22 Feb 2012

yes it is same but i do not think it will be same with real vibration time series. check this http://www.dataq.com/applicat/articles/an11.htm

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().

1 Comment

Lisa Justin on 22 Feb 2012

i want to avoid using any window function, that is the reason i need DFT. How do i represent an interval of 0:N-1 summation in matlab? I am just experimenting with DFT to see what i get. I want to compare the results with windowing(FFT) and without windowing (DFT).

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

1 Comment

Lisa Justin on 22 Feb 2012

N=1024
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.

1 Comment

Lisa Justin on 23 Feb 2012

Thanks!

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.

1 Comment

Lisa Justin on 23 Feb 2012

Thanks guys!