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

1、1校验码（1）码距码距就是两个码字 C1 与 C2 之间不同的比特数。如： 1100 与 1010 的码距为 2; 1111 与 0000 的码距为 4 。一个编码系统的码距就是整个编码系统中任意（ 所有 ）两个码字的最小距离。若一个编码系统有四种编码分别为： 0000 ， 0011 ， 1100 ， 1111 ，此编码系统中 0000 与 1111 的码距为 4;0000 与 0011 的码距为 2，是此编码系统的最小码距。因此该编码 系统的码距为 2 。（2） 8421 码BCD 码也叫 8421 码就是将十进制的数以 8421 的形式展开成二进制，大家知道十进制是 09十个数组成，着十个

2、数每个数都有自己的8421码：0 = 00001 = 00012 = 00103 = 00114 = 01005 = 01016 = 01107 = 01118 = 10009 = 1001举个例子：321 的 8421 码就是3 2 10011 0010 0001之所以叫8421 码，是因为四位 8421 码时 ,从左到右每个"1"代表的十进制数分别是"8"II"2" 、 "1"如下："1000"为十进制"8""0100"为十进制"4"

3、;"0010"为十进制"2""0001"为十进制"1"5421 码与此相同，每位一代表的是十进制的"5"、"4"、"2"、"1"即:"1000"为十进制"5""0100"为十进制"4""0010"为十进制"2""0001"为十进制"1"3）什么是检错与纠错有很多网友和学员不明白，

4、为什么有些编码能检查出错误，而不能纠正错误? 下面来举一个生活当中简单的例子来说明这一点。若希赛公司发出一个通知： “明天 14: 0016:00 开会 ”，但在通知过程中由于行政部工作人员疏忽，变成了 “明天 10:0016: 00 开会 ”。员工收到这个错误通知后由于无法判断其正确与否，就会按这个错误时间 去安排与组织。为了使接收者能判断正误，可以在通知内容中增加 “下午 ”两个字，即改为： “明天 下午 14:0016:00 开会 ”。这时，如果仍错为： “明天下午 10:0016:00 开会，则收到 此通知后，根据 “下午 ”与 “10:00 ”信息即可判断出通知发生了错误。但仍不能纠

5、正其错 误，因为无法判断是“下午 ”与 “10:00 ”哪一信息出错，即无法判断公司原来制定开会的具体时间。这时，接收者可以告诉发送方再发一次通知（ 员工向行政部人员询问，行政部再次确认会议时间），这就是检错重发 （ 这也就是我们所说的能检错， 但无法纠错 ）。为了实现不但能判断通知准确性（检错 ），同时还能正确判断会议开始的具体时间（纠错 ） ，行政部可以把通知内容再增加“两个小时 ”四个字，即改为： “明天下午 14:0016:00 开会两个小时 ”。这样，如果其中 “14:00错”为 “ 10:00 ，”不但能判断出错误，同 时还能纠正错误，因为其中增加的 “两个小时 ”这个标识可以判断

6、出正确的时间为“14:0016:00 ”。当然，这显然也增加了信息的冗余，降低了数据处理的效率。但随着带 宽的不断提高， 数据执行与处理的能力日益增强， 可靠性与效率的均衡， 这是值得的。 （ 4 ）码距和检错纠错有何关联 首先大家要了解以下两个概念：1. 在一个码组内为了检测e 个误码，要求最小码距应该满足： d>=e+12. 在一个码组内为了纠正t 个误码，要求最小码距应该满足：d>=2t+1现在举个例子来说明这个问题：假如我们现在要对 A， B 两个字母进行编码。我们可以选用不同长度的编码，以 产生不同码距的编码，分析它们的检错纠错能力。l 若用 1 位长度的二进制编码。若

7、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

8、），如果发生一位错码，必将变成 01 或 1 0 ，这都禁用码组 （非法码 ），故接收端可以 判断为误码，却不能纠正其错误。因为无法判断误码（01 或10）是 A（00） 错误还是 B（11）错误造成，即无法判断原信息是A或B,或说A与B形成误码（01或10）的可能性（概率）是相同的。如果产生二位错码，即00 错为 11 ，或 11 错为 00 ，结果将从一个合法编变成另一个合法编码，接收端就无法判断其是否有错。所以此种编码的检错能力为1位，纠错能力为0位。I若用3位长度的二进制编码，可选用111，000作为合法编码。A，B之间的最小码距为 3。合法码：111,000 ;非法码：001,010

