FFT处理器

2025-01-17

FFT处理器（精选8篇）

FFT处理器篇1

0 引言

海洋面积占地球总面积的71% ,我国是海洋大国,对于勘探海洋内蕴涵的石油等资源,声呐系统起着关键作用。本文主要通过CORDIC算法和基4时域FFT算法,设计并实现了声呐系统的核心———FFT处理器。

1 CORDIC 算法

1. 1 CORDIC 算法原理

1959年J. Volder提出了CORDIC算法,即标旋转数字计算机方法,并将其首先应用于导航系统。它通过移位和加减运算代替乘法运算,简单地说就是一种逼近方法。通过迭代方式完成角度的旋转, 最终得到结果,可以计算三角函数,双曲线,指数,对数的运算。1974年J. Walther用它研究了一种能计算出多种超越函数的统一算法。算法原理如图1所示。

1. 2 CORDIC 算法结构

实现CORDIC算法的硬件结构主要通过流水线、单步循环迭代和粒度迭代三种结构来实现,本文主要采用流水线结构。流水线结构是基于循环迭代结构,将其展开这样就能使CORDIC算法满足高速要求。如图2所示。

流水线CORDIC算法结构,也称为高速流水线结构。是将运算单元分成很多组,在每组中加入流水线寄存器,每组数据计算结束后,放入寄存器中, 寄存器的作用是临时存储数据。插入了寄存器的单步迭代结构可以同时工作,所以加快了计算的速度, 因为它可以同一时间输出计算结果,所以它只需要一个时钟周期就可以完成一次运算。

2 FFT 算法

2. 1 FFT 算法原理

FFT是离散傅氏变换 ( DFT ) 的快速算法 ,称作快速傅里叶变换。它是傅里叶变换在时域和频域上都呈离散的形式,根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅里叶变换的算法进行改进获得的。其中包含基2、基4、基8蝶形算法等等。

2. 2 几种蝶形算法分析

通过比较各种基算法的实数乘法和实数加法, 可以得到运算量比较表,如表1所示。

比较三种常用结构,基2结构的运算量最大, 基8结构最小,在FFT运算过程中,运算量的减少往往伴随着硬件的消耗增加,所以达到运算量和成本的平衡成为关键。由于本文要求FFT处理器能处理水声信号的要求,即速度快,运算量少,硬件的复杂度不能太高,所以选用了基4结构来实现FFT处理器。

2. 3 FFT 处理器硬件实现结构

作为一款优秀的FFT处理器,算法的选择很重要,同时硬件结构也是决定运算速度的关键。FFT处理器的硬件实现结构主要有三种 : 全并行结构、流水结构、递归结构等。从三种结构的选择上来说,就是运算速度和硬件消耗的比较,综合比较上述三种结构,运算速度和硬件消耗成正比,即速度越快硬件消耗越大,速度越慢硬件消耗越小。本文设计的FFT处理器主要针对于水声系统,即对速度和硬件消耗都有一定的要求, 所以采用了流水线结构。流水线结构的主要特点是逐级顺序处理,事实上是一种串行处理结构,如图3所示。

流水线结构的运算方式是当数据输入到单元RAM中后,运算结果直接输入到下一级,起初的RAM会再一次接收新的数据,这样反复操作,直至所有数据计算完成后,再开始下一级的运算。

3 总体模块图

图4为FFT处理器整体结构图,它是一个FFT处理器的外部结构图,包含8个接口。考虑到FFT处理器都是以负数的形式运算,故输出为两个接口即实部与虚部,输入也相应地对应两个接口,数据位宽是16位。其中Reset接口为模块复位键, CLK接口为模块时钟输入键,Enable接口为模块使能键。

4 系统集成

本文设计的FFT处理器设计在水声系统中的声呐波束形成器上,针对声呐波束形成器的特点设计了整体结构,如图5所示。

各等间距直线阵输出阵列信号,即阵元数据,输入到A/D转换器,模拟信号转换成数字信号后,输入到FFT处理器中,由于数据位宽为16位,也就是1024点数字信号,FFT处理器将其进行基4蝶形运算,最后将得到的频域信号输入到CRT显示器,并显示出来,或者输送到下一级处理单元。

5 结果分析

首先分析了CORDIC算法和FFT算法,比较了各个算法在速度上和硬件消耗上的优缺点,又针对应用于水声系统的FFT处理器比较了各个硬件结构的区别,最终选择了基于流水线结构的FFT处理器。在每一级运算处理中,流水线结构都能够满足运算的需求,且提高了运算速度,达到了预期目标。

6 结束语

在声呐波束形成器中,本文设计的FFT处理器基本达到了数据处理的要求,但还存在种种不足。由于采用CORDIC算法,在运算精度上还不够高,可以说到了一定的瓶颈,影响了FFT处理器的品质。在结构的选择上虽然综合考虑了运算速度和硬件消耗,但就声呐系统而言,速度仍需要加快,硬件消耗仍需要减少,尤其是占用了很多硬件资源导致了系统成本的上升。这是下一步研究的方向。

FFT处理器篇2

作业要求：

1、利用matlab编程计算教材中59页例2-2的结果，并画出频谱图。

2、已知有限长序列x(n)＝［7，6，5，4，3，2］，求x(n)的DFT和IDFT。要求：①画出序列傅里叶变换对应的|X(k)|和arg［X(k)］的图形。

②画出原信号与傅里叶逆变换IDFT［X(k)］的图形进行比较。

3、实验教材第11页第3题。

4、已知一个周期序列x(k)cos(

8k

3)0.5cos(

4k)，利用FFT计算其频谱。

FFT处理器篇3

DFT作为DSP领域中时域和频域转换的基本运算,存在运算量太大的缺点,导致其应用受到局限。DFT快速算法FFT的提出,简化了DFT的运算过程[1],使其在实时信号处理领域中得到广泛应用。FFT实现的方法包括软件实现和硬件实现两种。采用软件实现FFT的方法存在计算慢,实现过程复杂等缺点,所以目前比较流行的方式是采用硬件实现FFT。硬件实现的具体方法可以分为ASIC方法、FPGA方法、DSP方法和通用处理机方法等。

FPGA是20世纪80年代中期出现的一种新的电子设计自动化技术,具有集成度高,逻辑实现能力强,设计灵活等优势。在FPGA上实现数字信号处理,即用纯数字逻辑进行DSP模块设计,为高速数字信号处理算法提供了实现途径[2]。在此,采用FPGA方法设计64点FFT处理器[3]。

现有的FFT模块可以对多点数据进行运算,但是存在运算周期长,结构复杂,硬件资源耗费大等缺陷。采用64点FFT可以通过优化结构来快速处理多点数数据。目前设计的64点FFT处理器主要采用以专用处理单元取代常规FFT处理单元的方法[4],或者按照固定几何结构设计FFT处理器的方法[5]。这里所介绍的64点FFT处理器是在固定几何结构设计方法的基础上加以改进,将输入的64点数据均匀分成8组,并行输入给FFT运算单元,进行FFT运算。通过对蝶形运算单元进行优化设计,所设计的64点FFT处理器模块较之以往的FFT模块,节省了硬件资源,提高了运算效率。通过ModelSim仿真实验证明,在外部工作时钟频率为40 MHz下,对随机生成的序列进行64点FFT运算处理,运算时间为10 μs,缩短了现有FFT模块的运算时间。

1 按频率抽取的基——4FFT算法原理

对于序列长度为N(N为2的整数次幂)的FFT算法主要有基-2 FFT和基-4 FFT两种。计算一次基-2 FFT需要二次复乘和两次复加;计算一次基-4 FFT需要三次复乘和八次复加。从运算次数上看,基-2 FFT较为简单,但是因为基-2 FFT的复数运算较为复杂,所以在硬件实现上反而要比基-4 FFT占用的资源更多。为了满足对数据高速处理的要求,在此选择在FPGA上实现基-4 FFT的算法。

根据定义,对于长度为N的序列x(N)(0≤N≤N-1),它的DFT可表示为:

$\begin{array}{l} X (k) = D F Τ [x (n)] = \sum_{n = 0}^{Ν - 1} X (n) W_{Ν}^{k n} \\ k = 0, 1, 2, \dots, Ν - 1 (1) \end{array}$

式中:W $_{Ν}^{n k}$ =e-j2πNnk称为旋转因子。直接计算DFT,需要的计算量为N2次复乘和N(N-1)次复加。当N很大时,运算量相当大,无法满足实时处理的要求。因此利用旋转因子的对称性、周期性和可约性,把长序列分解成为短序列来进行快速傅里叶变换[1]。

由式(1)可以得到4个子序列:

