快速算法设计原理 [ 编辑 ] 快速算法的主要目标为节省计算时间，采取手段主要如下：
减少加法数量
减少乘法数量
减少循环 数量 其中以减少乘法数量最为重要，可以最为高效率节省计算量。 快速算法的设计重要的四种概念 [ 编辑 ] 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.
