基于FPGA的流水线FFT处理器设计

摘要

为了满足不同系统对实时性和低成本的要求，开发一种高性能的快速傅立叶变换处理器具有重要意义。为此，提出了一种基于现场可编程门阵列（FPGA）的无线局域网（WLAN）基2流水线FFT处理器。与存储在传统的ROM中不同，我们设计的流水线FFT处理器中的旋转因子可以直接访问。还提出了一种新的简单地址映射方案。FFT处理器有两条流水线，一条执行蝶形单元的复杂乘法，另一条是在RAM模块之间，RAM模块读取输入数据，存储蝶形单元的临时变量，并输出最终结果。最后，流水线64点FFT处理器可以在仅67个时钟周期内完全实现。

关键词：fft；FPGA；地址映射

一、引言

快速傅立叶变换（FFT）处理器广泛应用于无线局域网、图像处理、频谱测量、雷达和多媒体通信等不同领域。然而，快速傅立叶变换算法是一项要求很高的任务，它必须经过精确的设计才能得到有效的实现。如果使FFT处理器具有足够的灵活性和速度，可以配备无线传输系统的便携式设备。实时操作需要一个高效的FFT处理器，因此，设计一个FFT处理器具有重要意义。

近二十年来，FPGA发展迅速，并逐步普及。与传统ASIC的设计流程相比，基于FPGA的设计具有灵活性和高性价比的优点。许多研究人员研究了基于FPGA的流水线FFT。例如，他们提出了一种为无线应用设计FFT处理器的方法，但其设计有太多的时钟周期，速度不够快。与上述方案相比，本文提出了一种简单可行的基于FPGA的32位64点快速傅立叶变换（FFT）无线局域网流水线实现方案。

本文的组织结构如下。在下一节中，我们将介绍一个基本的基-2快速傅立叶变换算法，简要讨论哪种抽取方式对系统更好，三乘法，以及一种新的地址映射方案，它可以减少延迟并提高系统的速度。第三节提出了流水线快速傅立叶变换结构，并对每一单元进行了说明。第四部分是基于FPGA的64点FFT处理器的实现，并明确列出了硬件资源。最后一部分给出了结论。

二、FFT算法与地址映射方案

A.基-2FFT算法

FFT算法可以有效地计算离散傅立叶变换。给定n个复数的序列x（n），我们可以根据下面的公式计算它的dft和n个复数的另一个序列x（k）。

（1）

根据抽取方式的不同，可分为两类：DIF（频率抽取）和DIT（时间抽取）。DIF算法比DIT更易于设计。并且考虑到有限字长效应，DIF比DIT具有更大的优点，如在定点实现时通过乘法引入的加性噪声，降低了整个系统的复杂度。因此，我们使用DIF算法来设计基-2的FFT模块，目前大多数的FFT处理器也基于该算法。

B.三乘法

不可否认，复杂乘法是影响FFT处理器速度和吞吐量的主要因素。计算复杂乘法需要四个实数乘法和两个实数加法。众所周知，在FPGA中，实际乘法器的硬件面积大于实际加法器的硬件面积。因此，我们应该尽最大努力将复杂的乘法转换成加减法，以尽可能地优化整个性能。考虑到所有的操作数都是32位复数，两个输入x_m（i）和x_m（j）的差可以表示为z₁=x₁ jy₁，旋转因子可以表示为z₂=x₂ jy₂。所以它们的乘积也可以用z=x jy表示。也就是说，积的16位实部x等于x₁x₂-y₁y₂，16位虚部y等于x₁y₂ x₂y₁。

因此，我们可以很容易地将积z转换为以下方程

（2）

（3）

显然，使用这种分解方案，系统具有一些优势。实数乘法的数目从4减少到3。由于加法比乘法消耗少，从而降低了系统的功耗。在本研究中，我们可以在FPGA中节省16个嵌入式乘法器9位元件。

对于这个64点FFT处理器，在它们参与真正的乘法运算之前，可以得到x₂ y₂、x₁-y₁、x₁ y₁、x₂和y₂的数值。

C.新的地址映射方案

本文系统的块大小为64点，考虑到基2 64点FFT的特点，需要一次从存储器中读取8个操作数，才能实现高速的快速傅立叶变换。众所周知，并行访问数据对系统至关重要。因此，我们设计的这8个操作数位于内存块的不同行或列中，这种排列确保8个操作数无内存访问的冲突，可以并行执行。最初，我们使用8个32位双端口存储器按顺序存储64个操作数。而后采用一种新的线性移位无冲突地址映射方案来改变操作数的地址。操作数的主要二维地址将映射到新地址。

