信道编码(上)ppt课件.ppt

《信道编码(上)ppt课件.ppt》由会员分享，可在线阅读，更多相关《信道编码(上)ppt课件.ppt（107页珍藏版）》请在三一办公上搜索。

1、第三章 信道编码 （计划学时 18）,本章主要内容,检错、纠错原理 2学时 差错控制理论 1.5学时 线性分组码 2.5学时 循环码 3学时 循环码的扩展 3学时 卷积码 3学时纠正突发错误的编码 3学时,教学目的与要求 1.深刻理解信道编码的检、纠错原理。 2.熟练掌握建立译码规则的原则和计算错误概率的方法。 3.掌握线性分组码、循环码、卷积码等重要的信道编码的原理与方法。（重点） 4.了解Shnnon信道编码的内容和意义。,参考文献,1.王新梅：纠错码原理与方法 西安电子科技大学出版社（2001年4月 修正版）2.袁东风：宽带移动通信中的先进信道编码技术 北京邮电大学出版社 (2004年3

2、月第一版)3.吴伟陵：信息处理与编码 人民邮电出版社（1999年7月第一版）4.曹雪虹：信息论与编码 北京邮电大学出版社 (2001年8月第一版),第三章 信道编码 3.1 检错、纠错原理,本节的主要内容,检错原理 纠错原理 汉明重量与最小码距 检错纠错能力 信道编码的性能指标 几种简单的检、纠错码,外语关键词,信道编码：channel coding 检错与纠错：error detection and correction 汉明距离：hamming distance 最小码距：minimum code distance 重复码：repetition code 奇偶校验码：parity-chec

3、k code,温旧引新,三大编码： 信源编码、信道编码和加密编码信源编码： 压缩代码长度的编码。信道编码： 为了减少差错而进行的编码。,3.1.1 检错原理误码的必然性: 在有噪声和损失存在的信道中，输入符号与接收符号不能一一对应，传输错误和判断错误的情况总会存在。 误码的不可预知性： 误码是随机发生的。接收端并不了解是否发生了误码，更不知晓是哪个码元出现错误。,检错-如何检测有无误码？ 办法很多。比如双连编码方式把每个0和1都重复一次，再送入信道。接收端一旦发现有违背“双连”规律的码元，就能判断该码元发生了错误。,原因-冗余的作用 两个码元当一个用，增加了“冗余”，给误码留下了表达空间，才使

4、码字克服了原先0和1“非此即彼”的情况，。,例1、用2位二进码传输四种天气状况： 晴、 阴、 雨、 风,被传信息只有 2 bit，冗余1 bit。 码字增加为23=8个，许用码字4个，非法码字4个。 任意有1位发生错误时,该许用码将变成非法码。冗余使编码避免了非此即彼，具有了检错能力。,00 01 10 11,由于没有冗余,所以非此即彼,错了也不知,晴、 阴、 雨、 风 000 011 101 110,例2、改用3位二进制码元传输它们：,思考题：1.信源编码中要压缩掉冗余，信道编码中又要添加进冗余，是不是返工浪费？两种冗余有何不同？2. 是不是随便添加冗余, 都能克服非此即彼? 怎样的许用码才

5、能有检错功能？,3.1.2 纠错原理发现错误怎么办？ 有三种处理方案： （1）重发反馈方式（ARQ）； （2）自动纠错方式（FEC）； （3）混合纠错方式（FEC）；自动纠错的前提： 不仅知道有错，还应知道是哪个码元出现错误。,双连码只能检错，不能纠错，因为冗余不够。 三连重复码当其中任一码元出错时，还有2位没有错，通过比较就能发现是哪一位错了，从而可以进行纠正。 万一三连重复码有两位码元出错时，就会判断失误。因为超出了它的纠错能力。 三连重复码的纠错能力是1位，五连重复码的纠错能力是2位，添加的冗余越多，纠错能力就越强，然而传输效率就越低。 冗余也是编码具有纠错能力的前提,汉明距离(Hanm

6、ing distance)： 定义两个许用码字相同码位上不同玛元的个数叫它们的汉明距离。汉明距离反映了两个码字的差别。 双连重复码的汉明距离d=(00,11)=2；三连重复码的汉明距离d=(000,111)=3； 双连重复码发生1位错的误码是01或10，与许用码字11或00的汉明距离相同，无法判别误码来自谁。 当三连重复码有一位码元出错时，比如000变成001、010或100，误码与000的汉明距离为1，而与111的汉明距离为2，据此就可判定误码来自000；,例3、用5位二进码传输四种天气状况：,晴、 阴、 雨、 风00000 01011 10110 11101,被传信息只有 2 bit，冗余

