6
限为
Pe?Ae?nE(Rb) 9-14
式中E(Rb)——误差指数。图9-3位误差曲线
E(Rb)
C1?C2
Rb C2 C1
图9-3 不同信道容量时误差与速率关系
3. 汉明距离 ? 码长为n的分组码，汉明距离等于码字集合中所有两码字对位模2和的重量，即 d?d(ci,cj)??(ck?0n?1ik?cjk) 9-15
?
当码字集合中含有全0的码字，则d等于重量（1码个数）最小的数目d0——是
差错控制能力的唯一参量。 4. 差错控制定理 码率为R??
k的（n，k）分组码，差错控制能力为 nd0?e?1 9-16 检出e位错：
纠正t位错：d0?2t?1 9-17 纠t位同时可检e位：d0?e?t?1 9-18
?
?
9.2 线性分组码 9.2.1 构思特点
1. 构思
为达到按“定理”规则所指定的差错控制能力，在待发送源码k位码字之后，通过k位信码的线性组合而提供n?k?r位冗余，则形成包括k位信码与r?n?k位冗余（称为监督元或校验元）的码率为R? 2. 最简单的（n，k）码
k的（n，k）线性分组码。 n7
? ?
奇、偶校验码 （n，1）重复码
9.2.2 （n，k）码编制过程举例
[例9-3] 试编制（n，k）=（5，2）分组码。 解：
1. 设置监督方程组
?
由（n，k）=（5，2），冗余位为r=3，k=2。码集合为：c?(c4c3c2c1c0)，c4c3—
—信码组，c2c1c0——监督位。
?
需设置3个各由c4c3组成的线性独立方程
c4?c2?0????c3?c1?0? 9-19 c1?c3? 或
c0?c4?c3?c4?c3?c0?0???2. 一致监督矩阵H
c2?c4式（9-19）系数矩阵为：
?10?100????P?I?
H??01?0103????11?001??9-20
3. 生成矩阵G——可由H直接得到
?
G?I29-21
??PT???I?2?10?101??Q????
01?011???PT??P?Ir??0?
G?HT?H?GT?Ik?
9-22
4.（n，k）码
?
码字 C=（信码组）?G?(nk?1nk?2?n1n0)?G 9-23 本例：C?(m1m0)?G?(10)??k2?
?10101???(10101)
01011???
（5，2）码共2?2?4个码字：00000，01011，10101，11110。
5. 差错控制能力为：d0?3 （可自动纠1位）。
6. 系统码定义
? （n，k）码中最高位开始为k位信息码，而监督元n?k位在其后部。
8
?
符合称为标准矩阵形式。
9.2.3 解码伴随式与纠错
1. 传输差错
?
CR?C?E （式9-10）
接收校验：C?HT?
?0 （码字无错） 9-24
T CR?H 2. 伴随式定义：
?C?HT?E?HT?E?HT 9-25
??0S?E?H?CR?H???0TT?
无错有错 9-26
例：由上述（5，2）码，如C=10101，错1位为CR?10111。
?1?0?T S?CRH?(10111)?1??0??001?11??00???010?
?10?01??d0?3可纠t?1位。结果S??010?是式（8-20）H矩阵中第4列——表明CR中第4位错，
所以，C=10101。
[例9-4] 试编（n，k）=（6，3）码，并指出其差错控制能力。若有两个码组为c1=111100及c2=001011，问是否属于（6，3）码，能否纠错。 解：
?c2?c5?c3? （1） ?c1?c4?c3 或
?c?c?c54?0?c5?c3?c2?0??c4?c3?c1?0 ， ?c?c?c?040?5?101100??? （2） H?011010 ????110001???100101??? （3） G?010011 ????001110?? （4） （6，3）码字：G矩阵中已有3个，尚有4个需计算：000000，001110，010011，
9
011101，100101，101011，110110，111000。d0?3（可纠1位码）。 （5）将码组c1=111100及c2=001011代入式中，得
S1?(111100)HT?(100) （H中的第4列）c1应为：111000。 S2?(001011)HT?(101) （H中的第1列） 纠为：101011。
（6）讨论：若错误超出本例t=1的纠错能力，如错2位：
?
设c3?(111111) S?(111)，H中无此（111）列，可通过ARQ重发纠错。 若码字001110错为c4?101010（错2位），则S4?(001)为H中第6列，纠为
?
c?101011，纠而仍错，误认为是码字101011的末位错。
? 在设n?k个联立方程组时尽量利用k位信息码字多位的线性组合。且各方程原 ?c2?c5?100100????则如：?c1?c4 则 H?010010?G 包括了3对重复列，使纠错的H
???c?c?3?001001???0矩阵必须由非全0及非重复列构成。
9.3 汉明对（n，h）的贡献
美国著名数学家R.W.Hamming对于信息论及编码技术做出了卓越的贡献，1980年出版的“编码与信息论”等专著，以他的名字命名“汉明距离”、“汉明界”、“汉明码”等，均为差错控制码的非常重要的组成部分。
9.3.1 汉明界
当要求可纠t位错，纠n与k的关系，汉明给出了“线性码最大码距下界”：
?t?n??? t?d0?1 9-27 ?n?k?lb????i???2?i?0???或 2n?kt?n?????i?? 9-28 i?0?? 例如：当欲使t?1（即d0?3），可得 2n?kt?n??n??n?????i?????0?????1???1?n 9-29 i?0??????10
即 n?k?lb(1?n)，若n?7，r?n?k?lb?8?3。 [例9-5] 由汉明界公式，试给出
（1）需纠t?2位错（即d0?5），给出n与k的关系。 （2）设n?7、 t?2，求k？ （3）选k?5，要求t?2，求n？ 解：
（1）当t?2， 2n?k?n??n??n??n?n(n?1)??????????????1?n? ?i??0??1??2?2i?0????????2n2?n ?1?，
2n2?n或 n?k?lb(1?)。
2 （2）设n?7 27?kn2?n72?7?(1?)?1??29，
22或 7?k?lb(29)?4.68。则k?2.142，只能取k?2。
?
特别说明：（n，k）码，要求纠1位错时，即 t?1，d0?3。却不可以为 d0?
、（7，4）可纠1位n?k?r，即d0不一定等于监督元数。但有些（n，k）码，如（7，3）错，监督元数r与d0相等是“巧合”——式（9-27）的对数值为整数。 （3）选k?5 2n?5n2?nn2?n?1?)，n?11。 ，即n?5?lb(1?229.3.2 汉明码、完备码
1. 汉明码——纠t位错时d0具有最小值的（n，k）码
如（7，4）码是汉明码，d0?3 t?1；（7，3）码d0?4 t?1，不是汉明码。 2. 汉明码定义——是（n，k）码可纠t位的高效码：
?
n?k?m，码长 n?2m?1
信息位 k?n?m?2?1?m 9-30
m?