在线咨询
eetop公众号 创芯大讲堂 创芯人才网
切换到宽版

EETOP 创芯网论坛 (原名:电子顶级开发网)

手机号码,快捷登录

手机号码,快捷登录

找回密码

  登录   注册  

快捷导航
搜帖子
查看: 1804|回复: 2

[原创] FFT实现的数字基础

[复制链接]
发表于 2019-11-7 23:11:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?注册

x
本文介绍FFT实现的数字基础,FFT是DFT(离散傅里叶变换)的快速算法​,FFT和DFT的特点是在时域中数值离散、时间离散(可以实现数字量化),在频域中频率离散、幅值离散,因此可用于数字设备中进行运算。
以下数字公式及结论详细推导过程请查阅数字信号处理。
1.DFT的数学公式如下:
DFT公式.png
由DFT公式可以推出当实现其算法时可知:
一段N数的DFT,需要N*(N-1)次复数加,和N2次复数乘,而一次复数加可以拆成2个加法,一次复数乘可以拆成4个乘法和2个加法,因此直接使用DFT实现实时的时域到频域的转换,对存储资源和运算单元的数量要求很高,因此使用FFT代替DFT处理时域到频域的运算。
2.FFT.蝶形信号算法流程
N点的DFT以2为基数,一直分拆到2点DFT,最终拆成如下公式:
FFT蝶形图.png
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级: 11.png
发表于 2019-11-20 09:40:30 | 显示全部楼层
还有就是拆分的时候,需要乘以exp,这部分没有说
发表于 2019-11-21 06:56:42 | 显示全部楼层
工程上,分裂基FFT的思路要好的多,更为一般化,并且容易在理解上扩展。N=N1*N2, N1/N2可以为任意数。
理论上,为什么FFT这么做是对的是另外一回事: sin/cos 正交性 -> FT-> DTFT -> DFT -> FFT
您需要登录后才可以回帖 登录 | 注册

本版积分规则

关闭

站长推荐 上一条 /1 下一条

×

小黑屋| 关于我们| 联系我们| 在线咨询| 隐私声明| EETOP 创芯网
( 京ICP备:10050787号 京公网安备:11010502037710 )

GMT+8, 2024-3-28 20:36 , Processed in 0.033598 second(s), 10 queries , Gzip On, Redis On.

eetop公众号 创芯大讲堂 创芯人才网
快速回复 返回顶部 返回列表