https://github.com/jyhmiinlin/pynufft
Revision 5565c1c6bbb92002eec6d7282743bae17922a46d authored by Jyh-Miin Lin on 19 March 2022, 08:57:48 UTC, committed by Jyh-Miin Lin on 19 March 2022, 08:57:48 UTC
1 parent 56d3350
Tip revision: 5565c1c6bbb92002eec6d7282743bae17922a46d authored by Jyh-Miin Lin on 19 March 2022, 08:57:48 UTC
minor update for the doc
minor update for the doc
Tip revision: 5565c1c
dft.html
<!DOCTYPE html>
<html class="writer-html5" lang="en" >
<head>
<meta charset="utf-8" /><meta name="generator" content="Docutils 0.17.1: http://docutils.sourceforge.net/" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Discrete Fourier transform (DFT) — PyNUFFT 2022.1.2 documentation</title>
<link rel="stylesheet" href="../_static/pygments.css" type="text/css" />
<link rel="stylesheet" href="../_static/css/theme.css" type="text/css" />
<link rel="stylesheet" href="../_static/graphviz.css" type="text/css" />
<!--[if lt IE 9]>
<script src="../_static/js/html5shiv.min.js"></script>
<![endif]-->
<script data-url_root="../" id="documentation_options" src="../_static/documentation_options.js"></script>
<script src="../_static/jquery.js"></script>
<script src="../_static/underscore.js"></script>
<script src="../_static/doctools.js"></script>
<script async="async" src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script>
<script src="../_static/js/theme.js"></script>
<link rel="index" title="Index" href="../genindex.html" />
<link rel="search" title="Search" href="../search.html" />
</head>
<body class="wy-body-for-nav">
<div class="wy-grid-for-nav">
<nav data-toggle="wy-nav-shift" class="wy-nav-side">
<div class="wy-side-scroll">
<div class="wy-side-nav-search" >
<a href="../index.html" class="icon icon-home"> PyNUFFT
<img src="../_static/logo.jpeg" class="logo" alt="Logo"/>
</a>
<div class="version">
2022.1.2
</div>
<div role="search">
<form id="rtd-search-form" class="wy-form" action="../search.html" method="get">
<input type="text" name="q" placeholder="Search docs" />
<input type="hidden" name="check_keywords" value="yes" />
<input type="hidden" name="area" value="default" />
</form>
</div>
</div><div class="wy-menu wy-menu-vertical" data-spy="affix" role="navigation" aria-label="Navigation menu">
<ul>
<li class="toctree-l1"><a class="reference internal" href="../overview/init.html">Overview</a></li>
<li class="toctree-l1"><a class="reference internal" href="../installation/init.html">Installation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../tutor/init.html">Tutorial</a></li>
<li class="toctree-l1"><a class="reference internal" href="../manu/init.html">Manual</a></li>
<li class="toctree-l1"><a class="reference internal" href="../API/init.html">API documentation</a></li>
<li class="toctree-l1"><a class="reference internal" href="../versionhistory.html">Version history</a></li>
<li class="toctree-l1"><a class="reference internal" href="../acknow/init.html">Acknowledgements</a></li>
</ul>
</div>
</div>
</nav>
<section data-toggle="wy-nav-shift" class="wy-nav-content-wrap"><nav class="wy-nav-top" aria-label="Mobile navigation menu" >
<i data-toggle="wy-nav-top" class="fa fa-bars"></i>
<a href="../index.html">PyNUFFT</a>
</nav>
<div class="wy-nav-content">
<div class="rst-content">
<div role="navigation" aria-label="Page navigation">
<ul class="wy-breadcrumbs">
<li><a href="../index.html" class="icon icon-home"></a> »</li>
<li>Discrete Fourier transform (DFT)</li>
<li class="wy-breadcrumbs-aside">
<a href="../_sources/misc/dft.rst.txt" rel="nofollow"> View page source</a>
</li>
</ul>
<hr/>
</div>
<div role="main" class="document" itemscope="itemscope" itemtype="http://schema.org/Article">
<div itemprop="articleBody">
<section id="discrete-fourier-transform-dft">
<h1>Discrete Fourier transform (DFT)<a class="headerlink" href="#discrete-fourier-transform-dft" title="Permalink to this headline"></a></h1>
<p><strong>Discrete Fourier transform (DFT)</strong></p>
<p>The discrete Fourier transform (DFT) is the digital version of Fourier transform, which is used to analyze digital signals. The formula of DFT is:</p>
<p><span class="math notranslate nohighlight">\(X(k)=\sum_{n=0}^{N-1} x(n)e^{-2 \pi i k n/N}\)</span></p>
<p>DFT incurs a complexity of <span class="math notranslate nohighlight">\(O(N^2)\)</span>.</p>
<p>A naive Python program can be easily done. Save the following python code as <em>dft_test.py</em> (However, the efficiency is not satisfactory. Python has provided an FFT which is faster than naive DFT.)</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">numpy</span>
<span class="k">def</span> <span class="nf">naive_DFT</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
<span class="n">N</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">size</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="n">X</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">zeros</span><span class="p">((</span><span class="n">N</span><span class="p">,),</span><span class="n">dtype</span><span class="o">=</span><span class="n">numpy</span><span class="o">.</span><span class="n">complex128</span><span class="p">)</span>
<span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">N</span><span class="p">):</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">N</span><span class="p">):</span>
<span class="n">X</span><span class="p">[</span><span class="n">m</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">*</span><span class="n">numpy</span><span class="o">.</span><span class="n">exp</span><span class="p">(</span><span class="o">-</span><span class="n">numpy</span><span class="o">.</span><span class="n">pi</span><span class="o">*</span><span class="mi">2</span><span class="n">j</span><span class="o">*</span><span class="n">m</span><span class="o">*</span><span class="n">n</span><span class="o">/</span><span class="n">N</span><span class="p">)</span>
<span class="k">return</span> <span class="n">X</span>
<span class="n">x</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">1024</span><span class="p">,)</span>
<span class="c1"># compute DFT</span>
<span class="n">X</span><span class="o">=</span><span class="n">naive_DFT</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="c1"># compute FFT using numpy's fft function</span>
<span class="n">X2</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">fft</span><span class="o">.</span><span class="n">fft</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="c1"># now compare DFT with numpy fft</span>
<span class="nb">print</span><span class="p">(</span><span class="s1">'Is DFT close to fft?'</span><span class="p">,</span><span class="n">numpy</span><span class="o">.</span><span class="n">allclose</span><span class="p">(</span><span class="n">X</span> <span class="o">-</span> <span class="n">X2</span><span class="p">,</span><span class="mf">1e-12</span><span class="p">))</span>
</pre></div>
</div>
<p>Now run <em>dft_test.py</em> program in command line:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>$ python3 dft_test.py
$ Is DFT close to fft? True
</pre></div>
</div>
<p><strong>Inverse Discrete Fourier transform (IDFT)</strong></p>
<p>Inverse discrete Fourier transform (IDFT)</p>
<p><span class="math notranslate nohighlight">\(x(n)= \frac{1}{N}\sum_{k=0}^{N-1} X(k)e^{2 \pi i k n/N}\)</span></p>
<p>Now test a function of IDFT <em>idft_test.py</em></p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span><span class="c1"># An example file of inverse Discrete Fourier transform (IDFT)</span>
<span class="kn">import</span> <span class="nn">numpy</span>
<span class="k">def</span> <span class="nf">naive_IDFT</span><span class="p">(</span><span class="n">x</span><span class="p">):</span>
<span class="n">N</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">size</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="n">X</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">zeros</span><span class="p">((</span><span class="n">N</span><span class="p">,),</span><span class="n">dtype</span><span class="o">=</span><span class="n">numpy</span><span class="o">.</span><span class="n">complex128</span><span class="p">)</span>
<span class="k">for</span> <span class="n">m</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">N</span><span class="p">):</span>
<span class="k">for</span> <span class="n">n</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="mi">0</span><span class="p">,</span><span class="n">N</span><span class="p">):</span>
<span class="n">X</span><span class="p">[</span><span class="n">m</span><span class="p">]</span> <span class="o">+=</span> <span class="n">x</span><span class="p">[</span><span class="n">n</span><span class="p">]</span><span class="o">*</span><span class="n">numpy</span><span class="o">.</span><span class="n">exp</span><span class="p">(</span><span class="n">numpy</span><span class="o">.</span><span class="n">pi</span><span class="o">*</span><span class="mi">2</span><span class="n">j</span><span class="o">*</span><span class="n">m</span><span class="o">*</span><span class="n">n</span><span class="o">/</span><span class="n">N</span><span class="p">)</span>
<span class="k">return</span> <span class="n">X</span><span class="o">/</span><span class="n">N</span>
<span class="n">x</span> <span class="o">=</span> <span class="n">numpy</span><span class="o">.</span><span class="n">random</span><span class="o">.</span><span class="n">rand</span><span class="p">(</span><span class="mi">1024</span><span class="p">,)</span>
<span class="c1"># compute FFT</span>
<span class="n">X</span><span class="o">=</span><span class="n">numpy</span><span class="o">.</span><span class="n">fft</span><span class="o">.</span><span class="n">fft</span><span class="p">(</span><span class="n">x</span><span class="p">)</span>
<span class="c1"># compute IDFT using IDFT</span>
<span class="n">x2</span> <span class="o">=</span> <span class="n">naive_IDFT</span><span class="p">(</span><span class="n">X</span><span class="p">)</span>
<span class="c1"># now compare DFT with numpy fft</span>
<span class="nb">print</span><span class="p">(</span><span class="s1">'Is IDFT close to original?'</span><span class="p">,</span><span class="n">numpy</span><span class="o">.</span><span class="n">allclose</span><span class="p">(</span><span class="n">x</span> <span class="o">-</span> <span class="n">x2</span><span class="p">,</span><span class="mf">1e-12</span><span class="p">))</span>
</pre></div>
</div>
<p>Now run <em>idft_test.py</em> program in command line:</p>
<div class="highlight-default notranslate"><div class="highlight"><pre><span></span>$ python3 idft_test.py
$ Is IDFT close to original? True
</pre></div>
</div>
</section>
</div>
</div>
<footer>
<hr/>
<div role="contentinfo">
<p>© Copyright 2012-2022, PyNUFFT services.</p>
</div>
Built with <a href="https://www.sphinx-doc.org/">Sphinx</a> using a
<a href="https://github.com/readthedocs/sphinx_rtd_theme">theme</a>
provided by <a href="https://readthedocs.org">Read the Docs</a>.
</footer>
</div>
</div>
</section>
</div>
<script>
jQuery(function () {
SphinxRtdTheme.Navigation.enable(true);
});
</script>
</body>
</html>
Computing file changes ...
