despain_derivation.html

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

    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mrow>
      <mi>P</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>Q</mi>
     </mrow>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>b</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>q</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>P</mi>
   </mrow>
  </msup>
  </mpadded>

  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mrow>
      <mi>P</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>Q</mi>
     </mrow>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>q</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>a</mi>
   </mrow>
  </msup>
  </mpadded>

 </mrow>
</math>
</td>
<td align="right">...(6)</td>
</tr>
</table>

<p>Note that the left most exponent is always a multiple of
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>2</mi>
  <mo>&InvisibleTimes;</mo>
  <mi>&pi;</mi>
 </mrow>
</math>
, and cancel common fectors in the other exponents.</p>

<table width="100%"><tr><td align="left"><math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>H</mi>
  <mfenced open="[" close="]">
   <mrow>
    <mi>b</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>P</mi>
    <mo>+</mo>
    <mi>a</mi>   
   </mrow>
  </mfenced>
  <mo>=</mo>
  <msubsup>
   <mo>&Sigma;</mo>
   <mrow>
    <mrow>
     <mi>p</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>Q</mi>
     <mo>+</mo>
     <mi>q</mi>
    </mrow>   
    <mo>=</mo>
    <mi>0</mi>
   </mrow>
   <mrow>
    <mi>P</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>Q</mi>
    <mo>-</mo>
    <mi>1</mi>
   </mrow>
  </msubsup>
  <mi>h</mi>
  <mfenced open="[" close="]">
   <mrow>
    <mi>p</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>Q</mi>
    <mo>+</mo>
    <mi>q</mi>
   </mrow>
  </mfenced>
  
  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mi>P</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>a</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>p</mi>
   </mrow>
  </msup>
  </mpadded>

  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mi>Q</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>b</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>q</mi>
   </mrow>
  </msup>
  </mpadded>

  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mrow>
      <mi>P</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>Q</mi>
     </mrow>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>q</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>a</mi>
   </mrow>
  </msup>
  </mpadded>

 </mrow>
</math>
</td>
<td align="right">...(7)</td>
</tr>
</table>

<p>Now extract common factors from the sum, and break it into two separate sums,
over orthogonal dimensions.</p>

<table width="100%"><tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>H</mi>
  <mfenced open="[" close="]">
   <mrow>
    <mi>b</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>P</mi>
    <mo>+</mo>
    <mi>a</mi>   
   </mrow>
  </mfenced>
  <mo>=</mo>
  <msubsup>
   <mo>&Sigma;</mo>
   <mrow>
    <mi>q</mi>
    <mo>=</mo>
    <mi>0</mi>
   </mrow>
   <mrow>
    <mi>Q</mi>
    <mo>-</mo>
    <mi>1</mi>
   </mrow>
  </msubsup>

  <mfenced open="{" close="}">
  <mrow>
   <mfenced>
    <mrow>
    <msubsup>
     <mo>&Sigma;</mo>
     <mrow>
      <mi>p</mi>
      <mo>=</mo>
      <mi>0</mi>
     </mrow>
     <mrow>
      <mi>P</mi>
      <mo>-</mo>
      <mi>1</mi>
     </mrow>
    </msubsup>

    <mi>h</mi>
    <mfenced open="[" close="]">
     <mrow>
      <mi>p</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>Q</mi>
      <mo>+</mo>
      <mi>q</mi>
     </mrow>
    </mfenced>
  
    <mo>.</mo>

    <mpadded lspace="10% width">
    <msup>
     <mi>e</mi>
     <mrow>
      <mo>-</mo>
      <mi>j</mi>
      <mo>&InvisibleTimes;</mo>
      <mfrac>
       <mrow>
        <mi>2</mi>
        <mo>&InvisibleTimes;</mo>
        <mi>&pi;</mi>
       </mrow>
       <mi>P</mi>
      </mfrac>
      <mo>&InvisibleTimes;</mo>
      <mi>p</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>a</mi>
     </mrow>
    </msup>
    </mpadded>

    </mrow>
   </mfenced>

   <mo>.</mo>
   <mpadded lspace="10% width">
   <msup>
    <mi>e</mi>
    <mrow>
     <mo>-</mo>
     <mi>j</mi>
     <mo>&InvisibleTimes;</mo>
     <mfrac>
      <mrow>
       <mi>2</mi>
       <mo>&InvisibleTimes;</mo>
       <mi>&pi;</mi>
      </mrow>
      <mrow>
      <mi>P</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>Q</mi>
      </mrow>
     </mfrac>
     <mo>&InvisibleTimes;</mo>
     <mi>a</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>q</mi>
    </mrow>
   </msup>
   </mpadded>

   </mrow>
  </mfenced>

  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mi>Q</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>q</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>b</mi>
   </mrow>
  </msup>
  </mpadded>
 </mrow>