7、3 bit。共25=32个码字， 许用码字4个，非法码字28个。当任意发生1位错误时,误码与源码的汉明距离是1位，而误码与其它码字的汉明距离是2位。 更多的冗余不仅避免了码字之间非此即彼，而且能够帮助分析误码的可能来源，使编码具有了自动纠错能力。,检错原理：冗余的添入，增加了码字总数，给误码留下了空间，就给判断正确与错误提供了可能。纠错原理：更多冗余的添入，拉大了许用码字之间的汉明距离，就有可能区别误码与各个许用码字之间汉明距离的不同，从而判断误码可能的来源。,检、纠错原理小结,3.1.3 汉明重量与最小码距汉明重量(Hamming weight)定义码字中码元 1 的个数叫做该码字的汉明重量

8、。 如：W01011=3；W00000=0；汉明重量与汉明距离的关系： d (u, v) = W uv u和v是任意两个码字，代表按位模2加(异或)。 u和v码元相同的位模2加为0，不同的位模2加为1， W uv就给出了u和v不同位的个数。,最小汉明距离 一种编码有许多个码字，全部两两比较后，可以找出最小的汉明距离d0。例3中：C1=00000；C2=01011；C3=10110；C4=11101； 则：d (C1, C2)=3； d (C1, C3)=3； d (C1, C4)=4； d (C2, C3)=4； d (C2, C4)=3； d (C3, C4)=3； 因此最小的汉明距离为d0

9、=3（可纠1位错）例2中：C1=000；C2=011；C3=101；C4=110； 同样不难求出最小的汉明距离为d0=2（可检错）例1中：C1=00；C2=01；C3=10；C4=11； 同样可求出最小的汉明距离为d0=1（非此即彼）,定理：线性群码的最小汉明距离等于非零码字的最小汉明重量 d0= Wmin. 以例3的5位二进码传输四种天气状况： C1=00000；C2=01011；C3=10110；C4=11101； 解释什么是线性码？ C4=C2C3； C3=C2C4；C2=C3C4；C1=C2C3 C4 ；任何一个码字都能由其它码字的模2加得到。什么是群码？ 各码字无论怎样模2加，都不会

10、得到这4个码字之外的东西,这4个码字构成了一个封闭集合。可见它是线性群码，定理条件成立。 于是 d 0 = Wmin =3,定理的证明：设u 与v 之间码距最小，于是： d 0 = d (u, v ) = W uv W min 式中uv是另一许用码字，其重量当然不应小于 设定的最小重量 W min ；另一方面，设非零码字c 具有最小重量，则： W min= W c = W c0 = d (c, 0 ) d 0 式中d (c ,0) 是码字c 与全零码字0的距离，它当然不应小于设定的最小汉明距离d 0 ； 两式同时考虑， 只能有 d 0 = Wmin,逐层深入：,1、没有冗余不行，冗余是检错纠错

11、的前提。2、随意添加一些冗余未必有用。应当通过有计划地添加冗余，使编码者能够恰当地选择许用码字，从而尽量拉大许用码字之间的汉明距离，为检错纠错创造条件。 3、仅仅拉大个别码字之间汉明距离是无益的，只有全部码字的汉明距离都大才有意义。为此只须关注最小汉明距离。 因此，足够多的冗余只是能够检错纠错的必要条件，而精心选择许用码字使它们的最小汉明距离大于某个数值才是能够检错纠错的充分条件。4、为了求得最小汉明距离，不必一一计算全部码字之间的汉明距离，只须寻找最小码字重量即可。,3.1.4 检错、纠错能力检错、纠错能力与最小汉明距离有直接关系设d0为最小汉明距离，e为可检错位数，t为可纠错位数，则：(a

12、)为了发现e个错误码元，要求最小码距d 0e+1 ；(b)为了纠正t个错误码元，要求最小码距 d 02 t+1 ；(c) 为发现e个错码元，同时又能纠正其中t (te )个错误码元，要求最小码距 d 0 e +t +1 ；,纠错、检错能力与最小码矩的关系,如果只检错不纠错，则最多检错位数是e=d0-1。如果只纠错不检错，则最多纠错位数是： t = INT (d0-1)/2，INT表示取整数如果既纠错又检错，则e和t就不能独立，它们应满足关系式：e+td0-1，而且e必须大于t，,例1已知汉明距离d0=7,分析检、纠错能力。 （1）只检不纠：e =d0-1=6；可检到6位错。 （2）只纠不检：t

