《数字电子学及其工程应用》第八章节录

8-1 检错和纠错

　　在任何把信息以数字（1、0的序列）形式传送的数字环境中，存在一定百分数的数字被误收的某种概率。只有在理想的无噪声系统中，才能期望绝对无误地接收这样的数据。因此，重要的是提供信息的编码方式，以便在接收端有了差错能够被检查出来，或被检查和纠正。

　　考虑一个系统，其中八个不同信息中的任何一个需要作为数码来传送。这个系统至少需要三个二进数字来编码。用直接二进码的八个信息如图8-1所示。应注意，在这个系统中，如果任何码字中一位或多位被颠倒了，结果这个码字就不能与其它有效信息区分开。例如，如果传送信息001，而被误收为011，接收机将认为011是正确的信息。

　　在上述的系统中，不同的码字最少只由一个数字位相互区分开。也就是，在信息组中，二进信息间的小差别或距离只是一比特的变化，这个最小的差别叫做码距。如在上例中，当最小的距离是1时，误差不能被检查出来。然而，如果用四个二进数字来编8个码字，那么在码字间的最小距离可以增加到2，如图8-2的表中所示。

信息序号 二进码字 a2 a1 a0 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 图8-1

信息序号 二进码字 a3 a2 a1 a0 0 0 0 0 0 1 1 0 0 1 2 1 0 1 0 3 0 0 1 1 4 1 1 0 0 5 0 1 0 1 6 0 1 1 0 7 1 1 1 1 图8-2

注意，图8-2的8个码字相互间最少有两比特位的差异。因此，如果任何信息的一个数位被颠倒，就成为一个不用的码字，接收机能检查出来。例如信息是1001，误收为1011，接收机知道发生了一个差错，因为1011不是一个码字。然而，差错不能被纠正。假定只有一个数位是错的，正确码字可以是1001，1111，0011或1010。也可看到，在这个系统中，偶数个(2或4)差错将成为不可检出的。 　　为了使一个系统能检查和纠正一个差错，码间最小距离必须至少是“3”。在这样的系统中，接收机实际上选择最接近误收信息的一个有数信息。因为最小距离是3，正确信息能从包括单一差错的信息中被唯一地确定下来。如果发生两个差错，接收的信息特离真正的信息较运（2比特），而离一个不正确的信息较近（1比特）。因此最小距离为3时，或能纠正一个错，或能检二个错，但不能同时纠一个错和检二个错。

码距 码能力 检错　纠错 1 2 3 4 5 6 7 0　　　0 1　　　0 2　或　1 2　加　1 2　加　2 3　加　2 3　加　3 图8-3

　　编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。图8-3的表概括了最小距离为1至7的码的纠错和检错能力。

　　增大编码信息的最小距离的一个基本缺点是，在任何给定的系统中，都会因而降低传输率。显然，这是由于增加的码位（为增大最小距离所需的）减小了有用的信息时间。这就给每个信息增加了所谓多余度。所以，选择最小距离要取决于特定系统的参数。数字系统的设计者必须考虑信息发生差错的概率和该系统能容许的最小差错率等因素。不过这些问题不是本书的内容。在本章我们主要涉及一些常用码的结构和产生、检查这些码的电路。

8-2 奇偶码

　　奇偶监督码是一种增加二进制传输系统最小距离的简单和广泛采用的方法。例如，单个的奇偶监督将使码的最小距离由一增加到二。

　　一个二进码字，如果它的码元有奇数个1，就称为具有奇性。例如，码字“1011010111”有七个1，因此，这个码字具有奇性。同样，偶性码字具有偶数个1。注意奇性检测等效于所有码元的模二加，并能够由所有码元的异或运算来确定。对于一个n位字，奇性由式(8-1)给出：

奇性=a₀⊕a₁⊕a₂⊕…⊕a_n　(8-1)

很明显，用同样的方式，我们也能够根据每一个码字的零的个数来构成奇偶监督。

　　单个的奇偶监督码可描述为：给每一个码字加一个监督位，用它来构成奇性或偶性监督。例如，在图8-2中，对于二进码就是这样做的。可以看出，附加码元d₂，是简单地选来使每个字成为偶性的。因此，若有一个码元是错的，就可以分辨得出，因为奇偶监督将成为奇性。

　　在一个典型系统里，在传输以前，由奇偶发生器把奇偶监督位加到每个字中。原有信息中的数字在接收机中被检测， 如果没有出现正确的奇、偶性，这个信息标定为错误的，这个系统将把错误的字抛掉或者请求重发。注意，用单个的奇偶监督码仅能检出奇数个码元的错误。

　　例如考虑图8-4里的奇性监督码。把奇、偶监督位加到一个8-4-2-1 BCD码，使之能够进行奇监督（将所有监督位反过来将产生偶监督码）。可以看到，如果将任何码字里的奇数个码元反过来，那么将成为偶性码，因而，无效的字是可以分辨出来的。然而，如果有两个或四个码元反过来，那末奇偶监督将仍然是奇性码，并且这个字被认为是正确的。只当一个给定的字里同时出现两个错误的概率被忽略不计时，单个的奇偶监督才是有效的，实际上，奇监督码比偶监督码可取，因为它排除了传输全0的情况。

图8-4 附加奇性监督位的BCD码