例如，我们假设原始的二维坐标是（a，b），其中a和b分别代表一个存储器中数据的地址和8个存储器的数量。然后，我们通过以下方程得到一个新的无冲突地址（A，B）：

（4）

（5）

在我们的设计中，可以保证不同时读取或写入内存位置，这种新的映射方案是可行的、有效的和简单的。

三、流水线FFT处理器架构

对于大吞吐量系统，流水线结构是一种很好的选择，同时由于其结构规则、控制简单，也是实现高速大尺寸FFT的理想方法。通过优化结构，节省硬件资源，可以提高流水线FFT处理器的性能。我们提出的FFT处理器的方块图由四个基本单元组成。控制单元是FFT处理器的核心，协调了整个系统。蝴蝶单元（BU）采用三级流水线结构，实现了复杂的乘法运算。两个双端口RAM用于存储和输出数据。地址发生器单元（AGU）产生8个3位读写地址。

A.控制单元

控制单元为整个系统生成所有的控制信号，负责处理器的运行控制。48位信号w_con控制整个FFT处理器。这个信号产生两个参数，写入参数和读取参数，来控制AGU。它还生成sel1和sel2信号，从两个RAM中选择数据，每个RAM由8个32位寄存器组成。BU和其余部分也由w_con控制。此控制单元协调基于7位计数器的FFT处理器的所有步骤。

B.DIF蝴蝶单元

对于快速傅立叶变换（FFT）算法来说，计算两个输入数据之和与差的BU是其核心部分，并且在计算差与旋转因子的乘积中起着极其重要的作用。

我们只使用11个因子，，，，，，，，，和表示在这个FFT处理器中我们需要的所有32个因子，因为这个旋转因子可以分为两个部分。例如，可以从和的乘积中派生出来。此外，的值是一个常数1，对于，只需要一个负号就可以添加到相关数据的实部，然后对实部和虚部进行求反。所以我们可以消除这两个因素，也就是说，实际上我们只需要9个旋转因素。此外，我们使用16位定点小数来表示这9个旋转因子。定点小数算法虽然精度不高，但能满足一般系统的要求。

由于旋转因子与相应数据的相乘非常重要，因此采用三级流水线结构进行复杂的相乘，获得了高速的计算结果。

在BU中，两个复杂输入都是32位，包括16位实部和16位虚部。为了避免算术溢出，需要将它们的和缩小2倍，并且对它们的差异应用相同的操作。另一方面，第二多路复用器的因数和第一参数con_s不涉及复合乘法器，它们可用作常数1。从而降低了复杂乘法器的功耗，节省了硬件资源。

有一些要点需要强调。差分因子和旋转因子都是32位，所以第一个复数乘法器的结果将是64位。但是，由于我们采用定点十进制计算，我们应该把它截取到一个32位参数f_mult作为第二个复数乘法器的输入。

本单元最显著的优点是利用3个32位寄存器实现蝶形变换的三级流水线，用寄存器1存储差分，寄存器2存储第二级F_mult截获的结果，寄存器3存储最终结果cmul_b。

C. RAM单元

RAM1和RAM2分别由8个32位寄存器组成。数据总是从RAM2写入外部存储器，并且总是从外部存储器读取到RAM1。

然后让我们介绍本单元中使用的关键算法。考虑到64点FFT的特点，我们可以将基2-dif 8点FFT作为一个整体单元，因此完成64点FFT只有两个阶段。这两个阶段与标准基2 DIF 64点FFT的六个阶段相同。系统并行一次从外部存储器读取8个32位操作数到RAM1，我们只需要读取16次。

RAM单元中的管道简要讨论如下。首先，系统从外部存储器中读取8个操作数，并将它们写入RAM1，计算结果后将结果存储在RAM2中。同时，系统读取接下来的8个操作数。随后，系统将从RAM1或RAM2访问操作数，以计算这16个操作数。此外，在一个时钟内，四个蝶形计算将同时执行。这16个操作数的最终结果将全部存储在RAM2中，然后写入外部存储器。同时，将读取另外8个操作数。因此，只需要76个时钟周期就可以完成这个基2 DIF 64点FFT。

D.AGU

与其他单位相比，AGU也相当重要。它将创建8个读取地址和8个写入地址，从而确定对外部存储器的数据访问。

在该快速傅立叶变换（FFT）处理器中，我们采用了就地计算的方法，使其成为一个更简单、更快的系统。也就是说，我们把结果写在它们被读取的地方。与通过地址映射配置的64个输入操作数的序列不同，该FFT处理器的最终输出序列是位倒序的，需要调整到正常顺序。在计算FFT之前，我们可以做适当的调整。因此，尽管我们调整了输入或输出的顺序，但是我们的FFT处理器的性能不会降低。

