1.5.1 考点精讲

可靠性计算在软件设计师考试中出现频度较高，出题方式也较为单一，主要是计算，是一个很好得分的知识点，另外一个知识点是校验码，出现频度较低，需要了解概念及计算过程，本节将详细介绍这部分内容。

1．可靠性计算

可靠性计算主要涉及 3 种系统，即串联系统、并联系统和冗余系统，其中串联系统和并联系统的可靠性计算都非常简单，只要了解其概念，公式很容易记住。冗余系统要复杂一些，有些学员常常搞不清楚。

（1）串联系统

假设一个系统由 n 个子系统组成，当且仅当所有的子系统都能正常工作时，系统才能正常工作，这种系统称为串联系统，如图 1-8 所示。

设系统各个子系统的可靠性分别用 R ₁ , R ₂ , ', R _n 表示，则系统的可靠性 R = R ₁ × R ₂ ×' × R _n 。

如果系统的各个子系统的失效率分别用 λ ₁ , λ ₂ , ', λ _n 来表示，则系统的失效率 λ = λ ₁ + λ ₂ +'+ λ _n 。

（2）并联系统

假如一个系统由 n 个子系统组成，只要有一个子系统能够正常工作，系统就能正常工作，如图 1-9 所示。

设系统各个子系统的可靠性分别用 R ₁ , R ₂ , ', R _n 表示，则系统的可靠性 R =1 −( 1 − R ₁ )×(1− R ₂ )× '×( 1− R _n )。

假如所有子系统的失效率均为 λ ，则系统的失效率为：

在并联系统中只有一个子系统是真正需要的，其余 n −1 个子系统都被称为冗余子系统。该系统随着冗余子系统数量的增加，其平均无故障时间也会增加。

（3）模冗余系统

m 模冗余系统由 m 个（ m =2 n +1 为奇数）相同的子系统和一个表决器组成，经过表决器表决后， m 个子系统中占多数相同结果的输出可作为系统的输出，如图 1-10 所示。

在 m 个子系统中，只有 n +1 个或 n +1 个以上的子系统能正常工作，系统就能正常工作并输出正确结果。假设表决器是完全可靠的，每个子系统的可靠性为 R ₀ ，则 m 模冗余系统的可靠性为：

2．校验码

为了实现数据的自动检错与纠错，引入了校验码。而最简单的就是奇偶校验码，它分为奇校验和偶校验两种，均是添加 1 位校验位，根据信息码中 1 的个数来决定校验位的取值，使得填入校验位后，1 的个数为奇数（奇校验）或偶数（偶校验）。这方面知识更深入的考查点主要包括以下几个方面。

（1）海明码距

海明的冗余数据位检测和纠正代码差错的理论和方法指出：可以在数据代码上添加若干冗余位组成码字。而将一个码字变成另一个码字时必须改变的最小位数就是码字之间的海明距离，简称码距。从这里将得出：没有加冗余校验码的任何编码，它们的码距就是 1，即只要改一位就可以变成另一个码字；而奇偶校验码则添加了 1 位校验码，使得要变成另一个码字最少要修改两位，这就使其码距变成 2 了。根据定义得知，码距是不同码字的海明距离的最小值。判断码距时，可以列出一些码进行判断，找出最小的位数即可。

另外，还需要记住以下几个关键的关系。

●　可查出多少位错误：根据海明的研究发现，可以发现“ - 码距−1”位的错误。

●　可以纠正多少位错误：根据海明的研究发现，可以纠正“<码距/2”位的错误，因此如果要能够纠正 n 位错误，则所需最小的码距应该是“2 n +1”。

（2）海明校验码

要计算海明校验码，首先要知道海明校验码是放置在 2 的幂次位上的，即“1、2、4、8、16、32……”，而对于信息位为 m 的原始数据，需加入 k 位的校验码，它满足 m + k +1<2 ^k 。计算时总令人感到头痛。而有一种简单的方法，则是从第 1 位开始写，遇到校验位留下空格。例如，原始信息为 101101100，采用偶校验则如图 1-11 所示。

然后根据以下公式填充校验位“1、2、4、8”：

Bit 1=B3 ⊕ B5 ⊕ B7 ⊕ B9 ⊕ B11 ⊕ B13 = 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 =1

Bit 2=B3 ⊕ B6 ⊕ B7 ⊕ B10 ⊕ B11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 =1

Bit 4=B5 ⊕ B6 ⊕ B7 ⊕ B12 ⊕ B13 = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 =0

Bit 8=B9 ⊕ B10 ⊕ B11 ⊕ B12 ⊕ B13 = 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0=0

（注：⊕指的是异或运算，B n 代表位数）

然后将结果填入，得到如图 1-12 所示的完成计算。

而如果给出一个加入了校验码的信息，并说明有一位错误要找出，则可以采用基本相同的方法，假如给出的是如图 1-13 所示的信息。

可根据以下公式计算：

Bit 1=B1 ⊕ B3 ⊕ B5 ⊕ B7 ⊕ B9 ⊕ B11 ⊕ B13 = 1⊕ 1 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0 =1

Bit 2=B2 ⊕ B3 ⊕ B6 ⊕ B7 ⊕ B10 ⊕ B11 = 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 1 ⊕ 0 =1

Bit 4=B4 ⊕ B5 ⊕ B6 ⊕ B7 ⊕ B12 ⊕ B13 = 0 ⊕ 0 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 =0

Bit 8=B8⊕ B9 ⊕ B10 ⊕ B11 ⊕ B12 ⊕ B13 =0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 0=1

然后从高位往下写，得到 1101，即十进制的 11，因此出错的位数为第 11 位。而剩下的问题就是这个公式如何来的？首先计算校验码时，1、2、4、8 位都是空的，因此在公式的左边；当进行校验时，1、2、4、8 位都已经有值，因此要参与计算。而这些值是根据右表得到的，也就是生成B1、B2、B4、B8 这 4 个公式，而公式中要参与计算的位，是在表格中出现“1”的那个位。要说明的是，右边的表格，就是对数据位的二进制描述。

由于海明码距在计算和纠错过程中，计算都过于复杂，无法很容易使用硬件实现，因此在实际中并不是应用得很广泛。

（3）CRC校验码

由于CRC的实现原理十分易于用硬件实现，因此被广泛地应用于计算机网络上的差错控制。而CRC的考查点主要有两个：计算CRC校验码，验算一个加了CRC校验的码是否有错误。

●计算CRC校验码

要计算CRC校验码，需根据CRC生成多项式进行。例如，原始报文为“11001010101”，其生成多项式为“ x ⁴ + x ³ + x +1”。在计算时，是在原始报文的后面加若干个0（等于校验码的位数，而生成多项式的最高幂次就是校验位的位数，即使用该生成多项式产生的校验码为4位）作为被除数，除以生成多项式所对应的二进制数（根据其幂次的值决定，得到11011，因为生成多项式中除了没有 x ² 之外，其他位都有），然后使用模2除，得到的商就是校验码，如图1-14所示。

然后将 0011 添加到原始报文的后面就是结果：11001010101 0011 。

●检查信息码是否有CRC错误

要想检查信息码是否出现了CRC错误的计算很简单，只需用待检查的信息码做被除数，除以生成多项式，如果能够整除就说明没有错误，否则就是出错了。另外要注意的是，当CRC检查出现错误时，它是不会进行纠错的，通常是让信息的发送方重发一遍。 1dQGSCihb16p2Afwq8TOo05uGplfjjEVuj/4Q9CkRI/QH48Nnx4mVzG60oAPq/PX