快速演算法設計原理 快速演算法的主要目標為節省計算時間，採取手段主要如下：
減少加法數量
減少乘法數量
減少迴圈 數量 其中以減少乘法數量最為重要，可以最為高效率節省計算量。 快速演算法的設計重要的四種概念 N-point DFT 對於任何點數的離散傅立葉轉換(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)}
Replacement of DFTs 對於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})}
(
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}
(
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}}}
(
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}}}
複數的乘法 if
x
=
a
+
i
b
{\displaystyle x=a+ib}
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
)
=
(
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}}}
x
1
=
c
(
a
+
b
)
{\displaystyle x_{1}=c(a+b)}
y
1
=
x
1
{\displaystyle y_{1}=x_{1}}
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}}
[1]
参考
^ Jian-Jiun Ding, Advanced Digital Signal Processing class note, the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2018&2020.
