快速演算法

维基教科书,自由的教学读本

算法优化,最主要的目的是用來減少運算時間,像是加法、乘法的數目,以及所花的運算週期。此外還能降低硬體實現所花費的成本,像是減少緩衝器的數量、重複利用相同的硬體架構。

概覽[编辑]

一般來說,快速演算法的設計可以透過將運算展開,並進行歸納、分析,利用运算次数更少的乘法、除法(如乘以二、除以二等左移、右移)來完成運算,達到降低運算時間的目的。

而在設計的過程中,因為乘法的運算時間會遠大於加法,因此通常會以使用多少個乘法來衡量整體的運算時間。此外,因為是從硬體的角度來看,所以對於乘上、0,都可以視為不需要任何的運算時間(trivial multiplications),因為對於乘上,或者除上,分別只要進行左移位元或右移位元的運算即可達成。

簡單矩陣有关的算法优化設計[编辑]

以下举几个例子,用以说明如何优化算法,使得矩阵演算能够最优化。 1.

從上面這個式子來看,在左邊的部分需要用到兩個乘法、一個加法,然而經過一些化簡、合併,在右邊的地方就只需要一個乘法(乘2不需要運算時間)、一個加法。

2.

,因此從原本需要四個乘法、兩個加法,變成只要一個乘法、一個加法。

3.

,因此從原本的四個乘法、兩個加法,變成只需要一個乘法、二個加法。

4.

, 左邊的部分可以參考例子2,右邊則是例子3,因此從原本的四個乘法、兩個加法,變成兩個乘法、四個加法。

5.

左邊的部分一樣可以參考例子2,所以需要一個乘法、一個加法,右邊的部分則需要兩個乘法,最後要將左右兩式相加,因此還需要兩個加法才能得到,所以一共需要三個乘法、三個加法。

實際應用[编辑]

一般來說,做傅立葉轉換會用到複數的乘法,會比一般實數的乘法多上四倍,若是利用快速演算法,則可以化簡如下:

因此左邊的部分可以參考例子2,所以需要一個乘法,右邊的部分則需要兩個乘法,因此可以由四個乘法變為三個乘法。

另外舉一個DFT的例子,一般來說DFT會需要個實數乘法:

,左邊都是一些trivial multiplication,所以不需要乘法運算,右邊則可以參考例子3,所以需要一個乘法。整個DFT的運算可以由下式表示:

所以最後一供需要個乘法。

參考資料[编辑]

[1]http://djj.ee.ntu.edu.tw/ADSP10.pdf

  1. 丁建均.高等數位訊號處理.於2017年6月20日查閱.