动机
码除了加法封闭,还可能有其他有用的代数结构。循环码把合法字循环移位后仍得到合法字。用多项式表示字,可以把移位变为乘法,从而得到具体编码规则和紧凑的校验方法。这里在有限域 F q \mathbb F_q F q 上工作,固定正整数长度 n n n 。
定义
把字 ( c 0 , … , c n − 1 ) (c_0,\ldots,c_{n-1}) ( c 0 , … , c n − 1 ) 与商环 R = F q [ x ] / ( x n − 1 ) R=\mathbb F_q[x]/(x^n-1) R = F q [ x ] / ( x n − 1 ) 中的剩余类对应,其代表为
c ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 . c(x)=c_0+c_1x+\cdots+c_{n-1}x^{n-1}. c ( x ) = c 0 + c 1 x + ⋯ + c n − 1 x n − 1 .
由多项式除法,每个剩余类有唯一的次数小于 n n n 的代表。在 R R R 中乘以 x x x 会把字变为 ( c n − 1 , c 0 , … , c n − 2 ) (c_{n-1},c_0,\ldots,c_{n-2}) ( c n − 1 , c 0 , … , c n − 2 ) :最高次项由于 x n = 1 x^n=1 x n = 1 而回到开头。我们固定这一移位方向;反向约定会改变写出的坐标。
循环码 是在线性子空间 C ≤ F q n C\le\mathbb F_q^n C ≤ F q n 中再要求对该移位封闭的码。首项系数为一的多项式称为首一多项式。选首一生成多项式,可避免相差非零标量的歧义。
定理/命题
有限域上长度为 n n n 的每个非零循环码 C C C 都有唯一的首一最低次数码字多项式 g g g 。它整除 x n − 1 x^n-1 x n − 1 ,而码恰由 R R R 中 g g g 的倍数剩余类组成。
若首一多项式 g g g 整除 x n − 1 x^n-1 x n − 1 且次数为 r r r ,则其循环码维数为 n − r n-r n − r 。令 h = ( x n − 1 ) / g h=(x^n-1)/g h = ( x n − 1 ) / g ,则剩余类 c c c 属于码当且仅当 c ( x ) h ( x ) ≡ 0 ( m o d x n − 1 ) c(x)h(x)\equiv0\pmod{x^n-1} c ( x ) h ( x ) ≡ 0 ( mod x n − 1 ) 。
概念视角 结构
循环码构成模多项式的因子格 两个定理给出长度为 n n n 的循环码与 x n − 1 x^n-1 x n − 1 的首一因子之间的双射,其中零码对应 g = x n − 1 g=x^n-1 g = x n − 1 。这个对应把次序反转:g g g 的码包含 g ′ g' g ′ 的码,当且仅当 g ∣ g ′ g\mid g' g ∣ g ′ 。因此数循环码就是数因子。在 F 2 \mathbb F_2 F 2 上,
x 7 + 1 = ( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 1 ) x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1) x 7 + 1 = ( x + 1 ) ( x 3 + x + 1 ) ( x 3 + x 2 + 1 ) 有三个互异的不可约因子,所以长度为七的二元循环码恰有 2 3 = 8 2^3=8 2 3 = 8 个。
证明思路
对一次移位和线性组合封闭,说明 C C C 对任意多项式乘法封闭,因此是 R R R 的理想。选最低次数的非零代表 g g g ,乘以标量使它首一。任取码字代表 c c c ,多项式除法给出 c = a g + b c=ag+b c = a g + b ,其中 deg b < deg g \deg b<\deg g deg b < deg g 。c , a g c,ag c , a g 都代表码字,所以差 b b b 也代表码字。最低次数迫使 b = 0 b=0 b = 0 ,因此每个码字都由 g g g 的倍数表示;反过来所有倍数都属于 C C C 。
用 g g g 除 x n − 1 x^n-1 x n − 1 :写成 x n − 1 = a g + b x^n-1=ag+b x n − 1 = a g + b ,且 deg b < deg g \deg b<\deg g deg b < deg g 。在 R R R 中左侧为零,故 b b b 代表码字。它的次数小于 n n n ,所以它就是自己的唯一代表;最低次数迫使 b = 0 b=0 b = 0 ,即 g g g 整除 x n − 1 x^n-1 x n − 1 。若另有首一最低次数多项式生成同一码,两者互相整除,次数相同且都首一,因此相等。
证明透视
最低次数与域的假设在哪里用到 deg g \deg g deg g 的最小性用了两次,分别针对两个不同的余式。第一次除法中,余式 b b b 是码字,因为 c c c 与 a g ag a g 都是码字;第二次中,它是码字,因为 x n − 1 x^n-1 x n − 1 在 R R R 中为零。两次都有 deg b < deg g \deg b\lt\deg g deg b < deg g ,所以非零的 b b b 会与 g g g 的选法矛盾。域的假设在两次除法之前就已用到:要使 g g g 首一,其首项系数必须可逆;而用首一多项式做除法,余式次数必然较小。理想性质把“对一次移位封闭”变成“对乘以 a a a 封闭”;没有它,a g ag a g 根本不一定是码字。排除零码只因为零码没有可供选取 g g g 的非零元素。
设 deg g = r \deg g=r deg g = r 。g , x g , … , x n − r − 1 g g,xg,\ldots,x^{n-r-1}g g , xg , … , x n − r − 1 g 次数互不相同且小于 n n n ,故其剩余类线性无关。每个码字是 g g g 的倍数;把乘数模 h = ( x n − 1 ) / g h=(x^n-1)/g h = ( x n − 1 ) / g 约化,就能把它表示成这 n − r n-r n − r 个元素的线性组合。因此它们构成基底。对于校验,g g g 的倍数与 h h h 相乘后模 x n − 1 x^n-1 x n − 1 为零。反之,若 x n − 1 = g h x^n-1=gh x n − 1 = g h 在多项式环中整除 c h ch c h ,消去非零多项式 h h h 得 g ∣ c g\mid c g ∣ c 。不需要假设 g , h g,h g , h 互素。
零码是边界情形:它不含次数小于 n n n 的非零代表。可另外用因子 g = x n − 1 g=x^n-1 g = x n − 1 描述,它在 R R R 中的剩余类为零,维数为零。整个空间对应 g = 1 g=1 g = 1 。
例题详解
在 F 2 \mathbb F_2 F 2 上,g = x 3 + x + 1 g=x^3+x+1 g = x 3 + x + 1 整除 x 7 − 1 = x 7 + 1 x^7-1=x^7+1 x 7 − 1 = x 7 + 1 。直接相乘得
( x 3 + x + 1 ) ( x 4 + x 2 + x + 1 ) = x 7 + 1. (x^3+x+1)(x^4+x^2+x+1)=x^7+1. ( x 3 + x + 1 ) ( x 4 + x 2 + x + 1 ) = x 7 + 1. 特征二下出现两次的项相消。码的维数为 7 − 3 = 4 7-3=4 7 − 3 = 4 ,共有 16 个字;校验多项式为 h = x 4 + x 2 + x + 1 h=x^4+x^2+x+1 h = x 4 + x 2 + x + 1 。
取消息多项式 a ( x ) = 1 + x 2 a(x)=1+x^2 a ( x ) = 1 + x 2 ,则码字为
a ( x ) g ( x ) = 1 + x + x 2 + x 5 , a(x)g(x)=1+x+x^2+x^5, a ( x ) g ( x ) = 1 + x + x 2 + x 5 , 坐标字是 ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) (1,1,1,0,0,1,0) ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) 。其循环移位为 ( 0 , 1 , 1 , 1 , 0 , 0 , 1 ) (0,1,1,1,0,0,1) ( 0 , 1 , 1 , 1 , 0 , 0 , 1 ) ,由 x a ( x ) g ( x ) x a(x)g(x) x a ( x ) g ( x ) 模 x 7 − 1 x^7-1 x 7 − 1 表示;按构造它属于码。此例直到出现 x 7 x^7 x 7 的系数时才需约化。
字 ( 1 , 0 , 0 , 0 , 0 , 0 , 0 ) (1,0,0,0,0,0,0) ( 1 , 0 , 0 , 0 , 0 , 0 , 0 ) 表示 1 1 1 。次数为三的 g g g 不整除 1 1 1 ,所以它不是码字。等价地,其校验乘积为 h h h ;h h h 次数为四,小于七,故在 R R R 中非零。
常见错误
加法封闭的向量空间不一定对移位封闭:二元长度三的码 { 000 , 100 } \{000,100\} { 000 , 100 } 是线性的,但移位 100 100 100 得到 010 010 010 ,不在码中。它的多项式是 0 0 0 与 1 1 1 ,而 x ⋅ 1 = x x\cdot1=x x ⋅ 1 = x 不在其中,所以这个集合不是 R R R 的理想,也没有生成多项式。
反例模式
不整除模多项式的生成多项式 人们可能以为每个 r r r 次首一多项式 g g g 都生成维数为 n − r n-r n − r 的码。在 F 2 \mathbb F_2 F 2 上取 n = 3 n=3 n = 3 与 g = x 2 + 1 g=x^2+1 g = x 2 + 1 ,它不整除 x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) x^3+1=(x+1)(x^2+x+1) x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) 。在 R R R 中,它的倍式是 0 0 0 、g = 1 + x 2 g=1+x^2 g = 1 + x 2 、x g ≡ 1 + x xg\equiv1+x xg ≡ 1 + x 以及两者之和 x + x 2 x+x^2 x + x 2 :共四个字,所以维数是二,而不是 3 − 2 = 1 3-2=1 3 − 2 = 1 。贝祖(Bézout)等式解释了原因:若 d = gcd ( g , x n − 1 ) = u g + v ( x n − 1 ) d=\gcd(g,x^n-1)=ug+v(x^n-1) d = g cd( g , x n − 1 ) = ug + v ( x n − 1 ) ,则在 R R R 中 d ≡ u g d\equiv ug d ≡ ug ,所以 g g g 与 d d d 生成同一个理想;这里 d = x + 1 d=x+1 d = x + 1 。修正就是定理的假设:维数公式适用于 x n − 1 x^n-1 x n − 1 的首一因子,而定理中的生成多项式必定是这样的因子。
乘以 x x x 是在 R R R 中进行的,其中 x n = 1 x^n=1 x n = 1 。未经模 x n − 1 x^n-1 x n − 1 约化的普通乘积次数可能达到 n n n 或以上,便不是长度 n n n 的字。取 n = 7 n=7 n = 7 ,码字 x 3 g = x 3 + x 4 + x 6 x^3g=x^3+x^4+x^6 x 3 g = x 3 + x 4 + x 6 移位后为 x 4 + x 5 + x 7 ≡ 1 + x 4 + x 5 x^4+x^5+x^7\equiv1+x^4+x^5 x 4 + x 5 + x 7 ≡ 1 + x 4 + x 5 ,写作 ( 1 , 0 , 0 , 0 , 1 , 1 , 0 ) (1,0,0,0,1,1,0) ( 1 , 0 , 0 , 0 , 1 , 1 , 0 ) 。
校验多项式不保证纠正任意错误,它只用于检查是否属于码。要定位或纠正错误,还需要译码算法和最小距离论证。
总结
商环记录循环移位。多项式除法给出整除 x n − 1 x^n-1 x n − 1 的唯一首一生成元;它的次数决定维数,互补因子给出成员检验。零码与整个空间按明确约定分别处理。
练习
快速检查
(在 F 2 \mathbb F_2 F 2 上取 n = 3 n=3 n = 3 、g = x + 1 g=x+1 g = x + 1 。验证 g ∣ x 3 − 1 g\mid x^3-1 g ∣ x 3 − 1 ,并求码的维数。)
分解 x 3 + 1 x^3+1 x 3 + 1 ,并使用 dim C = n − deg g \dim C=n-\deg g dim C = n − deg g 。
解答 · 答案 特征二下 x 3 − 1 = x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) x^3-1=x^3+1=(x+1)(x^2+x+1) x 3 − 1 = x 3 + 1 = ( x + 1 ) ( x 2 + x + 1 ) 。生成元次数为一,维数为 3 − 1 = 2 3-1=2 3 − 1 = 2 。
快速检查
(对此长度三的码,1 + x 1+x 1 + x 和 1 1 1 分别是码字吗?)
解答 · 答案 1 + x = g 1+x=g 1 + x = g 是码字;常数多项式 1 1 1 不被 g g g 整除,因此不是码字。
用一组基编码
维数证明给出直接编码器。令 k = n − r k=n-r k = n − r ,把消息写成 a ( x ) = a 0 + ⋯ + a k − 1 x k − 1 a(x)=a_0+\cdots+a_{k-1}x^{k-1} a ( x ) = a 0 + ⋯ + a k − 1 x k − 1 ,输出 a ( x ) g ( x ) a(x)g(x) a ( x ) g ( x ) 。它的次数至多为 ( k − 1 ) + r = n − 1 (k-1)+r=n-1 ( k − 1 ) + r = n − 1 ,故这个乘积已是长度 n n n 的代表,编码这一步无需回绕。不同消息给出不同码字:若 a g = b g ag=bg a g = b g ,则 ( a − b ) g = 0 (a-b)g=0 ( a − b ) g = 0 ;多项式环没有零因子,所以 a = b a=b a = b 。
g , x g , … , x k − 1 g g,xg,\ldots,x^{k-1}g g , xg , … , x k − 1 g 的系数向量构成生成矩阵的各行。七位例子按低次在前的约定得到
( 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 ) . \begin{pmatrix}
1&1&0&1&0&0&0\\
0&1&1&0&1&0&0\\
0&0&1&1&0&1&0\\
0&0&0&1&1&0&1
\end{pmatrix}. 1 0 0 0 1 1 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0 0 1 0 0 0 0 1 .
消息 ( 1 , 0 , 1 , 0 ) (1,0,1,0) ( 1 , 0 , 1 , 0 ) 选择第一行和第三行,二元和为 ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) (1,1,1,0,0,1,0) ( 1 , 1 , 1 , 0 , 0 , 1 , 0 ) ,与多项式计算一致。若采用高次在前的坐标,写出的向量和移位方向会反过来;只要约定始终一致,底层的码没有改变。
此编码器在这些坐标中不是系统式的:消息位没有原封不动地占据四个指定位置。下一节用多项式除法构造系统编码。不同生成矩阵可以生成同一码,所以看到不同矩阵本身不代表码不同。
多项式除法与系统编码
令 r = deg g r=\deg g r = deg g ,消息 a a a 的次数小于 n − r n-r n − r 。用 g g g 除 x r a x^ra x r a :
x r a = q g + s , deg s < r . x^ra=qg+s,\qquad \deg s<r. x r a = q g + s , deg s < r .
于是 c = x r a − s = q g c=x^ra-s=qg c = x r a − s = q g 是码字。它在 r , … , n − 1 r,\ldots,n-1 r , … , n − 1 次的系数恰为 a a a 的系数,而前 r r r 个系数来自 − s -s − s :余式次数小于 r r r ,不会影响较高位置。特征二下减法与加法相同;一般域上的负号不可省略。
七位二元例子取 a = 1 + x 2 a=1+x^2 a = 1 + x 2 ,则 x 3 a = x 3 + x 5 x^3a=x^3+x^5 x 3 a = x 3 + x 5 。由 x 3 ≡ x + 1 ( m o d g ) x^3\equiv x+1\pmod g x 3 ≡ x + 1 ( mod g ) ,有 x 5 ≡ x 2 ( x + 1 ) = x 3 + x 2 ≡ x 2 + x + 1 x^5\equiv x^2(x+1)=x^3+x^2\equiv x^2+x+1 x 5 ≡ x 2 ( x + 1 ) = x 3 + x 2 ≡ x 2 + x + 1 ,因此 x 3 + x 5 ≡ x 2 ( m o d g ) x^3+x^5\equiv x^2\pmod g x 3 + x 5 ≡ x 2 ( mod g ) 。系统码字是 x 5 + x 3 + x 2 x^5+x^3+x^2 x 5 + x 3 + x 2 ,坐标为 ( 0 , 0 , 1 , 1 , 0 , 1 , 0 ) (0,0,1,1,0,1,0) ( 0 , 0 , 1 , 1 , 0 , 1 , 0 ) ,最后四位 ( 1 , 0 , 1 , 0 ) (1,0,1,0) ( 1 , 0 , 1 , 0 ) 就是消息。用 g g g 除该码字恰得 x 2 x^2 x 2 ,独立验证它属于码。
系统编码与直接编码通常把相同消息映为不同码字:前者得到 x 2 + x 3 + x 5 x^2+x^3+x^5 x 2 + x 3 + x 5 ,后者得到 1 + x + x 2 + x 5 1+x+x^2+x^5 1 + x + x 2 + x 5 。两者都属于同一码,因为它们都是 g g g 的倍数。因此消息到码字的例子必须说明编码约定。
校验乘积与伴随式
记 M = x n − 1 = g h M=x^n-1=gh M = x n − 1 = g h 。收到的多项式 r r r 的校验乘积为 r h m o d M rh\bmod M r h mod M ;若为零,r r r 是码字,否则不是。若 r = c + e r=c+e r = c + e 且 c c c 是码字,则 r h ≡ e h ( m o d M ) rh\equiv eh\pmod M r h ≡ e h ( mod M ) 。这与矩阵伴随式类似:结果依赖错误而不依赖发送码字。
另一种常用伴随式是 r r r 除以 g g g 的余式。它也恰在码字上为零,因为成员条件是 g ∣ r g\mid r g ∣ r 。两种伴随式的表示不同,不能作为多项式直接等同;它们对成员资格给出等价信息,且加入码字后均只依赖错误。要译码,还须规定如何将伴随式对应到候选错误图样。若多个错误有相同伴随式,单凭它不能确定实际发生哪个。
对七位码,单坐标错误 e = x j e=x^j e = x j 的余式为 x j m o d g x^j\bmod g x j mod g 。前三个余式是 1 , x , x 2 1,x,x^2 1 , x , x 2 ;由 x 3 ≡ x + 1 x^3\equiv x+1 x 3 ≡ x + 1 ,第四个是 x + 1 x+1 x + 1 。它们非零且彼此不同。完整的单错误译码表还须检查七个位置,证明七个余式均非零且不同;只列出四个不足以得出全部位置的结论。
可选 循环码的对偶码也是循环码吗? 是的,其生成多项式是倒序后的校验多项式。
自然的下一个问题
循环码的对偶码也是循环码吗? 是的,其生成多项式是倒序后的校验多项式。
设 σ \sigma σ 为移位。若 d d d 与每个码字正交,则 ⟨ c , σ d ⟩ = ⟨ σ − 1 c , d ⟩ = 0 \langle c,\sigma d\rangle=\langle\sigma^{-1}c,d\rangle=0 ⟨ c , σ d ⟩ = ⟨ σ − 1 c , d ⟩ = 0 ,因为 σ − 1 c ∈ C \sigma^{-1}c\in C σ − 1 c ∈ C ;所以对偶码是循环码,并有一个整除 x n − 1 x^n-1 x n − 1 的首一生成多项式。记 k = deg h k=\deg h k = deg h ,这个生成多项式就是倒序多项式 x k h ( x − 1 ) x^kh(x^{-1}) x k h ( x − 1 ) ,再缩放为首一。对长度为七的码,h = 1 + x + x 2 + x 4 h=1+x+x^2+x^4 h = 1 + x + x 2 + x 4 给出 1 + x 2 + x 3 + x 4 1+x^2+x^3+x^4 1 + x 2 + x 3 + x 4 ,它的八个倍式都与全部十六个码字正交。
关闭
快速检查
(二元长度三的码取 g = x + 1 g=x+1 g = x + 1 ,用 r = 1 r=1 r = 1 为消息 a = 1 + x a=1+x a = 1 + x 构造系统码字。)
解答 · 答案 用 x + 1 x+1 x + 1 除 x a = x + x 2 xa=x+x^2 x a = x + x 2 ,恰得 x ( x + 1 ) x(x+1) x ( x + 1 ) ,余式为零,码字为 x + x 2 x+x^2 x + x 2 ,坐标 ( 0 , 1 , 1 ) (0,1,1) ( 0 , 1 , 1 ) 。最后两位包含消息系数 ( 1 , 1 ) (1,1) ( 1 , 1 ) 。
快速检查
(同一码收到 r = 1 + x + x 2 r=1+x+x^2 r = 1 + x + x 2 ,用模 g g g 的余式检验。)
解答 · 答案 在二元域上模 x + 1 x+1 x + 1 有 x ≡ 1 x\equiv1 x ≡ 1 ,所以 r ≡ 1 + 1 + 1 = 1 r\equiv1+1+1=1 r ≡ 1 + 1 + 1 = 1 ,非零。接收字不是码字;此检验本身不能指出哪个坐标被改变,或是否只发生一次改变。
七位例子的最小距离
继续使用 x 3 ≡ x + 1 ( m o d g ) x^3\equiv x+1\pmod g x 3 ≡ x + 1 ( mod g ) ,每步乘以 x x x 并约化,得到余式表:
j 0 1 2 3 4 5 6 x j m o d g 1 x x 2 x + 1 x 2 + x x 2 + x + 1 x 2 + 1 \begin{array}{c|ccccccc}
j&0&1&2&3&4&5&6\\
\hline
x^j\bmod g&1&x&x^2&x+1&x^2+x&x^2+x+1&x^2+1
\end{array} j x j mod g 0 1 1 x 2 x 2 3 x + 1 4 x 2 + x 5 x 2 + x + 1 6 x 2 + 1
对线性码,两字的距离等于其差的重量;码字之差仍为码字,而每个码字都可写成它与零之差。因此最小距离等于非零码字的最小重量。
它们恰好是次数小于三的七个非零多项式,各出现一次。重量一的码字将是 x j x^j x j ,但它的余式非零。重量二的码字将是不同位置的 x i + x j x^i+x^j x i + x j ;其余式为零只有在两项表值相等时才可能,而表中没有重复。另一方面,g = 1 + x + x 3 g=1+x+x^3 g = 1 + x + x 3 本身是重量为三的码字,因此最小距离恰为三。
该表现在支持单错误纠正:收到多项式的余式若非零,找到唯一具有相同余式的 x j x^j x j ,并将它加到接收字上。在至多发生一个错误的假设下,这恢复发送码字;零余式在此假设下对应没有错误。若不作此假设,两个或更多错误可能与单错误具有相同余式,过程可能输出另一合法码字。
此码有 16 个字,二元半径一球各有 1 + 7 = 8 1+7=8 1 + 7 = 8 个字。最小距离三保证这些球互不相交,而 16 ⋅ 8 = 128 = 2 7 16\cdot8=128=2^7 16 ⋅ 8 = 128 = 2 7 ,所以它们恰好划分整个空间。这是半径一填充界达到等号的完美码,并不意味着实际噪声的重量一定至多为一。
快速检查
(接收多项式模 g g g 的余式为 x 2 + x x^2+x x 2 + x ,假设至多一个错误,如何译码?)
解答 · 答案 表中该余式对应 x 4 x^4 x 4 。把 x 4 x^4 x 4 加到接收多项式后,余式为零;距离三说明所得码字是在一次坐标改变范围内的唯一码字。
快速检查
(发送零字时,为什么重量三的码字可以是未被检测的错误?)
解答 · 答案 零加上该码字仍得到该码字,它除以 g g g 的余式为零。接收者看到合法码字,单凭成员检验不会发现错误。最小距离定理保证检出至多两个错误,并不保证检出每个更高重量错误。
检查假设
系数为域,保证可以用非零多项式做除法,且多项式环没有零因子。证明用到了这两个事实:除法产生低次数余式,消去律证明校验条件。在一般系数环上这两步可能失败,不能直接照搬证明。正长度保证模数 x n − 1 x^n-1 x n − 1 和长度 n n n 的坐标约定有意义。
循环移位只是置换坐标,因而保持汉明(Hamming)重量。所有移位所得码字具有相同重量,但这本身不能确定最小距离:还须考虑所有非零线性组合。七位例子用余式表给出缺少的下界,再用重量三的生成元给出相配的上界。
一个重因子例子具体说明为何不要求 g , h g,h g , h 互素。在 F 2 \mathbb F_2 F 2 上取 n = 2 n=2 n = 2 ,则 x 2 − 1 = ( x + 1 ) 2 x^2-1=(x+1)^2 x 2 − 1 = ( x + 1 ) 2 。取 g = h = x + 1 g=h=x+1 g = h = x + 1 ,于是 gcd ( g , h ) = x + 1 \gcd(g,h)=x+1 g cd( g , h ) = x + 1 。g g g 生成的码为 { 00 , 11 } \{00,11\} { 00 , 11 } 。校验恒等式仍成立:在 F 2 [ x ] \mathbb F_2[x] F 2 [ x ] 中消去 h h h ,可知 g h gh g h 整除 c h ch c h 当且仅当 g g g 整除 c c c 。这是在取商之前的多项式环中消去;商环本身可以有零因子。