每日精学 203｜ReedSolomon已知擦除的插值恢复

2026-09-25

← 技术专题 · 每日精学目录

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

求值编码以多余采样点承载冗余；当部分符号显式缺失时，可选取任意三个可靠点恢复原多项式。算法依赖已知点正确，不能直接处理未知位置的错误。

01
模型与符号

消息次数小于三，可靠节点 a1,a2,a3 互异，观测 yi=f(ai) 无错误；全部运算在 GF(8) 中进行。

ℓi(x)：Lagrange基函数（多项式）

yi：可靠取值（域符号）

ai：插值节点（域元素）

f(0)：常数系数（域符号）

wi：固定节点插值权重（域元素）

02
从模型到公式

单位基函数

构造

\ell_i(x)=\prod_{j\ne i}\frac{x-a_j}{a_i-a_j}.

节点互异使分母非零，且

\ell_i(a_j)=\begin{cases}1&i=j,\\0&i\ne j.\end{cases}

在二元扩域中减号等于加号，但分母仍是域逆元。


恢复与唯一性

插值多项式为

\widehat f(x)=\sum_{i=1}^3y_i\ell_i(x).

它次数至多二且在三点匹配。若存在另一个解，差多项式次数至多二却有三个根，只能恒零，因此

\widehat f=f.

固定位置常数恢复

只恢复常数项时

f(0)=\sum_{i=1}^3w_i y_i,\quad w_i=\prod_{j\ne i}\frac{a_j}{a_i+a_j}.

节点固定为一、二、三时权重可离线计算；完整信息恢复还需求取其余系数或在其他点重新求值。

固定三个节点的常数项捷径

在当前多项式基标签中，域元素一、二、三满足 1+2+3=0。特征二还使平方和等于和的平方，因此对于二次多项式

f(1)+f(2)+f(3)=3u_0+u_1(1+2+3)+u_2(1^2+2^2+3^2)=u_0.

这里的加法均为域加法，3u0 表示三次相加，等于 u0，不是普通整数乘三。

故固定节点常数项可以写成

u_0=f(1)\mathbin{\oplus}f(2)\mathbin{\oplus}f(3).

该简化为拉格朗日权重结果提供独立检查，但只适用于指定节点及二次模型。

任意节点组合仍需正确计算各自权重，恢复常数项也不等于已经恢复全部多项式系数。

03
物理含义

三个点分别提供一个独立约束，Lagrange 权重将它们组合为任意所需位置的值。该过程不猜测缺失符号，只使用低次多项式的一致性。

04
固定参数算例

穷举所有消息及三点可靠节点组合，重建七个求值并检查完全一致；对硬件固定节点一、二、三单独验证常数项线性组合。

固定参数数值验证结果
量数值
reliable node sets35
messages per set512
full recovery cases17920
recovered symbol errors0
fixed node constant errors0
weight at node11
weight at node21
weight at node31
图 1：三点插值重建误差与固定节点权重图 1：三点插值重建误差与固定节点权重

图 1　三点插值重建误差与固定节点权重

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

05
数字实现的边界

RTL 输入 a[8:0] 为 f(1)、f(2)、f(3) 三个三位符号，使用离线插值权重输出 f(0)=u0。仅验证固定节点的常数项恢复，未实现任意节点选择或全码字插值。

模块采用同步高有效复位及 valid 握手；有效输入在一个时钟沿登记输出，空拍不改变数据寄存器而清除输出有效标志。端口采用有符号 32 位容器，实际有效范围按子核定义约束。

自检覆盖多组有效输入、空拍保持及复位；它验证指定算术或地址子核，不代表完整通信系统或完整译码器已经完成硬件验证。

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

06
适用范围

适用于已知符号擦除的块恢复和固定缺失模式加速。节点位置随块变化时，需要重新计算权重或选择对应预计算表。

07
工程上需要注意

可靠点含未知错误会污染插值。

重复节点使分母为零。

固定权重只适用于声明的节点集合。

恢复单个系数不等于完成全码字恢复。

Lagrange 单位基函数把三点可靠观测转化为唯一二次多项式。固定节点可预计算权重，但擦除模型与错误模型必须区分。

内容依据：每日精学第 203 课《ReedSolomon已知擦除的插值恢复》。图表沿用原课固定参数数值结果，属于数值验证，不代表设备实测。

阅读7
分享
写评论...