Gabidulin码与Moore求值

普通低次多项式不能有太多不同的根；低 $q$ 次数的线性化多项式，则不能让一个太高维的底域子空间都成为根。Gabidulin码把第二个限制变成纠错冗余：消息是线性化多项式，输入点要底域线性无关，输出的独立方向数便有一个可证明的下界。

形式陈述

编码合同中有两个不同的域

取 $K=\mathbb F_q$ 、 $L=\mathbb F_{q^m}$ ，整数 $1\le k\le n\le m$ ，并选在 $K$ 上线性无关的有序点 $g_1,\ldots,g_n\in L$ 。消息为 $k$ 个扩域系数 $f_0,\ldots,f_{k-1}$ ，对应线性化多项式

f(X)=\sum_{j=0}^{k-1}f_jX^{q^j},\qquad \operatorname{ev}_g(f)=(f(g_1),\ldots,f(g_n)). \tag{1}

由全部消息得到的集合

\operatorname{Gab}_k(g)=\{\operatorname{ev}_g(f):\deg_qf<k\}\subseteq L^n \tag{2}

称为本页的Gabidulin码，零多项式约定 $\deg_q0=-\infty$ 。它是维数为 $k$ 的扩域线性码，有 $q^{mk}$ 个码字；作为秩度量码，最小距离恰为

\boxed{d_R=n-k+1.} \tag{3}

因此它达到 $n\le m$ 时的秩Singleton界，是MRD码。编码的线性是“对消息系数取 $L$ -线性组合”；求值函数 $x\mapsto f(x)$ 本身通常只对 $K$ 线性。这两个说法不能互换。

一份明确的生成矩阵

取消息为行向量，生成矩阵是截断的Moore矩阵

G=\begin{pmatrix} g_1&\cdots&g_n\\ g_1^q&\cdots&g_n^q\\ \vdots&&\vdots\\ g_1^{q^{k-1}}&\cdots&g_n^{q^{k-1}} \end{pmatrix},\qquad \operatorname{ev}_g(f)=(f_0,\ldots,f_{k-1})G. \tag{4}

每个系数都在 $L$ 中运算；每个输入点的独立性则在 $K$ 中检查。 $k=1$ 时消息为 $f_0X$ ，不是常数多项式 $f_0$ 。

直觉

根数界怎样变成维数界

若非零线性化多项式的 $q$ -次数为 $s$ ，它的普通次数就是 $q^s$ 。其根形成一个 $K$ -子空间；若这个子空间维数为 $r$ ，便有 $q^r$ 个根。普通多项式根数界给 $q^r\le q^s$ ，所以

\dim_K\ker f\le\deg_q f. \tag{5}

现在记 $V=\langle g_1,\ldots,g_n\rangle_K$ ，维数为 $n$ 。输出坐标 $f(g_i)$ 张成的空间恰好是 $f(V)$ ，所以对非零消息

\operatorname{wt}_R(\operatorname{ev}_g(f)) =\dim_K f(V) =n-\dim_K(V\cap\ker f) \ge n-(k-1). \tag{6}

特别地，非零消息不能编码成零词，故编码单射，(4)有满行秩，码的扩域维数确实为 $k$ 。由于两码字之差仍是同一码中的非零词，(6)也给任意不同码字间的距离下界。

为什么不是只有一个下界

要达到 $n-k+1$ ，取 $W=\langle g_1,\ldots,g_{k-1}\rangle_K$ 。它的子空间根积 $P_W$ 是首一线性化多项式， $q$ -次数恰为 $k-1$ ，且在整个 $L$ 中的根恰好是 $W$ 。因此它是合法非零消息，在 $V$ 上的核维数恰为 $k-1$ ，(6)取等号。

当 $k=1$ 时， $W=\{0\}$ ，使用 $P_W=X$ ，仍是非零合法消息。这样同时处理了端点，没有把空基误写成无根的常数一。

从普通求值码迁移时该改哪一步

Reed–Solomon码在互异点上评价普通低次多项式，以“最多多少个零坐标”证明Hamming距离。这里用 $q$ 幂构成消息，以“输出张成空间还剩多少维”证明秩距离。所需的输入条件相应从互异升级为底域独立；两个证明结构相似，但计数对象、乘法和恢复算法都不同。

例子与边界

十六元域中的256份消息

令 $K=\mathbb F_2$ 、 $L=\mathbb F_2[a]/(a^4+a+1)$ ，选

g=(1,a,a^2,a^3),\qquad n=4,\quad k=2.

每条消息形如 $f_0X+f_1X^2$ ，共有 $16^2=256$ 条，最小秩距离为三。生成矩阵为

G=\begin{pmatrix} 1&a&a^2&a^3\\ 1&a^2&a+1&a^3+a^2 \end{pmatrix}. \tag{7}

