《计算机组成与体系结构（原书第4版）》 —2.7.2　汉明码

2.7.2　汉明码

与磁盘系统相比，数据通信通道更容易出错，同时也更能容忍错误。在数据通信中，只要有检测错误的能力就可以。如果通信设备确定一个消息包含一个错误位，那么它要做的就是请求重传。存储系统和主存没有这么奢侈。磁盘有时可以是一个金融交易或其他不可重现的实时数据集合的唯一存储库。因此，存储设备和主存必须具备不仅可以检测还能纠正一定数量错误的能力。

错误恢复编码在过去一个世纪已被深入研究。汉明码是最有效的编码之一，也是最老的编码。汉明码是对奇偶校验概念的改进，可以提升错误检测和校正能力，添加到信息字中的奇偶校验位的数量会成比例地增加。在可能发生随机错误的情况下使用汉明码。对于随机错误，我们假定每位的失败具有固定的发生概率，且与其他位故障无关。计算机主存通常会遇到这样的错误，所以在下面的讨论中，我们会在主存位错误检测和纠正的环境下介绍汉明码。

汉明码使用的奇偶校验位也称为校验位或冗余位。存储器字本身由m位组成，但是考虑到错误检测和纠正增加了r位冗余位。因此，最后的字叫作码字，是一个包含m个数据位和r个校验位的n位单元。每个数据字是由n=m+r位组成的唯一码字，如下所示：

汉明距离是指在两个码字中有多少位不同。例如，如果我们有以下的两个码字：

我们看到它们有3个位置（由*标记）不同，所以这两个码字的汉明距离是3。（请注意，还没有讨论过如何创建码字，我们会尽快做这件事。）

两个码字之间的汉明距离在错误检测的环境中很重要。如果两个码字的汉明距离为d，那么将一个码字转换到另一个码字有d位单位错误的情况就不会被检测到。因此，如果我们希望创建一个编码，它可以保证检测到所有位的错误（1位一个错误），那么任何两个码字之间的汉明距离必须至少为2。如果认为一个n位字不是合法的码字，那么这个码字就被认为是一个错误的码字。

若给定一个计算校验位的算法，则可以构建完整合法的码字列表。在这个编码中所有两个码字之间的最小汉明距离称为编码的最小汉明距离。编码的最小汉明距离通常由符号D（min）表示，它可以决定其错误检测和纠正能力。简单来说，对于任何码字X若想被接收为另一个有效的码字Y，则在X中必须出现至少D（min）个错误。因此，为了检测k（或更少）位错误，该码的汉明距离必须为D（min）=k+1。汉明码可以始终检测D（min）-1个错误并纠正(D(min)-1)/2个错误　符号  表示向下取整的函数，是小于等于这个括起来的数的最大整数。例如，8.3=8和 8.9=8。。因此，代码的汉明距离必须至少为2k+1以能够纠正k个错误。

码字由使用r个奇偶校验位的信息字构成。在我们继续讨论错误检测和纠正之前，来看一个简单的例子。最常见的错误检测使用附加到数据上的单个奇偶校验位（回顾关于ASCII字符表示的讨论）。在这个码字的任何一位中，一位错误会产生错误的奇偶校验。

例2.40假设存储器具有2个数据位和1个附加在码字尾部的偶校验位（因此码中1数量必须为偶数）。有2个数据位，共有4个可能的字。我们这里列出数据字、对应的奇偶校验位以及为这4个可能字中的每一个产生的码字：

得到的码字有3位。3位允许有8种不同的位模式，如下所示（有效码字用*标记）：

如果遇到码字001，则它是无效的，因为它表示出错已经发生在码字的某个地方。例如，假设存储在存储器中的正确码字为011，但是一个错误使码字变为001。这个错误可以检测到，但无法纠正。不可能确切地确定有几位发生了翻转，即指明哪些位是错误的。纠错码需要多于1位的奇偶校验位，如下讨论所示。

