快速算法设计的原则

• 快速算法的主要目标为节省计算时间，采取手段主要如下：
  1. 减少加法数量
  2. 减少乘法数量
  3. 减少循环数量
  • 其中以减少乘法数量最为重要，可以最为高效率节省计算量。

N-point DFT

对于任何点数的离散傅立叶转换(DFT)，都有其适合的快速算法．

线性非时变系统的运算复杂度

由于线性非时变系统可以用卷积Convolution来表示，故我们可以说其运算复杂度为，三个傅立叶转换的计算量（包括两个FTs 以及一个IFT)
⇒${\displaystyle 3\theta (NlogN)}$ 
⇒${\displaystyle \theta (NlogN)}$ 
若使用了快速算法，我们可以将其运算复杂度降为${\displaystyle \theta (N)}$ 

Replacement of DFTs

对于DFT的计算有复数(complex number)的问题，我们也可以透过矩阵的方式来处理．

运算简化技巧

下面以四个例子来解说：

(1) ${\displaystyle y_{1}=ax_{1}+2ax_{2}}$  ⇒${\displaystyle y_{1}={\begin{pmatrix}a&2a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒${\displaystyle y_{1}=a(x_{1}+2x_{2})}$ 
⇒1 MULs, 1 ADD (一个乘法，一个加法)

(2)${\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒${\displaystyle y_{1}=a(x_{1}+x_{2})}$ 
⇒${\displaystyle y_{2}=y1}$ 
⇒1 MULs, 1 ADD

(3)${\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\b&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒${\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}{\frac {a+b}{2}}&{\frac {a+b}{2}}\\{\frac {a+b}{2}}&{\frac {a+b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}{\frac {a-b}{2}}&-{\frac {a-b}{2}}\\-{\frac {a-b}{2}}&{\frac {a-b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒2MULs, 4 ADDs

(4)${\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\c&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒${\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}0&b-a\\c-a&0\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}$ 
⇒3MULs, 3 ADDs

if ${\displaystyle x=a+ib}$  and ${\displaystyle y=c+id}$ 
⇒${\displaystyle xy=ac-bd+i(ad+bc)}$ 
令e为实数项，f为虚数项
${\displaystyle {\begin{pmatrix}e\\f\end{pmatrix}}={\begin{pmatrix}c&-d\\d&c\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}c&c\\c&c\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}+{\begin{pmatrix}0&-c-d\\d-c&0\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}}$ 
(1) let ${\displaystyle x_{1}=c(a+b)}$  ; ${\displaystyle y_{1}=x_{1}}$ 
(2) let ${\displaystyle x_{2}=(-c-d)b}$  ; ${\displaystyle y_{2}=(d-c)a}$ 
⇒${\displaystyle e=x_{1}+x_{2}}$  ; ${\displaystyle f=y_{1}+y_{2}}$  ⇒3MULs, 3～5 ADDs 从这里我们可以看出虚数的乘法量大致为实数乘法量的三倍^[1]。