{"id":588,"date":"2010-03-15T16:11:27","date_gmt":"2010-03-15T20:11:27","guid":{"rendered":"https:\/\/blogs.mathworks.com\/steve\/?p=588"},"modified":"2019-10-29T13:23:21","modified_gmt":"2019-10-29T17:23:21","slug":"the-dft-and-the-dtft-mathjax","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/steve\/2010\/03\/15\/the-dft-and-the-dtft-mathjax\/","title":{"rendered":"The DFT and the DTFT"},"content":{"rendered":"\r\n<!DOCTYPE html\r\n  PUBLIC \"-\/\/W3C\/\/DTD HTML 4.01 Transitional\/\/EN\">\r\n<style type=\"text\/css\">\r\n\r\nh1 { font-size:18pt; }\r\nh2.titlebg { font-size:13pt; }\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\nh4 { color:#4A4F55; padding:0px; margin:0px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:10pt; font-weight:bold; line-height:140%; border-bottom:1px solid #d6d4d4; display:block; }\r\n   \r\np { padding:0px; margin:0px 0px 20px; }\r\nimg { padding:0px; margin:0px 0px 20px; border:none; }\r\np img, pre img, tt img, li img { margin-bottom:0px; } \r\n\r\nul { padding:0px; margin:0px 0px 20px 23px; list-style:square; }\r\nul li { padding:0px; margin:0px 0px 7px 0px; background:none; }\r\nul li ul { padding:5px 0px 0px; margin:0px 0px 7px 23px; }\r\nul li ol li { list-style:decimal; }\r\nol { padding:0px; margin:0px 0px 20px 0px; list-style:decimal; }\r\nol li { padding:0px; margin:0px 0px 7px 23px; list-style-type:decimal; }\r\nol li ol { padding:5px 0px 0px; margin:0px 0px 7px 0px; }\r\nol li ol li { list-style-type:lower-alpha; }\r\nol li ul { padding-top:7px; }\r\nol li ul li { list-style:square; }\r\n\r\npre, tt, code { font-size:12px; }\r\npre { margin:0px 0px 20px; }\r\npre.error { color:red; }\r\npre.codeinput { padding:10px; border:1px solid #d3d3d3; background:#f7f7f7; }\r\npre.codeoutput { padding:10px 11px; margin:0px 0px 20px; color:#4c4c4c; }\r\n\r\n@media print { pre.codeinput, pre.codeoutput { word-wrap:break-word; width:100%; } }\r\n\r\nspan.keyword { color:#0000FF }\r\nspan.comment { color:#228B22 }\r\nspan.string { color:#A020F0 }\r\nspan.untermstring { color:#B20000 }\r\nspan.syscmd { color:#B28C00 }\r\n\r\n.footer { width:auto; padding:10px 0px; margin:25px 0px 0px; border-top:1px dotted #878787; font-size:0.8em; line-height:140%; font-style:italic; color:#878787; text-align:left; float:none; }\r\n.footer p { margin:0px; }\r\n\r\n  <\/style><div class=\"content\"><p>It's finally time to start looking at the relationship between the discrete Fourier transform (DFT) and the discrete-time Fourier transform (DTFT). Let's look at a simple rectangular pulse, <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq33869.png\" alt=\"$x[n] = 1$\"><\/span><script type=\"math\/tex\">x[n] = 1<\/script> for <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq75061.png\" alt=\"$0 \\leq n < M$\"><\/span><script type=\"math\/tex\">0 \\leq n < M<\/script>. The DTFT of <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq17606.png\" alt=\"$x[n]$\"><\/span><script type=\"math\/tex\">x[n]<\/script> is:<\/p><p><span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq44745.png\" alt=\"$$X(\\omega) = \\frac{sin(\\omega M\/2)}{sin(\\omega\/2)} e^{-j \\omega (M-1)\/2}$$\"><\/span><script type=\"math\/tex; mode=display\">X(\\omega) = \\frac{sin(\\omega M\/2)}{sin(\\omega\/2)} e^{-j \\omega (M-1)\/2}<\/script><\/p><p>Let's plot <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq28803.png\" alt=\"$|X(\\omega)|$\"><\/span><script type=\"math\/tex\">|X(\\omega)|<\/script> for <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq66486.png\" alt=\"$M=8$\"><\/span><script type=\"math\/tex\">M=8<\/script> over a couple of periods:<\/p><pre class=\"codeinput\">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(<span class=\"string\">'|X(\\omega)|'<\/span>)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_01.png\" alt=\"\"> <p>It turns out that, under certain conditions, the DFT is just equally-spaced samples of the DTFT. Suppose <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq88255.png\" alt=\"$X_P[k]$\"><\/span><script type=\"math\/tex\">X_P[k]<\/script> is the P-point DFT of <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq17606.png\" alt=\"$x[n]$\"><\/span><script type=\"math\/tex\">x[n]<\/script>. If <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq17606.png\" alt=\"$x[n]$\"><\/span><script type=\"math\/tex\">x[n]<\/script> is nonzero only over the finite domain <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq75061.png\" alt=\"$0 \\leq n < M$\"><\/span><script type=\"math\/tex\">0 \\leq n < M<\/script>, then <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq88255.png\" alt=\"$X_P[k]$\"><\/span><script type=\"math\/tex\">X_P[k]<\/script> equals <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq30711.png\" alt=\"$X(\\omega)$\"><\/span><script type=\"math\/tex\">X(\\omega)<\/script> at equally spaced intervals of <span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq84050.png\" alt=\"$\\omega$\"><\/span><script type=\"math\/tex\">\\omega<\/script>:<\/p><p><span class=\"MathJax_Preview\"><img decoding=\"async\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_eq68762.png\" alt=\"$$X_P[k] = X(2\\pi k\/P),\\ k=0, \\ldots, P-1$$\"><\/span><script type=\"math\/tex; mode=display\">X_P[k] = X(2\\pi k\/P),\\ k=0, \\ldots, P-1<\/script><\/p><p>The MATLAB function <tt>fft<\/tt> computes the DFT. Here's the 8-point DFT of our 8-point rectangular pulse:<\/p><pre class=\"codeinput\">x = ones(1, M);\r\nX = fft(x)\r\n<\/pre><pre class=\"codeoutput\">\r\nX =\r\n\r\n     8     0     0     0     0     0     0     0\r\n\r\n<\/pre><p>One 8 and a bunch of zeros?? That doesn't seem anything like the DTFT plot above. But when you superimpose the output of <tt>fft<\/tt> in the right places on the DTFT plot, it all becomes clear.<\/p><pre class=\"codeinput\">P = 8;\r\nw_k = (0:P-1) * (2*pi\/P);\r\nX = fft(x);\r\nplot(w, abs(X_dtft))\r\nhold <span class=\"string\">on<\/span>\r\nplot(w_k, abs(X), <span class=\"string\">'o'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_02.png\" alt=\"\"> <p>Now you can see that the seven zeros in the output of <tt>fft<\/tt> correspond to the seven places (in each period) where the DTFT equals zero.<\/p><p>You can get more samples of the DTFT simply by increasing P. One way to do that is to <b>zero-pad<\/b>.<\/p><pre class=\"codeinput\">x16 = [x, zeros(1, 8)]\r\n<\/pre><pre class=\"codeoutput\">\r\nx16 =\r\n\r\n  Columns 1 through 13\r\n\r\n     1     1     1     1     1     1     1     1     0     0     0     0     0\r\n\r\n  Columns 14 through 16\r\n\r\n     0     0     0\r\n\r\n<\/pre><pre class=\"codeinput\">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 <span class=\"string\">on<\/span>\r\nplot(w_k, abs(X16), <span class=\"string\">'o'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_03.png\" alt=\"\"> <p>Another way to increase P is to use the <tt>fft(x,P)<\/tt> syntax of the <tt>fft<\/tt> function.  This syntax computes the P-point DFT of <tt>x<\/tt> by using zero-padding. Let's try a 50-point DFT.<\/p><pre class=\"codeinput\">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 <span class=\"string\">on<\/span>\r\nplot(w_k, abs(Xp), <span class=\"string\">'o'<\/span>)\r\nhold <span class=\"string\">off<\/span>\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/images\/steve\/2010\/dft_samples_dtft_04.png\" alt=\"\"> <p>If you've ever wondered what that whole zero-padding business was all about with Fourier transforms, now you know.  When you 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 the original sequence.<\/p><p>I think the next logical place to go in our Fourier exploration is to start considering some of the reasons why many people find the output of <tt>fft<\/tt> so surprising or puzzling.  Here's a sample:<\/p><div><ul><li>Why isn't the zero frequency (or \"DC\" frequency) in the center of the output from <tt>fft<\/tt>?<\/li><li>Why isn't the output of <tt>fft<\/tt> real when the input is symmetric?<\/li><\/ul><\/div><p>Do you have puzzles to add? Let me know by adding your comments.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_a2db1f8e7ad547dcb2e4c2022a68d8fb() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='a2db1f8e7ad547dcb2e4c2022a68d8fb ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' a2db1f8e7ad547dcb2e4c2022a68d8fb';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2012 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_a2db1f8e7ad547dcb2e4c2022a68d8fb()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.14<br><\/p><p class=\"footer\"><br>\r\n      Published with MATLAB&reg; 7.14<br><\/p><\/div><!--\r\na2db1f8e7ad547dcb2e4c2022a68d8fb ##### SOURCE BEGIN #####\r\n%%\r\n% It's finally time to start looking at the relationship between the discrete\r\n% Fourier transform (DFT) and the discrete-time Fourier transform (DTFT). Let's\r\n% look at a simple rectangular pulse, $x[n] = 1$ for $0 \\leq n < M$. The DTFT of\r\n% $x[n]$ is:\r\n%\r\n% $$X(\\omega) = \\frac{sin(\\omega M\/2)}{sin(\\omega\/2)} e^{-j \\omega (M-1)\/2}$$\r\n%\r\n% Let's plot $|X(\\omega)|$ for $M=8$ over a couple of periods:\r\n\r\nM = 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)|')\r\n\r\n%%\r\n% It turns out that, under certain conditions, the DFT is just equally-spaced\r\n% samples of the DTFT. Suppose $X_P[k]$ is the P-point DFT of $x[n]$. If $x[n]$\r\n% is nonzero only over the finite domain $0 \\leq n < M$, then $X_P[k]$ equals\r\n% $X(\\omega)$ at equally spaced intervals of $\\omega$:\r\n%\r\n% $$X_P[k] = X(2\\pi k\/P),\\ k=0, \\ldots, P-1$$\r\n%\r\n% The MATLAB function |fft| computes the DFT. Here's the 8-point DFT of our\r\n% 8-point rectangular pulse:\r\n\r\nx = ones(1, M);\r\nX = fft(x)\r\n\r\n%%\r\n% One 8 and a bunch of zeros?? That doesn't seem anything like the DTFT plot\r\n% above. But when you superimpose the output of |fft| in the right places on the\r\n% DTFT plot, it all becomes clear.\r\n\r\nP = 8;\r\nw_k = (0:P-1) * (2*pi\/P);\r\nX = fft(x);\r\nplot(w, abs(X_dtft))\r\nhold on\r\nplot(w_k, abs(X), 'o')\r\nhold off\r\n\r\n%%\r\n% Now you can see that the seven zeros in the output of |fft| correspond to the\r\n% seven places (in each period) where the DTFT equals zero.\r\n%\r\n% You can get more samples of the DTFT simply by increasing P. One way to do\r\n% that is to *zero-pad*.\r\n\r\nx16 = [x, zeros(1, 8)]\r\n\r\n%%\r\nP = 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\r\nplot(w_k, abs(X16), 'o')\r\nhold off\r\n\r\n%%\r\n% Another way to increase P is to use the |fft(x,P)| syntax of the |fft|\r\n% function.  This syntax computes the P-point DFT of |x| by using zero-padding.\r\n% Let's try a 50-point DFT.\r\n\r\nP = 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\r\nplot(w_k, abs(Xp), 'o')\r\nhold off\r\n\r\n%%\r\n% If you've ever wondered what that whole zero-padding business was all about\r\n% with Fourier transforms, now you know.  When you tack on a bunch of zeros to a\r\n% sequence and then compute the DFT, you're just getting more and more samples\r\n% of the DTFT of the original sequence.\r\n%\r\n% I think the next logical place to go in our Fourier exploration is to start\r\n% considering some of the reasons why many people find the output of |fft| so\r\n% surprising or puzzling.  Here's a sample:\r\n%\r\n% * Why isn't the zero frequency (or \"DC\" frequency) in the center of the output\r\n% from |fft|?\r\n% * Why isn't the output of |fft| real when the input is symmetric?\r\n%\r\n% Do you have puzzles to add? Let me know by adding your comments.\r\n##### SOURCE END ##### a2db1f8e7ad547dcb2e4c2022a68d8fb\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n\r\n\r\n\r\nh1 { font-size:18pt; }\r\nh2.titlebg { font-size:13pt; }\r\nh3 { color:#4A4F55; padding:0px; margin:5px 0px 5px; font-family:Arial, Helvetica, sans-serif; font-size:11pt; font-weight:bold;... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/steve\/2010\/03\/15\/the-dft-and-the-dtft-mathjax\/\">read more >><\/a><\/p>","protected":false},"author":42,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[208,508,426,90,32,288,532,68,34,52,130],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/588"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/users\/42"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/comments?post=588"}],"version-history":[{"count":16,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/588\/revisions"}],"predecessor-version":[{"id":3669,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/posts\/588\/revisions\/3669"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/media?parent=588"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/categories?post=588"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/steve\/wp-json\/wp\/v2\/tags?post=588"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}