13、 =(d0-1)/2=3；可纠3位错。 （3）又检又纠：e 与t不独立：e+td0-1，且et当t =1时，1e5，1位错已纠，能检出第25位错。当t =2时，2e4，2位错已纠，能检出第34位错。当t =3时，e 无解，3位错已纠， 3位以上无能力检到。,3.1.5 信道编码的性能指标编码效率 设某种编码的码字长n 位，其中信息只有k 位，r = nk 为冗余位，最多可纠错 t 位。则考察编码效率的指标有： （1）信息传输率：=k /n （2）错位可纠率：= t /n （3）冗余利用率：= t /r漏检率 把编码检查不出的错误所出现的概率叫做漏检率。差错率 把编码不能自动纠正的错误所出现的概

14、率叫做差错率。,例2讨论双连重复码的编码效率和漏检率。 编码效率 =k /n=1/2=0.5 假设对称信道，0与1的错误概率均为p，则： 漏检率=2位同时出错的概率=p2,例3讨论三连重复码的编码效率和差错率。 编码效率 =k /n=1/3=0.33 差错率=3位同时出错的概率 +2位出错1位正确的概率=p3+3p2(1-p),例4某线性群码由以下16个码字组成：C0(0000000) C1(0001011) C2(0010110) C3 (0011101) C4 (0100111) C5(0101100) C6 (0110001) C7 (0111010) C8 (1000101) C9(1

15、001110) C10 (1010011) C11(1011000) C12(1100010) C13 (1101001) C14 (1110100) C15 (1111111)求最小汉明距离、可纠错位数、编码效率和差错率。解：最小汉明距离: d0=Wmin=3 可纠错位数: t =(d0-1)/ 2=1 编码效率： m=16 k=log m=4 n=7 =k /n =4/ 7=0.71 差错率= 1- (1-p)7-7p(1-p)6,3.1.6 几种简单的检错、纠错码（1）n连重复码 n为奇数时，可纠正 t =(n-1)/2位错误。错传概率为p时， 差错率=n位同时出错的概率+(n-1)位出

16、错1位正确的概率 +(n+1)/2位出错(n-1)/2位正确的概率 =pn+Cn1 pn-1(1-p)+ Cn(n-1)/2 p(n+1)/2(1-p)(n-1)/2n为偶数时，可纠正(n/2-1)位错误，还能发现第n/2位出错。 漏检率=n位同时出错的概率+(n-1)位出错1位正确的概率 +(n/2+1)位出错(n/2-1)位正确的概率 =pn+Cn1 pn-1(1-p)+ Cn(n/2-1) p(n/2+1) (1-p)(n/2-1)它的编码效率很低，只有 =1 /n,（2）奇偶校验码k 个信息位后面添加1位“奇偶校验位”，其关系为：,编码效率 它的效率很高，达到：=（n-1 )/n =

17、1-1/n检、纠错能力 可查出任何奇数位的错误，却不能发现偶数位的错误，也没有纠错能力。漏检率=Cn2 p2(1-p)n-2 +Cn4 p4(1-p)n-4 +,（3）双向监督码为了增加奇偶校验码的检错能力，对列再进行奇偶校验，增加一行“竖直奇偶校验位” ，进行双向监督。也称方阵码。,干扰造成的误码，往往 发生在连续若干个码元上。 采用上述双向监督，就把 行中难以发现的错误，在 列中发现。,（4）恒比码从n 位二进制自然码中挑出和的个数之比恒定的一些码字组成许用码集合。五中取三码是从25 =32 个二进自然码中挑出含 3 个1，2 个 0的码字，共10个（5取2的组合数），用来表达10个阿拉伯

18、数字； 七中取四码则是从 27 =128 个二进自然码中选出含4 个1 ，3 个0 的码字，共35个（7取3的组合数），可用来表达26个英文字母和标点符号。,例5讨论恒比码的编码效率和漏检率。五中取三码的编码效率=k/n=log10/5=66.4% 七中取四码的编码效率=k/n=log35/7=73.3% 它们可以发现多位错误，却不能发现同时出现0误为1且1误为0的错误，也无纠错能力。五中取三码的漏检率为： C31p(1-p)2C21p(1-p)+C32p2(1-p)C22p2 (1-p)0 =6p2(1-p)3 +3p4(1-p)七中取四码的漏检率请同学们推导。,小结：信道编码的原理： 检错

