动机
最小距离定理告诉我们,附近的码字是唯一的,但接收者仍需把它找出来。随着码变大,逐一比较所有消息的代价可能很高。伴随式则从方程中消去未知的被传送字,只保留关于错误的信息。对于二元长度十五的 BCH 码,两个扩域伴随式确定一个二次多项式,其非零根标出被改动的位置。
关键的简化恰恰是二元性。被改动的比特与被传送的比特相差一,所以每个错误都以相同的系数贡献其位置。我们可以用第一和第三幂和来表示至多两个位置元素的和与积。这样,二次式记录了未知的位置,而无需在所有消息上搜索。
我们推导完整的算法,包括无错分支、单个错误、被拒绝的伴随式,以及对候选结果的验证。它的保证只涉及至多两个比特错误。即使所有代数检验都通过,译码器在该半径之外也可能输出一个看似合理但不正确的消息。理解这一局限是理解该算法的一部分。
定义
使用上一单元构造的域 与阶为十五的元素 。坐标编号为 ,字即其低次在前的多项式。该码由
生成,参数为 。等价地,其码字多项式在 处取值为零。假定每个接收到的系数都是比特。本单元处理的是错误,而不是符号缺失的删除位置。
定义 15.2.1
(接收字的伴随式)
对接收字 ,定义伴随式
在特征二中加法与减法相同。由于码字 在这些点处为零,同样的伴随式就是 与 。若错误支撑集为 ,则
定义 15.2.2
(位置元)
坐标 的位置元是 ,一个非零域元素。十五个非零域元素中的每一个恰好对应一个坐标。这个译码器使用的多项式,其根就是位置元本身。另一种常见约定使用位置元的倒数;其公式必须作相应一致的修改。
定理/命题
定理 15.2.3
(二次式识别一个或两个错误)
若接收字与某个码字至多有两个位置不同,则要么 且没有错误,要么 。在后一种情形,令
对于两个错误, 的根恰是它们两个互不相同的非零位置元。对于一个错误,根是零与它唯一的非零位置元。零根只是占位符,并不标识任何坐标。
定理 15.2.4
(经过验证的有界距离译码器)
计算伴随式,并使用下面描述的二次式过程。只要存在距离不超过二的码字,它就返回这个唯一的码字;若不存在,则报告失败。因此,若被传送的码字至多遭受两个错误,它就会被恢复。超出这一传输承诺之外,返回的邻近码字不一定就是被传送的那个。
证明思路或证明
幂和恒等式
证明
(位置元的幂和)
把可能的位置元记为 。对于一个错误,取其位置为 ,并仅在推导中令 。则 ,。在特征二中展开得
因为二项式系数三在这个域中等于一。于是 。单个非零错误给出 。两个互不相同的非零位置也给出 ,因为在特征二中 会推出 。因此在非空且至多两个错误的承诺下,除以 是合理的,并给出 。
现在展开 得 。在一个错误的情形,其根是零与 ;在两个错误的情形,其根是两个实际位置。 的导数是非零常数 ,所以根不会重复。这些陈述也解释了为什么在承诺之外产生的任意二次式可能在 中没有根。
为什么两个伴随式检验了整个码
证明
(两个伴随式检验全部四个定义根)
对二元多项式 ,平方与取值可交换: 且 。因此 已经检验了根 ,而 检验第四个定义根 。它们的极小多项式因子恰是 的两个因子。上一单元的取值为零刻画证明了
在没有错误数界的情况下,零伴随式并不意味着被传送的字未被改动:一个非零码字本身就可以是错误。然而在至多两个错误的承诺之下,一个两个伴随式都为零的非零错误,会是重量至多为二的非零码字,与距离五矛盾。
从十五维二元字空间到 的伴随式映射在 上是线性的。其核的维数为七,所以其秩为八。由于 的二元维数也是八,每个伴随式对都会出现。因此这两个域符号恰好提供了该码所需的八个独立校验比特;它们并没有丢掉接收者日后还需要的额外约束。
这一计算有有用的几何解释。所有具有相同伴随式的接收字构成码的一个陪集,因为它们的差的伴随式为零。译码就是为该陪集选一个小重量的代表并将其减去。选择代表时不需要知道传送的是哪个码字。距离五表明,一个陪集至多含有一个重量至多为二的代表;并不表明每个陪集都含有这样的代表。因此失败信息是关于错误半径模型的有意义的信息,而不是线性性或域运算出了问题的证据。最后的练习精确计数了有这类代表的陪集个数。
概念视角算法
把译码器看作即时计算的查找表
重量至多为二的不同错误图样有不同的伴随式,所以在半径二内译码,等同于查一张从伴随式对到错误图样的表;表中没有条目的伴随式对就表示失败。这张表可以预先算好并存储。二次式的做法则是按需计算给定 的条目: 与 是定位多项式的系数,它的非零根直接读出错误图样。由正确性定理,两种程序定义了从接收字到输出的同一个函数。
算法,包括失败分支
先计算 。若二者都为零,返回 。若 而 ,报告失败:前述恒等式排除了任何重量至多为二的错误模式具有这样的伴随式。
若 ,构造 与 。在全部十五个幂 处计算 。记录每个零点的坐标。若 ,则要求恰有一个这样的非零根;若 ,则要求恰有两个。否则报告失败。非零导数排除了重根,但并不保证任意多项式在所给的域中分裂。
恰好翻转所记录的比特,得到 。最后验证翻转的个数至多为二,且 。只有两项检验都通过才返回 。用 做多项式除法同样可验证成员关系。这些检验使算法的输出约定变得明确,并能捕捉有误的中间计算;它们不能替代前面的证明,即在承诺之下正确的根必定会出现。
证明
(每个分支的正确性)
若有任何码字与接收字相距不超过二,就把它取作推导中的 。它的实际错误位置必须恰是上面所得的非零根,所以算法能找到它。反过来,任何被返回的候选者,经验证,都是距离至多为二的码字。若存在两个这样的候选者,它们的距离至多为四,与该码的距离五矛盾。因此所有分支都满足所述的有界距离约定。
证明透视
两个承诺用在两个不同位置
存在性一半用到的假设是:有某个码字 与 相距不超过二。只有这样,幂和推导才适用于一个重量至多为二的实际错误,从而保证 的非零根位于 中,并恰是错误位置。唯一性一半完全不需要关于传送的承诺:验证使每个返回的字都是距离至多为二的码字,而两个这样的字相距至多为四,为距离五所不容。
关键一步是二次式背后的消元。在生成多项式的根处取值完全消去 ,二元错误值则只留下两个未知位置,其初等对称函数就是 与 。失败分支使情况分析完整:、根的个数不对,或最后检验不通过,每一种都只会在没有码字与 相距不超过二时出现,所以报告失败永远不会丢掉正确答案。
例题详解
例题 15.2.5
(位置零与位置一处的错误)
设错误出现在位置 ,即 。被传送的码字不影响伴随式的计算。我们得到 与 。幂和恒等式给出 ,且
非零根对应于位置零与位置一,所以翻转这两个比特。两个接收到的伴随式随之被抵消。注意,域元素一表示坐标零,而域元素零表示根本没有坐标;混淆二者会使译出的错误模式发生位移。
例题 15.2.6
(在确定位置之前先约化域中的幂)
取位置 处的错误。位置元为 与 ,所以 。又 ,因为 且 。因此
对于这个除法,把 乘以 并使用 ,即得 。二次式为 。查幂次表或对全部十五个候选者取值,即可定位到位置二与位置五。在约化这些表达式时,二元系数表是必要的:模十六的普通整数系数并不描述 中的算术。
例题 15.2.7
(一个错误,以及一个必须被拒绝的伴随式)
对于位置四处的单个错误,,所以 ,。故 ,。舍去零根,翻转坐标四。相反,若没有错误,则两个伴随式都为零,不会进入二次式分支,从而避免了除以零。
对于三个错误的多项式 ,第一个伴随式为 ,但第三个为 。这里 。译码器拒绝这一对。该例子说明了一个在半径之外但可被检测的模式;并不意味着三个或更多错误的每种模式都可被检测。
常见错误
反例模式
通过验证的码字仍可能是错误的被传送字
设 。若发出的是零,则是三个错误产生了 。但 与 只相差两个错误,所以译码器返回 。它的答案是一个有效的、唯一邻近的码字,却与被传送的零字不同。在承诺的半径之外,代数验证无法重构究竟发生了哪种传输历史。
常见错误
(二元幂和不能照搬到其他字母表或约定)
的公式也不能原封不动地照搬到非二元码。在非二元码中,错误系数可能有不同的非零值,所以伴随式是加权幂和,而不是 与 。也不应把我们这种以位置元为根的多项式与倒数根约定混用:两者都可用,但改变其中一个定义时,查找规则与公式必须一并更改。
对这个固定的码,霍纳(Horner)法取值与检验十五个可能的根,都是小规模的精确有限域计算。这并不证明对任意错误预算存在适用于一般 BCH 码的快速译码器。针对更长的码与更大的设计距离的算法,需要更完整的错误位置多项式计算,以及另行的代价分析。
总结
两个扩域伴随式完整地表达了这个二元码的奇偶校验。在至多两个错误之下,它们的第一和第三幂和恢复出位置元的和与积。一个二次式、明确的零伴随式分支以及最后的成员检验,合起来构成完整的有界距离译码器。它的保证在半径二之内是精确的,在半径之外则有意加以限制。
练习
快速检查
(对两个互不相同的错误位置,为什么分母 不会为零?为什么这一论证用到了特征二?)
写 ,并问两个域元素之和何时为零。
解答
方程 给出 。在特征二中,,与位置互不相同矛盾。在其他特征中,互为相反数的非零元素可以不同,所以该推断不成立;二元错误的幂和设定也需要修改。
快速检查
(若 且 ,指出 的两个根,并解释翻转哪个坐标。)
当常数项为零时把 分解。
解答
该多项式分解为 。其根为零与 。只有后者是非零幂 ,从而是坐标位置。找出那个唯一的指数 并翻转其比特;零作为占位符被舍去,而不被解释为坐标零。
快速检查
(在 个伴随式对中,有多少个对应于重量至多为二的可纠正错误?解释为什么这些对互不相同。)
比较两个具有相同伴随式的错误模式。
解答
共有 个错误模式。若有两个具有相同的伴随式,它们的和就是重量至多为四的码字,除非二者相同否则不可能。因此恰有 个伴随式对是可纠正的,剩下 个对没有重量至多为二的错误代表。译码器在这些陪集上报告失败。
快速检查
(设发出的是零,但错误多项式等于 。译码器返回什么?为什么这与它的定理并不矛盾?)
计算一个码字的伴随式。
解答
接收字为 ,它是码字,所以其伴随式为零。译码器不作任何改动地返回 。五个比特被改动,所以这次传输违反了至多两个错误的假设。其观察到的字同样与无错误地发出 相一致;仅从接收字,接收者无法区分这两种历史。