基于FPGA的快速傅立叶变换

傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域。但由于其运算量与变换点数Ｎ的平方成正比关系，因此，在Ｎ较大时，直接应用ＤＦＴ算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根本性的变化。本文主要描述了采用ＦＰＧＡ来实现２ｋ／４ｋ／８ｋ点ＦＦＴ的设计方法。

１　整体结构

一般情况下，Ｎ点的傅立叶变换对为：

其中，ＷＮ＝ｅｘｐ(－２ ｐｉ／Ｎ)。Ｘ(ｋ)和ｘ(ｎ)都为复数。与之相对的快速傅立叶变换有很多种,如ＤＩＴ(时域抽取法)、ＤＩＦ（频域抽取法）、Ｃｏｏｌｅｙ－Ｔｕｋｅｙ和Ｗｉｎｏｇｒａｄ等。对于２ｎ傅立叶变换，Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法可导出ＤＩＴ和ＤＩＦ算法。本文运用的基本思想是Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然ＤＩＴ与ＤＩＦ有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，所以可以根据需要任取其中一种，本文主要以ＤＩＴ方法为对象来讨论。

Ｎ＝８１９２点ＤＦＴ的运算表达式为：

式中，ｍ＝(４ｎ１＋ｎ２)(２０４８ｋ１＋ｋ２)(ｎ＝４ｎ１＋ｎ２，ｋ＝２０４８ｋ１＋ｋ２)其中ｎ１和ｋ２可取０,１,．．．,２０４７,ｋ１和ｎ２可取０,１,２,３。

由式（３）可知，８ｋ傅立叶变换可由４×２ｋ的傅立叶变换构成。同理，４ｋ傅立叶变换可由２×２ｋ的傅立叶变换构成。而２ｋ傅立叶变换可由１２８×１６的傅立叶变换构成。１２８的傅立叶变换可进一步由１６×８的傅立叶变换构成，归根结底，整个傅立叶变换可由基２、基４的傅立叶变换构成。２ｋ的ＦＦＴ可以通过５个基４和１个基２变换来实现；４ｋ的ＦＦＴ变换可通过６个基４变换来实现；８ｋ的ＦＦＴ可以通过６个基４和１个基２变换来实现。也就是说：ＦＦＴ的基本结构可由基２／４模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图１所示。

图１中，ＲＡＭ用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，ＲＯＭ用来存储旋转因子表。蝶形运算单元即为基２／４模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。 （科教作文网http://zw.NSEaC.com编辑发布）

２　蝶形运算器的实现

基４和基２的信号流如图２所示。图中，若Ａ＝ｒ０＋ｊ＊ｉ０，Ｂ＝ｒ１＋ｊ＊ｉ１，Ｃ＝ｒ２＋ｊ＊ｉ２，Ｄ＝ｒ３＋ｊ＊ｉ３是要进行变换的信号，Ｗｋ０＝ｃ０＋ｊ＊ｓ０＝１，Ｗｋ１＝ｃ１＋ｊ＊ｓ１，Ｗｋ２＝ｃ２＋ｊ＊ｓ２，Ｗｋ３＝ｃ３＋ｊ＊ｓ３为旋转因子，将其分别代入图２中的基４蝶形运算单元，则有：

Ａ′＝[ｒ０＋(ｒ１×ｃ１－ｉ１×ｓ１)＋(ｒ２×ｃ２－ｉ２×ｓ２)＋(ｒ３×ｃ３－ｉ３×ｓ３)]＋ｊ[ｉ０＋(ｉ１×ｃ１＋ｒ１×ｓ１)＋(ｉ２×ｃ２＋ｒ２×ｓ２)＋(ｉ３×ｃ３＋ｒ３×ｓ３)] 　（４）