系统的可靠性分析与设计 · 海明码原理、码距与四步计算法

问到点子上了，这正是系统可靠性模型一节要回答的。先说最著名的时间模型，由 Shooman 提出的可靠性增长模型，它基于这样一个假设：一个软件中的故障数目在 t 等于 0 时是常数，随着故障被纠正，故障数目逐渐减少。

在此假设下，软件经过一段时间调试后剩余的故障数可以估计：τ 是调试时间，Er(τ) 是时刻 τ 剩余的故障数，E0 是 τ 等于 0 时的故障数，I 为软件中的指令数，直觉就是初始的减掉已经改掉的；由它可得风险函数 Z(t) 等于 C 乘以 Er(τ)，C 是比例常数。

这正是它的死穴，原文提示写得直白：在 Shooman 的模型中，需要确定在调试前软件中的故障数目，这往往是一件很困难的任务。应试抓三个标签：Shooman、时间模型、可靠性增长模型。

你这个直觉就是第二个模型——故障植入模型，一个面向错误数的数学模型，以程序的错误数作为衡量可靠性的标准，原型是 1972 年由 Mills 提出。基本假设四条：固有错误数是未知常数；人为错误数按均匀分布随机植入；固有错误和人为错误被检测到的概率相同；检测到的错误立即改正。

用 N0 表示固有错误数，N1 表示植入的人为错误数，检测到的错误中人为错误为 k 个时，用最大似然法求解可得 N0 的点估计值——埋进去的错和原生的错被逮到的概率一样，按比例折算就出来了。

有。Basin 在 1974 年提出两步查错法：由两个错误检测人员独立对程序进行测试，检测到的错误立即改正。N1 是第一个检测员检测到的错误数，n 是第二个的，实际测得两人相同的错误数为 k 时，同样可解出固有错误数 N0 的点估计值——相当于拿第二个检测员当「植入的错误」用。

没错。第三个是数据模型，最早由 Nelson 于 1973 年提出：对一个预先确定的输入环境，软件的可靠度定义为在 n 次连续运行中软件完成指定任务的概率。令导致软件差错的所有输入的集合为 Ee，则一次运行出现差错的概率 P1 等于 Ee 的元素个数除以输入集 E 的元素个数，一次运行正常的概率 R1 等于 1 减 P1，于是 n 次运行不出现差错的概率 R(n) 等于 R1 的 n 次方；只要知道每次运行的时间，R(n) 就能转换成时间模型中的 R(t)。

先立框架。防止故障造成系统失效的两种技术：故障掩蔽技术，是防止故障造成差错的各种技术；系统重组技术，是防止差错导致系统失效的各种技术。它们是达到容错的两种基本途径，都建立在资源冗余的基础上，冗余有硬件、信息、时间、软件四种形式。

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

总结到位，这三个「不负责」正是选择题的三个干扰项。再补两个考点。一，TMR 的可靠度用组合模型可算，Rv 和 Rm 分别是表决器和模块的可靠度、各模块相同且 Rm 等于 e 的负 λt 次方；无修复的屏蔽冗余系统里，当屏蔽冗余因模块中的故障而耗尽时，再发生模块故障将导致输出的错误，模块若有修复能力，可靠性会大大提高。二，上面的分析没考虑表决的可靠性，要容忍表决器的故障，可以对表决器也采用 3 倍冗余。

TMR 的推广是 N 模冗余 NMR，与三模冗余原理相同，但采用 N 个相同的模块，N 大于 3 且 N 为奇数，以方便进行多数表决。「N 必须是奇数」这句几乎是必考的原文。

对。信息冗余是指通过在数据中附加冗余的信息以达到故障检测、故障掩蔽或容错的目的，应用最广泛的是海明校验码和奇偶校验码。先考你个冷知识：海明校验码谁提出的、哪一年？

正确。海明校验码是由 Richard Hamming 于 1950 年提出，目前仍被广泛采用的一种很有效的校验方法。它的能力一句话记：只要增加少数几个校验位，就能检测出二位同时出错，亦能检测出一位出错并能自动恢复该出错位的正确值，后者称为自动纠错。原理是在 k 个数据位之外加上 r 个校验位，从而形成一个 k 加 r 位的新的码字，使新的码字的码距比较均匀地拉大。

按原文理解：码距就是码字之间要拉开的距离，加校验位把码距拉大，查错纠错能力就上来了——海明码和 CRC 的原文都拿「增加码距」当立身之本，CRC 的原话是给信息码加上几位校验码「以增加整个编码系统的码距和查错纠错能力」。当某一位出错后，就会引起相关的几个校验位的值发生变化，不但可以发现出错，还能指出是哪一位出错，为自动纠错提供了依据。

基本的海明纠错码能纠正一位错，原理是基于重叠奇偶校验的概念：将原始数据位分成若干个重叠的组，每组设一位奇偶校验位，由于组间有重叠，每位原始数据从属于多于一个组，而且每位原始数据的从属关系是不一样的。纠错时根据哪些组的奇偶校验位出错，就可以唯一地确定是哪一位数据出错，将该位取反就完成了纠错。海明校验码是一种特殊的（n，k）线性纠错码，(n,k) 线性码可借助奇偶校验矩阵来描述，它是一个 n 减 k 行、n 列的矩阵，元素是 0 和 1，每一列与码字中的一个位相对应，每一行与校验位相对应。

原文给了推导并使用长度为 m 位的码字的海明码所需四步。第一步，确定最小的校验位数 k，将它们记成 D1、D2 一直到 Dk，每个校验位符合不同的奇偶测试规定。第二步，原有信息和 k 个校验位一起编成长为 m 加 k 位的新码字，选择 k 个校验位、0 或 1，以满足必要的奇偶条件。第三步，对所接收的信息作所需的 k 个奇偶检查。第四步，如果所有的奇偶检查结果均正确，则认为信息无错误；如果发现有一位或多位错了，则错误的位由这些检查的结果来唯一地确定。