如果有效的码字受到两位错误的影响，则上述示例会发生什么？例如，假设码字内011转换成000。这个错误不能检测到。如果检查上述示例中的代码，将看到D（min）是2，这意味着该代码仅能保证检测单个位的错误。

我们已经说过了一个编码的错误检测和纠正能力取决于D（min），从错误检测的角度来看，我们在例2.40中已经看到了这种关系。纠错需要该编码包含额外的冗余位，如果编码是检测和纠正k个错误，那么应确保最小汉明距离D（min）=2k+1。这种汉明距离保证所有合法的码字都有足够远的距离，即使有k个变化，得出的无效码字也更接近一个唯一有效的码字。这是很重要的，因为纠错中使用的方法是将无效码字转换为不同位数最少的有效码字。在例2.41中说明了这个想法。

例2.41假设我们有以下代码（不用担心如何生成此代码，我们很快就会解决这个问题）：

首先，我们来确定D（min）。通过检查所有可能的码字对，我们发现最小汉明距离D（min）=3。因此，这段代码最多可以检测两个错误并纠正1位错误。如何纠正？假设我们读取的无效码字是10000。它必须至少有一个错误，因为这与任何有效码字都不匹配。我们现在确定码字与每个合法码字之间的汉明距离：它与第一个码字有1位不同，与第二个是4位，与第三个是2位，与最后一个是3位。因此可生成一个差异向量\[1，4，2，3\]。要想对此码字进行更正，我们使用最接近的合法码字自动更正，从而修正为00000。请注意，此“修正”不一定正确！我们假设发生了最小数量的可能错误，即1个可能的错误。原始码字可能为10110，当发生两个错误时可能变为10000。

假设确实发生了两个错误。例如，假设我们读取的无效代码字是11000。如果我们计算的距离向量为\[2，3，3，2\]，我们看到没有“最近”的码字，无法进行修正。如本例所示，如果发生多个错误，最小汉明距离3允许只校正一个错误，并且不能保证纠正。

在我们的讨论中，已经简单介绍了各种各样的编码，但没有给出如何生成编码的任何细节。用于生成编码的方法有很多种，也许更直观的方法之一是用于编码设计的汉明码算法，我们现在介绍它。在解释算法的实际步骤之前，我们会介绍一些背景资料。

假设我们希望设计的代码包含m个数据位和r个校验位，它允许修正单个位错误。这意味着有2m个合法的码字，每个都有唯一的校验位组合。因为我们专注于单个位错误，所以来检查一组无效码字与所有合法码字距离为1的字。

每个有效码字都有n位，并且这些位都可能会出现错误。因此，每个有效码字有n个距离为1的非法码字。因此，如果我们关心每一个合法码字和每一个由一个错误组成的无效码字，我们会得到与每个码字相关联的n+1个位模式（1个合法字和n个不合法的字）。因为每个码字由n位组成，其中n=m+r，所以总共可能有2n个位模式。得到以下不等式：

其中n+1是每个码字的位模式的数量，2m是合法码字的数量，2n是可能位模式的总数。因为n=m+r，所以我们可以将不等式重写为：

或者

这个不等式是很重要的，因为它规定了所需检查位数量的下限（我们总是尽可能少地使用检查位）来构造一个具有m个数据位和r个校验位的代码，它可校正所有单个位错误。

假设我们有长度m=4的数据字，然后：

这意味着r必须大于或等于3。我们选择r=3。这意味着要建立一个4位数据字的代码，它应该能纠正单个位的错误，我们必须添加3个校验位。

汉明算法

汉明算法为设计编码纠正单个位错误提供了一种简单的方法。要为任何大小的内存字构造纠错代码，请按照下列步骤操作：

1.确定编码所需的校验位数r，然后为n个位（其中n=m+r）编号，从右到左，以1（不是0）开始。

2.位数为2的幂的位是奇偶校验位，其他是数据位。