$\begin{array}{l} A = X (k) = \sum_{m = 0}^{(Ν / 4) - 1} x (4 m) W_{Ν}^{4 m k} \\ B = X (k + 1) = \sum_{m = 0}^{(Ν / 4) - 1} x (4 m + 1) W_{Ν}^{(4 m + 1) k} \\ C = X (k + 2) = \sum_{m = 0}^{(Ν / 4) - 1} x (4 m + 2) W_{Ν}^{(4 m + 2) k} \\ D = X (k + 3) = \sum_{m = 0}^{(Ν / 4) - 1} x (4 m + 3) W_{Ν}^{(4 m + 3) k} \end{array} (2)$

利用旋转因子W $_{Ν}^{n k}$ 的特性,如:W $_{4}^{0}$ =1,W $_{4}^{1}$ =-j,W24=-1,W $_{4}^{3}$ =j,将A,B,C,D作为复数操作数进行运算,由式(2)可得简化计算式:

$[\begin{matrix} X (k) \\ X (k + 1) \\ X (k + 2) \\ X (k + 3) \end{matrix}] = [\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & - j & 1 & j \\ 1 & - 1 & 1 & - 1 \\ 1 & j & - 1 & - j \end{matrix}] [\begin{matrix} A \\ B W_{Ν}^{k} \\ C W_{Ν}^{2 k} \\ D W_{Ν}^{3 k} \end{matrix}] (3)$

式(3)就是在FPGA上实现基-4 FFT算法的基本运算法则。

不同于以往的基-4 FFT算法,这里是将输入的64点数据以8位输入数据为一组,共分成8组的方式输入给FFT运算单元进行FFT运算的。完整的FFT蝶形运算共分6级,经历196个循环状态。将来自存储单元的数据输入到FFT运算单元中,前三级是按8位1组的方法,分为8组进行运算;后三级是将前三级运算所得到的中间数据送入运算单元进行运算。经过FFT运算后,将所得到运算结果写入存储单元中保存。结果以倒位序方式输出,需要经过调整位序变换成为自然顺序输出。

2 FFT运算器设计

2.1 系统的整体结构

一个完整的FFT运算单元应该包括以下几个组成部分:

全局控制单元包括控制器和地址产生单元,用于调控整个FFT运算系统,生成蝶形运算单元以及其他子单元所需的地址,控制各子单元时序,保证其正常有序地工作;

蝶形运算器单元由蝶形运算器和旋转因子存储单元(ROM)组成,负责将送入的输入数据进行蝶形运算,是FFT运算器的核心单元;

存储寄存器单元采用两个RAM乒乓通信,通过通信接口单元接收总线控制信号,负责存储输入数据、中间数据和运算所得最终结果。

系统整体框图如图1所示。

2.2 各功能单元介绍

(1) 控制单元。

控制单元由控制器和地址总线组成。地址产生单元提供各个功能单元所需要的地址,保证数据存储、读写的顺利进行。在此,采用三位二进制编码来定义每个子单元的地址,并将所得的地址汇总,生成地址图表。由于每个单元模块的地址是惟一的,这就确保了在同一时刻、同一存储单元只能对数据进行单向通信,避免数据间的相互干扰,提高了精度。在时钟信号的控制下,控制器发出控制信号,控制整个FFT运算单元FFT运算。此外,系统中还添加一个复位信号RST。在此信号的激励下,FFT运算单元复位,并在下一时钟信号来临时,重新记录输入数据,开始新的64点FFT运算。

(2) 蝶形运算单元。

蝶形运算单元是实现FFT算法最为重要的部分[6]。蝶形运算主要有两种实现方式:传统的蝶形运算通常以输入倒位序,输出自然顺序,输出数据采用同址运算的方式进行存储,以节省存储单元空间,但是由于这种方式每级蝶形运算的计算单元都是变换位序的,从具体操作上难以实现,不便于扩展;另一种运算是采用输入自然顺序,输出倒位序的方式,这种方式中每级运算的计算单元都是固定的,实现上比较容易,只要对不同级的蝶形运算输入不同的旋转因子,即改变相对应旋转因子ROM的地址,就可以实现扩展[7]。

旋转因子ROM能储存固定地址的旋转因子,给蝶形运算提供所需的乘积项。旋转因子ROM在运算系统中实际上就是用于存放sin和cos的值。三角函数在第二、三、四象限的函数值可以通过第一象限的函数值转化得来,所以对于每一级运算所需要的旋转因子都可以从旋转因子表中得到,无需另外添加存储单元。因此,系统只是在ROM单元中存储第一级的旋转因子数据,其他的旋转因子通过转换得到,从而可节省存储单元ROMR的资源[8]。

(3) 存储单元。

FFT存储单元采用两个并行的双口RAM“乒乓操作”的设计方法。“乒乓操作”的原理是在时钟和控制信号的控制下,数据流在两个RAM之间交替读写。按此方式,数据流不会产生延迟,从而提高存储效率[9]。输入数据先存入存储器中,再导入FFT处理器中,处理结束后写回存储器中。同时系统使用D触发器对原始信号进行延迟,每个D触发器延迟一个时钟周期,由4个周期组成,包括3个周期的FFT运算以及之后把运算结果回写给存储器所占用的1个周期。

每个输入数据的长度是32位(实部为16位,虚部为16位),并行输入给存储器单元。在全局控制单元的调控下,从存储单元读取的输入数据经过判别后,进入蝶形运算单元,与旋转因子表中相应位置的旋转因子乘积运算后得出结果,将所得的输出结果经过判别后,写入RAM1中,同时,前一个时钟周期所得的运算结果由RAM2输出[10]。

通常数据格式的表示方法有浮点、定点和块浮点三种。浮点数是用两组固定的bit表示指数和小数,可以表示的动态范围比较大,不会出现数据的溢出问题,但是实现浮点运算的电路却很复杂;定点数是用固定的bit表示整数和小数,表示的动态范围比较小,容易出现数据溢出,但是其运算电路简单,运算速度也快;块浮点数是介于二者之间的数据表示方法。

在此采用定点数,为了保证数据不会溢出,从蝶形运算单元输出的运算结果被2整除,然后送入存储单元保存以备输出。

综合式(2)、式(3)两个部分,可以组合生成蝶形运算单元部分,蝶形运算单元结构内图如图2所示。

3 实验结果验证

这里的FFT运算器通过硬件描述语言VHDL代码进行编写,在ModelSimSE PLUS 6.1f环境下完成系统仿真,波形仿真如图3所示。

由波形仿真图可以看出,地址控制单元以3位二进制编码定义各子单元的地址,存储的数据在时序信号和地址总线单元控制下进行FFT运算。实验证明,当外部时钟频率为40 MHz时,可以对随机生成的64点序列进行FFT定点运算,运算时间为10 μs。

4 结语

这里的FFT运算器采用定点数处理,当处理浮点数时,系统存在处理异常、数据溢出等问题。但是由于可以迅速处理多点数信号, 因此在数字图像处理、实时通信系统的调试和解调等方面具有一定的实际意义,达到了使用FPGA实现DSP算法的目的。

本文在以下方面有所创新:

(1) 输入的64位数据以8位共8组的方式并行输入,将FFT运算流程分为6级,整个FFT运算过程清晰,结构合理,提高了运行效率。

(2) 使用2块双口RAM作为存储器,采用“乒乓操作”,在一个时钟周期内保证数据传递的单向性,减少了数据传输的冗余,提高了精度。

(3) 将整个FFT运算器进行模块化设计,在控制模块的调配下,各个子模块准确工作,保证了运算的可靠性。

参考文献

[1]程佩青.数字信号处理教程[M].2版.北京:清华大学出版社,2004.

[2]潘明海,刘英哲,于维双.一种基于FPGA实现的FFT结构[J].微计算机信息,2005(2):156-158.

[3]McAllister J,Woods R,Fischaber S,et al.Rapid Implemen-tation and Optimization of DSP Systems on FPGA-CentricHeterogeneous Platform[J].Journal of Systems Architec-ture,2007,53:511-523.

[4]侯卫华,郭晖,刘明峰,等.一款基于MVR-CORDIC的高速64点基-4FFT处理器[J].电子与封装,2008,8(5):22-25.

[5]赵梅,丁晓磊,朱恩.高速64点FFT芯片设计技术[J].电子工程师,2007,33(3):13-17.

[6]Sansaloni T,Perez-Pascual A,Valls J.Area-efficient FPGA-based FFT Processor[J].Electronics Letters,2003,39(19):1 369-1 370.

[7]田丰.邓建国,贾治华,等.FFT算法的一种FPGA实现[J].现代电子技术,2005,28(8):97-99.

[8]刘小明,吴曼青,洪一.基于FPGA的基-16 FFT模块的实现[J].合肥工业大学学报,2006,29(5):536-539.

[9]付宜利,王保国,靳保.基于FPGA的高速实时FFT处理器设计[J].微计算机信息,2007(2):194-195.

FFT处理器篇4

关键词：快速傅里叶变换,素因子算法,WFTA,流水线结构

