提高系统可靠性的措施

    防止故障造成系统失效的两种技术是故障掩蔽技术和系统重组技术，故障掩蔽技术是指防止故障造成差错的各种技术，系统重组技术是防止差错导致系统失效的各种技术。故障掩蔽技术和系统重组技术是达到容错的两种基本途径。而它们又是建立在资源冗余的基础上的。资源冗余有硬件冗余、信息冗余、时间冗余和软件冗余 4 种形式。主要介绍前两种形式。

1 硬件冗余

    硬件冗余最常用的是三模冗余（Triple Modular Redundancy，TMR），三个相同的模块接收三个相同的输入，产生的三个结果送至多数表决器。表决器的输出取决于三个输入的多数，若有一个故障模块，则另两个正常模块的输出可将故障模块的输出掩蔽，从而不在表决器输出产生差错。

    上图是一个简单的 TMR 系统，用组合模型可以计算出系统的可靠度为：

    由于Rm=e−λt  ，因此：

    其中 Rv 和 Rm 分别表示表决器和模块的可靠度（假设各模块的可靠度相同）。在无修复的屏蔽冗余系统中，当屏蔽冗余因模块中的故障而耗尽时，再发生模块故障将导致输出的错误。假若模块具有修复能力，则系统的可靠性将会大大提高。下面讨论修复对 TMR 结构可靠性的影响。

    设模块的失效率为λ，修复率为 μ，TMR 系统可靠度的马尔柯夫模型如下图所示

    TMR 系统的拉氏系数矩阵为：

    设系统的初态  P0(0)=(100)T ，则：

    对上式作部分分式分解可得：

    查拉氏逆变换表可得：

    系统的可靠度：

    用同样的方法，可以计算出带修复的 TMR 的可用度  ATMR(t) 。

    由 TMR 的完全状态图，可以计算出系统的拉氏系数矩阵为：

    用马尔柯夫模型可解出：

    则 TMR 结构系统的可用度为：

                                                                              ATMR(t)=P0(t)+P1(t) 

   对 TMR 函数积分，可得出平均无故障时间 MTTF：

    简化得：

    上面的分析没有考虑表决的可靠性，为了能够容忍表决器的故障，可以对表决器也采用 3 倍冗余。一般说来，对于一个由若干模块构成的系统，可以对每个模块分别实施 TMR 技术。

    TMR 的推广是 N 模冗余（N-Modular Redundancy，NMR）。与三模冗余原理相同，但采用 N 个相同的模块， N > 3 ，且 N 为奇数，以方便进行多数表决。NMR 的结构如图所示。

2 信息冗余

    信息冗余是指通过在数据中附加冗余的信息以达到故障检测、故障掩蔽或容错的目的。应用最广泛的是海明校验码、奇偶校验码。

    1．海明校验码

    海明校验码是由 Richard Hamming 于 1950 年提出，目前仍然被广泛采用的一种很有效的校验方法，是只要增加少数几个校验位，就能检测出二位同时出错，亦能检测出一位出错并能自动恢复该出错位的正确值的有效手段，后者称为自动纠错。它的实现原理，是在 k 个数据位之外加上 r 个校验位，从而形成一个 k+r 位的新的码字，使新的码字的码距比较均匀地拉大。把数据的每一个二进制位分配在几个不同的偶校验位的组合中，当某一位出错后，就会引起相关的几个校验位的值发生变化，不但可以发现出错，还能指出是哪一位出错，为进一步自动纠错提供了依据。

    基本的海明纠错码能纠正一位错。它的原理是基于重叠奇偶校验的概念：将原始数据位分成若干个重叠的组，每组设一位奇偶校验位。由于组间有重叠，因此每位原始数据从属于多于一个组。而且每位原始数据的从属关系是不一样的，纠错时，根据哪些组的奇偶校验位出错，就可以唯一地确定是哪一位数据出错。将该位取反就完成了纠错。

    海明校验码是一种特殊的（n，k）线性纠错码，线性纠错码可借助它们的奇偶校验矩阵（Parity-Check Matrix，PCM）来描述。（n，k）线性码的 PCM 是一个(n−k)×n 的矩阵，其元素是 0 和 1。矩阵的每一列与码字中的一个位相对应，而每一行与校验位相对应。

    推导并使用长度为 m 位的码字的海明码，所需步骤如下：

    （1）确定最小的校验位数 k，将它们记成 D1、D2、…、Dk，每个校验位符合不同的奇偶测试规定。

    （2）原有信息和 k 个校验位一起编成长为 m+k 位的新码字。选择 k 校验位（0 或 1）以满足必要的奇偶条件。

    （3）对所接收的信息作所需的 k 个奇偶检查。

    （4）如果所有的奇偶检查结果均正确，则认为信息无错误。

    如果发现有一位或多位错了，则错误的位由这些检查的结果来唯一地确定。

    2．循环冗余校验码

    循环冗余校验码（Cyclic Redundancy Chec，CRC）也广泛应用于移动通信和磁盘数据存储中。CRC 也是给信息码加上几位校验码，以增加整个编码系统的码距和查错纠错能力。

    CRC 的基本原理是：在 K 位信息码后再添加 R 位的校验码，整个编码长度为 N 位，因此，这种编码又称(N,K)码。对于一个给定的(N,K)码，可以证明存在一个最高次幂为 N-K=R 的多项式 G(x)。根据 G(x)可以生成 R 位的校验码，而 G(x)叫作这个 CRC 码的生成多项式。

    校验码的具体生成过程为：假设发送信息用信息多项式 C(x)表示，将 C(x)左移 R 位，则可表示成C(x)×2R这样 C(x)的右边就会空出 R 位，这就是校验码的位置。通过 C(x)×2R除以生成多项式 G(x)得到的余数就是校验码。

    CRC 码的生成步骤为：

    （1）将 x 的最高幂次为 R 的生成多项式 G(x)转换成对应的 R+1 位二进制数。

    （2）将信息码左移 R 位，相当于对应的信息多项式 C(x)×2R 。

    （3）用生成多项式（二进制数）对信息码做模 2 除，得到 R 位的余数。

    （4）将余数拼到信息码左移后空出的位置，得到完整的 CRC 码。