19、原理-添加冗余，克服非此即彼，分辨对错。 纠错原理-添加冗余，拉大码矩，判定错误来源 汉明距离与检纠错能力： 检错位数 e =d0-1， d0表示最小汉明距离 纠错位数 t =INT (d0-1)/2，INT表示取整数 简单的检纠错码： n连重复码、奇偶校验码、恒比码,课后复习题 思考题： 讨论七中取四码的编码效率和漏检率。作业题： 教材第114页习题三第1、4、6、7题；,第三章 信道编码 3.2 差错控制理论,本节的主要内容,译码规则 最小平均错误准则 最大后验概率准则 最大似然准则 错误概率的计算 信道编码定理,外语关键词,最小平均错误准则: Minimum mean error rat

20、e criterion 最大后验概率:Maximum posterior probability 最大似然准则： Maximum likelihood decoding criterion译码规则：Decoding rule错误概率：Error probability漏检率： Undetected error rate差错率： Uncorrected Error rate,温旧引新,检错、纠错原理：冗余的作用。 检错、纠错能力：最小汉明距离 编码效率： =k /n 漏检率： 实施编码后仍检查不出的错误所出现的概率。 差错率： 实施编码后仍检纠正不了的错误所出现的概率。,3.2.1 译码规则,编

21、码在发送端进行；误码在信道中发生；发现与纠正错误是在接收端译码器中进行。,译码规则是设计人员预先为译码器设计好的译码指令。对于每个接收符号bj；系统都应当为它指定一条译码规则：F(bj) = ai* 告诉译码器应当把bj译为哪个 ai ；比如三连重复码的译码规则是： F(000)=0; F(001)=0; F(010)=0; F(100)=0; F(111)=1; F(011)=1; F(110)=1; F(101)=1;,例1信源发出符号a1， a2，a3；接收端符号为 b1，b2，b3； 对它可以构造多种译码规则。比如：译码规则A: F(b1)=a1；F(b2)=a2 ；F(b3)=a3译

22、码规则B： F(b1)=a1； F(b2)=a3； F(b3)=a2 同样的信源信道，选用不同的译码规则，将会得到不同的结果。 究竟采用哪个译码规则更好呢？一个很自然的考虑就是按该规则译码后，造成的错误应最少。,能不能搞出一个不造成错误的译码规则呢？不能。这是因为同一种误码存在不同的来源。,无论怎样译码总不能两面兼顾。然而总得为接收到的代码指定一个译码吧！ 我们自然要选择错误概率最小的译码规则。 如何定义并计算错误概率？,3.2.2 译码错误概率,译码规则一旦确定，译码器就按指令办事。设译码规则为F(bj) = ai* ，当收到一个符号bj时， 按译码规则它就被译为 ai*。如果信源发出符号恰

23、为 ai*，就翻译对了；如果信源发出的是其它符号，译码器按指令仍然会把它译成为 ai*，就译错了。,译码错误概率计算公式,按规则A: F(b1)=a1；对应 p(a1 b1) = 0.15 F(b2)=a2 ；对应 p(a2 b2) = 0.12 F(b3)=a3 ；对应 p(a3 b3) = 0.12 正确概率P =0.15 + 0.12 + 0.12 = 0.39 错误概率PE=1-P =0.61,解：因为：p(aibj) = p(ai)p(bj|ai) =,按规则B: F(b1)=a1；对应 p(a1 b1) = 0.15 F(b2)=a3；对应 p(a3 b2) = 0.09 F(b3

24、)=a2；对应 p(a2 b3) = 0.20 正确概率 P =0.15 + 0.09 + 0.20 = 0.44 错误概率PE=1-P =0.56显然，译码规则B优于译码规则A。有没有更好的译码规则呢？最佳的译码规则是什么？怎样确定？,3.2.3 制定译码规则的准则,基本准则： 最合理的译码规则应当能使译码的平均错误概率最小。这个原则称为平均错误概率最小准则。要使平均错误概率最小，译码正确的平均概率就应当最大。其充分条件是对于每一个接收符号bj时都满足后验概率p(ai* | bj ) 为最大。可见，平均错误概率最小准则等价于后验概率择大准则。,后验概率择大准则,当收到一个符号bj时，系统并不

