FFT实现的数字基础

lookout~

本文介绍FFT实现的数字基础，FFT是DFT（离散傅里叶变换）的快速算法​,FFT和DFT的特点是在时域中数值离散、时间离散（可以实现数字量化），在频域中频率离散、幅值离散，因此可用于数字设备中进行运算。

以下数字公式及结论详细推导过程请查阅数字信号处理。

1.DFT的数学公式如下:

由DFT公式可以推出当实现其算法时可知：

一段N数的DFT，需要N*（N-1）次复数加，和N2次复数乘，而一次复数加可以拆成2个加法，一次复数乘可以拆成4个乘法和2个加法，因此直接使用DFT实现实时的时域到频域的转换，对存储资源和运算单元的数量要求很高，因此使用FFT代替DFT处理时域到频域的运算。

2.FFT.蝶形信号算法流程

N点的DFT以2为基数，一直分拆到2点DFT，最终拆成如下公式：

3.FFT实现的思路就是把各种128/256/512等不同数量的DFT  2分得到基2的FFT蝶形算法流程。

4.FFT可以按时域抽取DIT（时域乱序，频域正序），也可以按频域抽取DIF（时域正序，频域乱序）。本文主要实现按时域抽取FFT算法

5.FFT实现需要首先确定时域数据顺序，和W系数。

5.1.顺序

X(n)的地址按照二进制拆分，高bit和低bit互换，得到数据顺序。

例如：N=8，X(n)地址有三个bit，{N2N1N0}

时域顺序地址和时序乱序地址：{N2N1N0}

    

    

  

0

  

  

  

1

  

  

  

2

  

  

  

3

  

  

  

4

  

  

  

5

  

  

  

6

  

  

  

7

  

    

顺序

    

  

000

  

  

  

001

  

  

  

010

  

  

  

011

  

  

  

100

  

  

  

101

  

  

  

110

  

  

  

111

  

    

乱序

    

  

000

  

  

  

100

  

  

  

010

  

  

  

110

  

  

  

001

  

  

  

101

  

  

  

011

  

  

  

111

  

    

    

  

0

  

  

  

4

  

  

  

2

  

  

  

6

  

  

  

1

  

  

  

5

  

  

  

3

  

  

  

7

  

5.2.W系数

N=2m，第L级：

shiyinjita

还有就是拆分的时候，需要乘以exp，这部分没有说

masaka_xlw

工程上，分裂基FFT的思路要好的多，更为一般化，并且容易在理解上扩展。N=N1*N2, N1/N2可以为任意数。
理论上，为什么FFT这么做是对的是另外一回事： sin/cos 正交性 -> FT-> DTFT -> DFT -> FFT