dft_decomposition.abw

fft代码,采用蝶形算法,包括C,matlab和verilog代码

<?xml version="1.0" encoding="ISO-8859-1"?>
<abiword version="0.7.13"  fileformat="1.0">
<!-- =====================================================================  -->
<!-- This file is an AbiWord document.                                      -->
<!-- AbiWord is a free, Open Source word processor.                         -->
<!-- You may obtain more information about AbiWord at www.abisource.com     -->
<!-- You should not edit this file by hand.                                 -->
<!-- =====================================================================  -->

<!--         Build_ID          = (none) -->
<!--         Build_Version     = 0.7.13 -->
<!--         Build_Options     = LicensedTrademarks:Off Debug:Off BiDi:Off Gnome:Off LibXML:Off Pspell:Off -->
<!--         Build_Target      = /home/aaronl/src/debian/abiword-0.7.13/debian/build/obj -->
<!--         Build_CompileTime = 14:38:34 -->
<!--         Build_CompileDate = Feb 20 2001 -->

<pagesize pagetype="A4" orientation="portrait" width="8.267717" height="11.692913" units="inch" page-scale="1.000000"/>
<section>
<p style="Heading 2">Decomposition of a Discrete Fourier Transform</p>
<p></p>
<p>A discrete Fourier transform (DFT) of length N may be evaluated using N^2 multiply accumulate operations.  When N is a composite number, the symmetry of a DFT may be used to decompose it into a set of smaller DFTs, each with a length corresponding to a factor of &#x2018;N&#x2019;.  When N is a power of two, the DFT reduces to a set of DFTs of length two.  A DFT of length 2 is commonly  called a butterfly operation.</p>
<p></p>
<p>D<c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">ecomposing a DFT into smaller DFTs reduces the computation required to calculate it.  When N is a power of two, the number of multiply accumulates is N.log2(N).   Such a DFT is commonly called a Fast Fourier Transform (FFT).  When N is not a power of two, the number of multiply accumulates lies somewhere between N.log2(N) and N^2.</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">The decomposition may be carried out in different ways.  Two of the most common are known as decimation in time and decimation in frequency [].  A third way is the DeSpain algorithm [].  For hardware implementations, the DeSpain algorithm has the advantage of allowing many of the required multipliers to be replaced with simpler rotations by pi/2.</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">In the following, an algorithm will be developed for decomposing a DFT.  This algorithm yields decimation in time, decimation in frequency and DeSpain as special cases.</c></p>
<p></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Start with the definition of a DFT.</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{Insert DFT definition here} ... (1)</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Now factorise N into A factors, Ni, so that</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{N = product(i=0;A-1, Ni,  Ni E Z+, A&gt;=2} ... (2)</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Now replace the index n with a set of indices {n0, ..., nA-1} spanning N such that</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{n=sum(p=1;A-1, np . product(i=0,p-1;Ni) ) + n0, np=0, ..., Np-1 for p=0,...,A-1 } ... (3)</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Similarly, replace the index k with a set of indices {k0,...,KA-1 } spanning N.  In this case, reverse the ordering so the index &#x2018;runs the other way&#x2019; and is &#x2018;orthogonal&#x2019; to n.  {Clean up the terminology here.}</c></p>
<p></p>
<p><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{k=sum(q=1;A-1, kq . product(j=A-1,A-q;Nj) ) + k0, kq=0, ..., Nq-1 for q=0,...,A-1 } ... (4)</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Now substitute the expressions (2), (3) and (4) into the definition of the DFT (1).</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{ Big messy expression}</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">When the product in the exponent is expanded, one ends up with a sum of products.</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">{ (3)*(4) = ( + .. + .. + .. + ..  .. +) }</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"><c props="color:000000; font-family:Times New Roman; font-size:12pt; font-style:normal; font-weight:normal; text-decoration:none; text-position:normal">Each of the additive terms in the exponent yields a product term in the DFT.</c></p>
<p props="line-height:1.000000; margin-bottom:0.0000in; margin-left:0.0000in; margin-right:0.0000in; margin-top:0.0000in; text-align:left; text-indent:0.0000in"></p>