一、引言

快速傅里叶变换（FFT）作为计算和分析工具，在信号处理、图像处理、生物信息学、计算物理、应用数学等众多学科领域有着广泛的应用。在高速数字信号处理领域，如雷达信号处理，FFT的处理速度往往是整个系统设计性能的关键所在。针对高速实时信号处理的要求，传统的软件实现方法显然无法满足需求。近年来，现场可编程门阵列（FPGA）以其高性能、高灵活性、友好的开发环境、在线可编程等特点，使得基于FPGA的设计可以满足实时数字信号处理的要求，在市场竞争中具有很大的优势。

二、FFT算法原理

FFT算法的基本思想是利用权函数的周期性、对称性、特殊性及周期N的可互换性，将较长序列的DFT（离散傅里叶变换）运算逐次分解为较短序列的DFT运算。针对N=2的整数次幂，FFT算法有基-2算法、基-4算法、实因子算法和分裂基算法等。从处理速度和占用资源的角度考虑，本文选用基-4按时间抽取FFT算法（DIT）。

对于N=4γ，基-4 DIT具有log4N=γ次迭代运算，每次迭代包含N/4个蝶形单元。蝶形单元的运算表达式为：

A′ = A + B × W
B′ = A - B × W
C′ = C + D × W
D′ = C - D × W

其中，A, B, C, D和A′, B′, C′, D′均为复数据；W=e-j2π/N。进行1次蝶形运算共需3次复乘和8次复加运算。以64点数据为例，只需进行3次迭代运算，每次迭代运算含有N/4=16个蝶形单元。

三、FPGA选型与元器件功能

在基于FPGA的高速定点FFT算法设计中，选择合适的FPGA器件至关重要。本文将详细介绍FPGA选型过程，并阐述所选元器件的型号、作用、选择原因及功能。

3.1 FPGA选型

在FPGA选型时，需要综合考虑多个因素，包括逻辑资源、I/O资源、布线资源、DSP资源、存储器资源、锁相环资源、串行收发器资源和硬核微处理器资源等。同时，还需要考虑器件的功耗、性能、成本、供货稳定性以及开发工具的兼容性等。

针对高速定点FFT算法的设计需求，本文选择Altera公司的Stratix系列EP1S25型FPGA作为核心器件。该器件具有高性能体系、大容量存储资源、高带宽DSP模块等特点，能够满足高速定点FFT算法对处理速度和资源的需求。

3.2 元器件功能与电路框图

3.2.1 FPGA（EP1S25）

型号：EP1S25

作用：作为整个FFT处理器的核心器件，负责实现FFT算法中的各种运算和控制逻辑。

选择原因：

• 高性能：EP1S25具有高性能体系，能够满足高速定点FFT算法对处理速度的要求。

• 大容量存储资源：该器件包含大量的存储单元，可用于存储旋转因子和中间结果，提高FFT运算的效率。

• 高带宽DSP模块：EP1S25内置了高带宽DSP模块，能够完成较为耗费资源的乘法器单元功能，提高FFT运算的精度和速度。

• 开发环境友好：Altera公司提供了完善的开发环境和工具链，方便用户进行FPGA设计和仿真。

功能：

• 实现FFT算法中的蝶形运算、旋转因子乘法等运算。

• 协调控制各个模块之间的数据传输和时序关系。

• 提供与外部设备的接口，实现数据的输入和输出。

电路框图：

+-----------------+

|      FPGA       |

|  (EP1S25)       |

|                 |

|  蝶形运算单元   |

|  旋转因子单元   |

|  控制单元       |

|  数据控制单元   |

|  存储器接口     |

+-----------------+

3.2.2 存储器（RAM和ROM）

型号：根据设计需求定制

作用：用于存储输入数据、中间结果和旋转因子等。

选择原因：

• 大容量：需要足够大的存储容量来存储64点FFT运算所需的输入数据、中间结果和旋转因子。

• 高速访问：存储器需要具有高速访问能力，以满足FFT运算对数据处理速度的要求。

• 双端口设计：为了方便数据的读写操作，存储器采用双端口设计，允许同时进行读和写操作。

功能：

• 输入RAM：用于存储外部输入的64点复数数据。

• 中间结果RAM：用于存储FFT运算过程中产生的中间结果。

• 旋转因子ROM：用于存储FFT运算所需的旋转因子。旋转因子是预先计算好的固定值，存储在ROM中可以节省FPGA的逻辑资源。

电路框图：

+-------------+       +-------------+       +-------------+

|  输入RAM    |-------| 中间结果RAM |-------| 旋转因子ROM |

+-------------+       +-------------+       +-------------+

3.2.3 蝶形运算单元

型号：自定义设计

作用：实现FFT算法中的蝶形运算。

选择原因：

• 高效性：蝶形运算单元是FFT处理器的核心部件，其设计需要高效性，以减少运算时间和资源消耗。

• 并行性：为了提高FFT运算的速度，蝶形运算单元需要支持并行运算。

功能：

• 实现基-4蝶形运算公式中的复乘和复加运算。

• 支持并行输入和输出数据，提高运算速度。

电路框图：

+-----------------+

|  蝶形运算单元   |

|                 |

|  复乘器1        |

|  复乘器2        |

|  复加器1        |

|  复加器2        |

|  复加器3        |

+-----------------+

3.2.4 旋转因子单元

型号：自定义设计（基于ROM实现）

作用：提供FFT运算所需的旋转因子。

选择原因：

• 节省资源：旋转因子是预先计算好的固定值，存储在ROM中可以节省FPGA的逻辑资源。

• 高速访问：ROM具有高速访问能力，可以满足FFT运算对旋转因子的快速访问需求。

