fft变换并不是什么新的算法，它只是为了加速dft运算的一种方法，dft的表达式如下：
很显然求出N点的X(k)需要
N
2
N^{2}
N
2
次复数乘法和N*(N – 1)次复数加法；我们都知道实现一次复数乘法需要四次实数乘两次实数加，实现一次复数加法需要两次实数加；那么当N很大的时候，计算量就会相当的大。dft作为信号处理中最为常用的算法，这么大的计算量显然是不能在实际中得到很好的应用，为此fft就出现了；fft是如何进行的呢？下面将进行详细的介绍。
视频请戳
1、基于时间的抽取(DIT)基2fft算法
对于下式
令
N
=
x
M
N = x^{M}
N
=
x
M
，
M
M
M
为正整数，将
x
(
n
)
x(n)
x
(
n
)
按照奇偶分成两组，基令
n
=
2
r
n=2r
n
=
2
r
以及
n
=
2
r
+
1
n=2r+1
n
=
2
r
+
1
，而
r
=
0
,
1
,
.
.
.
,
N
/
2
−
1
r = 0,1,…,N/2 – 1
r
=
0
,
1
,
.
.
.
,
N
/
2
−
1
，于是有
令
则有
A
(
k
)
和
B
(
k
)
A(k)和B(k)
A
(
k
)
和
B
(
k
)
都是
N
/
2
N/2
N
/
2
点的dft，
X
(
k
)
X(k)
X
(
k
)
是N点dft，因此上式中
X
(
k
)
X(k)
X
(
k
)
不是完全形式，但是
所以
A
(
k
)
，
B
(
k
)
A(k)，B(k)
A
(
k
)
，
B
(
k
)
可以完全表示
X
(
k
)
X(k)
X
(
k
)
，当
N
=
8
N = 8
N
=
8
，
A
(
k
)
，
B
(
k
)
以
及
X
(
k
)
A(k)，B(k)以及X(k)
A
(
k
)
，
B
(
k
)
以
及
X
(
k
)
的关系可以用下图表示
上面推到出的结果
A
(
k
)
，
B
(
k
)
仍
然
是
高
复
合
数
(
N
/
2
)
A(k)，B(k)仍然是高复合数(N / 2)
A
(
k
)
，
B
(
k
)
仍
然
是
高
复
合
数
(
N
/
2
)
的dft，可以按照上述方法继续进行分解，分别令
r
=
2
l
，
r
=
2
l
+
1
，
l
=
0
,
1
，
.
.
.
，
N
/
4
−
1
r = 2l，r = 2l + 1，l = 0,1，…，N / 4 – 1
r
=
2
l
，
r
=
2
l
+
1
，
l
=
0
,
1
，
.
.
.
，
N
/
4
−
1
，则
A
(
k
)
和
B
(
k
)
A(k)和B(k)
A
(
k
)
和
B
(
k
)
可分别表示为
令
则有
同样的道理，令
同理有
如果
N
=
8
N = 8
N
=
8
，那么
C
(
k
)
，
D
(
k
)
，
E
(
k
)
，
F
(
k
)
C(k)，D(k)，E(k)，F(k)
C
(
k
)
，
D
(
k
)
，
E
(
k
)
，
F
(
k
)
都是两点dft，无需继续进行展开，则有
如果
N
=
16
,
32
或
者
是
2
的
更
高
次
幂
N = 16,32或者是2的更高次幂
N
=
1
6
,
3
2
或
者
是
2
的
更
高
次
幂
，可以按照上述方法继续进行展开；上述方法均是将时间n按照奇偶进行展开的，所以称为时间抽取DIT，上述方法的8点DFT可以表示为下图：
基本运算单元如下：
