No products are associated with this question.
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
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().
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)
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.
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);
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
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.
Play games and win prizes!Learn more