地面数字电视广播经过多年的发展,取得了很多成果,目前已经提出的地面数字电视广播标准有:欧洲的DVB-T、美国的ATSC和日本的ISDB-T。在此背景下,2006年8月国家标准化管理委员会颁布了中国数字电视地面广播传输系统标准GB20600—2006[1],即中国的DTMB。DTMB系统包括单载波和多载波两种模式,其中,多载波传输模式采用时域同步正交频分复用(TDS-OFDM)作为核心技术。在DTMB接收机中,为实现TDS-OFDM技术,需要进行多次快速傅里叶变换(FFT),FFT处理器占据了大量的运算时间及资源,在很大程度上决定了DTMB接收机的功耗和复杂度,必须采用复用的方式来减少资源的占用。因此,寻求一种高速有效的3 780点FFT处理器,对整个DTMB接收机系统具有重要的现实意义。

1 3 780点FFT算法

目前,关于FFT的计算,主要是基于基-2和基-4的算法,对于基-2和基-4的FFT,算法仿真和硬件实现都已有很多种成熟的算法。3 780点FFT不是以2或4为基,所以在实现时主要有两种方法[2]:

一种方法是把3 780点通过内插得到4 096点,利用现已成熟的基-2和基-4的FFT算法计算4 096点FFT,再抽取得到3 780点的FFT。

另一种方法是综合利用混合基算法、素因子算法(PFA)和Winograd傅里叶变换算法(WFTA)算法将3 780分解实现3 780点FFT的计算。

第一种方法没有计算准确的3 780点FFT,必然会带来计算误差,且采样速率发生改变,将增加OFDM系统中同步的复杂度,故不予考虑。本文重点对后者进行研究。下面先对混合基算法、素因子算法及WFTA算法进行介绍,并在此基础上,给出本文3 780点FFT的算法设计。

1.1 混合基算法

混合基算法[3]是一种将长点数的DFT转换为短点数DFT组合的算法。设有N点序列经x(n),其傅里叶变换(DFT)定义[3]为

undefined

若N=N1×N2(N1,N2可有公因子),通过映射得到

式中:<>N表示对N取模运算。将式(1)转化为

undefined

式中:将x(n1,n2)和X(k1,k2)看作二维数组,对x(n1,n2)的行(列)作DFT得到X′,再对X′的列(行)作DFT就得到X(k)。其中N1,N2可以继续利用上述特征进行二层分解以减少运算量。

1.2 素因子算法(PFA)

当混合基算法[3]中的N1,N2互素时,可以通过选择n1,n2,k1,k2前的特殊系数消去旋转因子Wundefined,进一步简化FFT的计算。通过映射得到

undefined

当A,B,C,D满足下列条件时

undefined

式(3)转化为

undefined

与混合基算法相比,素因子算法减少了中间的旋转因子,不仅减少了运算量,也减少了旋转因子的存储。其中N1,N2可以继续利用上述特征进行二层分解以减少运算量。

1.3 Winograd小点数DFT算法

Winograd小点数DFT算法[3]是一种高效的DFT算法,其特点在于乘法次数显著减少。

一个N点DFT可以写成矩阵的形式为

X =WNx (7)

式中:WN是N×N的矩阵,第k行n列元素为Wundefined,x=[x(0)…x(N-1)]T,X=[X(0)…X(N-1)]T。 Winograd证明,当N∈{2,3,4,5,7,8,9,16}时,复数矩阵WN能以下列方式分解

W = CGB (8)

式中:G为对角矩阵,且对角线上元素为实数或纯虚数;B,C为平凡矩阵,仅由0,-1,1或一些小点数构成。

1.4 3 780点FFT算法

3 780可分解为3 780=7×5×3×3×3×2×2,在考虑到WFTA算法提出的16,9,8,7,5,4,3,2几种小点数DFT算法,且优先使用PFA的基础上,给出如图1所示的算法方案。

将3 780点先通过素因子算法分解成27×140点,再对27点和140点分别采用混合基算法和素因子算法分解成9×3点和7×5×4点,其中9,3,7,5,4点FFT利用WFTA算法计算。与文献[4,5,6,7]中的3 780=60×63的混合基算法分解方案比较,该方案可节省3 780个旋转因子的存储。

2 3 780点FFT处理器设计

DTMB系统采用TDS-OFDM技术,在长时延环境下,符号间干扰(ISI)会严重影响接收机性能。文献[8]提出了一种迭代门限检测(ITD)与判决反馈均衡(DFE)相结合的算法,该算法能够有效消除ISI干扰,获得精确的信道状态信息(CSI),同时复杂度也相对较低。然而迭代的检测CSI需要增加FFT/IFFT运算次数,FFT次数与迭代次数的关系为:NFFT=2+3×N迭代次数。采用1次迭代操作即要求5次FFT/IFFT运算,因此,FFT处理器在DTMB接收机中需消耗大量的运算时间及资源,必须寻求一种高速有效的3 780点FFT处理器,以复用的方式来减少逻辑资源的占用。

文献[4,5,6,7]均对DTMB系统中3 780点FFT处理器进行了详细介绍,其处理器内部WFTA运算单元均采用串行数据处理方式进行硬件设计,吞吐率只能满足1帧时间内的2次复用条件。为提高系统吞吐率,本文将对上述3 780点FFT处理器的实现结构进行改进,其内部WFTA单元改用并行处理方式,吞吐率提高为上述文献中处理器的4倍,实现了高速3 780点FFT处理器的设计目标。在硬件实现过程中,由于内部WFTA基本运算单元以不同并行度进行DFT运算,所以需要协调不同WFTA模块间的吞吐率。同时,为满足并行处理要求,存储模块需采用内存分组方式提高数据并行度。下面对该3 780点FFT处理器的设计进行详细描述。

2.1 3 780点FFT处理器结构

为了使3 780点FFT处理器在DTMB接收机系统中能充分复用,在第1.4节算法基础上,采用流水线结构进行3 780点FFT处理器的硬件设计,且为进一步提高系统吞吐率,其内部WFTA单元采用并行数据处理方式进行硬件实现。处理器结构如图2所示,其中1,9,7,4表示各单元的输入输出并行度。

3 780点FFT处理器内部27点FFT和140点FFT运算分时交替进行,矩阵转置模块不需要采用双缓存结构,只需要存储3 780个中间变换结果。输入、输出缓存模块则分别采用两组双口RAM,以乒乓操作方式实现数据缓存及顺序调整。下面对图2中各单元的设计依次进行详细介绍。

2.2 输入缓存单元

由于27点FFT模块以9路输入并行度进行DFT运算,所以输入缓存单元需要完成数据缓存、顺序调整及9路数据并行输出功能。为保证流水线处理的高速进行,输入缓存单元采用两组存储器进行乒乓存储操作,每组存储器结构如图3所示。

由1.2节可知,3 780=27×140时,一层分解采用PFA算法,相应的一层映射公式为

n=140n1 +27n2 ,n1 =0,1,…,26, n2 =0,1,…,139 (9)

又27=9×3,二层分解采用混合计算法,相应的二层映射公式为

n1 = m1 + 3m2 ,m1 = 0,1,2, m2 = 0,1,…,8 (10)

根据式(9)～(10),用Matlab对下标如何调整进行仿真,生成存储地址映射表,通过查表方式,将串行接收的数据存储到9个深度为420的存储器中,并可按地址累加的方式输出9路并行数据,送入27点FFT模块进行运算,以满足27点FFT模块的9点并行度处理要求。

2.3 27点FFT单元

27点FFT运算分9点FFT和3点FFT两级,由混合基算法实现9点FFT和3点FFT的级联,其实现结构如图4所示,其中9点和3点FFT采用第2.6节WFTA运算单元。

图4中Cache1以乒乓操作方式完成混合基算法所需要的整序[2]。9点和3点WFTA单元分别以9路和3路输入并行度进行DFT运算,为解决不同基WFTA单元间吞吐率的协调问题,内部同时采用3个3点WFTA单元,使整个27点FFT单元以9路数据并行度进行DFT运算。

2.4 140点FFT单元

140点FFT单元内部由素因子算法实现7点、5点和3点FFT的级联,其实现结构如图5所示,其中Cache2、Cache3以乒乓操作方式完成素因子算法所需要的整序[2],7点、5点和3点FFT采用第2.6节WFTA运算单元。

7点、5点和4点WFTA单元分别以7路、5路和4路的输入并行度进行DFT运算, 不同基WFTA单元间吞吐率的协调原则是,高并行度运算单元的处理速度同步于低并行度处理单元。以35=7×5为例,完成1次35点FFT运算,7点和5点WFTA单元各需5个和7个时钟周期,可通过控制信号,占用每7个时钟周期中的5个完成1次7点WFTA运算,使35点FFT的运算速度同步于5点WFTA单元。同理,140点FFT运算速度同步于4点WFTA单元。