3.分配奇偶校验位以检查位的位置，如下所示：位b是被奇偶校验位b1，b2，…，bj检查的，即b1+b2+…+bj=b（其中“+”表示模2的和）。

我们现在举一个例子说明这些步骤和纠错的实际过程。

例2.42使用刚刚描述的汉明码和偶数校验位编码8位的ASCII字符K。（高阶位将为零），引入一个单个位错误，然后指示如何定位错误。

我们首先确定K的码字。

步骤1：确定必要的校验位的位数，将这些位加到数据位中，并给所有的n位编号。

因为m=8，所以有（8+r+1）≤2r，这意味着r必须大于或等于4。我们选择r=4。

步骤2：从1开始从右到左编号n位数，结果是：

奇偶校验位用框标记。

步骤3：分配奇偶校验位以检查不同位的位置。

为了执行这一步，我们首先将所有位的位置写成2的幂的和：

数字1包含在位置1、3、5、7、9和11中，因此，这个奇偶校验位将反映这些位置中位的奇偶性。类似地，2包含在位置2、3、6、7、10和11中，因此，位置2中的奇偶位反映了这组位的奇偶性。位置4为位置4、5、6、7和12提供奇偶校验，位置8为位置8、9、10、11和12提供奇偶校验，如果在非框空白处写数据位，然后加入奇偶校验位，我们得到以下的码字结果：

因此，字符K的码字为010011010110。

我们在b9位置引入一个错误，生成码字010111010110。如果我们使用奇偶校验位来检查不同位组，可以发现有以下结果。

位置1检查位置1、3、5、7、9和11：使用偶校验位，这会产生错误。

位置2检查位置2、3、6、7、10和11：这是正确的。

位置4检查位置4、5、6、7和12：这是正确的。

位置8检查位置8、9、10、11和12：这会产生一个错误。

奇偶校验位1和8显示错误。这两个奇偶校验位都检查位置9和11，所以单个位错误一定在位置9或11中。但是，因为位置2也检查了位置11，并表示在其检查的位的子集中没有发生错误，所以错误必然发生在位置9。（我们知道这个错误，因为这个错误是我们造成的。但是，请注意，即使我们不知道错误在哪里，使用这个方法也能确定错误的位置并通过简单地翻转位来纠正错误。）

根据奇偶位被定位的方式，检测和纠正错误位的一个更简单的方法是把表示错误的奇偶校验位的位置相加。我们发现奇偶校验位1和8产生了一个错误，且1+8=9，这正是发生错误的地方。

例2.43使用汉明算法查找3位存储字的所有码字，假设使用奇校验。

我们有8个可能的字：000，001，010，011，100，101，110和111。首先需要确定所需的校验位数。因为m=3，所以有（3+r+1）≤2r，这意味着r必须大于或等于3。我们选择r=3。因此，每个码字都有6位，并且校验位在位置1、2和4，如下所示：

从以前的例子中我们知道：

●位置1检查位置1、3和5的奇偶性

●位置2检查位置2、3和6的奇偶性

●位置4检查位置4、5和6的奇偶性

因此，我们为每个内存字提供以下码字：

我们的码字集合是001011、001100、010010、010101、100001、100110、111000、111111。如果其中任何一个字的某一位被翻转，我们可以准确地确定是哪个位翻转并改正它。例如，要发送111，我们实际发送代码字111111。如果接收到110111，则奇偶校验位1（它检查位置1、3和5）是对的，奇偶校验位2（它检查位置2、3和6）是对的，但是奇偶校验位4显示错误，因为只有位置5和6是1，这违反了奇校验。位置5不可能不正确，因为奇偶校验位1检查是正确的。位置6不可能错误，因为奇偶校验位2检查是正确的。因此，位置4是错误的，所以它应从0变为1，得到正确的码字111111。

在下一章中，您将看到使用简单的二进制电路实现一个汉明码是多么容易。由于其简单性，所以可以廉价地加入汉明码保护并且对性能影响很小。