Gabidulin码的插值译码

错误可能散布在所有位置，却只来自一个很小的底域子空间。若能找到一个线性化多项式把这个子空间全部消去，那么对接收词施加它以后，错误就不见了。困难是这个多项式和原消息都未知；直接同时求它们会产生非线性方程。本算法引入第二份多项式，把乘积先当成独立未知量，转成一次线性系统，最后再检查这份“乘积”确实能分解回来。

形式陈述

输入、输出与半径

给定Gabidulin码的数据

K=\mathbb F_q,\quad L=\mathbb F_{q^m},\quad 1\le k\le n\le m,\quad g_1,\ldots,g_n\text{ 在 }K\text{ 上独立},

一个接收词 $y\in L^n$ ，以及整数

0\le t\le\left\lfloor\frac{n-k}{2}\right\rfloor. \tag{1}

算法返回以下两种结果之一：

一份消息 $f$ ，满足 $\deg_qf<k$ ，并附码字 $c=(f(g_i))$ 、残差 $e=y-c$ 与 $\operatorname{wt}_R(e)\le t$ 的精确检查；该码字在此半径内唯一
“没有半径 $t$ 内的码字”，即不存在任何上述合法消息

这是对每一个合法输入 $y$ 的完整判定。若还承诺实际发送消息 $f_{\rm sent}$ 的错误秩至多 $t$ ，成功输出就等于该消息。没有这个传输承诺时，成功并不识别发送者的历史。

第一步：求一份首一辅助插值

设置未知多项式

\Lambda(X)=X^{q^t}+\sum_{j=0}^{t-1}\lambda_jX^{q^j},\qquad N(X)=\sum_{j=0}^{k+t-1}\nu_jX^{q^j}. \tag{2}

令它们满足 $N(g_i)=\Lambda(y_i)$ 。移项后是 $n$ 条关于 $k+2t\le n$ 个扩域未知系数的线性方程：

\sum_{j=0}^{k+t-1}\nu_jg_i^{q^j} -\sum_{j=0}^{t-1}\lambda_jy_i^{q^j} =y_i^{q^t},\qquad 1\le i\le n. \tag{3}

用精确行消元判断相容性，若相容就选任意一解。未知系数没有被取Frobenius幂，只有已知 $g_i,y_i$ 被取幂，因此(3)确实是 $L$ 上的普通线性系统。 $t=0$ 时 $\Lambda=X$ ，没有 $\lambda_j$ 未知量。

第二步：按指定方向做形式除法

求唯一的线性化多项式 $f,R$ ，满足

N=\Lambda\circ f+R,\qquad \deg_qR<t. \tag{4}

若 $R\ne0$ ，返回失败；否则检查 $\deg_qf<k$ ，重新编码并计算 $\operatorname{wt}_R(y-\operatorname{ev}_g(f))$ 。只有全部通过才返回消息，其余均返回失败。

(4)的乘法是形式复合，左因子是 $\Lambda$ 。不把它改成 $f\circ\Lambda$ ，也不提前按 $X^{q^m}=X$ 约简。零余式在 $t=0$ 时按 $\deg_q0=-\infty$ 理解。

直觉

真消息存在时，线性系统为什么一定相容

假设存在合法消息 $f_*$ ，其错误 $e_i=y_i-f_*(g_i)$ 张成 $r\le t$ 维底域空间 $E$ 。子空间根积 $P_E$ 是首一、 $q$ -次数为 $r$ 的线性化多项式，且消去每个错误值。令

\Lambda_* = X^{q^{t-r}}\circ P_E,\qquad N_* = \Lambda_*\circ f_*. \tag{5}

复合使 $\Lambda_*$ 首一且 $q$ -次数恰为 $t$ ，又不会重新产生已消去的错误。由线性化性质

\Lambda_*(y_i)=\Lambda_*(f_*(g_i))+\Lambda_*(e_i)=N_*(g_i).

并且 $\deg_qN_*<k+t$ ，所以它们确实是一份(3)的解。即使实际错误秩小于预算，也能补到固定次数 $t$ ；零错误时 $E=\{0\}$ ，根积为 $X$ 。

为什么任意一解都够，而不必找到那份特殊解

取(3)的任意一解 $(\Lambda,N)$ ，仍假定存在上述 $f_*$ 。在 $V=\langle g_1,\ldots,g_n\rangle_K$ 上定义误差映射

T\left(\sum_i a_ig_i\right)=\sum_i a_ie_i,\qquad a_i\in K.

