从多项式到距离保证
循环码的意义不止于码字可以轮转:我们还要知道码字相距多远,并利用接收字定位错误。本单元证明连续根下界,并完整构造一个小型译码表。内容以前面的距离和伴随式单元为基础。
令 为有限域、,以 表示 。坐标按常数项在前的次序书写。 在模 下乘 ,会把最后一个坐标移至第一个。对这种位移封闭的线性码是循环码:反复位移及线性组合显示它是 的理想。
定理 2.1.1
(循环码的生成多项式与维数)
长度为 、定义在 上的每个循环码 都有唯一首一生成多项式 ,且 。反过来, 的每个首一因子都生成一个循环码。若 ,则码字恰为乘积 (),且每个码字只有一种写法,故 。
证明
(最小次数与多项式除法)
考虑 在 的原像,它是包含 的理想。在原像中选次数最小的非零首一多项式 ;多项式除法的余式若非零,便会属于该理想且次数更小,故原像每个元素都被 整除,特别地 。若 是另一个同次数的首一元素,则 属于该理想而次数更小,故 。反过来每个首一因子都生成商环的一个理想。 给出零码;以下讨论距离时假设码含非零字。
每个 的乘积 次数小于 ,本身就是约简代表元。反过来,每个码字都由某个 代表。把 除以次数为 的 :若 且 ,则 。若 ,域上多项式环没有零因子,故 。因此 构成一组基底。
连续根下界
假设扩域 含有乘法阶恰为 的 。因 ,在其各次幂代值与商环代表元无关。我们假设此 存在;特别地,其阶与域的特征互素。令 为整数且 。
定理 2.1.2
(连续根距离下界)
若每个码字均满足 ,则每个非零码字的 Hamming 重量至少为 ,故 。
证明
(位置太少的 Vandermonde 方程组)
若非零码字只有 个非零系数,位置为互异的 ,令 。因 且 的阶为 ,这些值互异且非零。前 个根方程给出
系数矩阵为 Vandermonde 矩阵,行列式 。故每个 均为零,与非零系数的选择矛盾。所得只是下界,不自动保证等号;要得确切距离,还须展示达到下界的码字。
证明透视
重量上界、连续指数与阶分别在哪里起作用
三个假设分别在三处起作用。条件 保证所用的 个方程都在已知的 个根之内,于是方程数与未知数一样多。指数 连续,才使得把公因子 并入未知数后,系数矩阵成为 Vandermonde 矩阵;根的指数若分散,得到的是广义 Vandermonde 矩阵,其行列式可以为零。 的阶恰为 使各 互异,故行列式非零;而 让我们由 推出 。论证中没有构造任何重量为 的码字,所以结论只是下界。
七个位置的完整伴随式表
在 中令 。它在 没有根,故此三次多项式不可约。令 、,则 。反复相乘得到
表中七个元素互异且非零,而 ,故 的阶是七。直接相乘得
由 生成的循环码维数为四,有 16 个码字。由 及 ,定理在 时给出距离至少三。生成多项式本身的重量为三,故距离恰为三。依指定坐标次序,它的向量是 :这是码字,不是单一比特错误。
常见错误
(把所有根都当作连续根来数)
生成多项式 在 的幂中有三个根:、 与 。若把它们当作三个连续根,会得到 ,可是 本身的重量只有三。下界要求指数连续:,所以最长的连续段是 ,给出 ,而这里三正好达到。
对次数小于七的接收多项式 ,定义伴随式为除以 的余式,亦即 。码字余式为零,所以若 ,伴随式是 。查表可辨认每一个单比特错误位置:伴随式为零便原样输出 ;否则翻转表中唯一对应的坐标。这可纠正所有重量至多一的错误,并不保证修正任意损坏。
概念视角结构
这个码就是长度为七的二元汉明(Hamming)码
把每个 写成基底 下的坐标向量,并以这些向量为列,组成 的二元矩阵 。于是 就是 的坐标向量,所以该码是 的核。由上表,这些列恰好是 的七个非零向量,各出现一次:这正是汉明(Hamming)码的定义校验矩阵。十六个半径为一的球共含 个字,所以每个接收字都恰好在一个码字的距离一以内,没有任何伴随式能提示两位错误。
常见错误
(把向量当作最高次项在前来读)
字符串 表示 ,因为坐标按常数项在前书写。若反过来读,便成了 ,其伴随式为 。采用相反约定的译码器会把生成多项式当成受损的字并翻转一个坐标。计算伴随式之前,必须先固定坐标约定。
例题 2.1.3
(追踪一个接收字)
令 ,写作 。模 有 ,故伴随式为 。表中对应坐标 ;翻转它得到 ,写作 。由于码距为三,它是距离 至多一的唯一码字。
例题 2.1.4
(最后一个坐标出错)
传送码字 ,写作 ,并设坐标 被翻转,于是 ,写作 。利用上表,
伴随式指向坐标 ,翻转它便还原 。计算中从没用到传送的是哪个码字:码字部分对伴随式的贡献是 。
例题 2.1.5
(两个错误会被错误纠正)
传送零字,并设坐标 与 被翻转,于是 ,写作 。其伴随式为 ,所以单错误规则翻转坐标 ,输出 ,写作 。输出是码字,但与传送的字相距三。错误重量为二时,译码器仍然返回一个码字,只是返回了错的那个,而伴随式完全没有显示失败。
反例模式
零伴随式不等于没有错误
若传送零字而发生重量三错误 ,接收字是非零码字 ,伴随式仍为零,译码器会原样输出。零伴随式只证明接收字属于码,不证明信道没有出错。
练习
快速检查
(为何特征二中 会推出 ?)
把等式 两边平方。
解答 · 答案
特征二中平方是域同态,而 的系数在 ,故 。
快速检查
(若伴随式为 ,单错误规则翻转哪个坐标?)
在幂表中找出这个元素。
解答 · 答案
表中 ,故翻转从零起算的坐标 。
快速检查
(解释为何距离至少三排除两个码字同时距同一接收字至多一。)
使用 Hamming 距离的三角不等式。
解答 · 答案
三角不等式会使两码字距离至多二,与距离下界三矛盾。
快速检查
( 生成的码维数是多少? 呢?)
使用 ,并留意 在商环中代表什么。
解答
生成整个 维空间; 在商环中代表零,生成维数零的零码。本节对非零码的最小距离约定不为零码定义距离。
延伸阅读
MIT 多项式码讲义 讲解多项式编码及利用余式定位错误;CMU 编码理论讲义 讨论 BCH 码及连续根距离论证。