基于FPGA的快速傅立叶变换

1、基于FPGA的快速傅立叶变换作者：连冰宫丰奎张力李兵兵文章来源：国外电子元器件摘要：在对FFT（快速傅立叶变换）算法进行研究的基础上，描述了用FPGA实现FFT的方法，并对其中的整体结构、蝶形单元及性能等进行了分析。整体结构一般情况下，点的傅立叶变换对为：其中，( )。()和()都为复数。与之相对的快速傅立叶变换有很多种,如(时域抽取法)、（频域抽取法）、和等。对于傅立叶变换，算法可导出和算法。本文运用的基本思想是算法，即将高点数的傅立叶变换通过多重低点数傅立叶变换来实现。虽然与有差别，但由于它们在本质上都是一种基于标号分解的算法，故在运算量和算法复杂性等方面完全一样，而没有性能上的优劣之分，

2、所以可以根据需要任取其中一种，本文主要以方法为对象来讨论。点的运算表达式为：式中，()()(，)其中和可取,和可取,。由式（）可知，傅立叶变换可由的傅立叶变换构成。同理，傅立叶变换可由的傅立叶变换构成。而傅立叶变换可由的傅立叶变换构成。的傅立叶变换可进一步由的傅立叶变换构成，归根结底，整个傅立叶变换可由基、基的傅立叶变换构成。的可以通过个基和个基变换来实现；的变换可通过个基变换来实现；的可以通过个基和个基变换来实现。也就是说：的基本结构可由基模块、复数乘法器、存储单元和存储器控制模块构成，其整体结构如图所示。图中，用来存储输入数据、运算过程中的中间结果以及运算完成后的数据，用来存储旋转因子表。

3、蝶形运算单元即为基模块，控制模块可用于产生控制时序及地址信号，以控制中间运算过程及最后输出结果。蝶形运算器的实现基和基的信号流如图所示。图中，若，是要进行变换的信号，为旋转因子，将其分别代入图中的基蝶形运算单元，则有：()()()()()() （）()()()()()() (）()()()()()() （）()()()()()() （）而在基蝶形中，和的值均为，这样，将，和的表达式代入图中的基运算的四个等式中，则有：()() （） ()() （）()() （）()() （）在上述式（）（）中有很多类同项，如和等，它们仅仅是加减号的不同，其结构和运算均类似，这就为简化电路提供了可能。同时，在蝶形

4、运算中，复数乘法可以由实数乘法以一定的格式来表示，这也为设计复数乘法器提供了一种实现的途径。以基为例，在其运算单元中，实际上只需做三个复数乘法运算，即只须计算、和的值即可，这样在一个基蝶形单元里面，最多只需要个复数乘法器就可以了。在实际过程中，在不提高时钟频率下，只要将时序控制好便可利用流水线（）技术并只用一个复数乘法器就可完成这三个复数乘法，大大节省了硬件资源。的地址变换后输出的结果通常为一特定的倒序,因此，几级变换后对地址的控制必须准确无误。倒序的规律是和分解的方式密切相关的，以基为例，其基本倒序规则如下：基可以用三级基变换来表示，则其输入顺序则可用二进制序列（ ）来表示，变换结束后，其顺

5、序将变为（ ），如： ，即输入顺序为，输出时顺序变为。更进一步，对于基的变换，可由，等形式来构成，相对于不同的分解形式，往往会有不同的倒序方式。以为例，其输入顺序可以用二进制序列（ ）来表示变换结束后，其顺序可变为（ ）（ ），如： 。即输入顺序为，输出时顺序变为。在的傅立叶变换中，由于要经过多次的基和基运算，因此，从每次运算完成后到进入下一次运算前，应对运算的结果进行倒序，以保证运算的正确性。旋转因子点傅立叶变换的旋转因子有着明显的周期性和对称性。其周期性表现为：FFT之所以可使运算效率得到提高，就是利用之所以可使运算效率得到提高，就是利用了对称性和周期性把长序列的逐级分解成几个序列的，并最

6、终以短点数变换来实现长点数变换。根据旋转因子的对称性和周期性，在利用存储旋转因子时，可以只存储旋转因子表的一部分，而在读出时增加读出地址及符号的控制，这样可以正确实现。因此,充分利用旋转因子的性质，可节省以上存储单元。实际上，由于旋转因子可分解为正、余弦函数的组合，故中存的值为正、余弦函数值的组合。对的傅立叶变换来说，只是对一个周期进行不同的分割。由于变换的旋转因子包括了的所有因子，因此，实现时只要对读的地址进行控制，即可实现变换的通用。存储器的控制因是为时序电路而设计的，因此，控制信号要包括时序的控制信号及存储器的读写地址，并产生各种辅助的指示信号。同时在计算模块的内部，为保证高速，所有的乘

7、法器都须始终保持较高的利用率。这意味着在每一个时钟来临时都要向这些单元输入新的操作数，而这一切都需要控制信号的紧密配合。为了实现的流形运算，在运算的同时，存储器也要接收数据。这可以采用乒乓的方法来完成。这种方式决定了实现运算的最大时间。对于操作，其接收时间为个数据周期，这样的最大运算时间就是个数据周期。另外，由于输入数据是以一定的时钟为周期依次输入的，故在进行内部运算时，可以用较高的内部时钟进行运算，然后再存入依次输出。为节省资源，可对存储数据采用原址读出原址写入的方法，即在进行下一级变换的同时，首先应将结果回写到读出数据的存贮器中；而对于，则应采用与运算的数据相对应的方法来读出存储器中旋转因

8、子的值。在傅立叶变换中，要实现通用性，控制器是最主要的模块。、变换具有不同的内部运算时间和存储器地址，在设计中，针对不同的点数应设计不同的存储器存取地址，同时，在完成变换后，还要对开始输出有用信号的时刻进行指示。硬件的选择本设计的硬件实现选用的是现场可编程门阵列()来满足较高速度的需要。本系统在设计时选用的是公司的芯片，该芯片中包含有单元，可以完成较为耗费资源的乘法器单元。同时，该器件也包含有大量存储单元，从而可保证旋转因子的精度。除了一些专用引脚外，上几乎所有的引脚均可供用户使用，这使得信号处理方案具有非常好的带宽。大量的引脚和多块存储器可使设计获得优越的并行处理性能。其独立的存储块可作为输入工作存储区和结果的缓存区，这使得可与计算同时进行。在实现的时间方面，该设计能在个时钟周期内完成一个点的。若采用的输入时钟，其变换时间在左右。而由于最新的使用了互连技术，故可在以下频率稳定地工作，同时，的实现时间也可以大大缩小。运算结果的精度与输入数据的位数及运算过程中的位数有关，同时和数据的表示形式也有很大关系。一般来说，浮点方