跳转到内容

快速演算法設計的原則

维基百科,自由的百科全书

快速演算法設計原理

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

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

N-point DFT

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

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

由於線性非時變系統可以用卷積Convolution來表示,故我們可以說其運算複雜度為,三個傅立葉轉換的計算量(包括兩個FTs 以及一個IFT)


若使用了快速演算法,我們可以將其運算複雜度降為

Replacement of DFTs

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

運算簡化技巧

下面以四個例子來解說:

(1)

⇒1 MULs, 1 ADD (一個乘法,一個加法)


(2)


⇒1 MULs, 1 ADD


(3)

⇒2MULs, 4 ADDs


(4)

⇒3MULs, 3 ADDs


複數的乘法

if and

令e為實數項,f為虛數項

(1) let  ;
(2) let  ;
 ; ⇒3MULs, 3~5 ADDs 從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍[1]

参考

  1. ^ Jian-Jiun Ding, Advanced Digital Signal Processing class note, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2018&2020.