系统的可靠性分析与设计 · 海明码演算、CRC 与可靠性预计模型

拆开其实很朴素。循环冗余校验码广泛应用于移动通信和磁盘数据存储，基本原理是在 K 位信息码后添加 R 位校验码，整个编码长度为 N 位，因此这种编码又称 (N,K) 码。对于一个给定的 (N,K) 码，可以证明存在一个最高次幂为 N 减 K 等于 R 的多项式 G(x)，根据它可以生成 R 位的校验码，G(x) 就叫这个 CRC 码的生成多项式。

校验码的生成过程：假设发送信息用信息多项式 C(x) 表示，将 C(x) 左移 R 位、也就是乘 2 的 R 次方，右边空出 R 位，这就是校验码的位置；用 C(x) 乘 2 的 R 次方再除以生成多项式 G(x)，得到的余数就是校验码。落到原文给的四个步骤：一，将 x 的最高幂次为 R 的生成多项式 G(x) 转换成对应的 R 加 1 位二进制数；二，将信息码左移 R 位；三，用生成多项式对信息码做模 2 除，得到 R 位的余数；四，将余数拼到信息码左移后空出的位置，得到完整的 CRC 码。

不借不退——模 2 运算就是不进不借的异或。拿一个小例子走一遍：设信息码 1010，生成多项式 G(x) 等于 x 三次方加 x 加 1，写成二进制就是 1011，最高幂次 3，所以校验位 R 等于 3。第一步信息码左移 3 位变成 1010000，然后拿 1011 去做模 2 除。

对齐首位：1010000 的前 4 位是 1010，首位是 1，商 1，1010 异或 1011 等于 0001；落下一位，当前 4 位窗口是 0010，首位是 0，商 0，原样落下；再落一位，窗口 0100，首位还是 0，商 0。最后落下一位，窗口变成 1000，首位是 1，商 1，1000 异或 1011 等于 0011。被除数 7 位全部用尽，余数就是 0011 的后三位，也就是 011。

对，规则只有一条：每一步看被除数当前最高位，是 1 就商 1 并与 1011 异或，是 0 就商 0 原样落下，窗口逐位右移，直到被除数用尽。按这条规则 1010000 除以 1011，四步分别是 1010 异或 1011 得 0001，窗口 0010 商 0，窗口 0100 商 0，窗口 1000 商 1 异或得 0011，余数取后三位 011。所以校验码是 011，完整 CRC 码就是把信息码 1010 拼上 011，等于 1010011。

最后一节，备份与恢复。硬件故障、系统软件和应用软件的故障、操作员的失误，甚至病毒、人为破坏总是不可避免的，为保证故障发生后系统能尽快从错误状态恢复到某种逻辑一致的状态，系统必须有备份与恢复机制。备份最常用的技术是数据转储和建立日志文件。数据转储分两种：静态转储指在系统中无事务时进行，动态转储指转储操作与用户事务并发进行、不影响事务运行，但不能保证副本中的数据正确有效。日志文件是把所有事务对系统的修改活动都登记下来，静态转储配日志可以在重装后备副本后利用日志恢复、避免重新运行事务；动态转储则把副本和转储期间的日志文件结合起来恢复。

对号入座。脱机备份也叫冷备份，是一种静态转储技术，备份系统所有的物理文件，包括控制文件、数据文件、重做日志和归档日志以及初始化文件；优点是恢复过程中步骤最少，它比热备份快并且出错机会少，定期的脱机备份加上一组好的重做日志可以把系统数据恢复到任何一个时间点上。联机备份也叫热备份，是一种动态转储技术，只备份所需文件，被看作部分备份，在系统运行时执行；优点是可以实现完全的时间点恢复，数据库一直打开也减少了对物理资源的要求；缺点是比较复杂，需要对系统核心有深刻认识并反复测试。

那就现在补上，三道题都考它。原文定义先立住：失效，是硬件的物理改变；故障，是由于部件的失效、环境的物理干扰、操作错误或不正确的设计引起的硬件或软件中的错误状态；错误也叫差错，是故障在程序或数据结构中的具体位置，而且错误与故障位置之间可能出现一定距离。练习第 3 题就考这三者的链条——物理改变是失效，错误状态是故障，落点才是错误。