　　奇偶监督可以用在数字系统的主要接口设备中。由于在每个信息中加了多余度，仅当出现错误的概率和错误的危害足够大时，才采用奇偶监督码。

　　为了说明奇偶监督码的应用，考虑下例。假设以400比特/秒的速率传输四码位信息（100字/秒)。设由试验数据或适当的计算确定了任何单个码位出现错误的概率为3.1×10-5。因为，每个字包含四个码位，接收到错字的概率大约为1.25×l0-4，即在100字/秒的传输速率下，平均每80秒错一个字。

　　加一个奇偶监督位后，每个字需要五个码位，从而，将传输速率降低到80字／秒，能够检测一个错误，并且能指令发送机重发错了的信息以校正信息。出现两个错误的概率计算如下：如果五个码位是A、B、C、D、E，那么两个错误可能以下述10种组合出现。即

AB、AC、AD、AE
BC、BD、BE
CD、CE
DE

　　出现任何一对的概率是(3.1×10^-5)²，或9.6×10^-10，因此，在单个字里出现两个错误的概率等于10×9.6×10^-10，或9.6×10^-9。以80字/秒的新的传输速率， 可能以每1.3×10^-6秒， 即平均每15天，出现一个未被检出的错误。因为三个错误能被检测出，四个码位错误的概率与两个错误相比可以忽略不计，因此，我们在这里不考虑任何更多的错误。

8-5 汉明码

　　在8-1节中我们提出了码字间最小距离的概念，并指出能纠正信息字中的单个错误，所需的最小距离为3。实现这种纠正的方法之一是汉明码。

　　汉明码是一种多重（复式）奇偶检错系统。它将信息用逻辑形式编码，以便能够检错和纠错。用在汉明码中的全部传输码字是由原来的信息和附加的奇偶监督位组成的。每一个这种奇偶位被编在传输码字的特定比特位置上。实现得合适时，这个系统对于错误的数位无论是原有信息位中的，还是附加监督位中的都能把它分离出来。

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

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

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

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

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

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

奇偶监督的位数

　　推求汉明码时的一项基本考虑是确定所需最少的监督位数k。考虑长度为m位的信息，若附加了k个监督位，则所发送的总长度为m+k。在接收器中要进行k个奇偶检查，每个检查结果或是真或是伪。这个奇偶检查的结果可以表示成一个k位的二进字，它可以确定最多2k种不同状态。 这些状态中必有一个其所有奇偶测试试都是真的，它便是判定信息正确的条件。于是剩下的（2^k-1）种状态，可以用来判定误码的位置。于是导出下一关系：

2^k-1≥m+k　(8-4)

我们将使用满足式(8-4)要求的k的最小值。图8-9中的表是从式(8-4)导出的。这个表对于不同的k值（直到k=8）分别给出了未编码信息的最大字长m。

图8-9 ‘错误-纠正’汉明码的最大字长

码字格式

　　在常用的汉明码字格式中，监督位被安排在1、2、4、8、… 的位置上。这些位置分别地标上D₁一直到D_k 。虽然监督位的位置安排有点任意性，但可以看到这种惯用的定位方式在用单个奇偶测试来唯一地确定每个监督位时是方便的。

　　为了说明码字格式，我们考虑一个要求传输11位信息的系统。从式(8-4)我们确定屉必须是4，这就形成15位码字格式， 列在图8-10中。

图8-10 汉明码中监督和信息位的定位

奇偶监督

　　k个监督位是通过对m+k位复合码字进行奇偶监督而确定的。在上例中，m+k=15，只要进行四次偶性测试。这些测试（以A、B、C、D表示）在图8-11所示各位的位置上进行。可见，在码字位置为1-3-5-7-9-11-13-15上的偶监督的测试唯一地确定监督位D₁，同样，奇偶测试B、C和D，分别确定监督数字D₂、D₃及D₄。

图8-11 奇偶监督置位

　　对接收到的信息进行同样的奇偶测试(1到0)。如果所有的测试都是真，则认为信息是正确的。如果一个或多个测试有问题，则单个误码的位置就可找到了。例如， 如果第10位数字反了，则A和C的测试将是真，同时B和D的测试将是伪。指定0为真的结果，1为伪的结果，并构成二进数DC BA，以A为最低有效位，则错误位置就简单地用二进数DC BA=1010指出了。

图8-12 四位数信息的编码

为了进一步说明汉明码的编码和测试，讨论一下四位信息1001的编码要求。首先把未编码的信息寄存到适当的码位上，如图8-12所示。然后监督位D1、D2和D3可以通过在1-3-5-7、2-3-6-7和4-5-6-7码位上进行偶性测试而分别确定出来。这个要求的监督位为D1=0，D2=0以及D3=1，这就可以使我们写全编码后的码字，它就是0011001。 　　现在讨论接收到的七位码字中某一个码元发生错误后所造成的影响。例如，接收的信息是0001001， 则在1-3-5-7和2-3-6-7位置上的奇偶检测将是奇数，而在4-5-6-7位置上将是偶数。奇数代表错误，因此检查的结果A和B是1，C是0。于是错误位置(CBA)是011，或者说是接收信息的第三位数字。正确的信息应是0011001。 　　现将用四位码字作出的一个系统的全部16种信息的汉明码列在图8-13中。

D1 D2 m1 D3 m2 m3 m4 0 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1 1 1 1 1 1 1 图8-13 未编码信息的汉明码