以 $f(X)=aX+X^2$ 为例，逐点求值得到

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

$f(X)=X(X+a)$ 的根恰为 $0,a$ ，核维数一；因为四个输入点张成整个 $L$ ，输出张成空间维数为三。虽然第二坐标为零，这个词仍有三个独立输出方向。

公开程序逐一枚举全部255个非零码字，其中225个重量三，30个重量四；这验证本例的距离，不代替(5)–(6)的一般证明。

互异不够，独立性不能省略

$1,a,1+a$ 是三个互异非零元素，却在二元底域上满足 $1+a+(1+a)=0$ 。若把它们当作长度三、 $k=1$ 的求值点，消息 $f=X$ 只产生秩二的词，达不到公式(3)预期的三。

$n\le m$ 也来自独立性，而非实现偏好：一个 $m$ 维底域空间放不下更多独立输入点。改变底域时，必须重新检查维数、独立性和Frobenius幂。十六元域相对于四元底域只有二维，不能沿用上述四点输入合同。

右侧混合点可以，任意逐坐标缩放不可以

若 $V\in\operatorname{GL}_n(K)$ ，将求值点行向量换为 $gV$ ，它们仍然底域独立。由 $K$ -线性， $\operatorname{ev}_{gV}(f)=\operatorname{ev}_g(f)V$ 。所以这种点变换恰好对应秩等距的列混合。

若把不同坐标乘上不同的 $L$ -标量，则通常不能把这些标量从 $f$ 内外自由移动，也未必保持秩。一般的广义RS缩放接口不能原样套进这里。

推论与应用

任意k份正确坐标足以完成擦除恢复

设只保留位置集合 $J$ 中的 $k$ 个坐标，且知道这些位置没有错误。求解

\sum_{j=0}^{k-1}f_jg_i^{q^j}=c_i\qquad(i\in J). \tag{9}

所用 $k$ 个输入点是原独立集的子集，因此对应方形Moore矩阵可逆。其可逆性也可直接由(5)证明：非零的低于 $k$ 次消息不可能同时消去它们张成的 $k$ 维空间。所以(9)唯一恢复消息，进而重建所有擦除坐标。

对(8)，只保留头两个坐标就有

f_0+f_1=a+1,\qquad af_0+a^2f_1=0.

将第一式乘以 $a$ 后与第二式相加，得到 $(a^2+a)f_1=a^2+a$ 。该系数非零，故 $f_1=1,f_0=a$ 。错误位置已知的擦除与未知错误是不同输入合同，不能把“任选 $k$ 个坐标”用于仍可能被污染的数据。

作为Hamming码，本构造也达到 $n-k+1$ ：秩重量不超过Hamming重量，而取上文 $P_W$ 时，恰有前 $k-1$ 个求值坐标为零，其他输入点不在 $W$ 中。这一附带结论不把两种错误预算合并。

未知秩错误要使用新的恢复器

若接收词为 $y=c+e$ 且 $\operatorname{wt}_R(e)\le\lfloor(n-k)/2\rfloor$ ，半径内的码字唯一。但距离论证尚未提供怎样找到它。Gabidulin插值译码构造一份湮灭错误方向的辅助多项式，解扩域线性系统，再按正确方向进行形式复合除法，最后核验实际残差的秩。

终点任务把(8)的四个坐标同时加上 $a^3$ ，要求恢复消息并解释为何四处错误仍在秩一预算内。程序还在四元底域上重做构造，防止把 $q$ 默认为特征素数。

参考资料

E. M. Gabidulin，Theory of Codes with Maximum Rank Distance，1985，俄文原刊21(1):3–16，英文译刊21(1):1–12。本条作为原始研究的书目入口。
Sven Puchinger、Antonia Wachter-Zeh，Sub-Quadratic Decoding of Gabidulin Codes，2016年v2，§II-A的线性化次数、根空间与Moore插值，§II-C Definition 4的独立点求值定义。正文另完整展开距离达到、端点和擦除证明，不采用其快速算法复杂度。
Pierre Loidreau，Sur la reconstruction des polynômes linéaires : un nouvel algorithme de décodage des codes de Gabidulin，2004，C. R. Acad. Sci. Paris, Ser. I 339:745–750，§2的秩与Gabidulin求值构造。

形式陈述 ​

编码合同中有两个不同的域 ​

一份明确的生成矩阵 ​

根数界怎样变成维数界 ​

为什么不是只有一个下界 ​

从普通求值码迁移时该改哪一步 ​

十六元域中的256份消息 ​

互异不够，独立性不能省略 ​

右侧混合点可以，任意逐坐标缩放不可以 ​

任意k份正确坐标足以完成擦除恢复 ​

未知秩错误要使用新的恢复器 ​

反向链接