2.5 输出缓存单元

该模块完成3 780点FFT结果存储及整序输出功能。为了匹配140点FFT单元的4路数据并行输出要求,内部采用4个深度为945的双口RAM,以地址累加的方式对输入数据进行缓存。为保证流水线处理的高速进行,输出缓存单元采用两组存储器进行乒乓存储操作,每组存储器结构如图6所示。

由1.2节可知,3 780=27×140时,一层分解采用PFA算法,相应的一层映射公式为

k=1 540k1 +2 241k2 ,k1 =0,1,…,26,k2 =0,1,…,139 (11)

又140=35×4,二层分解采用混合计算法,相应的二层映射公式为

k2 =36l1 +105l2 ,l1 =0,1,…,34,l2 =0,1,2,3 (12)

根据式(11)～(12),用Matlab对下标如何调整进行仿真,生成存储地址映射表,通过查表方式,将缓存数据以串行方式输出,实现3 780点FFT输出整序功能。

2.6 WFTA算法FFT单元

为了提高吞吐率,WFTA运算单元采用并行数据处理方式进行硬件实现。3,4,5,7,9点WFTA模块结构相似,以3点为例说明其实现过程。

N=3时,WFTA计算公式为

undefined

X=Wx,对W分解得X=CGBx,C,G,B分别为

undefined

3点WFTA信号流如图7所示。

其硬件结构如图8所示。

其中,D为寄存器,AC为累加器,B,G,C为矩阵系数产生器。

3 综合及分析

编写Verilog程序[9],输入复随机数据,采用Modelsim进行功能仿真,用ISE软件并选用Xilinx Virtex-5 XC5VLX330t芯片来进行综合。将1 000次仿真输出数据导入Matlab分析,当输入为10 bit数据,输出为18 bit数据时,系统信噪比可达69 dB,满足TDS_OFDM系统对信噪比的要求。在对信噪比有更高要求的应用场合,可以在WFTA运算模块后加入块浮点模块来提高处理精度。

文献[4,5,6,7]及本文处理器完成一次3 780点FFT运算所需时钟数Nclk如表1所示。其中,若3 780点FFT分1,2,…,n级计算,且各级并行度为vi(i=1,2,…,n),则有

undefined (17)

从表1可以看出,本文3 780点FFT处理器的吞吐率是文献[4,5,6,7]中处理器吞吐率的4.5倍。但是与文献[5]中处理器相比,该处理器所占逻辑资源是其1.5倍,即该设计的3 780点FFT处理器,是用高1.5倍的逻辑资源换取4.5倍的高吞吐率。

4 结束语

综合利用混合基算法、素因子算法及WFTA算法实现3 780点FFT运算,满足了系统的高计算精度要求;为提高系统吞吐率,在采用流水线结构进行硬件实现的基础上,其内部小点数WFTA单元采用并行数据处理方式进行硬件实现,使系统吞吐率提高为串行处理方式时的4.5倍。

参考文献

[1]GB20600—2006,数字电视地面广播传输系统帧结构、信道编码和调制[S].2006.

[2]杨旭霞,归琳,余松煜.3780点FFT处理器的研究[J].电视技术,2005,29(11):32-34.

[3]崔振,王永贺,门爱东.DMB-T系统中FFT模块的设计与实现[J].电视技术,2008,32(S1):6-7.

[4]YANG Zhixing,HU Yupeng,PAN Changyong,et al.Design of a 3780-point IFFT processor for TDS-OFDM[J].IEEE Trans.Broadcasting,2002,48(1):57-61.

[5]余飞.DTMB系统中3780点FFT处理器的算法设计及FPGA实现[D].武汉:武汉理工大学,2008.

[6]上海明波通信技术有限公司.3780点快速傅里叶变换处理器及运算控制方法:中国,200810043761.X[P].2010-03-10.

[7]复旦大学.流水线结构的3780点快速傅里叶变换处理器:中国,200710044716.1[P].2008-03-05.

[8]LIU Guanghui.ITD-DFE based channel estimation and equalization inTDS-OFDM receivers[J].IEEE Trans.Consumer Electronics,2007,53(2):304-309.

FFT处理器篇5

关键词：FFT,FPGA,基4算法,硬件实验结果

数字信号处理领域中FFT作为时域和频域转换的基本运算,是数字谱分析的必要前提。因FFT的超级运算能力,使其在雷达处理、观测、跟踪、定时定位处理、高速图像处理、保密无线通讯和数字通信、匹配滤波等领域中得到极为广泛地应用。

近年来由于现场可编程门阵列(Field Programmable Gate Array,FPGA)的飞速发展,他能够进行并行信号处理,容易实现流水线结构,且升级简便,非常适合实现FFT算法[1,2]。一些FPGA厂商,如Altera公司和XILINX公司,都研制了相应的FFT IP核。但这些器件价格十分昂贵,不能得到广泛应用。因此,自主研发基于FPGA芯片的FFT处理器,把FFT实时化的要求和FPGA芯片设计灵活性结合起来,实现并行算法与硬件结构的优化配置,提高 FFT 处理速度,满足现代信号处理的高速度、高可靠性要求,已经成为了当今数字信号处理的一个研究点。本文正是适应这种趋势,采用频率抽取基4算法,设计并实现了一个集成于FPGA内部的FFT处理器。相对于传统的设计方法,应用FPGA作为算法实现的载体,使得FFT处理器除了具有算法实现准确性高和设备的稳定性强等特点外,更有系统集成度高、简单灵活、体积小、易于升级扩展和成本低廉等优点。

1 FFT的基本原理

对一维时域信号进行傅里叶变换,设xn是长为N的复序列,其DFT定义为:

undefined

其中:WnK=e-j2π/N,xn为时域采样序列。

通过式(1)计算N点DFT,需要进行N2次乘法和N(N-1)次加法运算。当N较大时,运算量是很大的,其中还不包括计算Wk所需的运算量,为了减少运算量、提高运算速度、提高运算结果的实时性,。

2 频率抽取基4算法

在本文应用频率抽取基4算法实现FFT处理器。基4按时域抽取(DIT)是在时域x(n)上将n分为4m,4m+1,4m+2,4m+3分解抽取,式(1)可写为:

undefined

其中undefined;k=0,1,2,…,N-1。

令a(m)=x(4m),b(m)=x(4m+1),c(m)=x(4m+2),d(m)=x(4m+3),由于Wundefined=Wundefined,所以式(2)可以得:

undefined

再令undefined,则式(2)化为:

undefined

再令undefined,则式(4)可以写成:

undefined

由式(5)中可以注意到一些便于硬件实现的特点:如可以用分组加A+CW2P,BWP+DW3P,A-CW2P,BWP-DW3P,然后再进行2次相加等特点。

3 FFT的整体结构

在对频率抽样基4的算法进行介绍后,提出本文设计的FFT处理器的整体结构。本设计应用级联结构,每一级都使用1个独立的蝶型运算单元来加以运算。即:第1个蝶型运算单元计算第1列4只蝶型,第2个单元计算第2列。在实现过程中应用Verilog HDL作为系统设计的实体输入方式,设计了1个集成于FPGA芯片内部的使用基4算法1 024点32位(16位实数,16位虚数)的 FFT 计算单元,如图1所示。

从图1中可以看出,该FFT处理器采用5级流水线结构,RAM采用乒乓操作。每组RAM都由地址发生器进行控制,整个运算单元又接收状态发生器的控制。

4 蝶形单元结构

FFT的核心操作是蝶型运算,蝶型运算的速度直接影响着整个FFT处理器的速度,本文的蝶形单元的结构如图2所示。

由图2可以看出,蝶形运算包括复数乘法和加法2个部分,加法实现较为容易,因此只有提高复数乘法的运算速度才能加快蝶形单元的处理速度。鉴于复数乘法硬件实现较困难,计算速度慢。因此本设计采用CORDIC(坐标旋转数字计算机)算法来实现复数的乘法运算。CORDIC算法不但能够将复数乘法转化为硬件易于实现的加减和移位运算,而且根据他的迭代原理,CORDIC单元可以用流水线结构进行表示,可以使向量旋转并行处理,大大地加快了蝶型运算的速度[3]。

4.1 复数乘法单元

复数乘法单元,简称复乘单元,是FFT算法实现过程用来完成复数乘法的单元模块。在本设计中,应用复乘单元计算出基4算法式(5)中的A,BWP,CW2P,DW3P。

如蝶形单元结构图所示,按照基4算法的信号处理流程,由于第一级运算只有一个旋转因子W0,相当于将B,C,D都乘以1,因此第一级运算是不需要复数乘法单元的。

复乘单元CORDIC算法流水线形式如图3所示。

4.2 后续单元的设计