25、知道发的是什么符号。但是系统可以根据信源和信道的统计性质算出收到bj的条件下，信源发出各个 ai 的后验概率p(ai | bj )，(i=1,2 , , m) ，并进行比较。把后验概率最大的那个ai 指定为应当翻译的发送符号，记作ai* 。此即后验概率择大准则。它要求译码规则：F(bj) = ai* 满足： p(ai* | bj ) p(ai | bj ) i=1, 2, , m,看出，对于每个指定的bj，后验概率择大与联合概率择大是一致的。因此, 可以通过联合概率来确定译码规则并计算错误概率。,例3求例2中满足最小错误概率的译码规则。解：由联合概率矩阵每列选出最大者，打上*号:,即知： F(

26、b1) = a1； F(b2) = a2 ；F(b3) = a2不妨称它为译码规则C，它与规则A和规则B都不同。 正确概率 P =0.15 + 0.12 + 0.20 = 0.47 错误概率PE=1-P =0.53显然，译码规则C优于译码规则A与 B 。,p(aibj) =,2等概信源的基本准则： 将最大后验概率准则： p(ai*| bj) p(ai| bj) 。代入贝叶斯公式，即：,信源符号等概率：p(ai) = p(ai*) = 1/m为常数，则后验概率最大的准则变成了前向概率最大： p(bj | ai*) p(bj | ai ) i=1, 2, , m在信源符号等概率分布的前提下，可以直

27、接由传输矩阵确定译码规则。,例4信源等概，信道与例2相同。试确定其译码规则和错误概率。解：由传输矩阵每列选最大者打上*号：,第二列元素相同，随便选哪列都行。比如仍选第一行的矩阵元，得到译码规则D： F(b1) = a1； F(b2) = a1；F(b3) = a2,正确概率,错误概率PE=1-P = 0.567,3最大似然准则： 有时信源并不等概，或不知道它是否等概，为了方便，也往往直接由前向传输矩阵出发，选每列的最大者来制定译码规则，称之为最大似然准则。 这样做，显然不能保证所设定的译码会使平均错误为最小。 作为一个简单实用的近似准则使用，仍然是可以的。何况很多时候实际信源与等概率信源差别并

28、不大。,例5已知信源和信道的统计性质：,分别按()按最小错误准则()最大似然准则，制定译码规则并计算错误概率。,可见： F(b1) = a3； F(b2) = a3 ；F(b3) = a2 P = 0.15 +0.3 +0.125 = 0.575；PE = 1-P= 0.425；,解：(1)由 p(aibj) = p(ai)p(bj|ai)=,(2) 直接在信道传输矩阵每列最大者上打*,译码规则：F(b1) = a1； F(b2) = a3 ；F(b3) = a2正确概率：,= 0.4 /4 + 0.5 /4 + 0.6 /2 = 0.525； 错误概率：PE = 1-P= 0.475；,我们

29、已经有了两种评判信道编码效果的方法：检、纠错能力与译码错误概率。,3.2.4 错误概率与纠错能力,为什么后一种描述更科学？一方面，有些编码很难用检、纠错的位数来描述其功能，比如奇偶校验码能发现奇数个多位的错误，却不能发现偶数个，哪怕两位的错误。 另一方面，通信的可靠程度与纠错位数之间不是正比关系，而与码长以及具体编码方案都有关。最终可观测的质量指标应当是平均错误概率。平均错误概率是衡量编码优劣的最终判据，而“能纠正几位错”的说法是不严格的。更科学的说法是通过信道编码，把差错率控制到什么水平之下。,差错率的计算：,差错率是经过信道编码仍然不能得到纠正的错误所占的比率，可见差错率就是平均译码错误概

30、率。因此可用计算平均错误概率的方法计算差错率。在ARQ(重发反馈方式)的检错编码中，如果认为凡是发现的错误都要重发，直至正确为止。从这个意义上讲，凡是发现的错误都得到了纠正，没有纠正的就是没有发现的错误。因此差错率=漏检率。漏检率的计算，则要具体分析哪些情况的错误是该种编码发现不了的，它的概率多大。,例6讨论三连重复码对降低差错率的作用。 设：二元对称信道传输单符号的错误概率为： p=0.01，（正确概率为 =1-p =0.99）三连重复编码，发出的码字为： 0=000，1=111； 各种可能的接收符号为： 0=000，1=001，2=010，3=011， 4=100，5=101，6=110，

31、7=111； 三次扩展信道的转移矩阵为：,由于 p，所以矩阵中含 3 和 2p的矩阵元都较大，按最大似然准则选它们作为a*，可确定译码规则为：,F(0)= F(1)= F(2)= F(4)= 0 F(3)= F(5)= F(6)= F(7)= 1,平均错误概率为：,与编码前单符号传输相比，差错率由原来的百分之一降低到万分之三。代价是传输效率为原来的三分之一。,3.2.6 信道编码定理,定理：离散无记忆信道X, P(y|x), Y，X 是信道编码使用的符号集，Y 是接收符号集，P(y|x)为信道传输概率，信道容量为C。当信息传输率RC时，只要编码长度n 足够大，总可以在长度为n的编码符号序列中找

