跳转到内容

快速算法设计的原则

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

快速算法设计原理

  • 快速算法的主要目标为节省计算时间,采取手段主要如下:
    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.