原创 检错和纠错

转http://www.huihong-laser.com/oldchild/jsjsj/asm/jchjc.htm

检错和纠错

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

老顽童按：《数字电子学及其工程应用》是25年前一本数字电路译著，对各种校验码的讲解比较清楚。老顽童把它们节录出来，供考生们参考。

8-1 检错和纠错

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

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

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

编码信息纠错和检错能力的进一步提高需要进一步增加码字间的最小距离。图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-3 定重码(定比码)

“定重码”仅是单个奇偶监督的推广。在定重码中，奇数或偶数的性质保持不变，然而附加一种限制，就是在每个字中1的总数是固定的。随用途之不同，定重码要求的附加检错位可能多于一个，但较之单一的奇偶检错将增加更多的检错能力。

五中取二的定重码常常用于传输二进形式的十进数。在这种体制中采用7—4—2—1的权数去表示十进数；如表8-7所示。然后选择所增加的定重位使每个字恰好有两个1和三个0， 这种码有时称为“五中取二”码。

在图8-7的五位码中可以看到等效的十进制字码是用7-4-2-1-0权数构成的，并且应注意码字11000表示十进制的零。这样，当接收到的任何信息其1的个数少于二成多于二，就可以知道这个信息是错误的。

定重码能够检测出全部的单一错误和40%的两个错误（见习题8-6）。注意这种检错能力较之上面图8-4的单个奇偶捡错有了改进，而所需的监督位数并没有任何增加。两种十进字码都要求5位数字。但要提高检测能力而不付出代价是不可能的，注意通常四个二进数字就能传输多达16个不同的信息。如果所有16个不同信息都要应用，那末实现一个定重码就将需要6位码。因此所增大的检错能力是由BCD码中固有的多余度形成的。

图8-7 五中取二定重码

8-4 几何码——分组奇偶监督

当扰乱信号为加性噪声，例如白噪声^[3]时，奇偶检错码的结果是可以合理地预测到的。遗憾的是引起错误的根源是各种各样的。高频通信信道中常会有由于突发噪声或衰落所带来的间隔不定的成群错误。这些错误能用分组奇偶监督码更有效地检出^[4]。

现在考虑一个系统， 它传输若干个长度为m位的信息。如果把这些信息都编成每组n个信息的分组，则在这些不同的信息间，也如对单个信息一样，能够作奇偶监督。图8-8中n个信息的一个分组排列成矩形式样，并以横向奇偶（HP）及纵向奇偶（VP）的形式编出奇偶监督位。

图8-8用综横奇偶监督的几何码

研究图8-8可知：分组奇偶监督码不仅能检测许多形式的错误。并且在给定的行或列中产生孤立的错误时，还可对该错误进行纠正。但是这种码却不能用来检测在二维空间为对称的偶数个错误。例如，如果4个数字a₂、a₃、C₂、C₃是错误的，则a行和C行的数字和第二列第三列或者是正确的，或者有偶数个附加错误而奇偶检错统统认为是正确的。凡何码在错误检测中仍然是一种有用的工具，并已被广泛使用。实现它们比较便宜，在字母符报传输中或者在计算机之间或者计算机与外部设备（比如作孔卡片、作孔纸带，磁带等单元）之间的数据传输中，都使用它们。

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位数字反了， 则AB和C的测试将是真，同时B和D的测试将是伪。指定0为真的结果，1为伪的结果，并构成二进数DC BA，以A为最低有效位，则错误位置就简单地用二进数DC BA="1010指出了"。

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