</math>
</td>
<td align="right">...(8)</td>
</tr>
</table>

<p>The structure of this expression can be more plainly seen by
inroducing intermediate variables 'x' and 'y'.</p>

<table width="100%">
<tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>x</mi>
  <mfenced open="[" close="]">
   <mi>a</mi>
   <mi>q</mi>   
  </mfenced>
  <mo>=</mo>

  <mrow>
   <msubsup>
    <mo>&Sigma;</mo>
    <mrow>
     <mi>p</mi>
     <mo>=</mo>
     <mi>0</mi>
    </mrow>
    <mrow>
     <mi>P</mi>
     <mo>-</mo>
     <mi>1</mi>
    </mrow>
   </msubsup>

   <mi>h</mi>
  <mfenced open="[" close="]">
   <mrow>
    <mi>p</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>Q</mi>
    <mo>+</mo>
    <mi>q</mi>
   </mrow>
  </mfenced>
  
   <mo>.</mo>

   <mpadded lspace="10% width">
   <msup>
    <mi>e</mi>
    <mrow>
     <mo>-</mo>
     <mi>j</mi>
     <mo>&InvisibleTimes;</mo>
     <mfrac>
      <mrow>
       <mi>2</mi>
       <mo>&InvisibleTimes;</mo>
       <mi>&pi;</mi>
      </mrow>
      <mi>P</mi>
     </mfrac>
     <mo>&InvisibleTimes;</mo>
     <mi>p</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>a</mi>
    </mrow>
   </msup>
   </mpadded>
  </mrow>
 </mrow>
</math>
</td>
<td align="right">...(9a)</td>
</tr>

<tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>y</mi>
  <mfenced open="[" close="]">
   <mi>a</mi>
   <mi>q</mi>   
  </mfenced>
  <mo>=</mo>

  <mrow>
   <mi>x</mi>
   <mfenced open="[" close="]">
    <mi>a</mi>
    <mi>q</mi>   
   </mfenced>
  
   <mo>.</mo>

   <mpadded lspace="10% width">
   <msup>
    <mi>e</mi>
    <mrow>
     <mo>-</mo>
     <mi>j</mi>
     <mo>&InvisibleTimes;</mo>
     <mfrac>
      <mrow>
       <mi>2</mi>
       <mo>&InvisibleTimes;</mo>
       <mi>&pi;</mi>
      </mrow>
      <mrow>
       <mi>P</mi>
       <mo>&InvisibleTimes;</mo>
       <mi>Q</mi>
      </mrow>
     </mfrac>
     <mo>&InvisibleTimes;</mo>
     <mi>a</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>q</mi>
    </mrow>
   </msup>
   </mpadded>
  </mrow>
 </mrow>
</math>
</td>
<td align="right">...(9b)</td>
</tr>

<tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>H</mi>
  <mfenced open="[" close="]">
   <mrow>
    <mi>b</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>P</mi>
    <mo>+</mo>
    <mi>a</mi>   
   </mrow>
  </mfenced>
  <mo>=</mo>

  <mrow>
   <msubsup>
    <mo>&Sigma;</mo>
    <mrow>
     <mi>q</mi>
     <mo>=</mo>
     <mi>0</mi>
    </mrow>
    <mrow>
     <mi>Q</mi>
     <mo>-</mo>
     <mi>1</mi>
    </mrow>
   </msubsup>

   <mi>y</mi>
   <mfenced open="[" close="]">
    <mi>a</mi>
    <mi>q</mi>
   </mfenced>
  
   <mo>.</mo>

   <mpadded lspace="10% width">
   <msup>
    <mi>e</mi>
    <mrow>
     <mo>-</mo>
     <mi>j</mi>
     <mo>&InvisibleTimes;</mo>
     <mfrac>
      <mrow>
       <mi>2</mi>
       <mo>&InvisibleTimes;</mo>
       <mi>&pi;</mi>
      </mrow>
      <mi>Q</mi>
     </mfrac>
     <mo>&InvisibleTimes;</mo>
     <mi>q</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>b</mi>
    </mrow>
   </msup>
   </mpadded>
  </mrow>
 </mrow>
</math>
</td>
<td align="right">...(9c)</td>
</tr>

</table>


</body>
</html>