动机
奇偶校验是每个被传送的码字都必须满足的一个方程。对循环码而言,把码字多项式在生成多项式的某个根处取值,就得到这样一个方程。有用的问题是:如何选取若干个根,使得少数几个被改动的坐标无法同时满足所有校验。一个域元素的连续幂给出了答案:只要所设想的错误的支撑集足够小,所得方程就构成一个可逆的范德蒙(Vandermonde)方程组。
这一构造区分了字母表的两种角色。被传送的符号可以保持为二元的,即使我们是在更大的域中对它们的多项式取值。扩域提供了足够多互不相同的校验点,但它并不会把每个二元坐标变成可独立选取的扩域符号。这一区别既解释了构造的威力,也解释了下面维数的计算。
我们假定读者已知域上的多项式除法,以及先前把循环码描述为模 的理想的内容。我们将证明这里用到的根界,包括使其行列式非零的各项假设。最后的二元例子是一个完全确定的码;一般的设计距离只是下界,并不保证对每种参数选择都取等号。
定义
设 为素数幂。在一个给定的、包含 的扩域 中工作。取正整数 ,以及乘法阶恰为 的元素 。于是 互不相同且非零。 上的一个字 对应于
坐标零是常数项系数。在模 下乘以 会旋转各坐标,原来的最后一个坐标移到位置零。
定义 15.1.1
(极小多项式)
对 ,它在 上的极小多项式是以 为根的、次数最小的正次首一多项式。多项式除法表明,它整除每个以 为根的 上的多项式:除以极小多项式,再对次数更小的余式取值。由极小性,余式必须恒等于零。
定义 15.1.2
(BCH 码与设计距离)
固定一个整数 与一个整数 。设 为
的各极小多项式的首一最小公倍式。指数按模 理解。由 生成的循环码称为具有这些连续定义根、设计距离为 的 BCH 码。常见的狭义选择是 。不同的设计参数可以产生同一个生成多项式,从而产生同一个码。
定理/命题
定理 15.1.3
(生成多项式存在于被传送的字母表上)
多项式 属于 ,并且整除 。它在模 下的倍式构成一个维数为 的线性循环码。等价地,该码的码字恰是次数小于 、且在每个所选定义根处取值为零的多项式。
定理 15.1.4
(连续根距离界)
若该码非零,则每个非零码字的重量至少为 。因此其最小距离至少为 ,并且它能唯一地纠正至多 个符号错误的每一种模式。仅凭这一距离结论并不能提供译码算法。
概念视角代数
把码看作扩域核在基域上的部分
设 为 上的 矩阵,第 行第 列的元素为 。于是 列出各值 ,所以该码就是 。从第 列提出因子 后,任意 列都成为可逆的范德蒙矩阵,因此任意 列在 上线性无关,这恰好等价于距离至少为 。在 上这个核的维数是 ;只保留分量属于 的向量,距离界依然成立,维数却变为 ,可能更小。
证明思路或证明
极小多项式把共轭校验打包在一起
证明
(弗罗贝尼乌斯(Frobenius)轨道与 g 生成的理想)
若 上的多项式 在 处为零,则 。因此一个根会带来它的整个弗罗贝尼乌斯(Frobenius)轨道。反过来,对 的轨道中互不相同的元素 ,构造所有 的乘积。弗罗贝尼乌斯映射置换这些因子,所以它固定每个系数。被弗罗贝尼乌斯固定的系数满足 。这个多项式在域中至多有 个根,而它已在 的全部 个元素处为零,所以被固定的元素恰好构成该子域。因此轨道乘积属于 。
每个以 为根的多项式在整个轨道上为零,从而在 中被这个互异线性因子的乘积整除。除以首一的轨道乘积同样在 中进行,这证明它就是极小多项式。这给出了计算生成多项式的实用方法:把指数按模 乘以 的作用分成轨道,然后对每个所需的轨道取一个极小多项式。同一轨道的重复出现不会引入新的独立因子。
每个定义根都是 的根。它的极小多项式整除该多项式,因此它们的最小公倍式也整除它。写 。模 下 的每个倍式都有唯一的代表 ,其中 :把乘子除以 即可。唯一性成立,因为这样的非零乘积次数小于 ,不可能在模 下为零。这些乘子给出大小为 的一组基。乘以 保持该理想,从而证明了循环性。
在所选根处取值为零,等价于被它们的极小多项式整除,从而被 整除。这证明了另一种校验描述。通过选取 在 上的一组基,扩域方程可以展开为若干个基域方程;若不考虑共轭性而直接数所列出的扩域方程,就会高估其秩。
生成多项式也给出了具体的编码器,无需为每条消息重新解方程组。把消息系数列为次数小于维数的多项式 ,再乘以固定的 。乘积的次数小于 ,所以此时无需约化。不同的消息给出不同的乘积,因为域上的多项式环没有零因子。在接收端,除以 可检验候选字。这些运算说明,即使尚未推导出任何高效的纠错过程,称其为一种构造也是恰当的。它们也揭示了码率的代价:加入一个真正新的共轭类会增大生成多项式的次数,并减少自由消息系数的个数。而加入一个来自已被要求的类的根则没有这种代价。
短支撑集迫使范德蒙矛盾
证明
(短支撑集无法满足全部校验)
假设某个非零码字的重量为 ,支撑位置互不相同,为 。令 。前 个连续根方程对 给出
第 行第 列为 的矩阵,其行列式为 。理解这一恒等式的一种方法,是把行列式看作交错多项式:每个差都整除它,总次数一致,比较首项单项式可得系数为一。这些因子非零,因为 的阶恰为 ,且支撑位置模 互不相同。
因此该方程组在 上可逆。它迫使对每个 都有 。但每个 都非零,即使 为负也是如此,并且每个支撑系数也非零。这一矛盾证明了重量界。线性性把最小非零重量化为最小距离。若两个码字都与同一个接收字相差不超过 处改动,则它们彼此相距不超过 ,这证明了所述半径内的唯一性。
证明透视
为什么连续根是特殊的
证明用了三个假设,各自在一个可辨认的位置。连续指数 使列因子 可以提出,留下范德蒙矩阵的各行 ;任意选取的 个根没有这种分解。 的阶恰为 ,使各 互不相同,所以行列式 非零。最后,每个 非零,才能由 推出 。
关键一步是只保留假设中的 个支撑坐标,并只用 个可用方程中的 个,使问题变成一个方阵线性方程组。论证以与支撑集的选取相矛盾而收尾。它从不计算 的根数,而 的次数可能接近 ,所以任何根数界都不能代替这个行列式。
例题详解
例题 15.1.5
(构造域并辨认两个共轭类)
取 ,以 记 的剩余类。该多项式在 中没有根。一个没有线性因子的可约四次式必是不可约二次式之积;而 上唯一的首一不可约二次式是 。该四次式模这个二次式余一,所以它不可约,商环确实是一个有十六个元素的域。
关系式为 。其非零乘法群有十五个元素,所以 的阶整除十五。它不是一或三,因为这两种可能都会给出次数低于四的非零多项式关系。又 ,因为若相等就会给出二次关系。所以它的阶为十五。
指数一和三模十五的弗罗贝尼乌斯轨道分别是 与 。第一个极小多项式是 。由于 的阶为五,它是 的根;其轨道有四个元素,所以这个四次式就是它的极小多项式。两组根互不相交。
例题 15.1.6
(参数恰为 [15,7,5] 的二元码)
取 与 。定义根为 。它们的两个共轭类给出
生成多项式的次数为八,所以二元维数为七。连续根定理给出距离至少为五。多项式 本身是重量为五的非零码字,所以距离也至多为五。因此精确参数为 ,并且每一对比特错误都能被唯一纠正。等号是由一个具体的码字确立的,而不是把设计距离解释为一个等式定理。
例题 15.1.7
(编码并旋转而不改变码)
采用系数消息的约定,把 乘以 来编码。八次与六次项各出现两次,在特征二中相消,留下
其六个非零坐标位于位置 。七个消息系数一般并不原样出现在七个指定的坐标上;我们并没有声称这个编码器是系统码。
对于越过端点的旋转,把 乘以 。由于在商环中 ,结果是 。它仍是一个码字。把旋转后的字在某个定义根处取值,相当于把其原来的值零乘以该根,这给出了校验得以保持的另一个直接解释。
常见错误
常见错误
(扩域校验不会改变消息字母表)
刚才构造的码有 个码字,而不是 个。每个坐标和每个乘子系数都属于 。在 中取值只是用来表达二元线性约束的一种手段。把所列出的每个域方程当作十六个独立的选择,会彻底改变这个构造。
常见错误
(一个共轭类只贡献一个因子)
把每个连续根都算作一个新的极小多项式因子会重复计算。根 、 与 已经属于同一个二元共轭类。把同一个极小多项式乘上多次会引入重复因子;由于 是奇数, 在特征二中没有重根,所以这样的乘积根本不整除 。对根 ,朴素乘积的次数是 ,而最小公倍式 的次数是 。
反例模式
阶太小的元素
也许有人以为任何满足 的非零 都可以用。取 、例题中的域 ,以及 ;它满足 ,但阶只是五。取 、,定义根 组成一个共轭类,所以 。于是
是重量为二的码字,低于设计值五。直接验证:每个定义根 都是 的幂,所以 ,。在证明中,位置 与 给出 与 ,范德蒙行列式为零。修正就是所述假设: 的阶必须恰为 ,使模 不同的位置给出不同的 。
距离证明是在错误数量的承诺之下给出唯一答案;要确定被改动的位置,需要用到配套单元中发展的伴随式算法。
总结
BCH 构造在保持基域字母表的同时选取扩域中的根。弗罗贝尼乌斯轨道决定生成多项式及其维数。连续的根的幂迫使每个短支撑集都满足一个可逆的范德蒙方程组,从而证明设计距离的下界。长度为十五的二元例子达到了该界,因为它的生成多项式本身的重量已是五。
练习
快速检查
(解释为什么由 可推出 ,以及为什么此时 没有重根。)
考虑 的素因数与 的导数。
解答
整除 的素数不可能整除 ,所以它不可能整除 。导数为 ,在该域中非零。它与 的公共根只能是零,但零不是后者的根。因此这两个多项式互素,没有重根。
快速检查
(证明这一构造的维数估计 ,允许右端为负。)
用弗罗贝尼乌斯轨道的大小来界定每个极小多项式的次数。
解答
每个极小多项式的次数至多为 ,因为弗罗贝尼乌斯轨道至多经过 步就闭合。最小公倍式的次数至多等于其各因子次数之和,故 ,即得所述维数界。共享的轨道可能使这一估计非常宽松。
快速检查
(在 上,设 的阶为七,并选取根 ,于是设计距离为四。求生成多项式与实际最小距离。)
列出模七的二元分圆轨道。
解答
二元指数轨道是 与 。所选的根遇到了这两个轨道,所以 。该码维数为一,由零字与全一字组成。其距离为七,严格大于设计值四。
快速检查
(解释为什么长度为十五的码虽然距离等于其设计距离,却不是完美的二错纠正码。)
把互不相交的半径二球的总大小与 比较。
解答
长度为十五的二元半径二的球含有 个字。 个码字的这类球互不相交,但它们合起来只含有 个字。因此有些接收字位于所有半径二的球之外。达到设计距离界,与用译码球填满整个环境空间,是两回事。