输入点独立，保证坐标唯一，所以 $T$ 定义良好；其像为 $E$ ，核维数为 $n-r$ 。记形式多项式 $Q=N-\Lambda\circ f_*$ 。由(3)有 $Q(g_i)=\Lambda(e_i)$ ，两边都对底域线性，于是在整个 $V$ 上

Q|_V=\Lambda\circ T.

特别地， $Q$ 消去 $\ker T$ ，至少有 $q^{n-r}$ 个根。但

\deg_q Q<k+t\le n-t\le n-r. \tag{6}

若 $Q$ 非零，普通次数小于 $q^{n-r}$ ，根数便不可能这么多。因此 $Q=0$ 是形式恒等式，即 $N=\Lambda\circ f_*$ 。

这一步把“存在一份能用的插值解”加强成“任何选出的解都能用”。因此相容系统的自由变量可以直接取零，不必猜哪个解对应真实错误空间。

形式除法的每一步怎样计算

若当前被除式最高项为 $uX^{q^s}$ ，且 $s\ge t$ ，因为 $\Lambda$ 首一， $\Lambda\circ(cX^{q^{s-t}})$ 的最高系数为 $c^{q^t}$ 。在 $L$ 上Frobenius可逆，所以选

c=u^{q^{m-t}}\quad(t>0),\qquad c=u\quad(t=0) \tag{7}

即可消去最高项。这里(1)确保 $t<m$ ；通用实现也可把逆Frobenius次数写成 $(-t)\bmod m$ 。将这项加入商，再减去整份复合式， $q$ -次数严格下降，有限步后得到(4)。

