- 相关推荐
基于FPGA的快速傅立叶变换
摘要：在对FFT（快速傅立叶变换）算法进行研究的基础上，描述了用FPGA实现FFT的方法，并对其中的整体结构、蝶形单元及性能等进行了分析。傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数Ｎ的平方成正比关系，因此，在Ｎ较大时，直接应用ＤＦＴ算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用ＦＰＧＡ来实现２ｋ／４ｋ／８ｋ点ＦＦＴ的设计方法。
１ 整体结构
一般情况下，Ｎ点的傅立叶变换对为：
其中，ＷＮ＝ｅｘｐ(－２ ｐｉ／Ｎ)。Ｘ(ｋ)和ｘ(ｎ)都为复数。与之相对的快速傅立叶变换有很多种,如ＤＩＴ(时域抽取法)、ＤＩＦ（频域抽取法）、Ｃｏｏｌｅｙ－Ｔｕｋｅｙ和Ｗｉｎｏｇｒａｄ等。对于２ｎ傅立叶变换，Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法可导出ＤＩＴ和ＤＩＦ算法。本文运用的基本思想是Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然ＤＩＴ与ＤＩＦ有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，所以可以根据需要任取其中一种，本文主要以ＤＩＴ方法为对象来讨论。
Ｎ＝８１９２点ＤＦＴ的运算表达式为：
式中，ｍ＝(４ｎ１＋ｎ２)(２０４８ｋ１＋ｋ２)(ｎ＝４ｎ１＋ｎ２，ｋ＝２０４８ｋ１＋ｋ２)其中ｎ１和ｋ２可取０,１,．．．,２０４７,ｋ１和ｎ２可取０,１,２,３。
由式（３）可知，８ｋ傅立叶变换可由４×２ｋ的傅立叶变换构成。同理，４ｋ傅立叶变换可由２×２ｋ的傅立叶变换构成。而２ｋ傅立叶变换可由１２８×１６的傅立叶变换构成。１２８的傅立叶变换可进一步由１６×８的傅立叶变换构成，归根结底，整个傅立叶变换可由基２、基４的傅立叶变换构成。２ｋ的ＦＦＴ可以通过５个基４和１个基２变换来实现；４ｋ的ＦＦＴ变换可通过６个基４变换来实现；８ｋ的ＦＦＴ可以通过６个基４和１个基２变换来实现。也就是说：ＦＦＴ的基本结构可由基２／４模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图１所示。
图１中，ＲＡＭ用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，ＲＯＭ用来存储旋转因子表。蝶形运算单元即为基２／４模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。
２ 蝶形运算器的实现
基４和基２的信号流如图２所示。图中，若Ａ＝ｒ０＋ｊ＊ｉ０，Ｂ＝ｒ１＋ｊ＊ｉ１，Ｃ＝ｒ２＋ｊ＊ｉ２，Ｄ＝ｒ３＋ｊ＊ｉ３是要进行变换的信号，Ｗｋ０＝ｃ０＋ｊ＊ｓ０＝１，Ｗｋ１＝ｃ１＋ｊ＊ｓ１，Ｗｋ２＝ｃ２＋ｊ＊ｓ２，Ｗｋ３＝ｃ３＋ｊ＊ｓ３为旋转因子，将其分别代入图２中的基４蝶形运算单元，则有：
Ａ′＝[ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｒ３×ｃ３－ｉ３×ｓ３)]＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)＋(ｉ２×ｃ２＋ｒ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)]? （４）
Ｂ′＝[ｒ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)－(ｒ２×ｃ２－ｉ２×ｓ２)－(ｉ３×ｃ３＋ｒ３×ｓ３)]＋ｊ[ｉ０－(ｒ１×ｃ１－ｉ１×ｓ１)－(ｉ２×ｃ２＋ｒ２×ｓ２)＋(ｒ３×ｃ３－ｉ３×ｓ３)] (５）
Ｃ′＝[ｒ０－(ｒ１×ｃ１－ｉ１×ｓ１)＋(ｒ２×ｃ２－ｉ２×ｓ２)－(ｒ３×ｃ３－ｉ３×ｓ３)]＋ｊ[ｉ０－(ｉ１×ｃ１＋ｒ１×ｓ１)＋(ｉ２×ｃ２＋ｒ２×ｓ２)－(ｉ３×ｃ３＋ｒ３×ｓ３)] （６）
Ｄ′＝[ｒ０－(ｉ１×ｃ１＋ｒ１×ｓ１)－(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)]＋ｊ[ｉ０＋(ｒ１×ｃ１－ｉ１×ｓ１)－(ｉ２×ｃ２＋ｒ２×ｓ２)－(ｒ３×ｃ３－ｉ３×ｓ３)]? （７）
而在基２蝶形中，Ｗｋ０和Ｗｋ２的值均为１，这样，将Ａ，Ｂ，Ｃ和Ｄ的表达式代入图２中的基２运算的四个等式中，则有：
Ａ′＝ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)]? （８）
Ｂ′＝ｒ０－ (ｒ１×ｃ１－ｉ１×ｓ１)＋ｊ[ｉ０－(ｉ１×ｃ１＋ｒ１×ｓ１)] （９）
Ｃ′＝ｒ２＋(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０＋(ｉ３×ｃ３＋ｒ３×ｓ３)]? （１０）
Ｄ′＝ｒ２－(ｒ３×ｃ３－ｉ３×ｓ３)＋ｊ[ｉ０－(ｉ３×ｃ３＋ｒ３×ｓ３)]? （１１）
在上述式（４）～（１１）中有很多类同项，如ｉ１×ｃ１＋ｒ１×ｓ１和ｒ１×ｃ１－ｉ１×ｓ１等，它们仅仅是加减号的不同，其结构和运算均类似，这就为简化电路提供了可能。同时，在蝶形运算中，复数乘法可以由实数乘法以一定的格式来表示，这也为设计复数乘法器提供了一种实现的途径。
以基４为例，在其运算单元中，实际上只需做三个复数乘法运算，即只须计算ＢＷｋ１、ＣＷｋ２和ＤＷｋ３的值即可，这样在一个基４蝶形单元里面，最多只需要３个复数乘法器就可以了。在实际过程中，在不提高时钟频率下，只要将时序控制好?便可利用流水线（Ｐｉｐｅｌｉｎｅ）技术并只用一个复数乘法器就可完成这三个复数乘法，大大节省了硬件资源。
图2 基2和基4蝶形算法的信号流图
３ ＦＦＴ的地址
ＦＦ
【基于FPGA的快速傅立叶变换】相关文章：
试析基于胜任素质的薪酬模式构建01-03
基于战略治理的企业环境风险研究08-28
自制快速干手器05-11
网购快速发展的隐忧05-14
基于软交换的固网智能化05-11
基于BP网遥感影像分类研究与应用08-10
基于minigui的网真机界面的实现08-05
基于军网的雷达远程诊断技术研究08-10
基于顾客价值的需求，流动网挖掘策略分析06-04
基于ＣＳ管理的房地产企业开发设计06-04