动机
插值能修复缺失的值,是因为它们的位置已知。面对未知错误时,任意选取一组插值点,可能选中被破坏的值,从而恢复出错误的多项式。逐一尝试所有可能的错误位置集合虽然是有限的,但所需的尝试次数可能多得无法承受。有用的观察是:一个多项式可以在每个被破坏的位置处取零,使这些位置上的方程变得无害,而无需事先知道这些位置。
乍看之下这引入了一个非线性问题:未知的消息多项式必须与未知的错误定位多项式相乘。我们改为把它们的乘积引入为一个新的独立未知量。接收到的值本来就是已知标量,因此所得方程是线性的。我们将证明,在译码假设成立时,它们的解为何能恢复出多项式商;以及在没有该假设时,为什么必须检验整除性。
我们使用求值码一章中域上根的界与距离的计算。这里的论证只计数域运算;实际的比特复杂度还取决于有限域及其运算如何表示。
定义
固定域 、互异点 ,以及满足 的整数 ,。码字是次数小于 的多项式的取值。设 为接收字。若一个候选消息多项式与 至多在 个坐标上不同,则称其在预算之内。在涉及次数界的陈述中,零多项式的次数为 。
寻求满足下式的多项式
使得
多项式 称为错误定位多项式,取为次数恰为 的首一多项式。当 时,它是固定的多项式 1。这些方程对 的 个低次系数与 的 个系数而言是线性的:因子 是数据,而不是未知量。共有 个未知系数和 个方程。
首一性排除了平凡的一对 ,它对每个接收字都满足方程,却不传达任何消息。把首项系数固定为 1 也消除了标量的不确定性。若发生的错误少于 个, 不必恰好是以这些错误位置为单根的多项式;允许存在额外的因子。
写出实际的系数行
记 。把未知的定位多项式低次项移到左边,每个接收坐标对应一行:
一旦求值点和接收值已知,这个系数矩阵的每个元素都是已知的。不出现两个未知系数的乘积。未知的乘积 已被 的独立系数列表所取代;之后用整除性来检验这种替换确实来自某个消息多项式。正是这一步使普通线性代数得以适用。
概念视角代数
把方程组看成一个多项式同余式
令 ,并设 是满足 、次数小于 的插值多项式。方程 恰好表示 在全部 个点上为零,即
由于 ,多项式 就是 除以 的余式。解码就是要找一个次数为 的首一 ,使这个余式的次数小于 。
求值点为零不造成困难。当 时,其对应的行化为 。我们从不除以求值点。当 时,第二个和为空,该行就是 ,因为常数单项式 的值为 1,在零处也是如此。这些约定使边界情形成为同一方程组的普通实例,而不是特殊的数值例外。
该方程组可能方程多于未知数,也可能方程相关。因此高斯(Gauss)消元法必须处理不相容与自由变量,而不能仅仅对一个假定非奇异的方阵求逆。后面的正确性证明有意允许所有这些可能。未用完错误预算的接收码字,自然会产生自由的定位系数;不应仅仅因为矩阵秩亏就拒绝这样的输入,把它当作例外。
定理/命题
定理 16.2.1
(在假设下每个解都有相同的消息商)
设次数小于 的多项式 与 至多在 个位置上不同。则该线性方程组有一个满足首一的、次数为 的 的解。每个这样的解都满足 。因此,即使线性方程组有多个解,其商也都是同一个 。
定理 16.2.2
(带有被检验输出的多项式时间唯一译码器)
求解该线性方程组。若它不相容,则报告在预算内没有码字。否则取任意一个解,用 除 ,仅当余式为零、商的次数小于 ,且其取值与 至多在 个位置上不同时,才接受该商。若任一检验失败,则报告在预算内没有码字。当 时,该过程对每个接收字都是正确的,并且仅使用多项式数量的域运算。
证明思路或证明
证明
(填充后的真实定位多项式与根的计数)
被保证的消息提供一个解。 设 为 的不正确位置的集合,记 。定义
填充因子使 成为次数恰为 的首一多项式。它可能引入重根,或在正确位置处取零,这些都是允许的。乘积的次数小于 。在正确位置,。在不正确位置,由于 ,两边均为零。因此这是一个解。这里并未使用接收方不经译码就能构造它的说法;这只证明了只要被保证的消息存在,线性方程组就是相容的。
任意解都有正确的商。 任取一个具有指定次数和首一性的解 ,并与真实的 比较。多项式 的次数至多为 。在每个正确位置,
这样的互异点至少有 个。因此根的界迫使 。由于 ,精确的多项式除法给出商 和零余式。这个论证既不要求定位系数唯一,也不要求接收值非零,也不要求知道被破坏的位置。
证明透视
方程个数并不等于正确性证明
方程的个数至少与未知数一样多,但仅凭这一观察,既不能证明相容性,也不能证明商正确。相容性来自填充后的真实定位多项式。正确性来自 在所有正确位置处的根。不等式 出现在那个根的计数中,在那里它具有超出矩阵维数的数学意义。
第二个定理的译码器在此论证之上再加上拒绝规则与代价上界。
证明
(半径内的唯一性与计算代价)
拒绝是合理的。 求值码的距离为 ,所以两个不同的消息多项式不可能同时处于预算之内。若存在一个,则第一个定理表明方程组是相容的,并且每个解都通过商与距离检验,得到该消息。因此,不相容或检验失败说明不存在这样的候选。反之,被接受的商已被显式验证为一个在预算之内的、满足次数界的有效多项式,所以接受不会凭空捏造一个无效的候选。
这说明了为什么“取任意一个解”是合理的。我们不必在解空间中搜索一个碰巧合适的定位多项式。若数据在预算之内可译码,则所有解给出同一个商;若不可译码,则没有任何解能通过最后的候选检验。非零余式是有意义的拒绝结果,而不是译码定理的失败。
代价。 用基本实现,高斯消元法可在 次域运算内求解含 个方程、至多 个未知数的方程组。写出幂、对次数为 的多项式做除法、对商求值,以及统计不一致的位置,同样只需多项式数量的运算。矩阵奇异时可以直接选取一个含自由变量的解;未知系数向量的唯一性是不必要的。这些界不包含对一次域运算的代价的未加说明的估计。在有明确高效的域表示时,这些运算还须以比特为单位实现并计数;代数证明本身并不保证某个特定的软件实现。
例题详解
例题 16.2.3
(在七元域上译出一个被破坏的取值)
取点 ,维数 ,预算 。收到 。记 ,。方程具有如下形式
行化简得 以及 。直接检验该解: 在五个点处的值为 , 的值为 ;乘积 给出同样的列表。
用 除 。商的第一项 留下余式 ;下一项 留下 ;最后一项 留下零。商为 。其字为 ,仅在第三个坐标上不同。定位多项式的根是求值点 ,而不是序数标签“第二个坐标”。
例题 16.2.4
(较小的预算是另一种假设)
在 上,取点 且 。 的字是 。若接收字为 而预算为零,则 ,方程组要求一个线性多项式在全部四个位置上一致。在 0 和 2 处的值已迫使 ,其在 1 处的值是 3,所以方程组不相容。这与纠一个错误并不矛盾:那一次运行要求的是零个错误。
预算为 1 时,,一个有效解是 ,(模 5)。精确除法恢复出消息。所选的预算决定了线性方程组,以及它的失败所能确立的结论。
例题 16.2.5
(多余的定位因子不会产生多余的消息)
使用 的全部七个点,,预算为 2。设接收字没有错误,等于 的取值。 配 ,以及 配 ,都是该方程组的解。它们的系数向量不同,但商都是同一个 。第一个定位多项式甚至在一个正确的点处取零。当错误预算有余量时,不能把它的根解释为实际错误的准确列表。
常见错误
(从定位多项式读出错误值)
恢复出消息之后,位置 处的实际错误值为 。定位多项式的系数并不直接编码这些值。在第一个例子中,被破坏的位置是域点 ,错误值为 ;定位多项式的常数项系数为 。若混淆这三个数,就会把坐标标签、错误大小与多项式系数混为一谈。线性方程组把接收符号用作数据,而定位多项式记录的是乘法应在何处压制某个方程。
常见错误
反例模式
有理拟合不一定是多项式消息
在 上,取点 ,,接收值为 。一对 , 满足每个方程:每个 都是 的逆元。但 不整除 。
在一个错误之内不存在二次消息。若某个二次消息在四个点处一致,则 的次数至多为 并有四个互异的根,所以它为零。在 处对该恒等式求值得 ,这在域中不可能。因此线性方程组在不可译码的数据上也可能是相容的;除法是必不可少的检验。
常见错误
(把预算提高到唯一译码半径以外)
半径条件不能随意去掉。对五点、维数为 的码,多项式 的字是 。接收字 与零字相差一个错误,与该非零字相差两个错误。预算为 时两个消息都被允许,所以没有任何译码器能统一地判断发送的是哪一个。这是信息本身的局限,而不是高斯消元法的缺陷。
含有擦除时,删去被擦除的坐标,并在其余互异的求值点上运行同一算法。若有 个符号被擦除,其余值中至多有 个错误,则条件为 ,即 。必须在幸存的位置中计数错误;按此约定,被擦除的位置不会同时被算作未知错误。
总结
定位多项式使有问题的求值方程变为零,而乘积变量把问题化为线性代数。根的计数论证证明,在唯一译码半径之内,每个解都有正确的商。精确除法与候选检验把真正的消息多项式与伪造的有理拟合区分开来,在违反错误假设的输入上也是如此。
练习
快速检查
(对 、,在没有擦除时被涵盖的最大整数错误预算是多少?若有两个位置被擦除呢?)
使用 ,再使用 。
解答 · 答案
没有擦除时, 允许 。有两个擦除时,剩下十个取值,所以 至多允许两个未知错误。混合不等式给出同样的答案,。
快速检查
(为什么选取 、 是不可接受的,尽管它满足插值方程?)
想想这对多项式对接收字说明了什么。
解答
它会使每个接收向量看起来都满足方程,而用 作除法没有定义。首一的首项系数固定了一个非零的、次数为 的定位多项式,并使其余方程成为非齐次线性约束。
快速检查
(在第一个例题中,通过计算模 下的 、 与 ,验证点 处的方程组方程。)
解答 · 答案
模 下 。 的整数值为 ,故 。又 。这检验了方程组的一行成立;一个解需要所有行都成立。
快速检查
(设在假设下两个首一的定位多项式解有不同的额外因子。在不假定线性方程组满秩的前提下,证明它们的商仍然一致。)
对每个解分别把根的计数用于 。
解答
每一对解都按同样的正确位置根的计数满足 。因此其非零的 整除 ,商为 。该论证确定的是商,而不是自由的定位因子,所以系数方程组秩亏不会对消息造成歧义。