若有两份分解，相减会得到 $\Lambda\circ(f-f')=R'-R$ 。左侧非零时的 $q$ -次数至少为 $t$ ，右侧低于 $t$ ，矛盾；所以商与余式唯一。这只用非零形式多项式复合时次数相加，不要求 $\Lambda:L\to L$ 是可逆函数。

两种出口为何都是完整结论

若半径内存在消息，(5)保证系统相容，(6)保证任意解必精确除出该消息，其次数与残差检查也必通过。因此任何失败出口都排除半径内消息。反过来，成功后的重新编码和秩检查直接给出存在性，而码距 $n-k+1>2t$ 给唯一性。

这是失败结论的逻辑依据；不能仅因为某个启发式求解器“没有找到”就声称不存在。

例子与边界

四个位置同时污染，仍恢复同一消息

在 $\mathbb F_{16}/\mathbb F_2$ 上，取 $a^4=a+1$ 、 $g=(1,a,a^2,a^3)$ 、 $k=2,t=1$ 。发送 $f=aX+X^2$ ，得到上一页的码字(8)，并在四个位置都加入 $u=a^3$ 。接收词为

y=(a^3+a+1,\ a^3,\ a+1,\ a^2+a+1). \tag{8}

设 $\Lambda=X^2+\lambda_0X$ 、 $N=\nu_0X+\nu_1X^2+\nu_2X^4$ 。下面用整数标签 $z=\sum_{j=0}^3z_j2^j$ 表示域元素 $\sum_jz_ja^j$ ；标签的运算在定义多项式下进行，不是模16算术。四行增广矩阵为

\left(\begin{array}{rrrr|r} 1&1&1&11&9\\ 2&4&3&8&12\\ 4&3&5&3&5\\ 8&12&15&7&6 \end{array}\right) \longrightarrow \left(\begin{array}{rrrr|r} 1&0&0&0&3\\ 0&1&0&0&12\\ 0&0&1&0&1\\ 0&0&0&1&8 \end{array}\right). \tag{9}

未知量顺序为 $(\nu_0,\nu_1,\nu_2,\lambda_0)$ 。于是

\Lambda=X^2+a^3X,\qquad N=X^4+(a^3+a^2)X^2+(a+1)X. \tag{10}

直接展开 $\Lambda\circ(aX+X^2)$ 恰为(10)。形式除法余式为零，重编码残差为 $(a^3,a^3,a^3,a^3)$ ，其秩一而Hamming重量四。证书同时包含插值相容、正确复合方向和实际距离。

插值方程得到N与Lambda，经左因子形式除法及残差秩检查恢复消息；无错输入的辅助多解仍产生同一个商 — 插值、形式除法与距离复核

辅助多项式不唯一，消息仍唯一

保持 $t=1$ ，但输入恰为合法码字、没有错误。对任意 $v\in L$ ，都可取 $\Lambda=X^2+vX$ 、 $N=\Lambda\circ f$ ；本例有16份不同的首一辅助多项式。式(3)的解集因而有一维自由参数，所有解却都除出同一个 $f$ 。

所以不能把“唯一译码半径”误解为“辅助插值系统只有一个解”，也不能在低于预算的错误秩下随意声称其齐次核至多一维。

一份明确的半径外输入

同一参数下，标签接收词 $y=(0,0,1,3)$ 的插值系统有唯一解

\Lambda=X^2,\qquad N=6X^4+X^2+7X,

这里 $6=a^2+a$ 、 $7=a^2+a+1$ 。形式除法保留非零余式 $7X$ ，因此没有距离至多一的码字。即使该系统相容，也不能在除法检查前宣布成功。

另一方面，若实际发送零词，却收到(8)之前的非零合法码字 $c$ ，译码器会正确认证 $c$ 在自身的零半径内，并输出非零消息。实际错误秩为三，超出一的预算；算法无法仅从 $y=c$ 分辨“发送 $c$ 且无错”与“发送零词且发生了这份错误”。

零半径、函数约简与变更底域

$t=0$ 时，(3)就是在全部输入点上拟合低于 $k$ 次的线性化消息。输入不属于码本便失败，属于码本便精确恢复；若 $k=n$ ，任意接收词都对应唯一消息，但没有冗余纠错能力。

形式多项式 $X^{q^m}-X$ 代表零函数，却不是零多项式。在(4)中提前约简会改变次数和可整除性，使上面的证明失去对象。公开程序专门测试超过扩域次数的形式除法，防止实现把高次系数循环折叠。

若底域为四元域，所有 $q$ 幂和逆Frobenius均用 $q=4$ 。不能仅因特征为二就改成平方；错误秩也必须在四元底域上计算。

推论与应用

实现成本与可复查输出

式(3)有至多 $n$ 个未知数，朴素消元需 $O(n^3)$ 次扩域算术。形式复合除法用 $O(n^2)$ 次扩域乘加及相应Frobenius幂，重新编码亦可直接按系数求值。残差转为 $m\times n$ 底域矩阵后，可用 $O(mn\min(m,n))$ 次底域算术计算秩。域表示、幂运算及位成本另计，这里不声称亚二次译码。

可下载标准库精确程序和完整结果。程序用确定性消元选一解，不枚举所有消息寻找答案；测试程序另建立小码的完整纠错球字典，逐输入比较独立的存在性判定。测试含奇特征、非素底域、 $n<m$ 、零半径、低于预算的错误秩及半径二，不能把其中声明为样本的部分称作全空间穷举。

和既有综合译码怎样衔接

综合译码通过校验矩阵确定错误陪集，一般还要在该陪集中寻找合适的首领。本页利用Gabidulin的特殊求值结构，把给定秩半径内的判定化为插值与形式除法。它没有解决任意线性码的一般最近邻问题，也没有直接包含网络模型里的行列擦除。

终点任务要求提交(9)、(10)、无错辅助多解、非零余式失败例及改底域后的恢复记录。只有把成功与失败的含义都写清楚，才能把一段返回消息的程序变成可审计译码器。

参考资料

Pierre Loidreau，Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin，2004，339:745–750，§3的线性化重构到译码、§4的高斯消元及复合除法接口。本文采用固定首一次数的非齐次系统，另证明任意解都可用；不依赖辅助解空间维数的概括。
Sven Puchinger、Antonia Wachter-Zeh，Sub-Quadratic Decoding of Gabidulin Codes，2016年v2，§II-A Lemma 1的左右形式除法与Lemma 2的子空间多项式；§III区分错误和擦除，并在脚注1注明纯错误情形允许任意独立点、 $n\le m$ 。正文使用朴素插值算法，不冒用该文快速算法的成本。

形式陈述 ​

输入、输出与半径 ​

第一步：求一份首一辅助插值 ​

第二步：按指定方向做形式除法 ​

真消息存在时，线性系统为什么一定相容 ​

为什么任意一解都够，而不必找到那份特殊解 ​

形式除法的每一步怎样计算 ​

两种出口为何都是完整结论 ​

四个位置同时污染，仍恢复同一消息 ​

辅助多项式不唯一，消息仍唯一 ​

一份明确的半径外输入 ​

零半径、函数约简与变更底域 ​

实现成本与可复查输出 ​

和既有综合译码怎样衔接 ​

反向链接