目录
引言
快速傅里叶变换（Fast Fourier Transform, FFT）是 离散傅里叶变换（DFT） 的高效计算算法，广泛应用于 信号处理、通信系统、频谱分析 等领域。
在 FPGA/ASIC 设计中，FFT 主要用于：
- OFDM（正交频分复用）系统
- 雷达和图像处理
- 实时信号分析
本文介绍 Verilog 实现 FFT 的方法，并提供 完整代码示例。
FFT 基本概念
3.1 DFT 和 FFT 关系
DFT（离散傅里叶变换）的数学定义如下：X(k)=∑n=0N−1x(n)⋅e−j(2πkn/N)
其中：
- X(k) 为第 k 个频域输出
- x(n) 为输入信号
- N 为变换点数
- 计算复杂度为 O(N²)
FFT 是优化后的 DFT，计算复杂度降低到 O(N logN)。
3.2 基 2 蝶形运算
FFT 采用 蝶形结构（Butterfly Unit） 进行运算，常见的 基-2（Radix-2）FFT 蝶形运算如下：
输入： A, B
权重： W
输出：
X1 = A + W * B
X2 = A - W * B
基-2 DIF（Decimation-In-Frequency）FFT 结构：
Stage 1: 8-point FFT
x0 ---+--- W0 --- x4
x1 ---+--- W1 --- x5
x2 ---+--- W2 --- x6
x3 ---+--- W3 --- x7
3.3 FFT 计算流程
FFT 计算包含 位倒序（Bit-Reversal）、蝶形运算（Butterfly Computation） 两步：
- 输入数据按照位倒序排列（Bit-Reversal Permutation）
- 依次进行蝶形运算，完成 FFT 计算
示例：
- 8 点 FFT（Radix-2 DIF）
- 输入序列 x(n)
- 变换输出 X(k)
Verilog FFT 代码实现
module fft #(
parameter N = 8, // FFT 点数（必须是 2 的幂）
parameter WIDTH = 16 // 数据位宽
)(
input clk,
input rst,
input signed [WIDTH-1:0] real_in [0:N-1], // 实部输入
input signed [WIDTH-1:0] imag_in [0:N-1], // 虚部输入
output reg signed [WIDTH-1:0] real_out [0:N-1], // 实部输出
output reg signed [WIDTH-1:0] imag_out [0:N-1] // 虚部输出
);
// 位倒序存储
reg signed [WIDTH-1:0] real_buf [0:N-1];
reg signed [WIDTH-1:0] imag_buf [0:N-1];
integer i;
always @(posedge clk or posedge rst) begin
if (rst) begin
for (i = 0; i < N; i = i + 1) begin
real_buf[i] <= 0;
imag_buf[i] <= 0;
end
end else begin
for (i = 0; i < N; i = i + 1) begin
real_buf[i] <= real_in[i];
imag_buf[i] <= imag_in[i];
end
end
end
// FFT 蝶形运算
reg signed [WIDTH-1:0] temp_real, temp_imag;
reg signed [WIDTH-1:0] w_real, w_imag;
always @(posedge clk) begin
for (i = 0; i < N/2; i = i + 1) begin
// 获取旋转因子 W
w_real = cos(2 * 3.14159265358979 * i / N) * (1 << (WIDTH-1));
w_imag = -sin(2 * 3.14159265358979 * i / N) * (1 << (WIDTH-1));
// 蝶形运算
temp_real = real_buf[i + N/2] * w_real - imag_buf[i + N/2] * w_imag;
temp_imag = real_buf[i + N/2] * w_imag + imag_buf[i + N/2] * w_real;
real_buf[i + N/2] = real_buf[i] - temp_real;
imag_buf[i + N/2] = imag_buf[i] - temp_imag;
real_buf[i] = real_buf[i] + temp_real;
imag_buf[i] = imag_buf[i] + temp_imag;
end
end
// 输出 FFT 结果
always @(posedge clk) begin
for (i = 0; i < N; i = i + 1) begin
real_out[i] <= real_buf[i];
imag_out[i] <= imag_buf[i];
end
end
endmodule
优化方案
1. 流水线优化
- FFT 计算可拆分为 多级流水线结构，提升时钟频率。
- 采用 分布式存储 解决数据依赖问题。
2. 优化旋转因子
- 预计算 W 系数 存入 ROM，提高计算效率。
- 采用 CORDIC 算法 计算 sin/cos 旋转因子，减少乘法计算量。
3. 支持不同点数的 FFT
- 采用 参数化 Verilog 代码 支持 16、32、64 点 FFT。
parameter N = 16; // 16 点 FFT
4. 采用固定小数位运算
- 使用 Q15/Q16 格式 代替浮点运算，提高 FPGA 计算效率。
发表回复