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

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 的形式展开成二进制，大家知道 十进制是 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 码， 是因为四位 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“ （3）什么是检错与纠错 有很多网友和学员不明白，为什么有些编码能检查出错误，而不能纠正错误?下 面来举一个生活当中简单的例子来说明这一点。若希赛公司发出一个通知：“明天 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” 。当然，这显然也增加了信息的冗余，降低了数据处理的效率。但随着带 宽的不断提高， 数据执行与处理的能力日益增强， 可靠性与效率的均衡， 这是值得的。 （4）码距和检错纠错有何关联码距和检错纠错有何关联 首先大家要了解以下两个概念：首先大家要了解以下两个概念： 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(0 0)，如果发生一位错码，必将变成01 或 10，这都禁用码组 (非法码 )，故接收端可以 判断为误码，却不能纠正其错误。因为无法判断误码(01 或 10)是 A(00)错误还是 B(1 1)错误造成，即无法判断原信息是A 或 B， 或说 A 与 B 形成误码 (01 或 10)的可能性 (概 率)是相同的。如果产生二位错码，即00 错为 11，或 11 错为 00，结果将从一个合 法编变成另一个合法编码，接收端就无法判断其是否有错。所以此种编码的检错能力 为 1 位，纠错能力为 0 位。 l 若用 3 位长度的二进制编码，可选用111，000 作为合法编码。 A，B 之间的最 小码距为 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，根据同样道理可以判定原来 的正确码组是 111，并能纠正错误。 但是，如果信息A(000) 或信息 B(111) 产生两位错误时，虽然能根据禁用码组识 别其错误，但纠错时去会做出错误的纠正而造成“误纠错 ”。 如果信息 A(000) 或信息 B(111) 产生三位错误时， 将从一个合法编码A(或 B)变成 了另一个合法编码B(或 A)，这时既检不出错，更不会纠错了，因为误码已成为合法 编码，译码后必然产生错误。所以检错位数为2 位，纠错位数为 1 位。 四、小结四、小结 编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。下表 概括了最小距离为1 至 7 的码的纠错和检错能力。 增大编码信息的码距的一个基本缺点是，在任何给定的系统中，都会因而降低数 据传输效率。显然， 这是由于增加的码位 (为增大最小距离所需的 )减小了有用的信息 时间。这就给每个信息增加了所谓多余度。所以，选择最小距离要取决于特定系统的 参数。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率 等因素，这里不再介绍，大家也可以在辅导平台中与我进一步来讨论这些问题。 （5）奇偶校验