32、到M(= 2nR)个许用码字和相应的译码规则，组成一个编码，使译码的错误概率PE任意小。逆定理：离散无记忆信道X, P(y|x), Y，P(y|x)为信道传输概率，其信道容量为C。当信息传输率R C时，无论码长n多大，也不可能找到一种编码，使译码错误概率任意小。,信道编码定理及其逆定理，合起来就是香农第二定理。 它指出在有噪声干扰信道中高效率高可靠地传输信息是可能的，可靠指错误概率可任意小，高效指传信率可无限接近信道容量。约束条件是传信率不大于信道容量。其办法是使用有足够多冗余进行信道编码。 香农第二定理仅指这种编码是存在的，并未给出实现这种编码的途径。,小结： 译码规则 译码错误概率的定义与

33、计算 制定译码规则的准则 最大后验概率准则-有最小平的均错误概率 最大似然准则-近等概信源的近似准则Shannon信道编码定理,课后复习题 思考题： 为什么用译码错误概率评判信道编码效果更科学？ 作业题： 教材第114页习题三第9、13题；,第三章 信道编码 3.3 线性分组码,本节的主要内容,线性分组码的基本概念 编码方法 校验原理 纠正多位错的方法 纠错能力的讨论,外语关键词： 线性分组码： linear block codes 生成矩阵： generator matrix 一致监督矩阵： parity-check matrix 校验原理： parity-check theorem 伴随子