按原文记特征：永久性描述连续稳定的失效、故障或错误，在硬件中反映不可恢复的物理改变；间歇性描述由不稳定的硬件或变化着的硬件或软件状态所引起的、仅仅偶然出现的故障或错误；瞬时性描述由于暂时的环境条件所引起的故障或错误。第 4 题问「由于暂时的环境条件而引起的故障」，答瞬时性——关键词就是「暂时、环境」。

这是反向坑：由硬件物理条件、不正确的硬件或软件设计、或不稳定但重复出现的环境条件所引起的故障，可以通过替换或重新设计来修复；但由于暂时的环境条件所引起的故障是不能修复的——因为硬件本身实际上并没有损坏。原文还补了一句：瞬时和间歇故障已经成为系统中的一个主要错误源。

四级从低到高：逻辑级、数据结构级、软件、系统级。逻辑级是固定型、短路、开路、桥接这些电路级故障；数据结构级的故障表现称为差错，常见三种——独立差错是一个故障使一个二进制位发生改变，算术差错是使一个数据的值增加或减少 2 的 i 次方，单向差错是使一个二进制向量中的某些位朝同一个方向改变；软件故障是设计过程造成的与设计说明不一致，其表现是软件差错，常见六种含非法转移、误转移、死循环、空间溢出、数据执行、无理数据；系统级表现为功能错误，即系统输出与设计说明的不一致。第 5 题选数据结构级时，认准「独立、算术、单向」三个差错名。还有一句原则要背：故障模型建立的级别越低，进行故障处理的代价也越低，但故障模型覆盖的故障也越少。

全对。那按惯例，把第 17 章的必背清单整个过一遍。指标三件套：可靠度 R(t) 是 t 等于 0 时系统正常的条件下 [0,t] 内正常运行的概率，可用度 A(t) 是时刻 t 可运行的概率，可维度 M(t) 是失效后在时间间隔内被修复的概率，失效率 λ 是单位时间内失效的预期次数；MTTF 等于 1 除以 λ，MTTR 等于 1 除以 μ，MTBF 等于 MTTR 加 MTTF。

故障模型：失效是硬件物理改变、故障是错误状态、差错是故障在程序或数据结构中的具体位置；三种表现，永久性连续稳定、间歇性偶然出现、瞬时性由暂时环境条件引起且不能修复。四级故障模型从低到高是逻辑级、数据结构级、软件、系统级，数据结构级差错是独立、算术、单向三种。配置方法：单机容错、双机热备份、服务器集群；心跳是主从系统按时间间隔互发信号表明运行状态；三种模式 active/standby 是双机热备、互为备机是双机互备、均活动带负载均衡是双机双工。

可靠度计算：串联是各模块可靠度 Ri(t) 的乘积，并联是 1 减各模块失效概率 Qi(t) 的连乘，Qi(t) 等于 1 减 Ri(t)；n 部件系统有 2 的 n 次方个状态；马尔柯夫模型能算组合模型能算的一切，还能算组合模型算不了的。软件可靠性模型：Shooman 是时间模型靠调试时间，Mills 1972 故障植入埋错误，Basin 1974 两步查错，Nelson 1973 数据模型靠输入集。

提高可靠性：故障掩蔽防差错、系统重组防失效；TMR 三模块加多数表决掩蔽单个故障模块，NMR 的 N 大于 3 且为奇数。编码：海明码 Richard Hamming 1950 年，检二错纠一错，k 数据位加 r 校验位拉大码距；CRC 是 (N,K) 码、模 2 除取余拼尾。备份：冷备份是静态转储全量快出错少，热备份是动态转储可完全时间点恢复。

全章必背清单收个尾：串联可靠度是各部件可靠度连乘、并联是 1 减去各失效率连乘；平均无故障时间 MTTF 与平均故障间隔时间 MTBF 衡量可靠性、平均修复时间 MTTR 衡量可维护性；软件容错两条路是 N 版本程序设计与恢复块；硬件冗余三模冗余 TMR 用表决器取多数；海明码 1950 年 Richard Hamming 提出、码距决定检错纠错能力，检错条件是码距大于等于错误数加一、纠错条件是码距大于等于两倍错误数加一；CRC 用生成多项式做模 2 除法。

去吧，错题对回这三集对应段落。下一章第 18 章讲知识产权，没有公式全是条文，正好让刚烧完的脑子换换口味——著作权、专利权、商标权，年限和归属是那边的重头戏。