快速演算法設計的原則

快速演算法設計原理

編輯
  • 快速演算法的主要目標為節省計算時間,採取手段主要如下:
    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.