第7章 纠错编码

第7章纠错编码第7章纠错编码7.1差错控制方式7.2纠错编码的基本原理7.3常用的简单编码7.4线性分组码7.5卷积码习题与思考题第7章纠错编码7.1差错控制方式常用的差错控制方式主要有三种：检错重发（ARQ，Automatic-Request-Repetition）、前向纠错（FEC,Forward-Error-Control）和混合纠错（HEC,Hybrid-Error-Correction）。它们的系统构成如图7.1所示。第7章纠错编码图7.1差错控制方式的系统构成(a)检错重发；(b)前向纠错；(c)混合纠错应答信号能够发现错误的码收端发端可以发现和纠正错误的码可以纠正错误的码(a)应答信号收端发端(b)应答信号收端发端(c)第7章纠错编码7.1.1检错重发在检错重发方式中，发送端经编码后发出能够发现错误的码，接收端收到后经检验如果发现传输中有错误，则通过反向信道把这一判断结果反馈给发送端，然后，发送端把前面发出的信息重新传送一次，直到接收端认为已正确地收到信息为止。常用的检错重发系统有三种，即停发等候重发、返回重发和选择重发。图7.2中画出了这三种系统的工作原理图。第7章纠错编码图7.2ARQ差错控制系统工作原理(a)停发等候重发；(b)返回重发；(c)选择重发TI发送端1发现错误NAK发送端211332码组接收端3TWACK(a)23456234567891011TW1234562345678发现错误接收端(b)从码组2开始重发NAK发送端12345627891011121314151234562发现错误接收端(c)重发码组2NAK789101112第7章纠错编码图7.2（a）表示停发等候重发系统的发送端、接收端的信号传递过程。发送端在TW时间内送出一个码组给接收端，接收端收到后经检测若未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号后再发出下一个码组。返回重发系统如图7.2（b）所示。第7章纠错编码7.1.2前向纠错在前向纠错系统中，发送端经编码发出能够纠正错误的码，接收端收到这些码组后，通过译码能自动发现并纠正传输中的错误。前向纠错方式不需要反馈信道，特别适合于只能提供单向信道的场合。由于该系统能自动纠错，不要求检错重发，因而具有延时小，实时性好等特点。第7章纠错编码7.1.3混合纠错混合纠错方式是前向纠错方式和检错重发方式的结合。在这种系统中，发送端不但有纠正错误的能力，而且对超出纠错能力的错误有检测能力。遇到后一种情况时，通过反馈信道要求发送端重发一遍。混合纠错方式在实时性和译码复杂性方面是前向纠错和检错重发方式的折衷。第7章纠错编码7.2纠错编码的基本原理现在我们来讨论纠错编码的基本原理。为了便于理解，先通过一个例子来说明。一个由三位二进制数字构成的码组，共有八种不同的可能组合。若将其全部利用来表示天气，则可以表示八种不同的天气，譬如：000（晴），001（云），010（雨），011（阴），100（雪），101（霜），110（雾），111（雹）。其中，任意码组在传输中若发生1个或多个错码，则该码组将变成另一信息码组。这时接收端将无法发现错误。第7章纠错编码若在上述八种码组中只准许使用四种来传送信息，譬如：000=晴011=云101=阴110=雨(7.1)第7章纠错编码分组码一般用符号（n，k）表示，其中k是每组二进制信息码元的数目，n是编码组的总位数，又称为码组长度（码长），n-k=r为每个码组中的监督码元数目或称监督位数目。通常，将分组码规定为具有如图7.3所示的结构。图中前面k位（an-1…ar）为信息位，后面附加r个监督位（ar-1…a0）。在式（7.1）的分组码中，n=3，k=2，r=1。第7章纠错编码表7.1第7章纠错编码图7.3分组码的结构an－1an－2…arar－1…a0时间k个信息位r个监督位码长n＝k＋r第7章纠错编码在分组码中，我们把“1”的数目称为码组的重量，而把两个码组对应位上数字不同的位数称为码组的距离，简称码距，又称汉明（Hamming）距离。式（7.1）中四个码组之间任何两个的距离均为2。我们把某种编码中各个码组间距离的最小值称为最小码距（d0），例如，按式（7.1）编码的最小码距d0=2。第7章纠错编码图7.4码距的几何意义(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(1,1,1)(0,1,1)a0a2a1第7章纠错编码一种编码的最小码距d0的大小直接关系到这种编码的检错和纠错能力。下面我们将具体对此加以说明。(1）为检测e个错码，要求最小码距为d0≥e+1(7.2)这可以用图7.5（a）简单证明如下：设一码组A位于0点。若码组A中发生一位错码，则可以认为A的位置将移动至以0点为圆心、以1为半径的圆上某点，但其位置不会超出此圆。第7章纠错编码图7.5码距与检错和纠错能力的关系45Bt0123BAed0(a)0123Atd0(b)BtAe(c)t1t第7章纠错编码(2）为纠正t个错码，要求最小码距d0≥2t+1（7.3）上式可用图7.5（b）来加以说明。图中画出码组A和B的距离为5。码组A或B若不发生多于2位的错码，则其位置均不会超出以原位置为圆心，以2为半径的圆。由于这两个圆的面积是不重叠的，故可以这样判决：若接收码组落于以A为圆心的圆上，就判决收到的是码组A；若落于以B为圆心的圆上，就判决为码组B。第7章纠错编码(3）为纠正t个错码，同时检测e个错码，要求最小码距为d0≥e+t+1(et)(7.4)在解释此式之前，先来说明什么是“纠正t个错码，同时检测e个错码”（简称纠、检结合）。在某些情况下，要求对于出现较频繁但错码很少的码组，按前向纠错方式工作，以节省反馈重发时间；同时又希望对一些错码数较多的码组，在超过该码的纠错能力后，能自动按检错重发方式工作，以降低系统的总误码率。这种工作方式就是“纠、检结合”。第7章纠错编码假设在随机信道中发送“0”时的错误概率和发送“1”时的相等，都等于p，且p1,容易证明，在码长为n的码组中恰好发生r个错码的概率为rrnrnnprnrnppCrP)!(!!)1()(（7.5）第7章纠错编码7.3常用的简单编码7.3.1奇偶监督码奇偶监督码是一种最简单的检错码，又称奇偶校验码，在计算机数据传输中得到了广泛的应用。在ISO和CCITT提出的七单位国际5层字母表、美国信息交换码ASCII字母表及我国的七单位字符编码标准中都采用7比特码组表示128种字符，如字符A的编码表示为1000001（在第8章将较详细地介绍）。第7章纠错编码一般情况下奇偶监督码的编码规则是：首先将要传输的信息分成组，然后将各位二元信息及附加监督位用模2和相加，选择正确的监督位，保证模2和的结果为0（偶校验）或1（奇校验）。这种监督关系可以用公式表示。设码组长度为n，表示为（an-1an-2an-3…a0），其中前n-1位为信息，第n位为校验位，则偶校验时有120012100nnaaaaaaaa监督码元a0即为(7.6a)（7.6b）第7章纠错编码奇校验时有111210110nnaaaaaaa（7.6c）（7.6d）监督码元a0为第7章纠错编码7.3.2水平奇偶监督码针对上述奇偶监督码检错能力不高，特别是不能检测突发错误的缺点，可以将经过奇偶监督编码的码元序列按行排列成方阵，每行为一组奇偶监督码（如表7.2所示），但发送时则按列的顺序传输：00010011101…1001011，接收端仍然将码元排成发送时的方阵形式，然后按行进行奇偶校验。由于按横行进行奇偶校验，因此称其为水平奇偶监督码或行奇偶监督码。第7章纠错编码表7.2水平奇偶监督码第7章纠错编码7.3.4群计数码在群计数码中，信息码元分组后计算其“1”的个数，然后将这个数目的二进制表示作为监督码元附加在信息码元之后送往信道。例如一组信息码元为11100101，其中有5个“1”，用二进制数字表示为“101”，传输的码组即为11100101101。这种码的检错能力很强，除了发生1变0和0变1成对的错误之外，它能检测出所有形式的错误。第7章纠错编码7.4线性分组码7.4.1线性分组码的概念前面介绍的奇偶监督码其编码原理利用了代数关系式，我们把这类建立在代数基础上的编码称为代数码。在代数码中，常见的是线性码。线性码中的信息位和监督位是由一些线性代数方程联系着的，或者说，线性码是按一组线性方程构成的。这里将以汉明码为例引入线性分组码的一般原理。第7章纠错编码按式（7.6a）条件构成的偶数监督码由于使用了1位监督位a0，因此它就能和信息位an-1…a1一起构成一个代数式，如式（7.6a）所示。在接收端解码时，实际上就是计算021aaaSnn（7.7）第7章纠错编码一般说来，若码长为n，信息位数为k，则监督位数r=n-k。如果希望用r个监督位构造出r个监督关系式来指示一位错码的n种可能位置，则要求2r-1≥n或2t≥k+r+1(7.8)下面我们通过一个例子来说明如何构成这些监督关系式。第7章纠错编码表7.3第7章纠错编码由表中规定可见，仅当1个错码位置在a2、a4、a5或a6时，校正子S1为1；否则S1为0。这就意味着a2、a4、a5和a64个码元构成的偶数监督关系为S1=a6⊕a5⊕a4⊕a2（7.9）同理，a1、a3、a5和a6构成的偶数监督关系为S2=a6⊕a5⊕a3⊕a1（7.10）第7章纠错编码以及a0、a3、a4和a6构成的偶数监督关系为S3=a6⊕a4⊕a3⊕a0（7.11）在发端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。监督位a2、a1和a0应根据信息位的取值按监督关系来确定，监督位应使上式中S1、S2和S3的值为零（表示编成的码组中应无错码），即第7章纠错编码a6⊕a5⊕a4⊕a2=0a6⊕a5⊕a3⊕a1=0a6⊕a4⊕a3⊕a0=0(7.12)由上式经移项运算，解出监督位为a2=a6⊕a5⊕a4a1=a6⊕a5⊕a3a0=a6⊕a4⊕a3(7.13)第7章纠错编码接收端收到每个码组后，先按式（7.9）~式（7.11）计算出S1、S2和S3，再按表7.3判断错误情况。例如，若接收码组为0000011，则按式（7.9）～式（7.11）计算可得S1=0，S2=1，S3=1。由于S1S2S3等于011，故根据表7.3可知在a3位有一错码。第7章纠错编码7.4.2线性分组码的矩阵描述现在我们再来讨论线性分组码的一般原理。上面已经提到，线性码是指信息位和监督位满足一组线性方程的码。式（7.12）就是这样一组线性方程的例子。现在将它改写成1·a6＋1·a5＋1·a4＋0·a3＋1·a2＋0·a1＋0·a0=01·a6＋1·a5＋0·a4＋1·a3＋0·a2＋1·a1＋0·a0=01·a6＋0·a5＋1·a4＋1·a3＋0·a2＋0·a1＋1·a0=0(7.14)第7章纠错编码注：上式中将“⊕”简写为“+”。在本章后面，除非另加说明，这类式中的“+”都指模2加。式（7.14）又可以表示成0001011001110101011101000123456aaaaaaa(模2)（7.15）第7章纠错编码上式还可以简记为H·AT=OT或A·HT=0（7.16）其中：101100111010101110100H0000123456OaaaaaaaA第7章纠错编码类似于式（7.12）改变成式（7.15）中矩阵形式那样，式（7.13）也可以改写成以下形式：3456012101111011110aaaaaaa（7.18）第7章纠错编码或者Qaaaaaaaaaaa34563456012011101110111（7.19）第7章纠错编码