34、向量： syndrome vector 错误格式向量： error pattern vector 纠错能力不等式： error correcting capability inequality,温旧引新,汉明距离：两码字不同码元的个数最小汉明距离=码字最小重量检纠错位数与最小汉明距离的关系： d0 e + t + 1 (te)冗余对检纠错的作用。编码效率： =k /n (r=n-k为冗余）,3.3.1 基本概念 信道编码从结构上也有块码和流码之分。 块码（分组码）: 将被编信息分组，每组信息分别各自建立与码字之间的对应关系，这种编码方式叫分组码。上节介绍过的奇偶校验码和多连重复码都属于分组码。

35、 流码（序列流编码）： 直接建立输入序列与检、纠错编码序列之间的对应关系。如，以后要讲的卷积码。,今天介绍的线性分组码，首先是分组：,信息序列按相同长度分组，k 位信息为一组，符号次序不变，每组后面添加 r 位冗余（称为监督位），合成来构成一个码长为 n=k+r 的码字。,我们把码长为n、信息位为k 的分组码记作 (n, k)码；如(7,3) 码 C = (c6c5c4c3c2c1c0 )， 其中: c6c5c4为信息位， c3c2c1c0为监督位。,“线性”指r 个监督元是由k 个信息元按一定的线性组合方式构成。比如(7,3)码的监督位c3c2c1c0与信息位c6c5c4之间满足线性方程：,

36、还要求是线性：,信息按三位分组：k = 3, 共有23 = 8个不同的组合方式，只要构造出8个许用码字，所有分组的编码就都有了。由上述方程构成的8个许用码字见右表所示。,例如，信息位是011，即c6=0, c5=1, c4=1根据方程， c3=c6c4 =1 ， c2=c6 c5 c4 =0 ， c1=c6c5 =1 ， c0=c5c4 =0 ，监督位是1010所以编码是011 1010,思考：选择什么样的方案（线性方程）才是好方案？我们希望的许用码字应是什么样的？答案：是最小汉明距离最大的那种编码。,长度为7的二进码共有 27 = 128个（7，3）许用码字只有 23 = 8个设计不同的线性

37、方程，就等于128个七位码集合中选择不同的8许用码字子集。,3.3.2 编码方法,由信息位生成监督位，再合起来构成一个码字的过程，其实可以一步进行，直接由信息位生成相应码字：,习惯上，码字写为行矢量： C = (c6c5c4c3c2c1c0 )，信息组亦可表示为行矢量: K = (c6c5c4)=(k2k1k0)；矩阵方程两边取转置，即得生成方程： C = KG 其中： G = = Ik Q,叫做生成矩阵，是k行n列的矩阵，左半边是kk单位方阵Ik,它的右半边是kr 矩阵Q。,还可以看到生成矩阵的三行正好是三个许用码字： C5=(100 1110) C3=(010 0111) C2=(001

38、1101)因此C = KG 可以写成：,即： C=k2C5+k1C3+k0C2表明“线性码”等价的定义是任意一个许用码字都能由其它许用码字的线性组合得到。,k2 c6k1 c5k0 c4 c3= c6 c4 c2 = c6 c5 c4 c1 = c6 c5 c0 = c5 c4 生成(7,3)码的逻辑电路,3.3.3 校验原理把输入的信息变成相应许用码字的过程叫编码，编码的核心是生成矩阵。 从收到的代码中恢复出原来信息的过程叫译码，译码的关键是一致校验矩阵。 1.一致校验矩阵： 将生成方程写成以下形式：,再写成矩阵形式：,H 叫一致校验矩阵。它的左半边是rk矩阵P，它的右半边是rr单位方阵Ir

39、 , P与生成矩阵中的Q互为转置关系：P=QT 或 Q=PT,监督方程可表为： HC T = 0 或 CHT = 0；,令：H = =P Ir,例1 码长为4的偶校验码是线性分组码吗？若是，写出生成矩阵和一致监督矩阵。解：设 C=(c3 ,c2 , c1 ,c0 )； n=4, k=3, r=1 则 c3 ,c2 , c1 为信息位， c0为监督位(是分组) 监督关系为： c0=c3 c2 c1 (是线性) 所以它是（4,3）线性分组码。 生成矩阵为：,一致校验矩阵： H =P Ir=（111 1）,例2 证明五连重复码是(5,1)线性分组码。并写出生成矩阵、一致校验矩阵。 解：五连重复码只有

40、2个许用码字：00000 和 11111 视首位为信息，后4位为监督，即k=1, r =4, n=5； 监督位c3 ,c2 , c1 , c0与信息位c4之间有线性关系： c3 = c4 ； c2 = c4 ； c1 = c4 ； c0 = c4 连同c4 = c4 五个方程写成矩阵形式：,转置得到生成矩阵：G=(1 1111)，由G写出一致监督矩阵是：,用的较多的是它的转置矩阵：,2.错误格式矢量：为了表述误码错误所在的位置，我们构造n维错误格式矢量: E=(en-1en-2e1e0)；如n =7时，若c2位有错，则写E=(0000100)；若c0 和c4两位错，则写 E = (001000

41、1)；设：发送入信道的码字为C = (c6c5c4c3c2c1c0)， 接收端收到的码字为R = (r6 r5 r4 r3 r2 r1 r0 ) ；不难知道三者的关系是： E = CR； R =CE； C =RE；,3.伴随子向量：定义伴随子向量： S = RHT每收到一个码字R，都可由一致校验矩阵H计算出对应的伴随子向量S。（1）若无错，R=C，则 S = RHT = CHT = 0（2）若有错，RC，则 S= RHT 0 由伴随子向量S是否为零就能检错。（3） S= RHT = (CE) HT = CHTEHT = EHT； 即：S= EHT 由伴随子S算出E，就能由C =RE 来纠错。,

42、如何由S = EHT来计算E? 左边的S是1行r列的行矢量，可由S= RHT得到。 右边的EHT实际上等于HT中与E矢量内1相乘的 那些行模2 加起来的结果。 在E未知的情况下，求解方程S = EHT实际上就 是要寻找HT中哪几行加起来能够与S相同，那么 与这些行相乘的E矢量元素就是1。 下面分两种情况来具体讨论。,3.3.4 纠错译码： (1)只有一位错的情况当接收代码R只有一位(第i位)错时，E中只有第 i 位为1，其它均为0，EHT的乘积，就是HT矩阵中第 i 行元素构成的行矢量。现在既然S=RHT已经算出，只要把伴随子S与HT比较，看S与HT的哪一行相同，就表明E中哪一位为1，错就在在

43、哪一位。,不难求出 S = RHT = (0001)0， 容易看到，(0001)是HT矩阵的第7行 即知错误格式矢量为： E =(0000001)； 纠错后为：C = RE = (1101001)；,如(7,3)线性分组码，已知： R = (1101000)；HT=,例3已知（7，4）线性分组码的生成矩阵：,（思考：它的码长几位？信息几位？） 1.求它的所有许用码字。2.求它的一致监督矩阵。3.若收到码字为(1011010)，请译码。,(2)一致校验矩阵：,(3)伴随子向量：,E=(0000010); C=RE=(1011000),S=RHT=,纠正多位错时，E中有多位是1。由S = EHT来

44、计算E，需要从HT中凑出来哪几行相加等于S，才能知道E中哪几位是1。一般情况下，一个S可能对应多个E。但是可以证明，只要限定E中1的个数不超过纠错能力t，则S = EHT算出来的E仍然是唯一的。这是因为许用码字的最小码距为2t +1，当含有t 个1的格式向量E与所有许用码字C模二加，得到的所有误码R之间，必定至少还有一位不同，因此在 t 位误码范围内发生的误码R都有不同的错误格式E相对应的。,(2)多位错的情况,五连重复码,即(5,1) 码，是能纠正两位错的线性分组码，例2中已求出它的一致监督矩阵是：,若收到一个码字是R=(01010) 先计算伴随子S=RHT=(1010) 显然S等于HT的第

45、2行与第4行的模2加（虽然也等于1、3、5行相加，但限制不超过两位），因此： E=(01010) ； C= ER=(00000),查表法进行纠错译码：,当纠错位数较多，一致监督矩阵较大时，凑出来哪几行相加等于S 也不容易。常用的方法是查表法进行纠错译码。,预先对每一个许用码字Ci写出它在纠错能力之内的各种可能的接收码字Rj(Ci)，按无错、一位错、二位错、t 位错的次序排序，罗列在Ci下面，编制出一个R-C对照表。从接收码直接查表得到纠错译码。,（5,1)码的译码表如下：,当收到R=(01010)时，查表即知它应译为C=(00000)(5,1)码是能纠正两位错误的完备码。纠错能力以内的误码共3

