⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 despain_derivation.html

📁 fft代码,采用蝶形算法,包括C,matlab和verilog代码
💻 HTML
📖 第 1 页 / 共 2 页
字号:
🔍
12 
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head>
<title>Derivation of the DeSpain Algorithm</title>
</head>

<body>
<h1>Derivation of the DeSpain Algorithm</h1>

<h2>Definition of the Discrete Fourier Transform.</h2>

<p>DFT:

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>X</mi>
  <mfenced open="[" close="]">
   <mi>k</mi>
  </mfenced>
  <mo>=</mo>
  <msubsup>
   <mo>&Sigma;</mo>
   <mrow>
    <mi>n</mi>
    <mo>=</mo>
    <mi>0</mi>
   </mrow>
   <mrow>
    <mi>N</mi>
    <mo>-</mo>
    <mi>1</mi>
   </mrow>
  </msubsup>
  <mi>x</mi>
  <mfenced open="[" close="]">
   <mi>n</mi>
  </mfenced>
  <mo>&InvisibleTimes;</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>N</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>n</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>k</mi>   
   </mrow>
  </msup>
  </mpadded>
 </mrow>
</math>
</p>

<p>Inverse DFT:

<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>x</mi>
  <mfenced open="[" close="]">
   <mi>n</mi>
  </mfenced>
  <mo>=</mo>
  <mfrac>
   <mi>1</mi>
   <mi>N</mi>
  </mfrac>
  <mo>&InvisibleTimes;</mo>
  <msubsup>
   <mo>&Sigma;</mo>
   <mrow>
    <mi>k</mi>
    <mo>=</mo>
    <mi>0</mi>
   </mrow>
   <mrow>
    <mi>N</mi>
    <mo>-</mo>
    <mi>1</mi>
   </mrow>
  </msubsup>
  <mi>X</mi>
  <mfenced open="[" close="]">
   <mi>k</mi>
  </mfenced>
  <mo>&InvisibleTimes;</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mi>j</mi>
    <mo>&InvisibleTimes;</mo>
    <mfrac>
     <mrow>
      <mi>2</mi>
      <mo>&InvisibleTimes;</mo>
      <mi>&pi;</mi>
     </mrow>
     <mi>N</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>n</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>k</mi>   
   </mrow>
  </msup>
  </mpadded>
 </mrow>
</math>
</p>

<p>Where 'n' and 'k' are related to time and frequency respectively by:</p>

<p><math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mrow>
   <mi>t</mi>
  </mrow>
  <mrow>
   <mo>=</mo>
   <mi>n</mi>
   <mo>.</mo>
   <mi>&Delta;t</mi>
  </mrow>
  <mrow>
   <mo>=</mo>
   <mi>n</mi>
   <mo>.</mo>
   <mfrac>
    <mi>T</mi>
    <mi>N</mi>
   </mfrac>
  </mrow>
 </mrow>
</math>
</p>

<p><math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mrow>
   <mi>&omega;</mi>
  </mrow>
  <mrow>
   <mo>=</mo>
   <mi>k</mi>
   <mo>.</mo>
   <mi>&Delta;&omega;</mi>
  </mrow>
  <mrow>
   <mo>=</mo>
   <mi>k</mi>
   <mo>.</mo>
   <mfrac>
    <mrow>
     <mi>2</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>&pi;</mi>
    </mrow>
    <mi>T</mi>
   </mfrac>
  </mrow>
 </mrow>
</math>
</p>

<h2>Derivation of the DeSpain Algorithm</h2>

<p>Start with the Discrete Fourier Transform.</p>