后续单元的主要作用就是将复乘单元的运算输出结果A,BWP,CW2P,DW3P依次输入到数据缓冲器中进行数据同步,然后对应式(5)进行复数加法运算,得出最终结果。由于4个复乘结果A,BWP,CW2P,DW3P是依次从 CORDIC 复乘单元中读出的,所以必须应用数据缓冲器进行数据同步处理,保证4个复乘结果同时输入到复数加法单元。

5 地址和状态发生器

FFT处理器控制部分主要由地址、状态发生器组成。地址发生器主要是产生FFT运算过程中用到ROM、RAM的存取地址;状态发生器是整个 FFT 处理器的控制中心,他主要功能如下:

(1) 使能或禁止FFT处理器工作;

(2) 使能或禁止各级存储模块工作;

(3) 使能或禁止各级地址发生器,数据分配器工作;

(4) 将FFT复位,将各级存储器清零。

在设计好FFT处理器的各个部分后,应用Actel公司开发的新一款的ILGOOe系列FPGA-AGLE600。他除了具有其他同类产品的基本性能外,更突出的特点是其采用FLASH*Freeze技术,加上其具有低静态、动态功耗,使得此款产品具有其他产品无法比拟的超低功耗性能。设计过程中将FFT处理器的各个部分分别设计输入,将整个FFT处理器烧录到AGLE600芯片内,并对FPGA管脚资源进行了配置,最终实现在1片FPGA芯片内部集成了一套FFT处理器系统。

6 硬件试验

由FFT的运算公式可知,方波经过FFT后应为Sa(ω)。图4所示是由FFT处理器对一个数据总长度为512点、脉冲宽度为20点方波进行FFT运算,并求模归一化后的结果。

7 结语

本文介绍FFT处理器的实现算法,提出一种以FPGA芯片为载体实现FFT处理器的方法,并对处理器的蝶形单元、后续单元和控制单元做了相关介绍。硬件试验的结果表明,设计的FFT处理器的运算结果满足要求,且具有较高的运算速度。

参考文献

[1]李铎,黄益庄.应用FPGA技术实现FFT[J].电子产品世界,2000(8):58-58.

[2]植强.一种基于FPGA的FFT阵列处理器[J].电子对抗技术,2002,7(6):36-39.

[3]Banerjee Ayan,Sundar Dhar,Anindya.FPGA Realization ofa CORDIC-based FFT Processor for Biomedical Signal Pro-cessing[J].Microprocessors and Microsystems,2001,25(3):131-142.

[4]胡广书.数字信号处理理论、算法与实现[M].北京:清华大学出版社,1997.

[5]丁玉美,高西全.数字信号处理[M].2版.西安:西安电子科技大学出版社,2000.

FFT处理器篇6

关键词：FFT,CORDIC算法,MODELSIM仿真,FPGA

快速傅里叶变换是DSP的核心技术之一,作为时域和频域转换的基本运算,是数字谱分析的必要前提,在雷达、观测、跟踪、高速图像处理、保密无线通信和数字通信等领域有广泛应用。FPGA(现场可编程门阵列)内部含有大量逻辑单元和高速RAM模块,使FFT算法可以灵活快速地实现,并具有很高的性能。针对快速信号处理的要求及FPGA器件的特点,提出了一种基于CORDIC算法的基二流水线结构的FFT处理器设计方法。

1 基二FFT算法原理分析

设序列长度是为N=2M,M为正整数。如此可以将序列x(n)分解成两组,偶数项为一组,奇数项为一组,可以得到两个N/2点的子序列,即:x1(r)=x(2r),x2(r)=x(2r+1),r=0,1,…,N/2-1;相应地将DFT运算分为两组[1]。

$\begin{array}{l} X (Κ) = D F Τ [x (n)] = \sum_{n = 0}^{Ν - 1} x (n) W_{Ν}^{k n} = \\ \sum_{n = 0 偶数}^{Ν - 1} x (n) W_{Ν}^{k n} + \sum_{n = 0 奇数}^{Ν - 1} x (n) W_{Ν}^{k n} = \\ \sum_{r = 0}^{Ν / 2 - 1} x (2 r) W_{Ν}^{2 k r} + \sum_{r = 0}^{Ν / 2 - 1} x (2 r + 1) W_{Ν}^{k (2 r + 1)} = \\ \sum_{r = 0}^{Ν / 2 - 1} x_{1} (r) W_{Ν / 2}^{k r} + W_{Ν}^{k} \sum_{r = 0}^{Ν / 2 - 1} x_{2} (r) W_{Ν / 2}^{k r} = \\ X_{1} (Κ)_{Ν / 2} + W_{Ν}^{k} X_{2} (Κ)_{Ν / 2} \end{array} (1)$

利用W $_{Ν}^{Κ}$ 的特性,式(1)可以写成

