《软件设计师读书笔记》由会员分享,可在线阅读,更多相关《软件设计师读书笔记(6页珍藏版)》请在金锄头文库上搜索。
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 十个数组成,着十个数每个数都有自己的8421
2、 码: 00000 10001 20010 30011 40100 50101 60110 70111 81000 91001 举个例子: 321 的 8421 码就是 3 2 1 0011 0010 0001之所以叫 8421 码,是因为四位 8421 码时,从左到右每个“1“代表的十进制数分别是“8“、“4“、“2“、“1“如下:“1000“ 为十进制 “8“0100“ 为十进制 “4“0010“ 为十进制 “2“0001“ 为十进制 “1“5421 码与此相同,每位一代表的是十进制的“5“、“4“、“2“、“1“即:“1000“ 为十进制 “5“0100“ 为十进制 “4“0010“ 为
3、十进制 “2“0001“ 为十进制 “1“(3)什么是检错与纠错有很多网友和学员不明白,为什么有些编码能检查出错误,而不能纠正错误?下面来举一个生活当中简单的例子来说明这一点。若希赛公司发出一个通知:“明天 14:0016:00 开会”,但在通知过程中由于行政部工作人员疏忽,变成了“明天 10:0016:00 开会”。员工收到这个错误通知后由于无法判断其正确与否,就会按这个错误时间去安排与组织。为了使接收者能判断正误,可以在通知内容中增加“下午”两个字,即改为: “明天下午 14:0016:00 开会”。这时,如果仍错为: “明天下午 10:0016:00 开会,则收到此通知后,根据 “下午”
4、与“10:00”信息即可判断出通知发生了错误。但仍不能纠正其错误,因为无法判断是 “下午”与“10:00”哪一信息出错,即无法判断公司原来制定开会的具体时间。这时,接收者可以告诉发送方再发一次通知(员工向行政部人员询问,行政部再次确认会议时间 ),这就是检错重发 (这也就是我们所说的能检错,但无法纠错)。为了实现不但能判断通知准确性 (检错),同时还能正确判断会议开始的具体时间(纠错),行政部可以把通知内容再增加 “两个小时”四个字,即改为: “明天下午 14:0016:00 开会两个小时 ”。这样,如果其中 “14:00”错为“10:00”,不但能判断出错误,同时还能纠正错误,因为其中增加的
5、 “两个小时”这个标识可以判断出正确的时间为 “14:0016:00”。当然,这显然也增加了信息的冗余,降低了数据处理的效率。但随着带宽的不断提高,数据执行与处理的能力日益增强,可靠性与效率的均衡,这是值得的。(4)码码距距和和检检错错纠纠错错有有何何关关联联首首先先大大家家要要了了解解以以下下两两个个概概念念:1.在一个码组内为了检测 e 个误码,要求最小码距应该满足: d=e+12.在一个码组内为了纠正 t 个误码,要求最小码距应该满足: d=2t+1现现在在举举个个例例子子来来说说明明这这个个问问题题:假如我们现在要对 A,B 两个字母进行编码。我们可以选用不同长度的编码,以产生不同码距
6、的编码,分析它们的检错纠错能力。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 位,无法纠
7、错。因为无论 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,000 作为合法编码。 A,B 之间的最小码距
8、为 3。合法码:111,000; 非法码:001,010,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,根据同样道理可以判
9、定原来的正确码组是 111,并能纠正错误。但是,如果信息 A(000)或信息 B(111)产生两位错误时,虽然能根据禁用码组识别其错误,但纠错时去会做出错误的纠正而造成“误纠错”。如果信息 A(000)或信息 B(111)产生三位错误时,将从 一个合法编码 A(或 B)变成了另一个合法编码 B(或 A),这时既检不出错,更不会纠错了,因为误码已成为合法编码,译码后必然产生错误。所以检错位数为2 位,纠错位数为 1 位。四四、小小结结编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。下表概括了最小距离为 1 至 7 的码的纠错和检错能力。增大编码信息的码距的一个基本缺点是,在任何
10、给定的系统中,都会因而降低数据传输效率。显然, 这是由于增加的码位 (为增大最小距离所需的 )减小了有用的信息时间。这就给每个信息增加了所谓多余度。所以,选择最小距离要取决于特定系统的参数。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素,这里不再介绍,大家也可以在辅导平台中与我进一步来讨论这些问题。(5)奇偶校验奇偶校验码是一种通过增加冗余位使得码字中“1“的个数恒为奇数或偶数的编码方法,它是一种检错码。在实际使用时又可分为垂直奇偶校验、水平奇偶校验和水平垂直奇偶校验等几种。 1.垂直奇偶校验垂直奇偶校验垂直奇偶校验又称为纵向奇偶校验,它是将要发送的整个信息块分为定
11、长 p 位的若干段(比如说 q 段),每段后面按“1“的个数为奇数或偶数的规律加上一位奇偶位,如图 2.19 所示。问位信息(I11,I21,Ipl,I12,Ipq)中,每 p 位构成一段(即图中的一列),共有 q 段(即共有 q 列。每段加上一位奇偶校验冗余位,即图中的 rio 编码规则为注意:此间的“+“指的是模二加,也即异或运算。图中箭头给出了串行发送的顺序,即逐位先后次序为 I11,I21,Ip1,r1,I12,Ipa,r2,儿,I 间,rq。在编码和校验过程中,用硬件方法或软件方法很容易实现上述连续半加运算,而且可以边发送边产生冗余位;同样,在接收端也可边接收边进行校验后去掉校验位。
12、垂直奇偶校验方法的编码效率为 R=p/(p+1)。通常,取一个字符的代码为一个信息段,这种垂直奇偶校验有时也称为字符奇偶校验。例如,在 8 位字符代码(即用 8 位二进制数位表示一个字符)中,p=8,编码效率便为 8/9。 垂直奇偶校验方法能检测出每列中的所有奇数位错,但检测不出偶数位的错。对于突发错误来说,奇数位错与偶数位错的发生概率接近于相等,因而对差错的漏检率接近于 1/20。 2.水平奇偶校验水平奇偶校验 为了降低对突发错误的漏检率,可以采用水平奇偶校验方法。水平奇偶校验又称为横向奇偶校验,它是对各个信息段的相应位横向进行编码,产生一个奇偶校验冗余位,如图 2.20 所示,编码规则为若
13、每个信息段就是一个字符的话,这里的 q 就是发送的信息块中的字符数。水平奇偶校验的编码效率为 R=q/(q+1)。水平奇偶校验不但可以检测出各段同一位上的奇数位错,而且还能检测出突发长度p 的所有突发错误。因为按发送顺序从图 2.20 可见,突发长度p 的突发错误必然分布在不同的行中,且每行一位,所以可以检出差错,它的漏检率要比垂直奇偶校验方法低。但是实现水平奇偶校验时,不论采用硬件方法还是软件方法,都不能在发送过程中边产生奇偶校验冗余位边插入发送,而必须等待要发送的全部信息块到齐后,才能计算冗余位,也就是一定.要使用数据缓冲器,因此它的编码和检测实现起来都要复杂一些。 3.水平垂直奇偶校验水平垂直奇偶校验同时进行水平奇偶校验和垂直奇偶校验就构成水平垂直奇偶校验,也称为纵横奇偶校实验,如图 2.21 所示。若水平垂直都采用偶校验,则水平垂直奇偶校验的编码效率为 R=pq/(p+1)(q+1)。. 水平垂直奇偶校验能检测出所有 3 位或 3 位以下的错误(因为此时至少在某一行或某一列上有一位错)、奇数位错、突发长度=p+1 的突发错以及很大一部分偶数位错。测量表.明,这种方式的编码可使误码率降至原误码率的百分之一到万分之一。 水平垂直奇偶校验不仅可检错,还可用来纠正部分差错。例如数据块中仅存在 1 位错时,便能确定错码的位置就在某行和某列的交叉处,从而可以纠正它. (6)