<table width="100%"><tr><td align="left"><math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>H</mi>
  <mfenced open="[" close="]">
   <mi>k</mi>
  </mfenced>
  <mo>=</mo>
  <msubsup>
   <mo>&Sigma;</mo>
   <mrow>
    <mi>n</mi>
    <mo>=</mo>
    <mi>0</mi>
   </mrow>
   <mrow>
    <mi>N</mi>
    <mo>-</mo>
    <mi>1</mi>
   </mrow>
  </msubsup>
  <mi>h</mi>
  <mfenced open="[" close="]">
   <mi>n</mi>
  </mfenced>
  <mo>&InvisibleTimes;</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>N</mi>
    </mfrac>
    <mo>&InvisibleTimes;</mo>
    <mi>n</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>k</mi>   
   </mrow>
  </msup>
  </mpadded>
 </mrow>
</math>
</td>
<td align="right">...(1)</td>
</tr>
</table>

<p>Choose two integers 'P' and 'Q', such that</p>

<table width="100%"><tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>N</mi>
  <mo>=</mo>
  <mi>P</mi>
  <mo>.</mo>
  <mi>Q</mi>
 </mrow>
</math>
</td>
<td align="right">...(2)</td>
</tr></table>

<p>That is, 'P' and 'Q' are factors of 'N'.</p>

<p>Now let</p>

<table width="100%"><tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>n</mi>
  <mo>=</mo>
  <mi>p</mi>
  <mo>&InvisibleTimes;</mo>
  <mi>Q</mi>
  <mo>+</mo>
  <mi>q</mi>   
 </mrow>
</math>
</td>
<td align="right">...(3)</td>
</tr></table>


<p>where
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>p</mi>
  <mo>=</mo>
  <mi>0</mi>
  <mo>,...,</mo>
  <mrow>
   <mi>P</mi>
   <mo>-</mo>
   <mi>1</mi>
  </mrow>
 </mrow>
</math>
;
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>q</mi>
  <mo>=</mo>
  <mi>0</mi>
  <mo>,...,</mo>
  <mrow>
   <mi>Q</mi>
   <mo>-</mo>
   <mi>1</mi>
  </mrow>
 </mrow>
</math>
, and</p>

<table width="100%"><tr><td align="left">
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>k</mi>
  <mo>=</mo>
  <mi>b</mi>
  <mo>&InvisibleTimes;</mo>
  <mi>P</mi>
  <mo>+</mo>
  <mi>a</mi>   
 </mrow>
</math>
</td>
<td align="right">...(4)</td>
</tr></table>

<p>where
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>b</mi>
  <mo>=</mo>
  <mi>0</mi>
  <mo>,...,</mo>
  <mrow>
   <mi>Q</mi>
   <mo>-</mo>
   <mi>1</mi>
  </mrow>
 </mrow>
</math>
;
<math xmlns="http://www.w3.org/1998/Math/MathML">
 <mrow>
  <mi>a</mi>
  <mo>=</mo>
  <mi>0</mi>
  <mo>,...,</mo>
  <mrow>
   <mi>P</mi>
   <mo>-</mo>
   <mi>1</mi>
  </mrow>
 </mrow>
</math>
.
</p>

<p>Substitute equations (2), (3) and (4) into equation (1) to give:</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>&InvisibleTimes;</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>

    <mfenced>
     <mrow>
     <mi>p</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>Q</mi>
     <mo>+</mo>
     <mi>q</mi>
     </mrow>
    </mfenced>

    <mo>&InvisibleTimes;</mo>

    <mfenced>
     <mrow>
     <mi>b</mi>
     <mo>&InvisibleTimes;</mo>
     <mi>P</mi>
     <mo>+</mo>
     <mi>a</mi>   
     </mrow>
    </mfenced>

   </mrow>
  </msup>
  </mpadded>
 </mrow>
</math>
</td>
<td align="right">...(5)</td>
</tr>
</table>


<p>Now expand the exponent.</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>
    <mi>2</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>&pi;</mi>
    <mi>p</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>b</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>a</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>p</mi>
    <mo>&InvisibleTimes;</mo>
    <mi>Q</mi>
   </mrow>
  </msup>
  </mpadded>

  <mo>.</mo>
  <mpadded lspace="10% width">
  <msup>
   <mi>e</mi>
   <mrow>
    <mo>-</mo>
12

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -