{"id":317,"date":"2010-03-15T17:59:21","date_gmt":"2010-03-15T17:59:21","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/2010\/03\/15\/the-dft-and-the-dtft\/"},"modified":"2010-03-15T17:59:21","modified_gmt":"2010-03-15T17:59:21","slug":"the-dft-and-the-dtft","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2010\/03\/15\/the-dft-and-the-dtft\/","title":{"rendered":"The DFT and the DTFT"},"content":{"rendered":"
\r\n

It's finally time to start looking at the relationship between the discrete Fourier transform (DFT) and the discrete-time\r\n Fourier transform (DTFT). Let's look at a simple rectangular pulse, for . The DTFT of is:\r\n <\/p>\r\n

<\/p>\r\n

Let's plot for over a couple of periods:\r\n <\/p>

M = 8;\r\nw = linspace(-2*pi, 2*pi, 800);\r\nX_dtft = (sin(w*M\/2) .\/ sin(w\/2)) .* exp(-1j * w * (M-1) \/ 2);\r\nplot(w, abs(X_dtft))\r\ntitle('|X(\\omega)|'<\/span>)<\/pre> 
It turns out that, under certain conditions, the DFT is just equally-spaced samples of the DTFT. Suppose   is the P-point DFT of  . If   is nonzero only over the finite domain  , then   equals   at equally spaced intervals of  :\r\n   <\/p>\r\n   
 <\/p>\r\n   
The MATLAB function fft<\/tt> computes the DFT. Here's the 8-point DFT of our 8-point rectangular pulse:\r\n   <\/p>
x = ones(1, M);\r\nX = fft(x)<\/pre>
\r\nX =\r\n\r\n     8     0     0     0     0     0     0     0\r\n\r\n<\/pre>
One 8 and a bunch of zeros?? That doesn't seem anything like the DTFT plot above. But when you superimpose the output of fft<\/tt> in the right places on the DTFT plot, it all becomes clear.\r\n   <\/p>
P = 8;\r\nw_k = (0:P-1) * (2*pi\/P);\r\nX = fft(x);\r\nplot(w, abs(X_dtft))\r\nhold on<\/span>\r\nplot(w_k, abs(X), 'o'<\/span>)\r\nhold off<\/span><\/pre> 
Now you can see that the seven zeros in the output of fft<\/tt> correspond to the seven places (in each period) where the DTFT equals zero.\r\n   <\/p>\r\n   
You can get more samples of the DTFT simply by increasing P. One way to do that is to zero-pad<\/b>.\r\n   <\/p>
x16 = [x, zeros(1, 8)]<\/pre>
\r\nx16 =\r\n\r\n  Columns 1 through 15\r\n\r\n     1     1     1     1     1     1     1     1     0     0     0     0     0     0     0\r\n\r\n  Column 16\r\n\r\n     0\r\n\r\n<\/pre>
P = 16;\r\nX16 = fft(x16);\r\nw_k = (0:P-1) * (2*pi\/P);\r\nX = fft(x);\r\nplot(w, abs(X_dtft))\r\nhold on<\/span>\r\nplot(w_k, abs(X16), 'o'<\/span>)\r\nhold off<\/span><\/pre> 
Another way to increase P is to use the fft(x,P)<\/tt> syntax of the fft<\/tt> function.  This syntax computes the P-point DFT of x<\/tt> by using zero-padding. Let's try a 50-point DFT.\r\n   <\/p>
P = 50;\r\nXp = fft(x, P);\r\nw_k = (0:P-1) * (2*pi\/P);\r\nX = fft(x);\r\nplot(w, abs(X_dtft))\r\nhold on<\/span>\r\nplot(w_k, abs(Xp), 'o'<\/span>)\r\nhold off<\/span><\/pre> 
If you've ever wondered what that whole zero-padding business was all about with Fourier transforms, now you know.  When you\r\n      tack on a bunch of zeros to a sequence and then compute the DFT, you're just getting more and more samples of the DTFT of\r\n      the original sequence.\r\n   <\/p>\r\n   
I think the next logical place to go in our Fourier exploration is to start considering some of the reasons why many people\r\n      find the output of fft<\/tt> so surprising or puzzling.  Here's a sample:\r\n   <\/p>\r\n   
\r\n      
    \r\n         
  • Why isn't the zero frequency (or \"DC\" frequency) in the center of the output from fft<\/tt>?\r\n         <\/li>\r\n         
  • Why isn't the output of fft<\/tt> real when the input is symmetric?\r\n         <\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   
    Do you have puzzles to add? Let me know by adding your comments.<\/p>