每日精学 138｜基二DIF蝶形分解

2026-09-25

雷达 · 通信 · 电子战　/　基础精学 138

基二频率抽取FFT先对输入前后半段执行和差，再对差支路乘旋转因子，把偶频与奇频输出化为两个半长DFT。

01
模型与符号

N为2的幂，负指数非归一化DFT；前后半段索引配对不发生循环偏移。

u[n],v[n]：和差支路（幅度）

WN：旋转因子（无量纲）

X[2k]：偶频输出（幅度谱）

X[2k+1]：奇频输出（幅度谱）

02
从模型到公式

前后半段配对

利用

W_N^{k(n+N/2)}=(-1)^kW_N^{kn}

得到

X[k]=\sum_{n=0}^{N/2-1}(x[n]+(-1)^kx[n+N/2])W_N^{kn}.

偶频支路

对 k=2r，定义 u[n]=x[n]+x[n+N/2]，则

X[2r]=\sum_{n=0}^{N/2-1}u[n]W_{N/2}^{rn}.

无需该层旋转即可得到偶频半长DFT。

奇频支路

对 k=2r+1，令

v[n]=(x[n]-x[n+N/2])W_N^n,

便有

X[2r+1]=\sum_{n=0}^{N/2-1}v[n]W_{N/2}^{rn}.

与DIT相比，旋转位于和差运算之后，定点舍入与溢出位置也随之改变。

和差先行的可逆性

在乘旋转因子之前，DIF 的和差映射可以直接求逆。设 u=a+b、v=a−b，则

a=(u+v)/2,\qquad b=(u-v)/2.

对整数输入，精确的 u,v 必有相同奇偶性，使两个分子均可被二整除。

若提前分别截断和差支路，这一可逆性可能消失；输出低位并非天然无用的冗余。

u\equiv v\pmod 2.

一般复数旋转只改变差支路的相位，不改变实数精确算术下的可逆结构。

DIT 与 DIF 的差别在分解方向和中间排列，不能仅凭单个和差核判断整个变换采用了哪一种输入或输出地址顺序。

03
物理含义

DIF按输出频率的奇偶递归拆分，因此常见就地数据流由自然序输入产生位反转序输出。

04
固定参数算例

取64点复数记录，显式形成和差支路，分别计算半长DFT并按偶奇频率交织，与原DFT比较；检验Parseval能量一致性。

固定参数数值验证结果
量数值
length64
半长32
transform max error5.40257841157e-15
parseval error0
butterfly energy error1.13686837722e-13
输出峰值25.8354589441
图 1：基二DIF蝶形分解的理论关系与固定参数验证图 1：基二DIF蝶形分解的理论关系与固定参数验证

图 1　基二DIF蝶形分解的理论关系与固定参数验证

表中数值和图中曲线由 MATLAB 实际运行得到，随机种子为 20261057；运行版本与完整结果另存为独立文件。

05
数字实现的边界

RTL实现实数和差蝶形 u=a+b、v=a−b，旋转乘法置于模块之后。64位输出保存精确和差，避免先缩窄到16位。 RTL 采用同步有效信号和异步低有效复位；

空拍保持状态且输出无效。除另有说明外，输入为16位有符号整数，结果为64位有符号整数，测试范围内不截断或饱和。输出在采样时钟上升沿更新。自检覆盖连续样本、空拍和复位；

未进行器件布局布线、时序收敛或功耗验证。

独立自检程序已在 Icarus Verilog 13.0 中实际运行并通过。该结果不包含器件综合、静态时序分析或板级测试。

06
适用范围

DIF结构适合自然序数据进入、按递归频率分组输出的FFT实现。差支路旋转的位置决定乘法器输入范围和流水寄存器安排。后级若接受位反转序，可直接消费输出；若要求自然序，则需要相应存储重排。

07
工程上需要注意

输出置换必须与后级接口约定匹配。

和差支路瞬间峰值可以为输入两倍。

数学等价不意味着DIT和DIF逐位结果相同。

基二频率抽取FFT先对输入前后半段执行和差，再对差支路乘旋转因子，把偶频与奇频输出化为两个半长DFT。

内容依据：每日精学第 138 课《基二DIF蝶形分解》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。

阅读10
分享
写评论...