功能：

• 存储FFT运算所需的旋转因子。

• 根据控制单元提供的地址信号，输出相应的旋转因子给蝶形运算单元。

电路框图：

+-----------------+

|  旋转因子单元   |

|                 |

|  ROM            |

|  地址译码器     |

+-----------------+

3.2.5 控制单元

型号：自定义设计（基于有限状态机实现）

作用：协调控制各个模块之间的数据传输和时序关系。

选择原因：

• 灵活性：有限状态机具有高度的灵活性，可以根据FFT运算的需求动态调整控制逻辑。

• 可靠性：有限状态机设计简单、易于调试，能够提高FFT处理器的可靠性。

功能：

• 产生控制信号，协调各个模块之间的工作。

• 控制数据的输入、输出和存储过程。

• 监控FFT运算的状态，确保运算的正确性。

电路框图：

+-----------------+

|   控制单元      |

|                 |

|  有限状态机     |

|  计数器         |

|  比较器         |

+-----------------+

3.2.6 数据控制单元

型号：自定义设计

作用：负责数据的输入输出控制，以及数据格式的转换和处理。

选择原因：

• 灵活性：数据控制单元需要根据FFT运算的需求灵活调整数据输入输出方式。

• 高效性：数据控制单元需要高效处理数据，以减少FFT运算的延迟。

功能：

• 控制数据的输入输出时序。

• 对输入数据进行预处理，如格式转换、定点化等。

• 对输出数据进行后处理，如格式转换、溢出判断等。

电路框图：

+-----------------+

|  数据控制单元   |

|                 |

|  数据输入接口   |

|  数据输出接口   |

|  数据格式转换器 |

|  溢出判断器     |

+-----------------+

四、设计方案详述

4.1 流水线方式FFT算法的实现

为了提高FFT工作频率和节省FPGA资源，采用流水线结构实现64点的FFT运算。流水线处理器的结构由多级组成，每级均由延时单元、转接器（SW）、蝶形运算和旋转因子乘法4个模块组成。延时节拍由方框中的数字表示。各级转接器和延时单元起到对序列进行码位抽取并将数据拉齐的作用。每级延时在FPGA内部用FIFO实现，不需要对序列进行寻址即可实现延时功能。数据串行输入，经过多级流水处理后，串行输出。

4.2 存储单元设计

为了实现算法的流水线设计，存储器RAM设计为双端口RAM，即在时钟信号和写控制信号同时为低电平时，从输入总线写入RAM；在时钟信号和读控制信号同时为高电平时，从RAM输出数据。ROM用于储存经过量化后的旋转因子，旋转因子为正弦函数和余弦函数的组合。根据旋转因子的对称性和周期性，在利用ROM存储旋转因子时，可以只存储旋转因子的一部分，通过地址的改变查询出每级蝶形运算所需的旋转因子。

4.3 运算结构设计

Radix-4蝶形运算单元是整个FFT处理器中的核心部件。在用Radix-4运算器计算时需要并行输入数据，如果能以并发数据输入的话，则同步性和控制度较好。存储RAM按单节拍输出数据，选择器不停旋转送入到确定的位置，每4点全部到位后R-4使能有效；然后4个时钟节拍得到有效结果数据，再通过选择器旋转送入到对应存储RAM中。复数运算中，对应复数的实部和虚部RAM用同一个地址发生器。地址发生器在进行RAM地址发生时采用两套地址，第一套是计数器按时钟节拍顺序产生的，用于输入数据的存储；第二套是由数据宽度为16b的ROM产生的，ROM中存放的数据为下级运算所需倒序的序列地址，发生地址给RAM，然后RAM按倒序地址输出下级需要进行运算的数据。

4.4 块浮点结构设计

数字信号处理系统可分为定点制、浮点制和块浮点制。定点制算法简单、速度快，但动态范围有限；浮点表示法动态范围大，可避免溢出，但系统实现复杂、硬件需求量大、速度慢。为了提高精度并减少复杂度和存储量，采用块浮点结构。块浮点算法是定点制和浮点制的结合，一组数共用同一个阶码，这个阶码是这组数中最大数的阶码。在调整时仅保留一位符号位，因而能够充分利用有限位长。这样处理比定点方法扩大了动态范围，并且提高了精度，比浮点运算在速度上有了提高。

五、综合仿真与验证

选用Altera公司的QuartusⅡ软件作为开发平台，以Stratix系列中的EP1S25型FPGA为器件，采用自顶向下的设计思路和VHDL语言，实现对各个模块单元的设计、综合和仿真。为了简化设计，只在数据输入时钟下输入了一组64个复数，其余输入设为0，并且实部和虚部都限定在一定范围内。为防止溢出先将输入数据乘以一定比例因子，再转化为十六进制数。输出的结果需要乘以相应的比例因子才是实际结果。将仿真结果与Matlab计算的结果相比较，数据基本一致，说明了设计正确。其误差主要来源于数据的截取和旋转因子的近似。

六、结论与展望

本文着重讨论了基于FPGA的64点高速定点FFT算法的实现方法。采用高基数结构和流水线结构，大大提高了FFT处理器的运行速度。同时块浮点结构的引入也大幅减少了浮点操作占用FPGA器件的资源数目，兼顾了FPGA高精度、低资源、低功耗的特点。从实验结果看，该方法可以满足高速实时处理数字信号的要求。

未来工作可以进一步优化FPGA资源的使用效率，提高FFT处理器的性能。同时，还可以探索将FFT算法应用于更多领域，如实时图像处理、无线通信等，以发挥FPGA在高速数字信号处理领域的优势。