快速演算法的主要目标为节省计算时间,采取手段主要如下:
减少加法数量
减少乘法数量
减少回圈 数量
其中以减少乘法数量最为重要,可以最为高效率节省计算量。
对于任何点数的离散傅立叶转换(DFT) ,都有其适合的快速演算法.
由于线性非时变系统 可以用卷积 Convolution来表示,故我们可以说其运算复杂度为,三个傅立叶转换的计算量(包括两个FTs 以及一个IFT)
⇒
3
θ
(
N
l
o
g
N
)
{\displaystyle 3\theta (NlogN)}
⇒
θ
(
N
l
o
g
N
)
{\displaystyle \theta (NlogN)}
若使用了快速演算法,我们可以将其运算复杂度降为
θ
(
N
)
{\displaystyle \theta (N)}
对于DFT的计算有复数(complex number)的问题,我们也可以透过矩阵的方式来处理.
下面以四个例子来解说:
(1)
y
1
=
a
x
1
+
2
a
x
2
{\displaystyle y_{1}=ax_{1}+2ax_{2}}
⇒
y
1
=
(
a
2
a
)
(
x
1
x
2
)
{\displaystyle y_{1}={\begin{pmatrix}a&2a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒
y
1
=
a
(
x
1
+
2
x
2
)
{\displaystyle y_{1}=a(x_{1}+2x_{2})}
⇒1 MULs, 1 ADD (一个乘法,一个加法)
(2)
(
y
1
y
2
)
=
(
a
a
a
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒
y
1
=
a
(
x
1
+
x
2
)
{\displaystyle y_{1}=a(x_{1}+x_{2})}
⇒
y
2
=
y
1
{\displaystyle y_{2}=y1}
⇒1 MULs, 1 ADD
(3)
(
y
1
y
2
)
=
(
a
b
b
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\b&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒
(
y
1
y
2
)
=
(
a
+
b
2
a
+
b
2
a
+
b
2
a
+
b
2
)
(
x
1
x
2
)
+
(
a
−
b
2
−
a
−
b
2
−
a
−
b
2
a
−
b
2
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}{\frac {a+b}{2}}&{\frac {a+b}{2}}\\{\frac {a+b}{2}}&{\frac {a+b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}{\frac {a-b}{2}}&-{\frac {a-b}{2}}\\-{\frac {a-b}{2}}&{\frac {a-b}{2}}\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒2MULs, 4 ADDs
(4)
(
y
1
y
2
)
=
(
a
b
c
a
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&b\\c&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒
(
y
1
y
2
)
=
(
a
a
a
a
)
(
x
1
x
2
)
+
(
0
b
−
a
c
−
a
0
)
(
x
1
x
2
)
{\displaystyle {\begin{pmatrix}y_{1}\\y_{2}\end{pmatrix}}={\begin{pmatrix}a&a\\a&a\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}+{\begin{pmatrix}0&b-a\\c-a&0\end{pmatrix}}{\begin{pmatrix}x_{1}\\x_{2}\end{pmatrix}}}
⇒3MULs, 3 ADDs
if
x
=
a
+
i
b
{\displaystyle x=a+ib}
and
y
=
c
+
i
d
{\displaystyle y=c+id}
⇒
x
y
=
a
c
−
b
d
+
i
(
a
d
+
b
c
)
{\displaystyle xy=ac-bd+i(ad+bc)}
令e为实数项,f为虚数项
(
e
f
)
=
(
c
−
d
d
c
)
(
a
b
)
=
(
c
c
c
c
)
(
a
b
)
+
(
0
−
c
−
d
d
−
c
0
)
(
a
b
)
{\displaystyle {\begin{pmatrix}e\\f\end{pmatrix}}={\begin{pmatrix}c&-d\\d&c\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}={\begin{pmatrix}c&c\\c&c\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}+{\begin{pmatrix}0&-c-d\\d-c&0\end{pmatrix}}{\begin{pmatrix}a\\b\end{pmatrix}}}
(1) let
x
1
=
c
(
a
+
b
)
{\displaystyle x_{1}=c(a+b)}
;
y
1
=
x
1
{\displaystyle y_{1}=x_{1}}
(2) let
x
2
=
(
−
c
−
d
)
b
{\displaystyle x_{2}=(-c-d)b}
;
y
2
=
(
d
−
c
)
a
{\displaystyle y_{2}=(d-c)a}
⇒
e
=
x
1
+
x
2
{\displaystyle e=x_{1}+x_{2}}
;
f
=
y
1
+
y
2
{\displaystyle f=y_{1}+y_{2}}
⇒3MULs, 3~5 ADDs
从这里我们可以看出虚数的乘法量大致为实数乘法量的三倍[ 1] 。
^ Jian-Jiun Ding, Advanced Digital Signal Processing class note, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2018&2020.