16
或 ci(x)?xg2(x) 9-46
[例9-8] 现利用g1(x)?x?x?x?1通过移位6次而产生（7，3）循环码。为方便计算令T(x)?g1(x)?x?x?x?1。在移位过程中，必须注意按式（9-39）进行模x?1运算，以“同余”式表示。如：当移位结果为 x(x?x?x?x)?x?x?x?x?
7n77，其中出现x?x，以模(x?1)运算后，x以其同余式1x6?x5?x3?1 （模x7?1）
65427653432432i7表示：
x717 （同余） 模 ?1??1(x?1) 77x?1x?1 需要说明的是，事实上（7，3）码的非全0码字，每码字均为d0?4。由g(x)移位6次可得全部非0码字；而表9-1的（7，4）码，d0?3及d0?4各7个码字，d0?7的1个码字，同d0码字可互循环。而由任一码字不可能通过移1，2…15得到全部码字。
表9-2 （7，3）循环码
移位i 0 1 2 3 4 5 6 （7，3）码 0 0 1 0 1 1 1 1 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 1 1 1 1 1 0 码多项式C(x)（模x7?1） T(x)?x4?x3?x2?1 xT(x)?x5?x4?x3?x x2T(x)?x6?x5?x4?x2 x3T(x)?x6?x5?x3?1 x4T(x)?x6?x4?x?1 x5T(x)?x5?x2?x?1 x6T(x)?x6?x3?x2?x 9.4.4 循环码编码步骤
1. 本书均指系统码循环码——信码多项式放在最高（左）位开始前k位，其后n?k?r位为监督位。因此信码多项式
?
m(x)?mk?1xk?1???m1x?m0 应首先提升n?k位，变为xn?k?m(x)
然后以生成多项式g(x)去除，得：
?
xn?k?m(x)b(x)?q(x)? （b(x)为余式，q(x)为整式商） 9-47
g(x)g(x)17
?
于是可得循环码 c(x)?xn?k?m(x)?b(x) 9-48
n?k?
式（8-48）的含义——为什么 c(x)?x?m(x)?b(x)？
由于码字c(x)均能为g(x)整除，即 c(x)?g(x)?q(x)?0 [ 模g(x)] 而
xn?k?m(x)?b(x)?g(x)q(x)?b(x)?b(x)?0 [ 模g(x)]，其中b(x)?b(x)?0。
2. 循环码编码电路
图9-4所示以g(x)?x?x?x?1做除法运算，可产生全部（7，3）循环码。图示双掷开关s在现在的位置下，可输入要编码的信码?mi?共k位。于是电路连续输出k位信码，同时经模2加单元及上端闭合开关反馈到前向支路。此后s开关立即反向扳动，待后续 r?n?k位监督元输出，可设（7，3）码的一个码字。
f a b c d
图9-4 g(x)?x4?x3?x2?1的（7，3）循环码编码（除法）电路
432 3. 循环码的对偶码
?
对偶码与（n，k）分组码对应。循环码也存在对偶码，作为x?1的因式分解——
7式（9-41）、（9-42）可提供出（7，k）码系列中的几对对偶码：（7，1）与（7，6），（7，3）与（7，4）对偶，并且由于x?1中包含两种最高幂次为x的g1(x)与g2(x)，如式（9-43）、（9-44）。因此（7，3）、（7，4）有两种对偶码。
?
74关系：x?1?g(x)?h(x) （h(x)称为监督多项式） 9-49
n若以g(x)生成（n，k）码，则以h(x)作生成多项式而生成的（n，n-k）码，两者互为对偶码。
4. 缩短码
? 必要性：选用一个合适的（n，k）码不是很容易，为方便应用可以对（n，k）码 根据需要缩短为
(n?i,k?i) i=1，2… 9-50 如例9-6中（7，4）码，可缩短2位得（5，2）码，其H与G矩阵变为：
18
H(5,3)?10?100?? H??11?010(7,4)去掉最左2列 9-51 ????01?001??G(5,2)?10?110???? G(7,4)中去用前面含2个0的 9-52 01?011??下两列，并去掉前面各2个0。
9.4.5 解码与伴随式纠错
1. 伴随多项式
? 与（n，k）分组码类比，若C(x)经传输后则接受为R(x)，可能含有差错。
R(x)?C(x)?E(x) （E(x)为误差多项式） 9-53 或 E(x)?R(x)?C(x) 9-54
?
如果能求出E(x)，当然即可纠错。C(x)?R(x)?E(x)，但不会一步到位。
?
若无错，则
R(x)?q(x) 即 R(x)?C(x)?0 [模g(x)] g(x)若有错：
R(x)S(x) 即 R(x)?S(x) [模g(x)] 9-55 ?q'(x)?g(x)g(x)?
纠错——若在（n，k）码纠错能力内，则S(x)得到后，最高幂次不高于（n-k）次，
则表明差错发生在监督位中，可以直接纠错，即C(x)?R(x)?E(x)?R(x)?S(x)，即只有此情况，才有S(x)?E(x)。
若错误发生在前k位中，则必须由S(x)去查表，或从该循环码对应的标准H矩阵
中，找出与S(x)相同的列来纠错。
[例9-10] 设表9-2中（7,3）循环码的一个码字C?(0111010)，其码字多项式为
C(x)?x5?x4?x3?x
设在监督项中发生错误，如x项，收码则为
3R(x)?x5?x4?x
收码处理如下
R(x)x5?x4?xx3?4?x?4 3232g(x)x?x?x?1x?x?x?119
即 R(x)?q(x)g(x)?S(x)?xg(x)?x 这里q(x)?x，S(x)?x。
其中，x阶次3小于n?k?7?3?4，因此实际上
3'3'3S(x)?E(x)?x3
但接收者并不知道哪位有错，不能随便认定S(x)?E(x)，因此以S?(1000)，利用标准H矩阵。式（9-86）是H矩阵第4列，因此可纠为
C(x)?R(x)?E(x)?R(x)?S(x)
即 C(x)?(x?x?x)?x?x?x?x?x
现在再来试分析，如果C(x)?x?x?x?x中后二项均发生错误，即
543543543R(x)?x5?x4，试求伴随式
R(x)x5?x4x3?x??x?4 g(x)x4?x3?x2?1x?x3?x2?1即有 R(x)?(x?x)?x?g(x)?(x?x) 其中 q(x)?x，S(x)?x?x
'5433H矩阵中无与（1010）对应的列，表明发生2位或多位错，可利用ARQ纠错。这一点
显然与相对应的（7，3）分组码，因d0=4，只能纠任何码元的1位错与检出2位错，是相同的。
然后再来看错误发生在信息码各项的情况。
[例9-11]C(x)?x?x?x?x中，x是信息码位置，若该位发生错误，
5435R(x)?x4?x3?x即错误发生在C(x)中的阶次高于n?k的情况。
求其伴随式：
R(x)x4?x3?xx2?x?1?4?1?4 3232g(x)x?x?x?1x?x?x?1q(x)=1，S(x)?x?x?1?E(x)，其中，既不可纠错，也检测不出错误项。这时由于S(x)结果对应的伴随式S?(0111)，若是1位错，（7，3）码的纠错能力应当能达到。这种发生在系统码(n,k)循环码的高于n?k阶次的各高次项的错误，欲纠错，只好利用（7，3）循
'220
环码对应的H矩阵式（9-86），即S?(0111)，它是标准型H矩阵第2列，即Cr应纠正为C=（0111010），对应的正确码字多项式为C(x)?(x?x?x?x)，完成了纠错。
5439.4.6 生成矩阵多项式
由例9-11，涉及到当R(x)中误差在前k项时，S(x)求出后需去找相应（n，k）码对应的H矩阵中与S(x)系数相同的列来对R(x)纠错。因此需“知道”H矩阵。
1. 循环码生成矩阵多项式G(x) ? 由g(x)已知——是（n，k）循环码中最低幂次的码字。 ? 对应的矩阵为：
?xk?1?g(x)??x6?x5?x4?x2???????如(7， G(x)??3)码?x5?x4?x3?x? 9-56 ?x?g(x)??x4?x3?x2?1???????g(x)??2. G(x)对应的G和H矩阵的标准形式
?
?1110100???'G(x)系数矩阵 G?0111010 9-57
????0011101??化为标准形式：
?
?1?100?1110??1?? G?010?0111 H?????1??001?1101????0?
01?1000?11?0100?? 9-58 10?0010??11?0001?H矩阵的n列与（n，k）循环码的隔伴随多项式S(x)相对应。因此为接收检纠错，
总是把与（n，k）循环码对应的标准H矩阵存储于接收端，也可由表9-3表示。
错误格式 对应伴随式S(x)
E(x) 法 432(模) g(x)?x?x?x?1
1 1 （0001） 错在监督位
x E(x)=S(x) x （0010）
纠错： x2 x2 （0100）
R(x)+S(x) x3 x3 （1000）
错在信息位 x4 x3?x2?1 （1101）
E(x)?S(x) x5 x2?x?1 （0111）
纠错：R(x)?E(x) x6 x3?x2?x （1110）
表9-3 （7，3）循环码H矩阵提供的E(x)与S(x)对应关系