每日精学 137｜FFT位反转地址置换

2026-09-25

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

位反转置换把FFT逐级偶奇分组映射为二进制地址位序颠倒，并且该置换自身就是其逆映射。

01
模型与符号

长度 N=2^p，地址使用恰好p个无符号二进制位；只讨论地址，不更改样本数值。

p：地址宽度（bit）

n：自然序地址（index）

r_p(n)：位反转地址（index）

b_i：第i位（bit）

02
从模型到公式

地址展开

自然地址的二进制展开为

$n=\sum_{i=0}^{p-1}b_i2^i.$

逐级按最低位、次低位分组等价于把这些位作为高位优先排序，故

$r_p(n)=\sum_{i=0}^{p-1}b_i2^{p-1-i}.$

逆与一一性

再做一次位反转，将第 p−1−i 位移回第i位，所以

由此可知映射是双射，既无丢失也无重复；置换能量保持

$\sum|x[r_p(n)]|^2=\sum|x[n]|^2$

固定点数量

固定地址要求二进制位串回文，即 b_i=b_p−1−i。独立位数量为

$\lceil p/2\rceil$

故

$N_{\mathrm{fixed}}=2^{\lceil p/2\rceil}.$

原地交换只需处理 n<r_p(n) 的非固定地址对，以避免重复交换。

自逆置换的固定点计数

长度 p 的二进制地址经位反转后不变，当且仅当位串是回文。前半部分及奇数长度时的中心位可自由选取，其余位由对称性决定，所以

$N_{\mathrm{fixed}}=2^{\lceil p/2\rceil}.$

其余地址两两配对，原地实现仅需交换每对中的一次：

$N_{\mathrm{swap}}=\frac{2^p-2^{\lceil p/2\rceil}}2.$

对六位地址得到八个固定点和二十八次交换。

这些计数提供独立于逐地址表的结构校验。若对每个地址都无条件交换，会把每一对交换两次而恢复原顺序；只处理反转地址大于原地址的情形可以避免重复。

03
物理含义

位反转不是数值上的按大小排序，而是FFT递归路径在内存地址中的编码。

04
固定参数算例

对p=6枚举64个地址，验证双射、自逆、固定点8个及原地交换恢复；同时绘制地址映射与位反转前后数据。

固定参数数值验证结果

量	数值
地址位数	6
length	64
distinct addresses	64
fixed addresses	8
swap pairs	28
energy difference	0
inverse max error	0

图 1　FFT位反转地址置换的理论关系与固定参数验证

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

05
数字实现的边界

RTL反转输入a的低6位并输出0至63的地址，高位被明确忽略；对应N=64地址核，测试穷举全部64个地址并穿插空拍。 RTL 采用同步有效信号和异步低有效复位；

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

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

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

06
适用范围

位反转用于FFT输入预排、输出恢复自然序和RAM地址调度。若后级只执行逐频点独立运算，可以保留置换序并同步置换参数表，以避免额外搬移。需要频率邻域关系的操作则必须使用正确自然频率索引。

07
工程上需要注意

非2幂长度不能直接使用固定p位位反转。

混合基FFT的数字反转不同于二进制位反转。

地址端序与显示位序混淆可能造成数据错位。

位反转置换把FFT逐级偶奇分组映射为二进制地址位序颠倒，并且该置换自身就是其逆映射。

内容依据：每日精学第 137 课《FFT位反转地址置换》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。

阅读8

写评论...

每日精学 137｜FFT位反转地址置换

01模型与符号

02从模型到公式

地址展开

逆与一一性

固定点数量

自逆置换的固定点计数

03物理含义

04固定参数算例

05数字实现的边界

06适用范围