FFT算法的一种FPGA实现

FFT算法的一种FPGA实现摘要：FFT运算在OFDM系统中起调制和解调的作用。针对OFDM系统中FFT运算的要求，研究了一种易于FPGA实现的FFT处理器的硬件结构。接收单元采用乒乓RAM结构，扩大了数据吞吐量。中间数据缓存单元采用双口RAM，减少了访问RAM的时钟消耗。计算单元采用基2算法，流水线结构，可在4个时钟后连续输出运算结果。各个单元协调一致的并行工作，提高了系统时钟频率，达到了高速处理。采用块浮点机制，动态扩大数据范围，在速度和精度之间得到折衷。模块化设计，易于实现更多点数的FFT运算。关键词：FFT；FPGA；蝶型运算；乒乓RAM结构1引言OFDM（正交频分复用）是一种多载波数字调制技术，被公认为是一种实现高速双向无线数据通信的良好方法。在OFDM系统中，各子载波上数据的调制和解调是采用FFT（快速傅里叶变换）算法来实现的。因此在OFDM系统中，FFT的实现方案是一个关键因素。其运算精度和速度必须能够达到系统指标。对于一个有512个子载波，子载波带宽20kHz的OFDM系统中，要求在50〃s内完成512点的FFT运算。硬件实现FFT算法的主要方案有：DSP（通用数字信号处理器）；FFT专用芯片；FPGA（现场可编程门阵列）。DSP具有纯软件实现的灵活性，适合用于流程复杂的算法，例如在通信系统中的信道编、解码，QAM映射等算法。如果在DSP中完成FFT运算，不仅要占用大量DSP的运算时间，使整个系统的数据吞吐率降低，也无法发挥DSP软件实现的灵活性。因此，前端的FFT运算应由ASIC或FPGA完成。采用专用的FFT处理芯片，虽然速度能达到要求，但其可扩展性差。FPGA具有硬件结构可重构的特点。适合于算法结构固定、运算量大的前端数字信号处理。新近推出的FPGA产品都采用多层布线结构，更低的核心电压，更丰富的IO管脚，容量可达到100k个逻辑单元（LES），内置嵌入式RAM资源，内部集成多个数字锁相环，多个嵌入的硬件乘法器，所有这一切都使得FPGA在数字信号处理领域显示出自己特有的优势。本设计根据OFDM系统的实际需要，提出一种用FPGA实现FFT运算的方案，并以64点FFT为例，在QuartusII软件上通过了综合和仿真。2方案分析FFT是DFT(离散傅里叶变换)的快速算法。以图1为例，N点FFT共需要log2N级运算，每级需要N/2个蝶型运算。因为系统中FFT运算点数为2的奇数次方，因此本设计采用的是按时间抽取的基二FFT运算。FPGA实现FFT需考虑的问题有：整体实现结构的设计。对FFT算法进行合理的模块划分，各个模块在中央控制单元的管理下并行工作，实现框图如图2所示。数据格式和长度的选择通常的数据表示方法有3种：浮点，定点和块浮点。浮点数用2组固定的bit来表示指数和小数，动态范围大。只要表示指数的位数足够多，浮点运算就不会发生溢出现象。但是完成浮点运算所需要的电路复杂，运算速度慢。定点数小数点位置固定，用固定的bit来表示整数和小数部分。定点数动态范围小，容易溢出。但是其运算电路简单、速度快。块浮点介于浮点和定点之间。在FFT运算过程中，逐级进行溢出判断和移位选择，实现动态范围扩展。本方案采用块浮点运算。即小数点的位置随中间运算结果动态范围的增大而右移。入口基带数据为10b补码格式。FFT运算结果输出2路10b。实部、虚部各一路，补码表示。由于入口数据精度的限制，旋转因子的实部、虚部取和输入数据同样的量化位数】3］。地址生成单元的设计在FFT中，输入数据和旋转因子的寻址是设计中最灵活的部分。一种容易想到的实现方案是利用RAM为每级蝶型运算生成地址查找表，蝶型运算序数作为查找表地址，读出的内容为输入数据和旋转因子地址。优点是地址生成速度快，缺点是消耗大量的片上RAM资源。N点FFT需要log2Nb表示地址。N/2个旋转因子用log2(N/2)b表示地址。每级地址查找表都需要(N・log2N+N/2・log(N/2))b。本文设计的一种地址生成逻辑，采用流水线结构，通过简单的移位和加法运算，延迟4个时钟得到数据地址，并对原理进行了详细的阐述。3实现技术整体设计分为数据接收部分和FFT运算部分。数据接收部分工作在频率低的clk_data。其他逻辑工作在频率高的clk_fast。两个时钟通过双口的接收RAM进行衔接。3.1数据接收单元数据接收单元将每帧数据按码位倒置的顺序乒乓存入接收RAM1或接收RAM2。数据接收模块有2b的标志信息通知给中心控制单元。中心控制单元根据标志位，交替的对接收RAM中的数据进行处理。当中央控制单元将接收RAM中的数据取出，经过蝶型运算，结果存入运算RAM1的同时，上一帧数据的FFT运算结果从运算RAM2取出。为了实现乒乓操作，接收RAM共有2块，用FPGA的片上RAM实现，为SimpleDualPort模式。读、写端口分别有自己独立的数据总线、地址总线和工作时钟。数据接收单元控制写端口，中心控制单元控制读端口。3.2运算单元运算单元由蝶型运算器和运算RAM组成。蝶型运算器完成对输入数据A，B的蝶型运算。设输人数掘为内=%十电=%+虹“旋挂因子捋-叫+电L则蝶型运算输出为、心->1+帅B一&阿+如+g+"Eg-A—/邠-M+知株+-如此—如*Jj从上两式可以看出共有2个乘累加项(bpWp-bqWq)和(bpWq+bqWp)。蝶型运算的各个模块都利用QuartusII开发软件中所提供的宏单元生成。整个蝶型运算为同步逻辑，共需要4个时钟周期。输入数据A，B为10b，因此乘累加运算单元输出为20b，才能保证不溢出。乘累加运算单元输出结果，截断低8位(蝶型运算因子低8位为小数)，保留整数部分输入到加法器、减法器。同时为了使数据同步，数据通过寄存器组延迟3个时钟。同时符号扩展2位，与乘累加单元输出结果对齐。从以上描述和FFT算法的分析［2］表明：每级FFT运算结果的动态范围最多需要扩展2b。因此中间运算结果的位宽应为24b，实部、虚部各12b。在进行下一级蝶型运算时，12b数据被取出。按照块浮点单元记录的动态范围扩展bit数，完成定标。截取其中的10b送入蝶型运算器。图:f蝶堂逐算耳集零KI图:f蝶堂逐算耳集零KI单氐WI此也推村如ktin宓I半短如甲兄1运算RAM1和运算RAM2作为FFT的中间的数据缓存。两块RAM交替作为数据读出和运算结果写入单元。直到第6级蝶型运算完成。运算RAM采用TrueDualPortMemory模式。每一侧的端口均可在独立的工作时钟下完成随机地址数据的读或者写操作。即可以同时将蝶型运算所需要的两个入口数据读出，也可以同时将两个运算结果写入。比单口RAM减小了一半的读写周期。3.3旋转因子查找表旋转因子查找表，存储FFT运算所需要的旋转因子昭：昭=#-网朴r=EfN龙一I3.4地址产生单元地址产生单元产生每一级蝶型运算所需的两个输入数据和旋转因子的地址。从图1可以看到，该FFT实现结构为原位运算。蝶型运算的结果仍然写回输入数据读出地址。因此需将读数据地址延迟若干时钟周期，作为运算结果写入地址。对于N点FFT运算，设m£(0“・log2N-1)，n£(0“・N/2-1)表示第m级的第n个蝶型运算。addr_A，addr_B，(addr_A<addr_B)分别表示两个入口数据的地址。观察地址生成规律：每一级蝶型运算可分为若干组(0“・N/2/2m-1)，每组2m个蝶型运算，两个入口数据共占用2m+1个地址。addt-B—addr.A=2"则m级的第n个蝶型运算的位置为第n/2m组的第n%2m个。因此：a^dr_A=<赤)*2^十川％炉flddr..A4-2"(n/2m)*2m+1操作可描述为将n的低m位清零，再左移1位。n%2m描述为取n的低mb位。为了获得更高频率的工作时钟，将该运算拆分为较小的逻辑单元，分为4个节拍流水输出。N点FFT共需要旋转因子N/2个，为当前蝶型运算所对应的旋转因子查找表入口地址。从时间抽取FFT算法的推导过程［2］可知第m.级蝶型运算所需旋转因子的排列规律。即在0~N/2-1的数中，可以被2整除的数，按从小到大的顺序重复排列，规则为：’'-(JV/2)需要移位和求余两种简单的运算。N点FFT共需要旋转因子N/2个，为当前蝶型运算所对应的旋转因子查在图1的8点FFT中，第1级""'"'J'''而在0~3中间可以被2整除的数为0和2。因此4个旋转因子地址为(0,2,0,2)，进而又可以表示为(0X2)%4,(1X2)%4,(2X2)%4,(3X2)%4。64点FFT旋转因子有32个，共需要5b表示地址。第m级，第n个蝶型运算的WrN地址可由逻辑移位的方法快速得到。将n(5b)左移位(5-m),低位补0,就得到了在(0"・31)中的addr_w。地址产生单元框图见图5。m,n作为输入，4个时钟周期后产生所需要的地址。衰I数幅高3位和矿展1而由关系m土&00.1110ODbHO101X,JOX23.5块浮点单元每级蝶型运算结果动态范围最大需要扩展2b。块浮点单元对蝶型运算结果的高3位进行检测，判断当前结果动态范围扩展bit数，记录当前级的最大扩展bit数。下一级蝶型运算时，根据前一级的最大扩展bit数，对读出的数据进行定标，选取数据送入蝶型运算器。块浮点单元将每一级运算结果动态范围扩展bit数进行累加，和FFT运算结果一同输出。3.6中央控制单元中央控制单元为整个系统的控制核心。功能模块之间的数据传递均通过中央控制单元。中央控制单元记录当前蝶型运算所处的级数和个数，传递给地址产生单元。地址产生单元在经过4个时钟后产生数据和旋转因子的地址。中央控制单元读取地址，向处于伺服状态的运算RAM和旋转因子查找表发出读使能请求。2个时钟延迟以后，数据和旋转因子被读出。读出的数据进行必要的延迟和定标处理，送给蝶型运算器。4个时钟延迟后，运算结果将被连续算出并写入RAM。设计中共用了2个时钟。4验证与仿真采用自顶向下的设计思路，完成系统设计和各个功能模块的VHDL代码编写。使用QuartusII针对EP1C6F256完成了综合和仿真，占用30%的逻辑单元和90%的片上RAM。clk_fast最快87.23MHzo第一级蝶型运算需要75个时钟，以后各级需要45个时钟，完成64点FFT共需要300个时钟共3.4口s。完成512点FFT,需要2691个时钟共33.63ps,OFDM符号速率可以达到29kS/s。5结语本设计的主要特点有：采用pipleline流水结构，各个单元协调同步工作。若FFT点数增大，流水线初始化时钟开销比率将显著降低。使用了2块双口RAM作为中间结果存储器，1个时钟可以同时读出或者写入2个操作数。减少了访问存储器的时钟消耗。块浮点单元的使用，定点数动态范围根据实际运算结果进行扩大，在实现复杂度，运算速度与运算精度方面得到了折衷。简易快捷的地址生成逻辑。模块化设计。设计中的各个逻辑单元功能单一，具有通用性，可以方便地