${\begin{cases} X (Κ) = X_{1} (Κ) + W_{Ν}^{k} X_{2} (Κ) \\ X (Κ + \frac{Ν}{2}) = X_{1} (Κ) - W_{Ν}^{k} X_{2} (Κ) \end{cases} ‚ Κ = 0, 1, \dots, \frac{Ν}{2} - 1 (2)$

继续照上式将序列分解,直到最后是二点的DFT为止。8点FFT蝶形图如图1所示。

2 基二FFT的FPGA实现

在FPGA上实现流水线型FFT处理器,其主要结构模块包括:输入的乒乓RAM模块、蝶形运算模块、旋转因子乘法模块(本文用CORDIC算法实现)、倒序输出模块、旋

转相角(φ)ROM,还有信号流程控制模块和地址产生器模块。具体如图2所示。

2.1 RAM的乒乓读取

为了使输入数据无等待周期,采取了乒乓操作。这种结构是将输入数据流不断写入存储深度为2N的存储单元,用RAM写地址值的最高位来区分低、高存储部分,数据首先输入的低位存储区,当低N个存储单元存储满之后,数据开始存入高N个存储单元,同时开始读取低N个存储单元的数据,由于读写频率相同,低存储单元的数据读完后高存储单元已经写满,此时则开始将数据写入低存储单元,读出高存储单元。如此循环往复,一旦RAM存满最初N个数据后,RAM就可以不间断的输出按要求分组的N个数据点。

由于FFT的蝶形运算特性,要求最终输出结果是顺序输出,即:RAM的读地址应该是其同步写地址的低N-1位二进制码的求逆。如此即可将按正常次序存入RAM的数据进行逆序输出。其中RAM写地址和RAM读地址均由地址产生单元产生,而要保证RAM读、写同步速,在进行求逆时不能有延时,因此对求逆运算要采用组合逻辑电路或者是函数运算来实现。

2.2 蝶形运算的实现

由于读入蝶形单元的数据是串行输入的,而蝶形单元涉及到前后不同地址的数据的加减运算,因此必须对先前输出的数据进行寄存,利用两个选择控制信号对输入数据进行运算控制,如图3所示[2]。

在选择器控制信号sel0的控制下选择对输入数据或输入数据与寄存器输出相加的结果进行寄存。当sel0为高电平时选择对输入数据进行寄存,低电平时对输入数据与寄存器输出的数据相加结果进行寄存。sel1信号控制对寄存器输出数据或寄存器与输入数据之差进行输出。移位寄存器深度可表示为2m-1,m为蝶形运算所在的级数。每级蝶形运算都有sel0、sel1两个控制信号,所有控制信号由控制单元产生。sel1信号为sel0取反后的信号,其频率为主控制时钟的2m分频,m为该蝶形所在的级数。每级蝶形运算输出即送往下一级蝶形运算,在输入下一级之前需与旋转因子W $_{Ν}^{k n}$ 进行相乘。

2.3 利用 CORDIC算法实现旋转因子乘法器

旋转因子的获取有两种方法:一种是将先所需要的旋转因子计算预先存储在ROM中,再通过ROM寻址获取后和相应的数据相乘。本文采用的是实时计算的方法,即将需要旋转的角度值预先存储在ROM中,通过ROM寻址将需要旋转的角度送入CORDIC计算器,直接计算出数据与cosφ和sinφ乘积值。实时计算的方法对计算点数不多的FFT,具有很大的灵活性,也可以节省存储空间。

CORDIC算法的原理如式(3)所示[3,4]:

${\begin{cases} x_{i + 1} = x_{i} - y_{i} d_{i} 2^{- i} \\ y_{i + 1} = y_{i} + x_{i} d_{i} 2^{- i} \\ z_{i + 1} = z_{i} - d_{i} \arctan^{- 1} 2^{- i} \end{cases} (3)$

$d_{i} = {\begin{cases} + 1 ‚ z_{i} > 0 \\ - 1 ‚ z_{i} < 0 \end{cases} (4)$

CORDIC算法的流水线实现流程如图4所示。

式(3)中(x0,y0)为旋转向量点的坐标值,经过逐步迭代移位相加运算后可以得到式(5)

${\begin{cases} x_{n} = A_{n} (x_{0} c o s z_{0} - y_{0} s i n z_{0}) \\ y_{n} = A_{n} (y_{0} c o s z_{0} + x_{0} s i n z_{0}) \\ z_{0} = 0 \\ A_{n} = \prod_{i = 0}^{n - 1} \sqrt{1 + 2^{- 2 i}} \end{cases} (5)$

当旋转向量和x轴重合时,即y0=0时,其最终结果可表示为

${\begin{cases} x_{n} = A_{n} \cdot x_{0} c o s z_{0} = A_{n} \cdot x_{0} \cos φ \\ y_{n} = A_{n} \cdot x_{0} s i n z_{0} = A_{n} \cdot x_{0} \sin φ \end{cases} (6)$

如此可以得到参数W $_{Ν}^{k n}$ 的实部和虚部。式(6)中An表示增益系数,其极限值为1.647,即一次旋转乘法完成后最终结果比预期的要大1.647倍,考虑到数据位的溢出,在运算初始过程中需将初始值x0进行右移1位处理,即将x0初始值缩小2倍。z0值为存储旋转相位角ROM的输出值φ,在不用乘旋转因子时ROM输出数据为φ=0。旋转结果xn为实部值,-yn为虚部值。其中只有第一级输入是全实数输入,以后每级的输入包含实部和虚部两部分,实部和虚部要分别进行旋转相乘和分别进行移位寄存处理,即每级中需包含两个运算单元,分别同步处理实部和虚部数据。得到旋转输出结果后将实部旋转后的实部和虚部旋转后的虚部相加得到新的实部数据作为下一级的实部输入,实部旋转后的虚部与虚部旋转后的实部相加得到新的虚部数据作为下级输入的虚部。

CORDIC算法所能获得的最大旋转角度为[5]: $φ = \lim_{n \to \infty} \sum_{i = 0}^{n} \arctan 2^{- i} \approx 99 °$ ,故设定旋转区间为[0,π/2],要求对ROM输出的相位角进行预判,之后利用三角函数的性质将第一区间外的相角转换到第一区间内进行运算以实现全相位的运算,如表1所示。

2.4 地址产生单元与ROM存储设计

地址产生单元主要用来产生RAM的读、写地址和旋转相角ROM的读地址。主要是根据时钟的步速(串行数据的输入步速)产生RAM的写地址,并按照求逆的要求将写地址的低N-1位二进制数按位序求逆产生对应RAM读地址。按照写地址的最高位是1还是0判定读地址的最高位是0还是1,保证其进行乒乓读取。ROM读地址的产生与RAM读地址的产生同步同时产生,但不用求逆,即与RAM写地址的低N-1位完全相同,并以N点为周期进行循环产生。

由于ROM地址产生器产生的地址是与RAM写地址的低位N-1值相等的,即数据开始串行输入蝶形单元的顺序值。而经过蝶形单元运算后产生了数据延迟,等到N个数据完全移出一级蝶形单元时,ROM的地址值已经重新开始计数,由此产生了ROM的循环寻址,即:将相角数据φ预先存入ROM时要考虑延迟后的寻址,ROM地址重新归零后对应的存储单元要存放的数据是对应延迟输出的几个相角值。如此就像循环右移一样,将本应该存储地址末尾的内容拿到存储地址的前几个地址,如图5所示。

2.5 控制信号与数据对准

在每级蝶形单元的交叉运算中都需要控制信号sel0,sel1,总计需要2M个控制时钟,M为基二运算过程中的蝶形运算中所需的级数。从数据开始输入的同时开始计数、分频,由于每级不同的延迟,数据从第m级输入到输出由于中间有移位寄存器的延迟作用会对数据的输出造成延迟,延迟量可以表述为2m-1,其中2m-1为移位寄存器的深度,读入数据过程中本身就有一个数据延迟,因此第m级的数据输出相对于开始输入蝶形单元的数据总延迟量可以表述为1+2+…+2m-1+2m。而控制数据输出的sel1信号不断经过时钟的2的整数次幂得到的,此时会产生各级输出数据(下级的输入)与下级蝶形运算控制信号的上升沿未能对准的情况,因此需要将各级数据在输出过程中进行不同单位的延迟(增加寄存次数)以保证蝶形单元的输出数据与下级蝶形单元的选择器控制时钟对齐,只有输入数据与蝶形单元的控制时钟的上升沿对准,才能保证数据进行正确的寄存和运算。

在蝶形运算过程中,由于是控制时钟的关系,按照二进制码逆序输入的数据最终在FFT处理器输出是十进制的逆序,即先输出的是第N个数据,最后才输出第一位数据。要得到正确的顺序输出在最后一级蝶形运算后需要进行倒序处理,同样为保证输出的连续性也采取了乒乓操作,只是此时有实、虚两部分数据,存储空间要比输入时的RAM大一倍。

3 仿真与验证

利用MATLAB产生的数据作为FFT的输入激励。设计输入信号为100 kHz与300 kHz的叠加,采样频率为1 MHz,FFT点数定为32,将采样值转换成二进制数据,并写入txt文件,如下文所示:

在testbench中利用verilog语言的系统函数MYM-readmemb将txt文件中的二进制数据读入存储数组datamem,在采样时钟的控制下,将datamem中数据串行读入FFT处理器,作为输入激励,如下文所示:

MYMreadmemb(″binarydata.txt″,datamem)

利用verilog系统函数MYMfdisplay将FFT处理器输出的实部和虚部数据写入txt文件,方便利用MATLAB读取分析。部分代码如下:

利用MATLAB绘图对比分析结果如图6所示。

对比分析可以证实该设计基本满足了FFT对频谱分析的要求。其幅度值不等是因为在硬件设计中采用了防止溢出的限幅措施。

4 总结

主要讨论了基二FFT在FPGA上的实现方法,结合CORDIC算法,在FPGA芯片上实现了FFT处理器,解决了设计过程中的乒乓读取,CORDIC旋转运算,ROM存储,数据与控制时钟的对准等问题。并进行了MODELSIM和MATLAB的联合仿真,仿真结果表明该设计满足了FFT处理的处理要求。在10 MHz采样率的情况下完成32点的FFT运算需要14.45 μs,满足实时处理的要求,并且具有可以继续扩展到更高的点数,具有推广价值。下一步将考虑更为节约资源的方法,使其用于具体的装备中。

参考文献

[1]俞卞章.数字信号处理[M].2版.西安:西北工业大学出版社,2002.

[2]高亚军.基于FPGA的数字信号处理[M].北京:电子工业出版社,2012.

[3]UWE M.Digital signal processing with field programmable gate arrays[M].刘凌,译.北京:清华大学出版社,2003.

[4]刘福奇,刘波.Verilog HDL应用程序设计[M].北京:电子工业出版社,2009.

FFT处理器篇7

关键词：快速傅里叶变换,FPGA,基-16算法,混合基算法,级联结构

0 引言

数字信号处理主要研究采用数字序列或符号序列表示信号,并用数字计算方法对这些序列进行处理,以便把信号变换成符合某种需要的形式。在现代数字信号处理中,最常用的变换方法就是离散傅里叶变换(DFT),然而,它的计算量较大,运算时间长,在某种程度上限制了它的使用范围[1]。快速傅里叶变换(FFT)的提出使DFT的实现变得接近实时,DFT的应用领域也得以迅速拓展。它在图像处理、语音分析、雷达、声纳、地震、通信系统、遥感遥测、地质勘探、航空航天、生物医学等众多领域都获得极其广泛的应用。随着FPGA技术的高速发展以及EDA技术的成熟,采用FPGA芯片实现FFT已经显示出巨大的潜力。

目前用FPGA实现的FFT处理器结构大致分为四种:递归结构、级联结构、并行结构和阵列结构[2,3,4,5,6]。递归结构只利用一个碟形运算单元对数据进行规律的循环计算,使用硬件资源较少,但运算时间较长。级联结构每一级均采用一个独立的碟形运算单元来处理,相对递归结构速度上有所提高,不足之处是增加了延时用的缓冲存储器使用量。并行结构对一级中的蝶形单元并行实现,阵列结构是将每一级的蝶形运算单元全部并行实现,这两种结构有很高的运算速度,但消耗的资源过大,一般不采用。为了提高运算速度,特别是为了适应多批数据处理,一般采用级联结构实现FFT处理器。

1 FFT整体结构设计

在FFT算法中,目前大多使用基-2和基-4算法实现级联结构的FFT处理器,除此之外,也可采用基-8和基-16算法来实现。随着基数的增大,对于相同点数的离散数列,处理器所分的级数越少,对缓冲存储器的需求也越小,因此考虑采用基-16算法来实现FFT处理器,但基-16算法只能实现离散数列点数是16的p次幂的FFT[7]。从而,引入混合基思想来改进基-16算法。

设x(n)为N点有限长序列,其DFT为[8]:

$X (k) = \sum_{n = 0}^{Ν - 1} x (n) W_{Ν}^{n k} ‚ k = 0, 1, 2, \dots Ν - 1 (1)$

式中:W $_{Ν}^{n k}$ =e-j2πnk/N;N可分解为N=r1r2。

可将n(n<N)表示为:

$n = n_{1} r_{2} + n_{0}$

式中:n1=0,1,2,…,r1-1;n2=0,1,2,…,r2-1。将频率变量k(k<N)表示为:

$k = k_{1} r_{1} + k_{0}$

式中:k1=0,1,…r2-1;k0=0,1,…r1-1。

式(1)可变换为:

$X (k_{1}, k_{0}) = \sum_{n_{0} = 0}^{r_{2} - 1} {[\sum_{n_{1} = 0}^{r_{1} - 1} x (n_{1}, n_{0}) W_{r_{1}}^{n_{1} k_{0}}] W_{Ν}^{n_{0} k_{0}}} W_{r_{2}}^{n_{0} k_{1}} (2)$

设r1=16p,r2=N/16p=2,4,8,式(2)先将原非16的p次幂的N点FFT分解为16p点的FFT;再分解为N/16p点的FFT。首先对输入信号进行16p点的FFT运算,然后将结果乘以一个旋转因子Wn0k0N,最后将计算出的数据进行一次N/16p点FFT运算,得到的结果即为所需要的N点FFT运算结果。这样处理,既能减少分解的级数,又能使计算离散数列点数只需是2的整数次幂即可。以1 024点为例,只需分解成两级基-16运算模块和一级基-4运算模块即可实现,其FFT处理器结构图如图1所示。在此结构图的前端增加/减少基-16运算模块或将最后一级基-4运算模块改为基-2或基-8运算模块,就可以实现其他离散数列的点数只需是2的整数次幂的FFT运算。

2 蝶形运算核的实现

2.1 基-16蝶形运算核

如果直接将基-16蝶形运算公式转换到硬件中实现基-16运算核,其结构将十分复杂的[9,10]。因此,采用易实现的频域抽选基-4算法来实现频域抽选基-16蝶形运算核。由基-4蝶行运算单元实现的基-16蝶行运算单元如图2所示。

采用并行流水结构实现的基-16运算核,一个数据时钟可处理16个数据。而每次蝶形运算在一个数据时钟内只需要计算出一个结果,这将造成资源浪费。因此,采用级联结构实现的基-16蝶形运算核,用两个基-4蝶形运算核分别复用4次来实现每一级中的四个蝶行运算,中间用一个串行出入/输出的寄存器进行连接,其结构框图如图3所示。

2.2 基-4蝶形运算核

基-4蝶形运算核的结构如图4所示,其中加减模块为两级流水结构,一次可以计算4个数据。蝶形运算的四个串行输入数据经串/并转换器转换为四路并行数据,进入加减运算单元。计算出的4个并行结果进入并/串转换器后,串行输入复数乘法器和旋转因子相乘然后输出结果。因为图1中最后一级的数据只需要进行加减运算不需要再乘以旋转因子,所以图1中的基-4蝶形运算核是没有复数乘法器的,数据从并/串转换器中直接输出给缓冲存储器。

2.3 复数乘法器

虽然现在的高端产中已经集成了可以完成乘法的DSP资源,但也是有限的。因此高效复数乘法器的设计对该设计来讲仍然非常的重要。复数乘法的标准式如下:

$\begin{array}{l} R + j Ι = (A + j B) \times (C + j D) \\ = (A C - B D) + j (A D + B C) \end{array}$

式中:A,B分别为输入数据的实部和虚部,C和D分别为旋转因子的实部和虚部。按照这种标准表达式,执行一次复数乘法需要进行4次实数乘法,2次实数加法和2次实数减法。将上述公式重新整理为:R=(C-D)·B+C(A-B),I=(C-D)A-C(A-B)优化后的复数乘法器需要进行3次实数乘法,2次实数加法和3次实数减法,相比传统结构多了一个减法器,少了一个乘法器。在FPGA中,加减法模块所占用的相对裸片面积要小于相同位数的乘法器模块。这样的优化还是很有价值的,在FFT吞吐量不变的情况下,可减少25%的乘法器使用量,在乘法器数量一定的情况下可高FFT吞吐量。

3 存储器单元

传统的级联结构的FFT处理器的缓冲存储器都是采用乒乓结构,基本思想就是用两块相同的RAM交替读出或写入数据。即其中一块RAM在写入数据时,另一块RAM用于读出数据。当用于写入数据的RAM写满时交换读写功能。将乒乓结构中RAM的内部存储单元地址用二进制数a9a8a7a6a5a4a3a2a1a0表示。以写满其中以块RAM为一个周期,用一个二进制计数器m9m8m7m6m5m4m3m2m1m0生成的顺序写入,混序读取的乒乓结构RAM的操作地址如表1所示。

表1中第一,二,四块存储器的写操作地址和读操作地址是可以互换的,也就是将数据混序写入,顺序读取。因此,根据这个规律采用一块可同时读写的双端口RAM来实现第一,二,四块存储器。其基本思想就是对同一个地址进行读和写。以用一块双端口RAM实现第一块存储器的为例,在第一个周期内双端口RAM按照地址m9m8m7m6m5m4m3m2m1m0进行写操作,即数据是按照自然顺序储存的。在第二个周期按照地址m0m1m2m3m4m5m6m7m8m9同时进行读写操作,读出的数据按照倒位序排列,写入的数据按照倒位序储存的。在第三个周期按照地址m9m8m7m6m5m4m3m2m1m0同时进行读写操作,读出的数据按照倒位序排列,写入的数据是按照自然顺序储存的。依次类推下去,读出的数据都是按照倒位序排列。同样第二块和第四块存储器的存储地址也具有这样类似的循环规律。因此只有第三块存储器需要用乒乓结构的RAM实现,与传统所有存储器都用乒乓结构RAM实现相比,节省了3/8的存储单元。设计中用Matlab软件直接生成旋转因子,并将其转化为16位有符号定点数写入MIF文件。然后用ROM直接调用MIF文件,将旋转因子预置在ROM中。

4 仿真结果

选用Altera公司生产的Cyclone Ⅱ的EP2C35F484C7芯片上进行验证,在Quartyus Ⅱ7.2软件中进行编译和仿真。通过对高基核的优化处理,该设计对逻辑单元消耗量和传统用基-4算法实现相近,仅为4 399,但由于本文采用了高基低基组合的混合基算法,在处理1 024点的离散数列时,处理器所分的级数仅为3级,相对传统的低基数算法,其实现减少了对缓冲存储器块数的需求;并通过对缓冲存储器的优化设计,又比全部用乒乓结构RAM实现的传统方法节省了3/8的存储单元,因此占用的存储资源仅为154 048 b。仿真波形如图5所示,该仿真结果和Matlab计算结果基本一致,存在一定的误差是由于有限字长效应引起的。

5 结语

在100 MHz的时钟下工作,完成一次1 024点的FFT从输入初始数据到运算结果完全输出仅需要54.48 μs,且连续运算时,处理一组1 024点FFT的时间仅为10.24 μs,达到了高速信号处理的要求。

参考文献

[1]蔡可红.基于FPGA的FFT设计与实现[D].南京:南京理工大学,2006.

[2]韩颖.高速专用FFT处理器的设计与实现[D].北京:北京理工大学,2003.

[3]陆旦前,陈建平,陈晓勇.FFT算法的一种FPGA设计[J].微电子技术,2007(6):178-180.

[4]鲍庆龙,刘平.基于FPGA的高速FFT算法实现[J].微处理机,2007(2):16-19.

[5]樊光辉,许茹,王德清.基于FPGA的高速流水线FFT算法实现[J].电子工程师,2008,34(3):38-40.

[6]贺卫东,段哲民,龚诚.基于FPGA的大点数FFT算法研究[J].电子测量技术,2007,30(11):14-16.

[7]谢彦林.可变点流水线结构FFT处理器的设计及其FPGA实现[D].西安:西安电子科技大学,2007.

[8]程佩青.数字信号处理教程[M].2版.北京:清华大学出版社,2004.

[9]刘小明.超高速快速傅里叶变换的实现[D].合肥:合肥工业大学,2006.

FFT处理器篇8

1 总体设计

目前基于FPGA的FFT硬件实现结构主要分为递归结构、流水线结构以及全并行结构[3]。递归结构是内存共享结构,在三种结构中占用硬件资源最少,但由于只有一个运算单元,因此运算时间最长。流水线结构是级联结构,FFT的每一级都使用一个独立的运算单元,前一级运算结果可以直接用于下一级运算而无需等到本级运算全部完成,因此在运算速度上有所提高,但同时占用的硬件资源也随之增多。全并行结构则是在FFT的每一级都设置与FFT的点数成正比的运算单元数,显然该结构在三种结构中运算速度最快,硬件资源占用也最多。

综合考虑上述三种结构,本文采用流水线结构,设计了一种1024点12位的基4DIT⁃FFT处理器。总体结构框图如图1所示。

2 基4DIT⁃FFT

2.1 基4DIT⁃FFT的运算单元

基4DIT⁃FFT即基4时间抽取法FFT,设序列x(n)的长度为N,且满足N=4M,M为自然数。x(n)的DFT可以表示为:

令:

因为,故式(1)可以表示为式(2)的形式:

又令:

式(2)变为:

这里得到的是一级蝶形运算单元,同理,a(m)~d(m)可以继续分解,最终得到N个1点DFT和M级蝶形运算。

由式(3)可以看出,一个基4蝶形运算单元需要3个复乘和8个复加。

2.2 基4DIT⁃FFT的选择

对于基2DIT⁃FFT,运算流图有log2N级,每级都由N 2个蝶形运算单元构成,每个蝶形运算单元包括1次复乘,2次复加,那么每级需要N2次复乘和N次复加,log2N级需要N 2log2N次复乘,N log2N次复加。同样根据式(3)和基4DIT⁃FFT的运算流图可知,基4DIT⁃FFT所需的复乘数为3N 8log2N(未计入乘以±j和1的计算),比基2DIT⁃FFT复乘次数减少了25%,复加次数不变。可以证明,当FFT的基大于4时,不会明显降低计算量[4],但控制复杂度却明显增大,所以综合考虑运算速度与控制复杂度,最终选择基4DIT⁃FFT进行方案设计。

3 CORDIC算法与FFT复乘运算

3.1 CORDIC算法基本原理

文献[5]率先提出了CORDIC(坐标旋转数字计算机)算法,当时并没有引起人们的关注,文献[6]提出了统一的CORDIC算法,人们开始对这种旋转后逐渐逼近的近似方法进行深入研究。文献[7,8]在量化误差分析方面进行了拓展,其中文献[8,9]第一次利用FPGA实现了CORDIC算法。文献[10]在分布式算法中实现了CORDIC算法。

CORDIC算法在圆坐标系中的基本原理如图2所示,在x⁃y坐标平面内将点(x1,y1)旋转角度θ到点(x2,y2),其关系可用式(4)表示:

为了方便在硬件上实现,做如下约定:tanθi=2-i,这时

;以δi确定旋转方向,+1代表逆时针旋转,-1代表顺时针旋转。

这时,第i步旋转可以表示为:

式中:是常数,称为每次旋转的伸缩系数,实际应用中,如果迭代次数n已知,可以预先计算出整个迭代过程中的伸缩系数,将输入数据校正后再参与运算。式(5)可以简化为只有加、减、移位的运算,如下:

添加旋转角度迭代式如下:

根据文献[6]的结论可知:

由式(6)~(8)可知,将所需旋转角度作为z1输入,根据n次迭代输出的xn+1,yn+1,就可得到旋转角度z1的三角函数值。

3.2 CORDIC算法与FFT复乘运算

由式(3)可知,基4DIT⁃FFT蝶形运算单元包含复加,复乘两种运算,复加相当于两次实数加法运算,硬件电路易于实现,而复乘包含四次实数乘法运算和两次实数加法运算,硬件实现较为复杂,因此讨论如何利用CORDIC算法简化复乘运算。

选取某一级的蝶形运算中的一个复乘运算:

为例进行分析,这里,下标m表示第m级蝶形运算,将WNk展开得到:

将式(10)代入式(9),得到:

将Xm和Y的实部和虚部分开表示,可以得到:

对比式(8),显然Xmre对应x1,Xmim对应y1,-2πk /N对应旋转角度z1。可见复乘单元的实部虚部与CORDIC算法中的平面坐标值一一对应,因此可以利用CORDIC算法简化基4DIT⁃FFT中复乘单元的硬件实现。

4 FFT复乘运算的硬件实现

4.1 复乘单元的整体设计

通过3.2节的分析,利用CORDIC算法的复乘单元的整体设计框图如图3所示,输入数据的实部和虚部首先经过伸缩系数校正模块,经过校正的数据分别送入R通道和I通道,为了节约资源,提高速度,可事先通过Matlab仿真得到δ0~δ11,存储在ROM中,这样可以免去Z通道,节约1 /3的加减法器。

4.2 伸缩系数校正模块的设计

如3.1节所述,实际应用中,迭代次数n已知可以预先计算出整个迭代过程中的伸缩系数,将输入数据校正后再参与运算。本设计中输入数据为12位字长,故迭代次数为12次,伸缩系数为:

如果直接乘以伸缩系数,将有悖于CORDIC算法的初衷,综合考虑硬件实现的简易程度与伸缩误差,最终选用式(14)所示的迭代近似实现:

其中δi根据Matlab的优化程序在-1,0,1三个值中选择最优值。优化程序得到的δi系数值如图4所示(从左到右依次为δ0~δ11):

4.3 旋转系数的设计

根据式(7)和式(8),可通过Matlab仿真得到δ0~δ11,这里仅给出第二级旋转因子W016,W116,W216,W316的系数δ0~δ11,以及利用CORDIC算法旋转的角度与实际应该旋转角度之间的误差(见图5中的z2)。

4.4 时序仿真结果

通过Altera公司的Quartus 9.1软件对复乘单元进行设计,并用Mentor公司的Model Sim 10.1a进行仿真验证,图6给出的是字长为12位的实部与字长为12位的虚部作为输入数据与第二级旋转因子之一W116进行复乘的仿真结果,图6结果显示,输入数据经过伸缩因子校正与CORDIC迭代运算共16个周期之后得到输出结果。

5 结语

本文设计了一种1 024点12位的基4DIT⁃FFT处理器。详细阐述了CORDIC算法在复乘单元中的设计与FPGA实现。将复数乘法转换为硬件易于实现的加、减、移位运算,并通过Matlab对伸缩系数与旋转系数进行预处理,免去Z通道,大大加快了运算速度,节约了资源,降低了系统复杂性。除了适用于本文的基4DIT⁃FFT,还可用于基2FFT以及分裂基FFT等处理器中,具有很高的研究价值,值得推广应用。

蝶形运算单元的后续设计主要为复数加减,较为简单,不再赘述。整个系统受控于状态发生器从而有序工作。地址发生器可根据基4DIT⁃FFT数据的存取规律进行设计,这里不再详述。

摘要：随着海洋开发和信息产业的发展,高速、大容量、高可靠性的水声通信系统成为研究热点。论述了一种用于水声通信系统中的基4DIT-FFT处理器的设计。该设计利用CORDIC算法优化蝶形运算单元,将复数乘法转换为硬件易于实现的加、减、移位运算,并通过Matlab对伸缩系数与旋转系数进行预处理,大大加快了运算速度且降低了系统复杂性。在此基础上设计了一种1024点12位的基4DIT-FFT处理器。

关键词：CORDIC算法,基4DIT-FFT,蝶形运算单元,流水线结构

参考文献

[1]周琳.深远海环境监测水声通信仿真方法与信道估计研究[D].青岛:中国海洋大学,2011:24-28.

[2]倪笑园.基于FH/MFSK的水声通信研究[D].杭州:浙江大学,2014:7-13.

[3]李伟,孙进平,王俊,等.一种基于FPGA的超高速32K点FFT处理器[J].北京航空航天大学学报,2007,33(12):1440-1443.

[4]PROAKIS J G,MANOLAKIS D G.数字信号处理:原理、算法与应用[M].张晓林,译.北京:电子工业出版社,2004.

[5]VOLDER J E.The CORDIC trigonometric computing technique[J].IRE transactions on electronics computers,1959,8(3):330-334.

[6]WALTHER J S.A unified algorithm for elementary functions[C]//Proceedings of 1971 Spring Joint Computer Conference.New York:ACM,1971:379-385.

[7]HU X B,HARBER R G,BASS S C.Expanding the range of convergence of the CORDIC algorithm[J].IEEE transactions on computer,1991,40(1):13-21.

[8]MEYER-BASE U,MEYER-BASE A,HILBERG W.Coordinate rotation digital computer(CORDIC)synthesis for FPGA[C]//Proceedings of 1994 the 44th International Workshop on Field-Programmable Logic and Applications.Prague:Springer Berlin Heidelberg,1994:397-408.

[9]MEYER-BASE U.The use of complex algorithm in the realization of universal sampling receiver using FPGAs[J].VDI/Springer,1995,10(404):215-228.

【FFT处理器】推荐阅读：

深度处理工艺处理05-27

膜处理处理技术12-05

网络处理器01-21

永磁处理器05-20

国产处理器05-31

处理器架构06-07

事件处理器06-25

数字处理器07-12

微控处理器07-13

安全处理器08-05