快速演算法設計的原則

快速演算法設計原理

• 快速演算法的主要目標為節省計算時間，採取手段主要如下：
  1. 減少加法數量
  2. 減少乘法數量
  3. 減少迴圈數量
  • 其中以減少乘法數量最為重要，可以最為高效率節省計算量。

快速演算法的設計重要的四種概念

N-point DFT

對於任何點數的離散傅立葉轉換(DFT)，都有其適合的快速演算法．

線性非時變系統的運算複雜度

由於線性非時變系統可以用卷積Convolution來表示，故我們可以說其運算複雜度為，三個傅立葉轉換的計算量（包括兩個FTs 以及一個IFT)
⇒$3\theta (NlogN)$
⇒$\theta (NlogN)$
若使用了快速演算法，我們可以將其運算複雜度降為$\theta (N)$

Replacement of DFTs

對於DFT的計算有複數(complex number)的問題，我們也可以透過矩陣的方式來處理．

運算簡化技巧

下面以四個例子來解說：

(1) $y_1=a{x}_1+2a{x}_2$ ⇒$y_1=\left(\begin{array}{cc}a& 2a\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒$y_1=a(x_1+2x_2)$
⇒1 MULs, 1 ADD (一個乘法，一個加法)

(2)$\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)=\left(\begin{array}{cc}a& a\\ a& a\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒$y_1=a(x_1+x_2)$
⇒$y_2=y1$
⇒1 MULs, 1 ADD

(3)$\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)=\left(\begin{array}{cc}a& b\\ b& a\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒$\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)=\left(\begin{array}{cc}\frac{a+b}{2}& \frac{a+b}{2}\\ \frac{a+b}{2}& \frac{a+b}{2}\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)+\left(\begin{array}{cc}\frac{a-b}{2}& -\frac{a-b}{2}\\ -\frac{a-b}{2}& \frac{a-b}{2}\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒2MULs, 4 ADDs

(4)$\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)=\left(\begin{array}{cc}a& b\\ c& a\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒$\left(\begin{array}{c}{y}_1\\ y_2\end{array}\right)=\left(\begin{array}{cc}a& a\\ a& a\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)+\left(\begin{array}{cc}0& b-a\\ c-a& 0\end{array}\right)\left(\begin{array}{c}{x}_1\\ x_2\end{array}\right)$
⇒3MULs, 3 ADDs

複數的乘法

if $x=a+ib$ and $y=c+id$
⇒$xy=ac-bd+i(ad+bc)$
令e為實數項，f為虛數項
$\left(\begin{array}{c}e\\ f\end{array}\right)=\left(\begin{array}{cc}c& -d\\ d& c\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{cc}c& c\\ c& c\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)+\left(\begin{array}{cc}0& -c-d\\ d-c& 0\end{array}\right)\left(\begin{array}{c}a\\ b\end{array}\right)$
(1) let $x_1=c(a+b)$ ; $y_1=x_1$
(2) let $x_2=(-c-d)b$ ; $y_2=(d-c)a$
⇒$e=x_1+x_2$ ; $f=y_1+y_2$ ⇒3MULs, 3～5 ADDs 從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍。