软件设计师读书笔记(精华版).doc

1．校验码 （1）码距 码距就是两个码字C1与C2之间不同的比特数。如：1100与1010的码距为2;1111与0000的码距为4。 　　一个编码系统的码距就是整个编码系统中任意(所有)两个码字的最小距离。若一个编码系统有四种编码分别为：0000，0011，1100，1111，此编码系统中0000与1111的码距为4;0000与0011的码距为2，是此编码系统的最小码距。因此该编码系统的码距为2。码也叫8421码就是将十进制的数以8421的形式展开成二进制，大家知道十进制是0～9十个数组成，着十个数每个数都有自己的8421码： 　　0＝0000 　　1＝0001 　　2＝0010 　　3＝0011 　　4＝0100 　　5＝0101 　　6＝0110 　　7＝0111 　　8＝1000 　　9＝1001 　　举个例子： 　　321的8421码就是 　　3 2 1 0011 0010 0001是因为四位8421码时,从左到右每个1代表的十进制数分别是8、4、2、1 如下： 1000 为十进制 8 0100 为十进制 4 0010 为十进制 2 0001 为十进制 1 5421码与此相同，每位一代表的是十进制的5、4、2、1 即: 1000 为十进制 5 0100 为十进制 4 0010 为十进制 2 0001 为十进制 1有很多网友和学员不明白，为什么有些编码能检查出错误，而不能纠正错误?下面来举一个生活当中简单的例子来说明这一点。若希赛公司发出一个通知：“明天14:00~16:00开会”，但在通知过程中由于行政部工作人员疏忽，变成了“明天10:00~16:00开会”。员工收到这个错误通知后由于无法判断其正确与否，就会按这个错误时间去安排与组织。 　　为了使接收者能判断正误，可以在通知内容中增加“下午”两个字，即改为：“明天下午14:00~16:00开会”。这时，如果仍错为：“明天下午10:00~16:00开会，则收到此通知后，根据“下午”与“10:00”信息即可判断出通知发生了错误。但仍不能纠正其错误，因为无法判断是“下午”与“10:00”哪一信息出错，即无法判断公司原来制定开会的具体时间。这时，接收者可以告诉发送方再发一次通知(员工向行政部人员询问，行政部再次确认会议时间)，这就是检错重发(这也就是我们所说的能检错，但无法纠错)。 　　为了实现不但能判断通知准确性(检错)，同时还能正确判断会议开始的具体时间(纠错)，行政部可以把通知内容再增加“两个小时”四个字，即改为：“明天下午14:00~16:00开会两个小时”。这样，如果其中“14:00”错为“10:00”，不但能判断出错误，同时还能纠正错误，因为其中增加的“两个小时”这个标识可以判断出正确的时间为“14:00~16:00”。当然，这显然也增加了信息的冗余，降低了数据处理的效率。但随着带宽的不断提高，数据执行与处理的能力日益增强，可靠性与效率的均衡，这是值得的。 码距和检错纠错有何关联首先大家要了解以下两个概念： 　　1.在一个码组内为了检测e个误码，要求最小码距应该满足： d=e+1 　　2.在一个码组内为了纠正t个误码，要求最小码距应该满足： d=2t+1 　　现在举个例子来说明这个问题： 　　假如我们现在要对A，B两个字母进行编码。我们可以选用不同长度的编码，以产生不同码距的编码，分析它们的检错纠错能力。 　　l 若用1位长度的二进制编码。若A=1，B=0。这样A，B之间的最小码距为1。 　　合法码：{0,1｝;　　　　　 非法码：{0,1｝; 　　根据上面的规则可知此编码的检错纠错能力均为0，即无检错纠错能力。其实道理很简单，这种编码无论由1错为0，或由0错为1，接收端都无法判断是否有错，因为1，0都是合法的编码。 　　l 若用2位长度的二进制编码，可选用11，00作为合法编码，也可以选用01，10作为合法编码。若以A=11，B=00为例，A、B之间的最小码距为2。 　　合法码：{11,00｝;　　　　　非法码：{01,10｝; 　　根据上面的规则可知此编码的检错位数为1位，无法纠错。因为无论A(11)或B(00)，如果发生一位错码，必将变成01或10，这都禁用码组(非法码)，故接收端可以判断为误码，却不能纠正其错误。因为无法判断误码(01或10)是A(00)错误还是B(11)错误造成，即无法判断原信息是A或B，或说A与B形成误码(01或10)的可能性(概率)是相同的。如果产生二位错码，即00错为11，或11错为00，结果将从一个合法编变成另一个合法编码，接收端就无法判断其是否有错。所以此种编码的检错能力为1位，纠错能力为0位。 　　l 若用3位长度的二进制编码，可选用111，