资料介绍
EDAPLD论文
基于FPGA的快速傅立叶变换
摘要：在对FFT（快速傅立叶变换）算法进行研究的基础上，描述了用FPGA实现FFT的方
法，并对其中的整体结构、蝶形单元及性能等进行了分析。
关键词：FPGA FFT
傅立叶变换是数字信号处理中的基本操作，广泛应用于表述及分析离散时域信号领域
。但由于其运算量与变换点数Ｎ的平方成正比关系，因此，在Ｎ较大时，直接应用ＤＦ
Ｔ算法进行谱变换是不切合实际的。然而，快速傅立叶变换技术的出现使情况发生了根
本性的变化。本文主要描述了采用ＦＰＧＡ来实现２ｋ／４ｋ／８ｋ点ＦＦＴ的设计方
法。
１ 整体结构
一般情况下，Ｎ点的傅立叶变换对为：
其中，ＷＮ＝ｅｘｐ(－２
ｐｉ／Ｎ)。Ｘ(ｋ)和ｘ(ｎ)都为复数。与之相对的快速傅立叶变换有很多种,如ＤＩＴ
(时域抽取法)、ＤＩＦ（频域抽取法）、Ｃｏｏｌｅｙ－Ｔｕｋｅｙ和Ｗｉｎｏｇｒａ
ｄ等。对于２ｎ傅立叶变换，Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法可导出ＤＩＴ和ＤＩＦ算
法。本文运用的基本思想是Ｃｏｏｌｅｙ－Ｔｕｋｅｙ算法，即将高点数的傅立叶变换
通过多重低点数傅立叶变换来实现。虽然ＤＩＴ与ＤＩＦ有差别，但由于它们在本质上
都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能
上的优劣之分，所以可以根据需要任取其中一种，本文主要以ＤＩＴ方法为对象来讨论
。
Ｎ＝８１９２点ＤＦＴ的运算表达式为：
式中，ｍ＝(４ｎ１＋ｎ２)(２０４８ｋ１＋ｋ２)(ｎ＝４ｎ１＋ｎ２，ｋ＝２０４
８ｋ１＋ｋ２)其中ｎ１和ｋ２可取０,１,．．．,２０４７,ｋ１和ｎ２可取０,１,２,
３。
由式（３）可知，８ｋ傅立叶变换可由４×２ｋ的傅立叶变换构成。同理，４ｋ傅立
叶变换可由２×２ｋ的傅立叶变换构成。而２ｋ傅立叶变换可由１２８×１６的傅立叶变
换构成。１２８的傅立叶变换可进一步由１
我要上传