cpu进行运算和处理的最有效长度 长度为2n的FFT运算基实现

　　摘要:大点数FFT运算是数字信号处理中关键技术环节,本文提出一种大点数FFT运算基的实现,该实现是根据[1]中所提出的算法,结合寄存器阵列模块和重排序模块,实现FFT运算基模块内部的数据传输和模式切换,以基4与基2为模块中的基本运算单元构成大点数的FFT运算基,在控制电路配合下实现快速傅里叶变换。该实现通过面向寄存器级的Simulink仿真模型,验证本文所设计模块功能的正确性和可行性,为基于大点数的FFT运算指出了一种实现方法。
　　关键词:数字信号处理;寄存器阵列模块;重排序模块;Simulink
　　
　　The Implement of 2n―Point FFT Module Radix
　　
　　ZHANG Si-wei, HU Jian-hao
　　(National Key Laboratory of Science and Technology on Communications the University
　　of Electronic Science and Technology of China, Chengdu, 610054, China)
　　
　　Abstract: The high radix FFT is the key calculation for the digital signal processing. In this paper we give an implementation for the high radix FFT, which is based on the algorithm provided in [1]. In the proposed implementation architecture register array module and reorder module are adopted to achieve the data transportation and calculation mode switching. We use radix-4 and radix-2 FFT as the basic calculation units to construct the high radix FFT with the traditional Fourier Transform algorithm. This implementation is validated with the register level simulation model, which is established with Matlab Simulink. The simulation results show that the proposed scheme is efficient for practical systems.
　　Key words: digital signal processing, register array module, reorder module, Simulink
　　
　　1引言
　　
　　 傅里叶变换是数字信号处理系统中最基本、最重要的运算,当傅里叶变换的长度为2n时,根据Cooley的算法可以实现快速傅里叶变换(FFT)[2]。FFT可以采用基2、基4、基8等流水的形式实现长度为L的FFT。研究表明采用高阶的基,如基8和基16可以有效提高FFT的处理速度。对于变长度且长度为2n形式,可以将L分解为2、4、8等元素幂次相乘的形式,根据文献[1]所提出算法,可以通过对基2、基4和基8FFT运算单元的迭代操作完成长度为L的FFT。同时根据[1]的分析,在进行分解时尽可能使高阶基的幂次最大化,可以有效降低处理时延。
　　本文介绍一种以基2和基4FFT为基本运算单元,配合寄存器阵列和排序单元,可以高效地完成基8的FFT。同时本文所介绍的结构通过配置可以灵活地实现基2、基4和基8的FFT;因此本文提出实现方法可以在控制电路的配合下,在迭代结构中[1]灵活地完成变长度的FFT。根据实现的运算结构,在运算过程中需要数据按照特定顺序和方式传输,并且满足当前运算模式控制的需要。因此数据传输,模式切换以及这两者的结合控制整个运算过程是本实现中FFT运算基执行过程的关键,也是本实现要解决的问题。本文还利用Matlab Simulink 工具为所提出实现方法搭建了寄存器级的仿真平台,通过仿真证明了所提出实现结构的正确性和有效性。
　　本文结构如下:在第2节中介绍FFT运算基模块的结构和各个子模块结构和功能,其中着重介绍寄存器矩阵模块和重排序模块的设计思路以及功能和结构的实现;在第3节中对基于本实现的实例进行性能和资源开销分析;在第4节中全文总结和展望。
　　
　　2FFT运算基模块结构实现
　　
　　根据本实现的变长度FFT的长度分解公式,本文提出的FFT运算基模块能计算8点和4点的傅里叶变换。为了使模块结构、运算和控制简单化,本实现中将8点傅里叶变换用一个4点傅里叶变换和一个2点傅里叶变换运算单元完成。依照[1]的规定,若FFT变换长度为2的奇次方,则先进行8点傅里叶变换,因此外部数据进入FFT运算基模块后,先进入4点傅里叶变换子模块,然后根据当前运算模式将数据通过寄存器矩阵模块和数据调整模块进入2点傅里叶变换子模块,并根据当前的运算模式判断如何处理所收到数据,最后数据送入重排序模块进行最后输出数据的顺序调整并输出,在重排序模块中通过运算模式选择以何种顺序输出一组运算结果,该运算过程一直进行,直到一次迭代完成。若变换长度为2的偶次方则根据当前运算模式只进行4点傅里叶变换,直到一次迭代完成。各个子模块结合当前的模式控制保证输出数据正确,结果顺序与传统的FFT运算结果顺序一致,在第3节中基于本实现的傅里叶变换实例证明了整个结构的正确性。根据以上的运算流程,FFT运算基模块的内部结构如下图1所示。
　　 根据图1中的结构,数据流动从左至右。传输过程中经过了4点傅里叶变换模块,寄存器阵列模块,数据调整模块,2点傅里叶变换模块和重排序模块。其中4点傅里叶变换子模块内部结构遵循传统傅里叶变换运算,由于模块中处理的数据为复数,因此在其内部分为实虚两部进行运算,在4点傅里叶变换子模块中共需要十六个两输入加法器实现运算。当运算模式为8点傅里叶变换时,为了保证输出数据顺序正确需要通过寄存器阵列模块进行数据传输模式调整,数据在一个周期内(八个数据的输入至输出为一个周期)的数据流动状态图如下图2所示,运算模式为4点傅里叶变换,输入数据顺序不调整经过两个单位时间延时送出。
　　图2为运算模式为8点傅里叶变换的六个状态(状态值为图上方括号内数字,一个状态对应于一个时钟)的数据流动,共接收24个数据,其中1和2状态数据从左至右传输,3和4状态数据从下至上传输,后面状态的传输方向与此类似,且在数据从左至右传输状态下的第一列和第二列数据分别向第二三列和第四列传输,从下至上传输状态与其类似,第四行和第三行数据分别向第二三行和第一行传输。根据图2,寄存器阵列模块从第三个时钟开始,每个时钟都向模块外传送数据,保证数据传输的高效性。数据流动过程中,该模块抽取出一个周期内第一组运算数据(八个数)的前两个1、2以及第二组运算数据的前两个5、6,为后面模块完成8点傅里叶变换提供合符要求的数据。按照图2中数据传输的模型,可以得到本实现中寄存器阵列模块内部结构简图如下图3所示。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文 　　根据图3并结合图2中的数据流动状态图,该模块相当于两个单位时间的数据延迟器,在延迟传输过程中对输入的数据进行传输模式调整以便后面模块使用。其中主要器件为十二个用于存储数据的寄存器以及用于控制信号延迟的寄存器和多个二选一开关组成的传输控制结构,其控制信号是FFT运算基的运算模式信号,它控制所有的传输控制结构按照正确的顺序抽取输入数据并输出。为了保证运算过程中运算模式切换准确进行,需要为部分控制信号加上与寄存器阵列模块等同的延迟寄存器,保证前一个模式下的所有数据都传送完毕。该模块在8点离散傅里叶变换的模式下,对数据传输模式调整,4点离散傅里叶变换的情况只进行两个单位时间的延迟,数据传输模式没有影响(图3中“运算模式为4点傅里叶变换的数据传输通道”所示)。寄存器阵列模块的输出数据流进入数据调整模块,以基4的傅里叶变换计算8点FFT需要对4点傅里叶变换的结果进行调整后才进行2点傅里叶变换,该模块内部由运算模式信号控制其输入数据是否需要进行调整,若是4点傅里叶变换模式,数据流通过该模块不做任何处理。本实现中的2点离散傅里叶变换子模块结构遵循传统傅里叶变换运算,运算模式信号控制其是否对输入数据进行处理。最后一个子模块为重排序模块,数据流进入该模块内时,根据当前运算模式对数据输出顺序进行处理。在一个周期内该模块的数据流动状态图如下图4所示。
　　 根据图4的数据流状态,4点傅里叶变换的模式下输入数据顺序不调整,8点傅里叶变换模式下对输入数据的顺序进行调整,8点FFT的输出结果顺序为1、3、5、7、2、4、6、8,以保证本实现模块数据输出顺序与传统8点傅里叶变换结果顺序一致。按照图4中数据排序的模型,可以得到本实现中重排序模块内部结构简图如下图5所示。
　　 根据图5并结合图4的数据流动状态图,该模块相当于一个单位时间的数据延迟器,在延迟过程中对输入数据进行顺序调整后输出,与寄存器阵列模块一样,通过数据寄存器以及二选一开关实现数据顺序重排,运算模式信号控制所有开关。
　　以上各个子模块按照图1中的结构相连,并在运算模式信号控制下实现长度能分解为基8和基4幂次方的FFT的迭代运算。
　　
　　3FFT运算基模块性能分析
　　
　　根据第二节介绍的各子模块的结构以及图1所示的连接关系,运用Simulink搭建寄存器级的仿真模型,并为其加入信源进行仿真,验证本实现功能和可行性,分析实例的性能和资源开销。实例中进行基8,基4以及基8向基4切换的定点傅里叶变换,其中数据位宽为十八位,符号位一位,小数位十五位。以下图6为实例中基8的定点傅里叶变换结果与基于传统算法的8点浮点傅里叶变换结果差值信噪比,图7为实例中基4的定点傅里叶变换结果与基于传统算法的4点浮点傅里叶变换结果差值信噪比,图8为运算模式切换过程的结果,基8向基4切换的定点傅里叶变换结果与基于传统算法8点浮点傅里叶变换向4点浮点傅里叶变换切换的结果的差值信噪比,本实现规定先进行基8的傅里叶变换再进行基4的傅里叶变换,其中基于传统算法的8点浮点傅里叶变换向4点浮点傅里叶变换切换过程由与本实例中相同的运算模式信号控制。三图中纵轴为定点结果与浮点结果差值信噪比,单位为dB,横轴为数据个数,Data1至Data8(或Data4)对应基8(或基4)运算结果中数值个数,基8(或8点)傅里叶变换的结果有八个值,基4(或4点)的结果有四个值。
　　 图6、图7、图8中的差值信噪比都在-75 dB以下,图6中的误差在Data2、Data4、Data6、Data8上扬,是由于在本实现中基8的傅里叶变换是由基4的傅里叶变换结果通过数据调整再进行基2的傅里叶变换得到,这些数据在数据调整中乘以定点化的旋转因子引入误差,旋转因子位宽为十八位,符号位一位,小数位十七位。图7中基4傅里叶变换结果的误差信噪比没有出现类似图6上扬的情况,因为4点傅里叶变换在运算过程中不需要调整数据。图8中为基8向基4切换过程的傅里叶变换结果的误差信噪比,误差上扬原因与图6类似。与图6相比,产生上扬误差的数据少一些,基8切换为基4傅里叶变换后,不再需要数据调整,上扬误差降至平均值,由于Data5、Data6、Data7、Data8在基4傅里叶变换模式下没有数据,因此它们部分误差信噪比缺失。根据以上三图,证明本实例中模块在基8定点傅里叶变换运算模式下、基4定点傅里叶变换运算模式下和基8向基4切换过程的结果与相对应的传统算法浮点傅里叶变换结果的差值信噪比都在可接受范围内。证明模块功能正确,本实现可行。
　　本实例中运算数据是复数形式,运算过程共需40个十八位加法器,14个用于数据调整模块的移位寄存器(十八位),16个用于寄存器阵列模块和重排序模块的十八位寄存器,31个用于数据选择的十八位二选一开关以及少量用于处理运算模式控制信号的寄存器和二选一开关(忽略),相应的基于传统算法的8点傅里叶变换需要32个十八位乘法器,112个十八位加法器。一个十八位加法器需要198个基本单元门(基本单元门为两输入与非门,两输入或非门),一个十八位乘法器(优化结构)需要3564个基本单元门,一个十八位寄存器需要72个基本单元门,一个十八位二选一开关需要54个基本单元门。
　　表1中器件位宽为十八位,其中数据证明本实现达到了节约硬件资源开销的目的。
　　
　　4总结和展望
　　
　　本文针对[1]中所提出的算法设计其实现。将数据寄存器,开关和运算单元相结合,通过控制信号控制模块运行过程,实现所设计模块所需功能。该实现为数字信号处理领域的数据流动控制方面列举了一个可行、有效、节约硬件资源开销的设计方法。其中寄存器阵列模块和重排序模块的设计思想可以运用在其它领域中数据的传输和排序处理,实现高效、准确的数据传输模式。
　　
　　参考文献
　　[1] Jienan Chen and JianHao hu. A Variable Length FFT Processor for LTE Applications. IEEE Conf. ICCTA , 2009.
　　(下转第75页)
　　[2] C. Cheng and K. K. Parhi. Low-Cost Fast VLSI Algorithm for Discrete Fourier Transform. IEEE Trans. Circuit Syst. I, Reg. Papers, 2007, 54(4): 791-806.
　　
　　作者简介
　　张思为,硕士生,研究方向:通信与信息系统;
　　胡剑浩,教授,博士生导师,研究方向:无线通信和VLSI的研究。
本文为全文原貌 未安装PDF浏览器用户请先下载安装 原版全文