9、,011,100,101,110;根据上面的规则可知此编码的检错位数为2位，纠错位数为1位。例如：当信息A(000)产生1位错误时，将有3种误码形式，即001或010或100，这些都是禁用码组，可确定是误码。而有这3个误码与合法编码000的距离最近，与合编码111的距离较远，根据误码少的概率大于误码多的概率的规律，可以判定原来的正确码组为000 ,只要把误码中的1改为0即可得到纠正。同理，如果信息B(111)产生1位错误时，则有另三种误码可能产生，即110 , 101 , 011，根据同样道理可以判定原来的正确码组是111，并能纠正错误。但是，如果信息A(000)或信息B(111)产生两位错误

10、时，虽然能根据禁用码组识别其错误，但纠错时去会做出错误的纠正而造成误纠错”。如果信息 A(000)或信息B(111)产生三位错误时，将从一个合法编码A(或B)变成了另一个合法编码B(或A)，这时既检不出错，更不会纠错了，因为误码已成为合法编码，译码后必然产生错误。所以检错位数为2位，纠错位数为1位。四、小结编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。概括了最小距离为 1至7的码的纠错和检错能力。码距4码的能力检措存D疳0心%1P4丰» 1且中2夕亘J-1且可j0 11且Q!3心增大编码信息的码距的一个基本缺点是，在任何给定的系统中，都会因而降低数据传输效率。显然

11、， 这是由于增加的码位(为增大最小距离所需的)减小了有用的信息时间。这就给每个信息增加了所谓多余度。所以，选择最小距离要取决于特定系统的参数。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素，这里不再介绍，大家也可以在辅导平台中与我进一步来讨论这些问题。(5)奇偶校验奇偶校验码是一种通过增加冗余位使得码字中"1"的个数恒为奇数或偶数的编码方法，它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。1.垂直奇偶校验垂直奇偶校验又称为纵向奇偶校验，它是将要发送的整个信息块分为定长p位的若干段（比如说q段），每段后面按&

12、quot;1"的个数为奇数或偶数的规律加上一位奇偶位，如图2.19所示。问位信息（111,121,lpl,l12,，中q每p位构成一段（即图中的一列），共有q段（即共有q列。 每段加上一位奇偶校验冗余位，即图中的rio编码规则为奇楼驰:严切+咕+“+ +1注意:此间的"+"指的是模二加，也即异或运算。图中箭头给出了串行发送的顺序 ，即逐位先后次序为111,121,Ip1,r1,I12,Ipa,r2,儿,1间,rq。在编码和校验过程中，用硬件方法或软件方法很容易实现上述连续半加运算，而且可以边发送边产生冗余位；同样,在接收端也可边接收边进行校验后去掉校验位。垂直奇偶

13、校验方法的编码效率为 R=p/（p+1）。通常,取一个字符的代码为一个信息段，这种 垂直奇偶校验有时也称为字符奇偶校验。例如，在8位字符代码（即用8位二进制数位表示一一个字符）中,p=8，编码效率便为8/9。垂直奇偶校验方法能检测出每列中的所有奇数位错，但检测不出偶数位的错。对于突发错误来说，奇数位错与偶数位错的发生概率接近于相等，因而对差错的漏检率接近于1/20。2.水平奇偶校验为了降低对突发错误的漏检率，可以采用水平奇偶校验方法。水平奇偶校验又称为横向奇 偶校验，它是对各个信息段的相应位横向进行编码，产生一个奇偶校验冗余位，如图2.20所示,编码规则为Wt脸冷址+计“+垢(ii跆©

14、;*ttt:r=Itt+I;+-+I +1 (匸 IQ'"”若每个信息段就是一个字符的话，这里的q就是发送的信息块中的字符数。水平奇偶校验的编码效率为R=q/(q+1)。水平奇偶校验不但可以检测出各段同一位上的奇数位错，而且还能检测出突发长度 <p的所有突发错误。因为按发送顺序从图2.20可见，突发长度p的突发错误必然分布在不同的行中，且每行一位，所以可以检出差错，它的漏检率要比垂直奇偶校验方法低。但是实现水平奇偶校验时，不论采用硬件方法还是软件方法，都不能在发送过程中边产生奇偶校验冗余位边插入发送，而必须等待要发送的全部信息块到齐后，才能计算冗余位，也就是一定要使用数据缓冲器，因此它的编码和检测实现起来都要复杂一些。冗余位3. 水平垂直奇偶校验，也称为纵横奇偶校实验同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验 如图2.21所示。若水平垂直都采用偶校验，则乍+L,严 Iy+l+'-'+I*射叶人讨決却对"+!>+*rLl+rZi+