每日精学 220｜列表译码的父路径索引重映射
雷达 · 通信 · 电子战 / 基础精学 220
01
摘要与关键词
候选排序产生的是父路径与分支标签，而软信息、部分和与已判决比特仍位于旧路径槽。若直接把保留名次当作父路径地址，候选度量可以正确而后续递推状态错误。索引重映射把选择结果转化为明确的状态复制关系，属于列表译码控制与数据的一致性问题。
技术分析在明确的模型和符号约定下给出基本关系、推导与适用边界，并用固定参数数值算例和独立整数接口自检分别核对模型运算与数字子核。两种验证层次的输入尺度和覆盖范围分别记录，有限算例不外推为完整系统性能。
关键词：列表译码的父路径索引重映射；条件模型；数值验证；数字实现
02
问题背景
候选排序产生的是父路径与分支标签，而软信息、部分和与已判决比特仍位于旧路径槽。若直接把保留名次当作父路径地址，候选度量可以正确而后续递推状态错误。索引重映射把选择结果转化为明确的状态复制关系，属于列表译码控制与数据的一致性问题。
该问题位于由模型关系到有限精度数据通路的连接处。数学等式首先规定各量的语义；随后需要确认计算采用的输入、范围与尺度符合等式前提。公开基础信号处理中的观测证据、约束集合和数值表示具有不同作用，混淆这些作用会使输出虽落在合法范围，却不再对应所声明的模型。
03
假设与符号表
父路径槽数为 L，每条状态含 D 个分量；保留候选的父标识范围为零到 L−1。重映射使用旧状态的同一快照，允许两个新槽指向同一父槽，不允许在读取结束前覆盖快照。
所有对数未特别注明时采用自然对数。向量和矩阵的行列方向由公式明确指定；概率质量、条件密度和未归一化权重分别按定义使用。整数码只表示某个中间量，不默认具有物理单位。实际数值算例保留所列固定参数，不能据其有限取值范围推断一般输入的性能。
L：活动路径容量（正整数）
pi：新槽 i 对应的父槽（路径地址）
Sj,d：旧路径 j 的第 d 个状态（状态量）
Ti,d：重映射后的新状态（状态量）
bi：保留候选的扩展比特（二元）
04
基础公式与完整推导
重映射矩阵
每个新槽只读取一个父槽，因此矩阵的每行恰有一个单位元。把矩阵乘法逐元素展开，即得到 T 的第 i 行等于 S 的第 pi 行；多行可以读取同一列，故该映射一般不是置换。
分支扩展
状态复制先确定旧状态，再施加分支更新。两个候选具有相同父地址但不同分支时，复制部分相同，更新部分允许不同。这解释了地址与分支必须同时进入流水线的原因。
重复父地址
两个新路径是否共享旧状态可以由行内积判断。该等式来自对 j 的求和，只有共同父地址才贡献一个单位元。重复父地址并不违反逻辑路径的独立性，但写操作必须隔离。
原地覆盖反例
先把槽一写入槽零，再读取槽零，会把两个输出都变成 b。理想结果应为 b 与 a。双缓冲、读后写阶段或带版本的共享存储可以保持快照语义。
地址误差边界
地址错误是离散的状态选错，不能归入很小的算术舍入误差。即使度量量化没有改变保留集合，一个父标识位错误仍可能替换整条状态向量。
05
一致性与敏感性分析
快照与版本一致性
版本号把候选选择与状态读取关联起来。重复父槽的多个新状态必须从同一旧版本取值，不能让较早到达的更新污染较晚的读取。
当 L 不是二的幂时，未使用地址码仍须被有效位屏蔽；地址位宽足够不代表所有位型都合法。
模型关系与数值误差的区分
推导中的恒等关系在其假设下精确成立；计算时观测模型误差、输入量化和中间舍入属于不同来源。设理想运算为 y=f(x)，输入量化扰动为 ex，具体数值实现误差为 ea，则输出可写为
若 f 在所讨论的连续参数点可微且扰动足够小，一阶项为 Df(x)ex。
地址、候选掩码、分支标签和状态版本是离散量，不满足这种局部微分假设；改变一个控制位可能换掉整个合法集合或数据来源。因此连续误差界不能用于替代控制语义检查。
只有将同一输入送入独立的数学参考与被测实现，差值才隔离数值实现误差。若两个程序各自生成随机输入，输出不同可能来自不同样本；若参考重复使用相同错误的符号约定，逐点一致也不能证明定义正确。固定参数算例、结构不变量和边界事务提供互补证据。
06
物理含义
父地址描述信息来源，新槽地址描述保留后的存储位置。两者分离后，候选重排不改变已得到的信息，只改变其组织方式。该操作没有信号幅度增益，也不是对软信息的线性滤波。
数学输出需要按定义解释。无量纲比值、自然对数度量、概率权重和整数地址分别回答不同问题；即使都存放在定点寄存器内，也不能互相替代。输出幅度变化可能来自公共尺度、观测变化或可行集合变化，只有回到模型定义才能确定其含义。
07
数值验证
固定四条父路径，每条三个互异整数状态；枚举四个父地址的全部四元组合，共 256 种映射。矩阵乘法参考与直接索引结果逐元素比较，并单独保存交换反例。
配套 MATLAB 语法脚本实际在 GNU Octave 10.3.0 中执行，完成断言、数据导出与图表生成。MATLAB R2026b 启动返回许可证到期错误，因此本次没有取得 MATLAB 原生运行结果。
该边界只限定运行环境，不将历史 MATLAB 日志作为本次数值证据。完整实际输出、运行版本及绘图数据与脚本一起保存。
| 结果字段 | 实际值 |
|---|---|
| mapping count | 256 |
| max state error | 0 |
| duplicate parent sum | 69 |
图 1 列表译码的父路径索引重映射的固定参数数值关系
图中横轴为脚本中规定的扫描参数或样本索引，纵轴为实际计算值；多条曲线按脚本列顺序对应各计算序列。曲线连接用于显示离散扫描结果，不意味着中间所有参数已经仿真。确定性穷举仅覆盖声明的有限域；随机向量用于补充不同组合，不构成连续参数上的证明。
08
数字实现与验证边界
四路八位状态选择器；输入四个二位父地址，输出四个对应状态字。硬件仅实现一个状态分量的重映射，完整向量需复用或并行扩展。
整数接口及有效周期
独立模块统一使用同步高有效复位和输入输出有效标志。输入总线分成八个十六位槽，各槽低八位承载本子核实际使用的码字；控制总线提供对应掩码、标签或地址。未使用槽不参与数学运算。
输出分成四个三十二位槽，负结果采用二补码；保护位用于保存中间精确整数结果，不代表算法必须使用三十二位物理精度。
被测时钟上升沿先判断复位；复位优先于有效输入并清除输出数据与输出有效位。非复位的有效输入在该边沿形成输出，输出有效位同步置一。无效输入周期仅清除输出有效位，数据保持上一次有效结果。调用者只能在输出有效时消费数据，不能把保持的旧值当作新的计算结果。
量化尺度与中间位宽
若整数码 q 对应实际量 x=q2−F，小数位数 F 应在接口中固定。两个同尺度量相加保持尺度，乘积的尺度为 2−2F。
模块中的宽位整数运算先保存完整结果；若外部需要重新缩放，必须明确舍入方向和饱和策略。
八位有符号输入包含最小码字 −128，它的正幅值 128 不能用八位有符号数表示。
绝对值、符号取反、乘积及多项加和必须先扩展位宽。精确整数参考直接使用宽整数计算，输出编码再转换为对应二补码，这样可区分算法差异与位宽回绕。
实际自检覆盖
Icarus Verilog 实际编译并运行独立自检，确认 4448 个有效向量、262 个无效周期和 5 次同步复位全部通过。输入包括零、一、127、128、254 和 255 的码字边界，多级组合与固定种子的随机向量。
自检同时核对有效标志、无效周期数据保持、复位与有效同时出现以及中途复位后继续接收。
| 事件 | 输入低三十二位 | 控制码 | 输出低三十二位 |
|---|---|---|---|
| 0 | 00000000 | 0000 | 00000000 |
| 1 | 00010001 | 0000 | 00000001 |
| 2 | 007f007f | 0000 | 0000007f |
| 3 | 00800080 | 0000 | 00000080 |
事件摘录以十六进制保存接口位型，完整输入和全部输出槽见独立追踪文件。低位摘录不承担全部数值结果的解释；完整测试通过状态来自对每个有效事务的全总线比较。参考向量由独立 Python 整数计算生成，不依赖被测 RTL 内的比较函数。
上述验证针对所声明的整数子核。它没有运行器件综合、静态时序、功耗分析或板级测量，也没有验证包含缓存、存储仲裁和完整算法控制器的系统。模块采用固定界限循环、组合算术与时钟寄存器构成，可作为可综合源代码；具体资源数和最高频率仍需目标工具与器件约束。
09
适用条件与工程应用
适用于分支选择后需要保持完整历史的列表算法。每一层可以具有不同的状态长度，但同一事务中的映射和状态必须使用相同版本。路径标识必须足够宽，并带有效标志。
工程接入应先确认输入是否正是公式中的量，再确定尺度、位序与事务边界。若某个量已由上游近似或饱和处理，应把该处理列入误差来源；后续子核的整数精确性不能恢复上游丢失的信息。并行和流水线可以改变吞吐与延迟，但不得改变同一事务中的控制与数据配对关系。
10
限制与非理想因素
错误地址、读写冲突与分支标签错拍是主要非理想因素。状态内容相同可能掩盖地址错误，因此验证使用互不相同的旧状态，并覆盖重复父地址与全体路径交换。
模型不匹配与有限精度并不具有相同修正方法。前者需要重新给出观测关系、约束或统计假设；后者需要增加保护位、选择合适缩放或改进数值运算。有限样本的误差为零仅说明当前输入与参考一致，不能自动推出未测试输入、完整链路或实际设备的误差为零。
11
配套脚本文件
| 文件 | 用途 |
|---|---|
| matlab/lesson220_verify.m | 固定参数数值计算与图表生成 |
| matlab/numerical_results.txt | 本次实际运行环境及关键数值 |
| matlab/plot_data.csv | 图表逐点数据 |
| systemverilog/lesson220_core.sv | 所声明的可综合整数子核 |
| systemverilog/tb_lesson220_core.sv | 有效周期、边界与复位自检 |
| systemverilog/reference_vectors.txt | 独立整数参考向量 |
| systemverilog/trace_results.txt | 实际事务追踪 |
12
结论
地址错误是离散的状态选错，不能归入很小的算术舍入误差。即使度量量化没有改变保留集合，一个父标识位错误仍可能替换整条状态向量。 父地址描述信息来源，新槽地址描述保留后的存储位置。
两者分离后，候选重排不改变已得到的信息，只改变其组织方式。该操作没有信号幅度增益，也不是对软信息的线性滤波。
固定参数数值复验和整数子核自检分别支持模型层关系与数字接口行为。结论的适用范围受所列假设、候选或状态集合、量化尺度以及实际运行环境限制；完整系统性能需在扩展模型与验证条件下另行评估。
13
参考资料
I. Tal and A. Vardy. List Decoding of Polar Codes. 2012. 在线原始资料。
GNU Octave. Arithmetic and Linear Algebra. 公开运行环境文档。
内容依据：每日精学第 220 课《列表译码的父路径索引重映射》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。