11
?
如（7，4）码：m?3，n?2?1，k?2?1?3?4。
333. 完备码（exhaust code） 由式（9-27），当等式成立时为完备（n，k）码
?
?t?n??d0?1???n?k?lb? 9-31 t????i??2?i?0???如（7，4）码：7?4?lb(1?n)?lb(8)?3。
?
汉明码是完备码。
[例9-6] 编制（7，4）汉明码，给出全过程。 解：
（1）构成H矩阵，由，P矩阵可随便提供4列3行非全0列，则
?
?1110?100??
H??0111?010????1101?001??即除后3列构成I3单位矩阵外，其余4列顺序随意，不影响差错控制能力。
（2）G?I4??PT??1?0???0??0000?101?100?111?? 010?110??001?011? （3）码字——2?1?15个非全0码字，G矩阵中已有4个，在计算11个。
?
4技巧：先把11个k?4位信码按自然码写出，只计算各自后3位，如表9-1所示
信息位 c6c5c4c3 0000 0001 0010 0011 0100 0101 0110 0111 监督位 c2c1c0 000 011 110 101 111 100 001 010 信息位 c6c5c4c3 1000 1001 1010 1011 1100 1101 1110 1111 监督位 c2c1c0 101 110 011 000 010 001 100 111
表9-1 （7，4）汉明码
12
9.3.3 汉明码的扩展与扩展码
1. 扩展汉明码（汉明增余码）
?
（7，4）汉明码码字中至少一个码字为d0?3（按例9-6，有7个码字）。加一位
监督位则d0?4，于是，相应的H矩阵变为
H(8,4)1?11????H(7,4)???1?0?? 9-32 ???0?（在（7，4）码H中顶部或底部加1列“1”，右边加1列“0”。）
或 H(8,4)??H(7,4)????1?110??1?00??由例9?6??1?????1??1mm1101000?1110100?? 9-33 1010010??1111111?d0?4，由H(8,4)构成的码，即(2,2?1?m)码称为扩展汉明码。 （n?1,k）k?4。n?8，
2. 一般（n，k）码的扩展码
如（5，2）扩展过程，由[例9-3]
H(5,3)?10100??10101?? 及 G??01010?(5,2)?01011?， ??????11001??则H(6,4)?1?1???0??111111?01000??101010?? G? (6,2)???10100?010111??10010?由（5，2）码变为（5，2）扩展码：（6，2）码。 3. 对偶码（Dual）
?
分组码（n，k）的对偶码为（n，n?k）=(n，r)。相应的H与G进行变换：H(n,k)
?G(n,r)， G(n,k)?H(n,r)。如（7，4）码与（7，3）码，（5，2）码与（5，3）码，（7，1）
码与（7，6）码等均为对称码，（6，3）码的对偶码为其本身。
[例9-7] （4，1）码与（4，3）码为对偶码。这里（4，1）码为重复码，（4，3）码为奇偶校验码。试通过求其H、G并产生码字，以证明两种简单码型均属于（n，k）线性分组码。
证： （1）（4，1）重复码n?4，k?1，n?k?r?3
13
?
?c2?c3?应提供n?k?3个监督方程，也是重复的：?c1?c3
?c?c3?0?1?100???H矩阵为3?4：H?1?010 ????1?001??G为1?4矩阵H??1?111? （4，1）码字：0000，1111。
?
?
?
?
d0?4，可纠1位，同时可检2位错。
（2）（4，3）校验码n?4，k?3，n?k?r?1
?
监督方程1个：c0?c3?c2?c1 H为1?4矩阵：H??111?1?
?
?
?100?1???G为3?4矩阵：G?010?1 ????001?1??（4，3）码码字：非全0码23?1?7个，即0000，0011，0101，0110，1001，1010，
?
1100，1111。看出这完全是偶校验码形式：在001，010…111各信码组（k?3）后面按“凑
足”偶数个1来决定第4位，是0还是1。
?
（原3位码组之间至少1位不同，又加1个偶校验位变为d0?2）。 d0?2可检1位错
结论：由以上分析，（4，1）与（4，3）码完全符合（n，k）分组码（增余码）一切规则。
因此，两者均为简单的分组码，只是因为简单，无须使用H、G等复杂手续。
9.4（n，k）循环码
循环码是（n，k）线性码的一个重要子类，电路实现编解码容易，它有R-S、CRC、BCH很多高效子类码，实际应用最多。
9.4.1 预备知识
1. 多项式表示编码序列 ? （n，k）码的1个码字，以多项式表示——为了表示一串2元码1，0序列的每个 码元位置是0还是1。
? 表示法：随便指定一个字母作“基序”，其幂次表示某码元排序中的序位；由其幂
14
权值表示是0还是1。（n，k）码表示为 c(x)?(an?1xn?1?an?2xn?2???a2x2?a1x1?a0x0) 9-34
4如： c1?(1001101) c1(x)?(x?x?x?1) c2?(00010)1 0c1(x)?(x?x?x?1) 2. 多项式运算规则
?
664模2和=模2减。如x?1?x?1；(x?x?1)?(x?1)?x 9-35
nn4343又如， (x5?x4?x2?1)?(x4?x3?x)?(x5?x3?x2?x?1)。
?
乘法：(x?1)(x3?x?1)?x4?x3?x2?1 x5?x3?
除法：?x32xx2?x?(x?x)?x2?x 通式表示：
被除式F(x)余式R(x)除式N(x)?商式q(x)?N(x) x3?x2x2?x演算： x2?xx5?x3?x x2?x?1x4?x2?x
x5?x4x4?x3?x2x4?x3?xx3?xx4?x3x3?x2?xx(余式)x2(余式)?
同余式：被除式F(x)与余式R(x)称为在模N(x)运算时的同余式，表示为
F(x)?R(x) [模N(x)] 如：x5?x3?x?x [模 x2?x] x4?x2?x?x2 [模 x2?x?1]
?
特例：x7?1?(x4?x3?x2?1)(x3?x2?1)
则： x7?1?0 [模x3?x2?1] 或 [模x4?x3?x2?1] 3. 循环移位特征
如：C=（1110100） c(x)?(x6?x5?x4?x2)
左移一位：x?c(x)?x?(x6?x5?x4?x2)?x6?x5?x3?1 （模x7?1）
9-369-379-38 9-39 9-40
15
再移一位：x?c(x)?x?(x?x?x?x)?x?x?x?1 （模x?1）
2265426479.4.2 （n，k）循环码的特点
1. 循环码特征（定义）
? 符合（n，k）线性分组码特点——在码内（码字集合）中的任意2个码字之和为 该码中的一个码字。
? 在（n，k）码中的任何一个码字连续位移i位（i=1，2…n?1），就可得到另一个 非全0码字。
2. 能符合定义的必要条件
?
若某（n，k）码，要看它是否是循环码。第一步是码长n为幂的多项式x?1分解
n出至少1个因式的最高幂次为n?k?r。如（n，k）=（7，k）码系列：
xn?1?x7?1?(x?1)[(x3?x?1)?(x3?x2?1)]?(x3?x?1)[(x?1)?(x3?x2?1)]?(x3?x2?1)[(x?1)?(x3?x?1)]x7?1?[(x?1)?(x3?x?1)](x3?x2?1)或
(1)??(2)? 9-41 ?(3)?(4)??(5)? 9-42 ?(6)??[(x?1)?(x3?x2?1)](x3?x?1)?[(x3?x?1)?(x3?x2?1)](x?1)例如：（7，3）码，n?7，k?3，n?k?r?4。 由式（9-41）、（9-42）中共6种，有两种组合因子式的幂次为n?k?r?4，即
g1(x)?(x?1)(x3?x?1)?x4?x3?x2?1 9-43 g2(x)?(x?1)(x3?x2?1)?x4?x2?x2?1 9-44
?
能提供出x?1含有最高幂为r?n?k的子因式g(x)是构成（n，k）循环码的先决
n条件。
9.4.3 由生成多项式构成循环码
?
作为一个例子，对于如（n，k）=（7，3）码，在通过上述式（9-43）、（9-44）提
供的g1(x)或g2(x)。本身就是由信码中高位开始含“0”最多的001对应的循环码，即为
g1(x)或g2(x)。
?
由定义及移位循环可得全部7个非全0码字：
ci(x)?xig1(x) i=1，2…6 9-45