46、0个，它们是一位错10个，二位错20 个，加上2个正确码字，正好取遍了全部五位码：25=32个。他们都已被列如译码表中。如果下面再罗列三位以上的误码，也只能出现重复的东西。按照译码规则，应当按照较少错位的情况来译码。他们都会被译为(00000)3位的误码是无法纠正的，它已超出纠错能力。 所以只须把纠错能力 t 位的范围内的误码列入表即可。,查表法的实质:由接收码求错误格式很困难，但是由错误格式写接收码却很容易。查表法就是采用后者，把每个许用码的可以纠正的误码都列出来供译码使用。可见，这个对照表实际上就是译码规则。表面上看似乎没有使用前面所讲的确定译码规则的方法，但是按出错位数多少的顺序列表，就

47、是按汉明距离的大小来列表，进一步说，也就是按传输概率的大小进行了选择。,（4）译码过程的电路实现,以（7, 4）码为例。它的一致监督矩阵为：,设接收码字R=(r6r5r4r3r2r1r0) 则伴随子S = RHT为一行三列的向量 S =(s2s1s0)；,其中 s2=r6r5r4r2； s1=r5r4r3r1； s0=r6r5r3r0；,r6 r5 r4 r3 r2 r1 r0 s2 s1 s0 e6 e5 e4 e3 e2 e1 e0 r6 r5 r4 r3 r2 r1 r0 c6 c5 c4 c3 c2 c1 c0 (7,4)码的译码电路原理图,上面部分是计算伴随子S =（s2s1s0）的

48、逻辑电路；中间七个与门电路构成计算错误格式：E=(e6e5e4e3e2e1e0)的电路， 当S与H的第一列相同时，即(s2s1s0)=101时， E= (1000000)，故有e6= s2s1s0； 同理可知： e5= s2s1s0 e4= s2s1s0； e3= s2s1s0； e2= s2s1s0 e1= s2s1s0； e0= s2s1s0； 下面的七个模二加构成纠错电路，E与R逐位模二加，哪位错了便将哪位改回来。,3.3.5 纠错能力的讨论,1. 最小码距与监督位数的关系 ： d0r+1 证明：设 C0为重量最小的非零码字，它的重量为d0,因为C0中的非零码元是d0个，C0H T相乘实

49、际上就是HT中对应于C0非零码元的那几行的逐位模二加，而这样的行数是d0个。 监督方程要求C0H T=0，意味着 HT 中d0行相加的结果等于零，因此H T中线性无关的行最多不超过(d0-1)个。,H T是n行r列的矩阵，因为n r， H T的秩至多为r，可见， (d0-1)r，即 d0 r +1 又由 2t+1d0 ，可推知：t r /2,2. 纠错位数不等式,HT是n行r 列的矩阵，所以S = RHT是一行r列的向量，每位只能取0或1，它共有2r个不同的取值，扣除了S=0的一个无错状态，用它来区分不同的错误格式，最多不超过2r -1个。,为了能用伴随子S区分t位以内的所有错误格式， 应当有

50、： 2r 1 Cn1 + Cn2 + Cnt 此即纠错能力不等式：2rCn0 +Cn1 + Cn2 + Cnt,另一方面，码长为n 的码字，发生一位错码的方式有 种，同时发生二位错的方式有 种, 发生t位 错的方式有 种。,下面以n =7的线性分组码为例进行讨论：(7,6)码： k=6， r=1，2r = 2 C70=1， t =0(7,5)码： k=5， r=2 ，2r = 4 C70=1， t =0(7,4)码： k=4， r=3, 2r =8 =C70 +C71 =1+7 = 8， t =1(7,3)码： k=3， r=4, 2r=16 C70+C71 =1+7=8， t =1(7,2)