动机
重复一个符号,是通过多份相同的信息来保护它。多项式求值则以另一种方式分散信息:若干消息符号成为系数,而传输的符号是多项式在互异点处的取值。只要幸存的取值足够多,就能确定整个多项式。这使得该构造在擦除情形下尤为清晰,因为接收方知道哪些位置丢失了。
关键事实是:两个低次多项式若不相等,就不可能在太多互异点上取值相同。由此可得距离的证明、针对擦除的插值译码器,以及冗余度的精确刻画。我们还将导出校验矩阵,把这一求值观点与前面线性码各章联系起来。未知错误需要另外的论证,后续译码单元将给出。
我们假定读者已掌握有限域运算、多项式除法,以及线性码及其距离的定义。
定义
设 为有限域,取整数 以及互异点 。对次数小于 的多项式 ,定义其求值字
这些字构成的集合称为 Reed–Solomon 求值码 。系数消息 表示 。所有运算都在该域中进行。当 是非素数的素数幂时,域运算并不是整数模 的运算。
擦除是明确缺失的坐标。错误是指收到的域元素与所发送的不同,而其位置不一定已知。我们设有 个擦除位置,并在其余位置中有 个错误;这两个坐标集合互不相交。最小距离在这些计数的界限下给出唯一性,而算法则需另行找出所发送的字。
对线性 码,下面证明的 Singleton 界断言 。达到该界的码称为极大距离可分码(MDS)。这是关于固定长度与维数下距离的陈述,不同于完美性,后者问的是互不相交的译码球是否填满整个环境空间。
定理/命题
定理 16.1.1
(Singleton 界)
每个线性 码都满足 。
求值构造达到这个界,而插值同时提供它的擦除译码器与校验关系。
定理 16.1.2
(求值码的参数与擦除恢复)
码 是线性码,参数为 。它的任意 个坐标即可确定整个码字。特别地,至多 个擦除可被唯一恢复。更一般地,当 时,含有 个未知错误和 个擦除的接收字,在该错误界内至多与一个码字相容。
定理 16.1.3
(插值权重给出校验关系)
假设 ,并令
以 ()为元素的 矩阵的秩为 ,并且 。这里在方程 中把字视为列向量;若采用行向量的约定,则取转置。
证明思路或证明
根的个数决定码的参数
证明
(根的界、单射性与一个最小重量的字)
求值是线性的,因为对和与标量倍数求值与这些运算可交换。次数至多为 的非零多项式在域中至多有 个互异的根。回忆其证明:根 通过除法给出因子 ;由于域中没有零因子,每个不同的根也是剩余因子的根。对次数归纳即证得该界。
若一个次数小于 的多项式在全部 个点上的取值皆为零,则根的界与 迫使该多项式为零。因此求值映射是单射,维数为 。对任意非零码字,至多有 个坐标为零,所以其重量至少为 。这个下界是可以达到的:多项式 在这 个点处为零,而在所选点集的其他点处不为零。当 时,取空积 1。故最小距离恰为 。
证明
(删去 个坐标)
下面给出 Singleton 界的一个不依赖求值构造的直接证明。对最小距离为 的码,从每个字中删去任意 个坐标。两个不同的码字不会因此变得相同:否则它们原本至多在这 个位置上不同。因此删除映射是单射。对于维数为 的线性码,这给出 ,从而得到该界。求值码由根的计数而达到这个界。
由取值恢复多项式
证明
(Lagrange 插值与一次距离计数)
任取 个互异的幸存点 ,其取值为 。定义 Lagrange 多项式
由互异性,每个分母都不为零。每个 的次数至多为 ,在 处等于 1,在其他选定点处等于 0。因此 具有所给的取值。若另一个次数小于 的多项式也具有这些取值,则它们的差有 个根,必为零。把重构出的 在缺失的坐标处求值,即可恢复所有擦除。
对于错误与擦除并存的情形,设两个候选码字在未被擦除的接收位置上,各自至多有 处与接收字不同。它们在未被擦除的位置上至多有 处互不相同,在被擦除的位置上至多有 处不同。它们之间的距离至多为 ,这是矛盾。由此证明了唯一性。但这并未告诉我们哪些未擦除位置是错的,因此在任意 个接收位置上做普通插值尚不是纠错算法。
选择消息符号的含义
系数编码器便于证明线性性,但消息不必是系数列表。可任选 个坐标位置作为信息位置。把消息解释为这些位置上期望的取值,插值出取这些值的唯一的次数小于 的多项式,再输出它在每个点的取值。于是消息原封不动地出现在指定坐标上:这是一个系统编码器。插值的单射性表明每个旧码字仍然出现,所以码及其距离都没有改变,改变的只是消息与码字之间的对应关系。
对于擦除恢复,信息位置不必在幸存位置之中。任意 个互异的幸存点就足够了。这种灵活性正是 MDS 性质在擦除模型中的操作含义:没有任何特定的 个位置享有特权。若幸存的符号多于 个,可以由任意 个重构,再与其余观测值比较。在仅有擦除的假设下它们一致。若没有这一假设,不一致说明仅有擦除的模型是错误的,但这本身并不能指出所有不正确的符号。
擦除的上限是尖锐的。取一个重量最小的非零码字,其支撑有 个位置,并恰好擦除这个支撑。所有幸存坐标都是零,与零码字的情形一样。接收方无法由幸存数据分辨这两个所发送的字。因此没有任何该码的译码器能恢复所有 个擦除的模式。前面的恢复定理与这个歧义例子给出了互相匹配的正反两方面的陈述,而不只是一个充分条件。
增大 会提高符号率 ,但同时降低所保证的擦除容忍度与最小距离。对于固定的求值构造,这种权衡是精确的。它并不比较所有字母表上所有可能的码,并且要有足够多互异的域点,仍是该构造的一部分要求。
插值也解释了校验矩阵
证明
(缺失的最高次系数,以及对各行的根计数)
对多项式 ()在全部 个点上做 Lagrange 插值。它的 系数为零。第 个 Lagrange 基多项式的 系数是 ,所以比较系数得
对于消息单项式 ()与行指标 ,有 。因此该恒等式表明 。由线性性,每个码字都在 中。
各行是线性无关的。若某个行组合为零,则一个次数至多为 的多项式 在全部 个点上满足 。每个 非零,所以 有 个根,必为零。于是秩为 ,核的维数为 ,与 的维数相等。当 时,该码是整个空间,空的校验矩阵可单独处理;此时不需要非零的校验方程。
证明透视
校验矩阵证明中各假设在哪里起作用
证明分为两半,各用不同的事实。包含关系 纯粹是次数的计算:次数 的消息单项式乘以次数 的行单项式,次数至多为 ,因此最高次 Lagrange 系数为零的恒等式适用。行的范围止于 的原因只在这里;多一行就会达到次数 ,恒等式便不再成立。各行线性无关则再次用到根的界,并用到 ,而这由各点互异保证。两半在维数计算中会合: 的维数为 ,所以包含关系变成相等,无需直接描述核。假设 只是保证 至少有一行。
例题详解
例题 16.1.4
(由三个系数编码出五个符号)
在 上,取点 且 。系数消息 表示 。它的取值为
因为未约化的值是 。该码为 :它能唯一纠正一个未知错误,或恢复两个擦除。若以前三个取值作为消息,则消息为 。系数编码与系统取值编码是同一个码的两种不同的消息约定。
例题 16.1.5
(恢复两个缺失的取值)
设点 处幸存的取值为 。记 。第一个给出 。另外两个给出模 7 下的 与 。用第二个方程减去第一个方程的两倍,得 ;于是 。重构出的多项式为 ,在 处被擦除的值是 。这三个点的互异性与次数的界,证明了唯一性,而不仅仅是这一次计算成功。
例题 16.1.6
(用两个校验方程检验同一个字)
对上面的五个点,权重为 。例如在点 0 处,分母为 (在该域中),其逆元为 5。矩阵为
对字 ,两个整数点积分别为 与 ,模 7 后均为零。若第四个坐标增加 1,则伴随式增加第四列 。这检验了成员资格,并分离出该指定错误对伴随式的影响;识别未知错误仍然需要译码规则。
概念视角结构
对偶码仍是一个求值码
的各行张成 ,因为 的秩为 且 。以次数小于 的多项式 为系数的行组合,就是字 。所以 先对次数小于 的多项式求值,再把第 个坐标乘以 。根的界使每个非零对偶字的重量至少为 :对偶码同样是 MDS 码。在例题中,两行的重量分别为五和四。
常见错误
常见错误
(MDS 不等于完美)
在 的例子中,半径为 1 的球含有 个字。该码有 个字,所以其互不相交的半径为 1 的球共含 个字,少于环境空间的 个。它达到了 Singleton 界,却仍使许多接收字落在这些球之外。不同的最优性陈述比较的是不同的资源。
反例模式
剩余类环不能代替域
在 上,非零的一次多项式 在 0 和 2 处都为零。在 处求值得到 ,重量为 2,而对长度为 4、维数参数为 2 的情形,域上的公式会预测距离为 3。失效的一步是根的界:2 是零因子,消去律不可用。四阶域是存在的,但它与这个剩余类环是不同的代数对象。
常见错误
(重复使用同一个求值点)
求值点必须互异。重复同一个点,只是把同一个方程再加一份,而不是一个独立的插值条件。在 上取点 与 ,多项式 的取值为 ,是重量为 的非零码字,低于根的计数所给出的 。对于长度大于 的情形,需要不同的或扩展的构造;本章的定义无法提供这么多互异的域元素。
总结
域上根的界给出精确的距离与单射的编码。Lagrange 插值恢复擦除,Singleton 论证解释了所达到的距离界,而对最高次系数的比较则产生显式的校验关系。这些结果把可恢复的缺失位置与未知错误区分开来,并为配套单元中的多项式时间错误译码器作好准备。
练习
快速检查
(在 上,在 处对 求值,并在 时写出码的参数。)
把每个值模 约化,再使用 。
解答 · 答案
该字为 ,码为 。在 处的整数值是 ,在该域中为零。
快速检查
(在该码中,只有取值 与 幸存。恢复 。)
记 ,把两个方程相减。
解答 · 答案
记 。相减得到模 下 ,所以 ,。两个互异点唯一地确定一个次数小于 的多项式。
快速检查
(对 求值码,解释当 时,为什么 、 被唯一性定理所涵盖,而 、 不被涵盖。)
比较 与 。
解答
第一组给出 ,所以两个相互竞争的码字会违反距离条件。第二组给出 ,超出了已证明的保证。保证失效并不是说每个这样的模式都有歧义;它的意思是该定理无法统一地证明唯一性。
快速检查
(直接证明一维求值码的距离为 。若所选的某个求值点为零,为什么该结论仍然成立?)
次数小于一的多项式是常数。
解答
次数小于 意味着常数多项式。每个非零常数给出所有 个分量都非零的字,所以其重量与最小距离为 。在 处对非零常数求值并不改变它; 是合法的求值点,不应与零码元混淆。
关于代数码族的更广泛视角,可参见 Guruswami 的关于 Reed–Solomon 及相关码的编码理论讲义。