基于时间抽取的基2 FFT算法及其原位运算原理摘要离散傅里叶变换（DFT）的直接计算具有O(N2)O(N^2)O(N2)的复杂度，难以满足实时信号处理的需求。本文以按时间抽取（DIT）的基2快速傅里叶变换（FFT）为例，阐述其分解原理、蝶形运算结构及原位运算的实现条件。分析表明，该算法将运算复杂度由O(N2)O(N^2)O(N2)降至O(Nlog⁡2N)O(N\log_2 N)O(Nlog2​N)，并可在仅NNN个复数存储单元的条件下完成全部计算，但要求序列长度为222的整数次幂。关键词：快速傅里叶变换；基2 算法；蝶形运算；原位运算；倒位序1 引言离散傅里叶变换（Discrete Fourier Transform, DFT）是数字信号处理中的基本运算工具，用于对有限长序列进行频谱分析。对于长度为NNN的序列，其NNN点 DFT 的直接计算需N2N^2N2次复数乘法；当NNN较大时，该运算量难以满足雷达、通信等实时系统的处理要求。快速傅里叶变换（Fast Fourier Transform, FFT）在不改变变换结果的前提下，通过分解 DFT 的运算结构显著降低运算量。本文以按时间抽取（Decimation-In-Time, DIT）的基2算法为对象，论述其数学分解过程与硬件实现中的原位运算机制。2 DFT 的定义与运算复杂度2.1 定义长度为NNN的序列x[n]x[n]x[n]的NNN点 DFT 及其逆变换（IDFT）定义为X[k]=∑n=0N−1x[n] WNnk,k=0,1,…,N−1(1)X[k]=\sum_{n=0}^{N-1}x[n]\,W_N^{nk},\qquad k=0,1,\dots,N-1 \qquad (1)X[k]=n=0∑N−1​x[n]WNnk​,k=0,1,…,N−1(1)x[n]=1N∑k=0N−1X[k] WN−nk,n=0,1,…,N−1(2)x[n]=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\,W_N^{-nk},\qquad n=0,1,\dots,N-1 \qquad (2)x[n]=N1​k=0∑N−1​X[k]WN−nk​,n=0,1,…,N−1(2)其中WN=e−j2π/NW_N=e^{-j2\pi/N}WN​=e−j2π/N称为旋转因子（twiddle factor）。它对应复平面单位圆上均匀分布的NNN个点，WNkW_N^{k}WNk​可直观理解为在该圆上旋转kkk个步长。从频域视角看，DFT 相当于用NNN个不同频率的基函数去"投影"输入序列，从而得到各频点的分量强度。DFT 可视为连续傅里叶变换在时域与频域同时离散化的结果：时域以间隔TsT_sTs​采样，频域以间隔Δf\Delta f