{"id":170,"date":"2009-02-02T18:57:01","date_gmt":"2009-02-02T18:57:01","guid":{"rendered":"https:\/\/blogs.mathworks.com\/loren\/2009\/02\/02\/a-pedagogical-tool-for-fourier-transforms\/"},"modified":"2017-05-30T11:51:52","modified_gmt":"2017-05-30T16:51:52","slug":"a-pedagogical-tool-for-fourier-transforms","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/loren\/2009\/02\/02\/a-pedagogical-tool-for-fourier-transforms\/","title":{"rendered":"A Pedagogical Tool for Fourier Transforms"},"content":{"rendered":"<div xmlns:mwsh=\"https:\/\/www.mathworks.com\/namespace\/mcode\/v1\/syntaxhighlight.dtd\" class=\"content\">\r\n   <introduction>\r\n      <p>I recently attended the DSP Workshop sponsored by the IEEE Signal Processing Society.  It focues on both signal processing <b>and<\/b> signal processing education.  I spoke to a lot of the attendees.  Some of the professors and instructors mentioned how important\r\n         it is to teach the basics solidly first, before going into more depth.  If the students don't get the fundamentals, then going\r\n         further doesn't help.\r\n      <\/p>\r\n   <\/introduction>\r\n   <h3>Contents<\/h3>\r\n   <div>\r\n      <ul>\r\n         <li><a href=\"#1\">Pedagogical Tool - dftmtx<\/a><\/li>\r\n         <li><a href=\"#4\">More on dftmtx<\/a><\/li>\r\n         <li><a href=\"#7\">Compare fft and Discrete Transform Matrix Methods<\/a><\/li>\r\n         <li><a href=\"#8\">Do You Have Good Links for Fourier Transform Teaching Material?<\/a><\/li>\r\n      <\/ul>\r\n   <\/div>\r\n   <h3>Pedagogical Tool - dftmtx<a name=\"1\"><\/a><\/h3>\r\n   <p>With that context, I asked how they teach Fourier transforms, especially once they go from the analog domain to the digital.\r\n       It turns out that most of them were unaware of some of the tools in <a href=\"https:\/\/www.mathworks.com\/products\/signal\/\">Signal Processing Toolbox<\/a>, such as <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2008b\/toolbox\/comm\/ref\/dftmtx.html\"><tt>dftmtx<\/tt><\/a>.\r\n   <\/p>\r\n   <p>Here's the help.<\/p><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">h = help(<span style=\"color: #A020F0\">'dftmtx'<\/span>);\r\ndisp(h(1:744))<\/pre><pre style=\"font-style:oblique\"> DFTMTX Discrete Fourier transform matrix.\r\n    DFTMTX(N) is the N-by-N complex matrix of values around\r\n    the unit-circle whose inner product with a column vector\r\n    of length N yields the discrete Fourier transform of the\r\n    vector.  If X is a column vector of length N, then\r\n    DFTMTX(N)*X yields the same result as FFT(X); however, \r\n    FFT(X) is more efficient.\r\n \r\n    The inverse discrete Fourier transform matrix is\r\n    CONJ(DFTMTX(N))\/N.\r\n \r\n    An interesting example is \r\n \r\n      D = dftmtx(4)\r\n \r\n    which returns\r\n \r\n      D = [1   1   1   1\r\n           1  -i  -1   i     \r\n           1  -1   1  -1\r\n           1   i  -1  -i]\r\n \r\n    which illustrates why no multiplications are necessary for\r\n    4-point DFTs.\r\n \r\n    See also FFT and IFFT.\r\n\r\n\r\n<\/pre><p>The help also mentions <a href=\"https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/fft.html\"><tt>fft<\/tt><\/a>, the discrete Fourier transform, computed with a fast Fourier transform (fft) algorithm. With the information given for <tt>dftmtx<\/tt>, let's compare results with those of <tt>fft<\/tt>.\r\n   <\/p>\r\n   <h3>More on dftmtx<a name=\"4\"><\/a><\/h3>\r\n   <p>On further inspection, you may notice that there are comments in the file outlining the calculation.  As an aside, the computation\r\n      is actually done using the function <tt>fft<\/tt> in MATLAB.\r\n   <\/p>\r\n   <p>Here's a brief description of the non-|fft| algorithm. Basically calculate frequencies on the unit circle and multiply by\r\n      <tt>sqrt(-1)<\/tt> (<tt>w<\/tt>).  Multiply these by integral steps for the number of points in the transform (<tt>w*x<\/tt>).  And then calculate all the <tt>sin<\/tt> and <tt>cos<\/tt> terms using <tt>exp<\/tt>.\r\n   <\/p>\r\n   <p>Explicitly, the calculation is:<\/p><pre> f = 2*pi\/n;                 % Angular increment.\r\n w = (0:f:2*pi-f\/2).' * i;   % Column.\r\n x = 0:n-1;                  % Row.\r\n D = exp(-w*x);              % Exponentiation of outer product.<\/pre><h3>Compare fft and Discrete Transform Matrix Methods<a name=\"7\"><\/a><\/h3><pre style=\"background: #F9F7F3; padding: 10px; border: 1px solid rgb(200,200,200)\">n = 1024;\r\nX = eye(n);\r\nXf = fft(X);       <span style=\"color: #228B22\">% fft result<\/span>\r\nf = 2*pi\/n;\r\nw = (0:f:2*pi-f\/2).' * 1i;\r\nx = 0:n-1;\r\nXd = exp(-w*x);     <span style=\"color: #228B22\">% matrix representation<\/span>\r\nnorm(Xf-Xd)<\/pre><pre style=\"font-style:oblique\">ans =\r\n  1.6769e-011\r\n<\/pre><h3>Do You Have Good Links for Fourier Transform Teaching Material?<a name=\"8\"><\/a><\/h3>\r\n   <p>If you know of web sites with good material for teaching discrete Fourier transforms, would you please post them <a href=\"https:\/\/blogs.mathworks.com\/loren\/?p=170#respond\">here<\/a>?  Thanks.\r\n   <\/p><script language=\"JavaScript\">\r\n<!--\r\n\r\n    function grabCode_2f59bdf9da8f42048454cfc2f966c39b() {\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='2f59bdf9da8f42048454cfc2f966c39b ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 2f59bdf9da8f42048454cfc2f966c39b';\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        author = 'Loren Shure';\r\n        copyright = 'Copyright 2009 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 author and copyright lines at the bottom if specified.\r\n        if ((author.length > 0) || (copyright.length > 0)) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (author.length > 0) {\r\n                d.writeln('% _' + author + '_');\r\n            }\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      \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_2f59bdf9da8f42048454cfc2f966c39b()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n            the MATLAB code \r\n            <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; 7.7<br><\/p>\r\n<\/div>\r\n<!--\r\n2f59bdf9da8f42048454cfc2f966c39b ##### SOURCE BEGIN #####\r\n%% A Pedagogical Tool for Fourier Transforms \r\n% I recently attended the <http:\/\/www.2009dsp.org\/ DSP Workshop> \r\n% sponsored by the IEEE Signal Processing Society.  It focues on both\r\n% signal processing *and* signal processing education.  I spoke to a lot of\r\n% the attendees.  Some of the professors and instructors mentioned how\r\n% important it is to teach the basics solidly first, before going into more\r\n% depth.  If the students don't get the fundamentals, then going further\r\n% doesn't help.  \r\n%% Pedagogical Tool - dftmtx\r\n% With that context, I asked how they teach Fourier transforms, especially\r\n% once they go from the analog domain to the digital.  It turns out that\r\n% most of them were unaware of some of the tools in\r\n% <https:\/\/www.mathworks.com\/products\/signal\/ Signal Processing Toolbox>,\r\n% such as\r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2008b\/toolbox\/comm\/ref\/dftmtx.html |dftmtx|>.\r\n%%\r\n% Here's the help.\r\nh = help('dftmtx');\r\ndisp(h(1:744))\r\n%% \r\n% The help also mentions \r\n% <https:\/\/www.mathworks.com\/help\/releases\/R2008b\/techdoc\/ref\/fft.html |fft|>,\r\n% the discrete Fourier transform, computed with a fast Fourier transform (fft)\r\n% algorithm. With the information given for |dftmtx|, let's compare results\r\n% with those of |fft|.\r\n%% More on dftmtx\r\n% On further inspection, you may notice that there are comments in the file\r\n% outlining the calculation.  As an aside, the computation is actually done\r\n% using the function |fft| in MATLAB.  \r\n%%\r\n% Here's a brief description of the non-|fft| algorithm.\r\n% Basically calculate frequencies on\r\n% the unit circle and multiply by |sqrt(-1)| (|w|).  Multiply these by\r\n% integral steps for the number of points in the transform (|w*x|).  And\r\n% then calculate all the |sin| and |cos| terms using |exp|.\r\n%%\r\n% Explicitly, the calculation is:\r\n%\r\n%   f = 2*pi\/n;                 % Angular increment.\r\n%   w = (0:f:2*pi-f\/2).' * i;   % Column.\r\n%   x = 0:n-1;                  % Row.\r\n%   D = exp(-w*x);              % Exponentiation of outer product.\r\n%\r\n%% Compare fft and Discrete Transform Matrix Methods\r\nn = 1024;\r\nX = eye(n);\r\nXf = fft(X);       % fft result\r\nf = 2*pi\/n;                \r\nw = (0:f:2*pi-f\/2).' * 1i;   \r\nx = 0:n-1;                  \r\nXd = exp(-w*x);     % matrix representation        \r\nnorm(Xf-Xd)\r\n%% Do You Have Good Links for Fourier Transform Teaching Material?\r\n% If you know of web sites with good material for teaching discrete Fourier\r\n% transforms, would you please post them\r\n% <https:\/\/blogs.mathworks.com\/loren\/?p=170#respond here>?  Thanks.\r\n\r\n##### SOURCE END ##### 2f59bdf9da8f42048454cfc2f966c39b\r\n-->","protected":false},"excerpt":{"rendered":"<p>\r\n   \r\n      I recently attended the DSP Workshop sponsored by the IEEE Signal Processing Society.  It focues on both signal processing and signal processing education.  I spoke to a lot of the... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/loren\/2009\/02\/02\/a-pedagogical-tool-for-fourier-transforms\/\">read more >><\/a><\/p>","protected":false},"author":39,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[25,15],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/170"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/users\/39"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/comments?post=170"}],"version-history":[{"count":1,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/170\/revisions"}],"predecessor-version":[{"id":2349,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/posts\/170\/revisions\/2349"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/media?parent=170"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/categories?post=170"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/loren\/wp-json\/wp\/v2\/tags?post=170"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}