四、硬件资源

成功地进行了功能仿真和时序仿真。本设计的主要硬件资源如下。该芯片为Cyclone II系列EP2C70F896C6。逻辑元件总数为562/68416（8%），管脚总数为563/622（91%），嵌入式乘法器9位元件总数为48/300（16%）。同时，时钟频率为31.69MHz。上文中提出的一种定点16位64点FFT处理器，共92个时钟周期，但我们的时钟周期是67个。我们的FFT处理器速度更快，功耗更低。

五、结论

本文提出了一种基于FPGA的无线局域网基-2FFT处理器，以Verilog HDL为硬件描述语言，QuartusII为设计合成工具。为了实现高吞吐量，蝶形单元和双端口RAM采用了流水线结构。采用一种新型的简单地址映射方案，使得专用的并行流水线快速处理输入数据，大大提高了系统的整体性能。对于基二系统，这种映射方案比其他大多数映射方案更好、更简单。该设计在FPGA芯片上实现。这种流水线的FFT在2.1微秒内完成了一个复杂的64点FFT，硬件测试结果说明它可以满足无线局域网的要求。

基于CORDIC的实时谐波分析仪基4快速傅立叶变换处理器的FPGA实现

本文介绍了一种基于CORDIC算法的基-4快速傅立叶变换处理器的设计，主要用于电力谐波信号的处理。该处理器采用现场可编程门阵列（FPGA），具有效率高、成本低、实现方便、开发周期短等特点，性能令人满意。选择CORDIC算法实现快速傅立叶变换的基本蝶形运算，省去了存储旋转因子的需要，与采用其他技术的相应算法相比，节省了大量硬件。采用双口存储器结构和相应的寻址方案实现了对现场数据的访问，并从双端口存储器中按适当的顺序获取数据并将结果写入双端口存储器所需的地址生成单元也集成在容纳控制器的芯片中。整个设计使用Altera CycloneII EP2C8Q208C8系列FPGA实现，需要大约3162个可配置逻辑块。

关键词：CORDIC；基数-4；FFT；FPGA

一、引言

随着电网中非线性器件的使用越来越多，谐波含量也越来越高，对电能质量的要求也越来越严格。电力系统中的谐波会导致设备和导体发热，变速驱动器缺火，以及电机的转矩脉动。高水平的电力系统谐波会造成电压畸变和电能质量问题。

为了保证电网和电力电子技术的安全运行，满足发展的需要，必须采取有效措施抑制谐波，谐波测试是谐波分析的第一步。

目前，谐波检测方法多种多样。基于瞬时无功功率（IRP）理论的谐波信号提取方法在谐波补偿中得到了广泛的应用。但目前，用数字控制代替传统的模拟控制似乎需要更多的研究。对于小波变换方法和神经网络方法，只有计算出各谐波电压、电流幅度和相位角，才能求出谐波含量。由于小波变换和神经网络的复杂性，在实际工程中还没有得到广泛的应用。在电网中，最常用的谐波估计方法仍然是基于快速傅立叶变换（FFT）的谐波估计方法，该方法可以得到各次谐波的幅度和相位。由于数据处理量大，必须采用单片机和DSP等高性能技术，但单片机的时钟频率有限，难以满足实时性要求。而采用DSP设计的快速傅立叶变换（FFT）处理器，不能很容易地更新其功能，扩大客户所需的容量。各种成本高的ASIC快速傅立叶变换器芯片，限制了其广泛应用。

基于FPGA的FFT处理器在信号处理、图像处理等领域有着广泛的应用。它具有并行性和吞吐能力强的特点，可以满足使用FPGA器件进行实时计算的要求。与传统的基于DSP或PC编程的快速傅立叶变换处理器相比，它具有很大的速度优势。利用FPGA不仅可以解决电力系统的柔性配置问题，而且可以很好地解决电力系统谐波检测中的实时性和准确性之间的矛盾。

本文提出了一种新的基于流水线、精简内存的基4快速傅立叶变换（FFT）体系结构。采用双端口存储器结构和相应的寻址方案实现了现场数据访问。提出的内存缩减CORDIC算法不需要存储旋转因子，从而节省了大量的区域，且对性能没有负面影响。作为一个案例研究，基于CORDIC的基-4FFT处理器已经在FPGA中实现。其余工作安排如下。第二节简要介绍了基4快速傅立叶变换和CORDIC算法的基本原理。第三节介绍了本文提出的基于CORDIC的快速傅立叶变换器的硬件结构，第四节给出了实验结果，并对今后的研究进行了展望。

资料编号：[4823]