1、1通信原理2通信原理第第11章差错控制编码章差错控制编码 3第11章差错控制编码l11.1 概述概述从前面的分析看，任何信道都不会绝对没有误码，只是误码率大小不同，如有线信道、无线信道。不同业务对误码率的要求也不同，如语音通信、数据通信。应用中，显然它们不可能都正好相配。因此需要差错控制，纠错编码。n错误分类：从码元错误特征看u随机错误：错码的出现是随机的 u突发错误：错码是成串集中出现的u混合错误：既存在随机错码又存在突发错码 n差错控制技术的种类u检错重发(ARQ)(CRC)、检错删除u前向纠错(FEC)u(反馈校验)4第11章差错控制编码n差错控制编码：常称为纠错编码纠错编码u校验码元校
2、验码元：上述4种技术中除第3种外，都是在接收端识别有无错码。所以在发送端需要在信息码元序列中增加一些差错控制码元，它们称为校验码元。u不同的编码方法，有不同的检错检错或纠错纠错能力。u(多余度多余度：就是指增加的校验码元多少。例如，若编码序列中平均每两个信息码元就添加一个校验码元，则这种编码的多余度为1/3。)u编码效率编码效率(简称码率码率)：设编码序列中信息码元数量为k，总码元数量为n(n k)，则比值R=k/n 就是码率。u冗余度冗余度：校验码元数r=(nk)和信息码元数 k 之比。u理论上，差错控制以降低信息传输速率为代价换取提高传输可靠性。5第11章差错控制编码n自动请求重发(ARQ
3、)系统u3种ARQ系统p停止等待ARQ系统 数据按分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组6第11章差错控制编码p拉后ARQ系统发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认确认(ACK)或否认否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，
4、从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道 接收数据有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 1110 11 12重发码组重发码组7第11章差错控制编码p选择重发ARQ系统它只重发出错的数据组，因此进一步提高了传输效率。接收数据有错码组有错码组9214365759810 11131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK98第11章差错控制编码uARQ的主要优点：和前
5、向纠错方法相比p监督码元较少即能使误码率降到很低，即码率较高；p检错的计算复杂度较低；p检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。uARQ的主要缺点：p需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。p因为重发而使ARQ系统的传输效率降低。p在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。p在要求实时通信的场合，例如电话通信，往往不允许使用ARQ法。9第11章差错控制编码uARQ系统的原理方框图p在发送端，输入的信息码元在编码器中被分组编码（加入监督码元）后，除了立即发送外，还暂存于缓冲存储器中。若接收端解码器检出错码，则由解码器
6、控制产生一个重发指令。此指令经过反向信道送到发送端。由发送端重发控制器控制缓冲存储器重发一次。p接收端仅当解码器认为接收信息码元正确时，才将信息码元送给收信者，否则在输出缓冲存储器中删除接收码元。p当解码器未发现错码时，经过反向信道发出不需重发指令。发送端收到此指令后，即继续发送后一码组，发送端的缓冲存储器中的内容也随之更新。1011.2 纠错编码基本原理纠错编码基本原理l11.2 纠错编码的基本原理纠错编码的基本原理n分组码基本原理：举例说明如下。u设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气，例如：“000”（晴），“001”
7、（云），“010”（阴），“011”（雨），“100”（雪），“101”（霜），“110”（雾），“111”（雹）。u其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。11u若在上述8种码组中只准许使用4种来传送天气，例如：“000”晴 “011”云 “101”阴 “110”雨p这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。例如，若“000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用码组禁用码组。接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“00
8、0”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。p但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组许用码组。11.2 纠错编码基本原理纠错编码基本原理12u检错和纠错p检错：对接收码，可判断其是否有错，但不知错在何处，错值如何。p纠错：对接收码，可判断其是否有错，错在何处，错值如何，从而纠正它。(二进码不需知道错值)p上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。p要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：“00
9、0”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。p例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。11.2 纠错编码基本原理纠错编码基本原理13u分组码的结构p将信息码分组，为每组信息码附加若干校验码的编码称为分组码分组码。p在分组码中，校验码元仅校验本码组中的信息码元。p信息位和校验位的关系：举例如下信息位校验位晴000云011阴101雨11011.2 纠错编码基本原理纠错编码基本原理14p分组码的一般结构u分组码的
10、符号：(n,k)pN 码组的总位数，又称为码组的长度（码长），pk 码组中信息码元的数目，pn k r 码组中的监督码元数目，或称监督位数目。11.2 纠错编码基本原理纠错编码基本原理15u分组码的码重和码距p码重：把码组中“1”的数目称为码组的重量，简称码重码重w。p码距：把两个码组中对应位上数字不同的位数称为码组的距离，简称码距码距d。码距又称汉明距离汉明距离。p两个码组的距离是它们(按位模2)和的重量。p例如，“000”晴，“011”云，“101”阴，“110”雨，4个码组之间，任意两个的距离均为2。p最小码距最小码距：把某种编码中各个码组之间距离的最小值称为最小码距(d0)。例如，上面
11、的编码的最小码距d0=2。11.2 纠错编码基本原理纠错编码基本原理16u码距的几何意义p对于3位的编码组，可以在3维空间中说明码距的几何意义。p每个码组的3个码元的值(a1,a2,a3)就是此立方体各顶点的坐标。而上述码距概念在此图中就对应于各顶点之间沿立方体各边行走的几何距离。p由此图可以直观看出，上例中4个许用码组之间的距离均为2。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a111.2 纠错编码基本原理纠错编码基本原理17u码距和检纠错能力的关系p一种编码的最小码距d0的大小直接关系着这种编码的检错和纠错能力p
12、要检测e个错码，要求最小码距 d0 e+1【证】设一个码组A位于O点。若码组A中发生一个错码，则我们可以认为A的位置将移动至以O点为圆心，以1为半径的圆上某点，但其位置不会超出此圆。若码组A中发生两位错码，则其位置不会超出以O点为圆心，以2为半径的圆。因此，只要最小码距不小于3，码组A发生两位以下错码时，不可能变成另一个准用码组，因而能检测错码的位数等于2。0123BA汉明距离ed011.2 纠错编码基本原理纠错编码基本原理18同理，若一种编码的最小码距为d0，则将能检测(d0-1)个错码。反之，若要求检测e个错码，则最小码距d0至少应不小于(e+1)。p要纠正t个错码，要求最小码距d0 2t
13、+1【证】图中画出码组A和B的距离为5。码组A或B若发生不多于两位错码，则其位置均不会超出半径为2以原位置为圆心的圆。这两个圆是不重叠的。判决规则为：若接收码组落于以A为圆心的圆上就判决收到的是码组A，若落于以B为圆心的圆上就判决为码组B。这样，就能够纠正两位错码。BtA汉 明 距离012345td011.2 纠错编码基本原理纠错编码基本原理19若这种编码中除码组A和B外，还有许多种不同码组，但任两码组之间的码距均不小于5，则以各码组的位置为中心以2为半径画出之圆都不会互相重叠。这样，每种码组如果发生不超过两位错码都将能被纠正。因此，当最小码距d05时，能够纠正2个错码，且最多能纠正2个。若错
14、码达到3个，就将落入另一圆上，从而发生错判。故一般说来，为纠正t个错码，最小码距应不小于(2t+1)。11.2 纠错编码基本原理纠错编码基本原理20p要纠正t个错码，同时检测e个错码，要求最小码距d0 e+t+1(e t)在解释此式之前，先来分析下图所示的例子。图中码组A和B之间距离为5。按照检错能力公式，最多能检测4个错码，即e=d0 1=5 1=4，按照纠错能力公式纠错时，能纠正2个错码。但是，不能同时作到两者，因为当错码位数超过纠错能力时，该码组立即进入另一码组的圆内而被错误地“纠正”了。例如，码组A若错了3位，就会被误认为码组B错了2位造成的结果，从而被错“纠”为B。这就是说，检错和纠
15、错公式不能同时成立或同时运用。11.2 纠错编码基本原理纠错编码基本原理ABe1tt汉明距离21所以，为了在可以纠正t个错码的同时，能够检测e个错码，就需要像下图所示那样，使某一码组（譬如码组A）发生e个错误之后所处的位置，与其他码组（譬如码组B）的纠错圆圈至少距离等于1，不然将落在该纠错圆上从而发生错误地“纠正”。因此，由此图可以直观看出，要求最小码距这种纠错和检错结合的工作方式简称纠检结合纠检结合。这种工作方式是自动在纠错和检错之间转换的。当错码数量少时，系统按前向纠错方式工作，以节省重发时间，提高传输效率；当错码数量多时，系统按反馈重发方式纠错，以降低系统的总误码率。所以，它适用于大多数
16、时间中错码数量很少，少数时间中错码数量多的情况。)(10teted11.2 纠错编码基本原理纠错编码基本原理2211.3 纠错编码的性能纠错编码的性能l11.3 纠错编码的性能纠错编码的性能n系统带宽和信噪比的关系：u由上节所述的纠错编码原理可知，为了减少接收错误码元数量，需要在发送信息码元序列中加入监督码元。这样作的结果使发送序列增长，冗余度增大。若仍须保持发送信息码元速率不变，则传输速率必须增大，因而增大了系统带宽。系统带宽的增大将引起系统中噪声功率增大，使信噪比下降。信噪比的下降反而又使系统接收码元序列中的错码增多。一般说来，采用纠错编码后，误码率总是能够得到很大改善的。改善的程度和所用
17、的编码有关。u例如，采用二进制传输某数字信号，误码率很大。若改用四进制传输，加以码率1/2的纠错编码，在同样的信道中，误码率可能就很小，在允许范围内。2311.3 纠错编码的性能纠错编码的性能u编码性能举例p未采用纠错编码时，若接收信噪比等于7dB，编码前误码率约为810-4，图中A点，在采用纠错编码后，误码率降至约410-5，图中B点。这样，不增大发送功率 就能降低误码率约一个半数量级。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)24p由图还可以看出，若保持误码率在10-5，图中C点，未采用编码时，约需要信噪比Eb/n0=10.5 dB。在采用这种编码时
18、，约需要信噪比7.5 dB，图中D点。可以节省功率2 dB。通常称这2 dB为编码增益。p上面两种情况付出的代价是带宽增大。10-610-510-410-310-210-1编码后PeCDEAB信噪比(dB)11.3 纠错编码的性能纠错编码的性能25n传输速率和Eb/n0的关系对于给定的传输系统式中，R 1为码率。若增加冗余，提高传输速率，则每bit等效能量(码位能量)降低，Ec/n0 Eb/n0。误码率公式中应用Ec/n0，误码率增大。假设系统原来工作在图中C点，提高速率后由C点升到E点。但加纠错编码后，仍可将误码率降到D点。这时付出的代价仍是带宽增大。传输速率的增加，并非一定要增大带宽，比如
19、采用多进制。采用多进制提高了信噪比要求；增大带宽，付出带宽、信噪比双重代价。纠错编码的作用在于：采用纠错编码所降低的信噪比要求，大于多进制所提高的信噪比要求。如QPSK调制采用1/2码率的纠错编码相同误码率需要的信噪比明显低于不编码的BPSK调制。000cbbEE k nREnnn11.3 纠错编码的性能纠错编码的性能2611.4 简单的实用编码简单的实用编码l11.4简单的实用编码简单的实用编码n11.4.1 奇偶校验码u奇偶校验码分为奇校验码和偶校验码两种，两者的原理相同。在偶校验码(常用)中，无论信息位多少，校验位只有1位，它使码组中“1”的数目为偶数，即满足下式条件：式中a0为校验位，
20、其他位为信息位。这种编码能够检测奇数个错码。在接收端，按照上式求“模2和”，若计算结果为“1”就说明存在错码，结果为“0”就认为无错码。奇校验码与偶校验码相似，只不过其码组中“1”的数目为奇数：0021aaann1021aaann2711.4 简单的实用编码简单的实用编码n11.4.2 二维奇偶校验码（方阵码）u二维奇偶校验码的构成它是先把上述奇偶监督码的若干码组排成矩阵，每一码组写成一行，然后再按列的方向增加第二维校验位，如下图所示图中a01 a02 a0m为m行奇偶校验码中的m个校验位。cn-1 cn-2 c1 c0为按列进行第二次编码所增加的校验位，它们构成了一校验位行。01210121
21、2021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn28u二维奇偶校验码的性能p这种编码检错能力较强。显然能检测奇数个错码，它也有可能检测偶数个错码。因为每行的监督位虽然不能用于检测本行中偶数个错码，但按列的方向有可能由cn-1 cn-2 c1 c0等校验位检测出来。p这种二维奇偶校验码适于检测突发错码。因为突发错码常常成串出现，随后有较长一段无错区间。p有一些偶数错码不可能检测出来。例如，构成矩形4角的4个错码，譬如图中错了，就检测不出。p二维奇偶校验码不仅可用来检错，还可以用来纠正一些错码。例如，仅在一行中有奇数个错码时。mmnnaaaa12212211
22、.4 简单的实用编码简单的实用编码29n 11.4.3 恒比码恒比码u在恒比码中，每个码组均含有相同数目的“1”（和“0”）。由于“1”的数目与“0”的数目之比保持恒定，故得此名。u这种码在检测时，只要计算接收码组中“1”的数目是否对，就知道有无错码。u恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。11.4 简单的实用编码简单的实用编码30n11.4.4 正反码正反码u正反码的编码：p它是一种简单的能够纠正错码的编码。其中的监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中“1”的个数而定。p
23、例如，若码长n=10，其中信息位 k=5，监督位 r=5。其编码规则为：当信息位中有奇数个“1”时，监督位是信息位的简单重复；当信息位有偶数个“1”时，监督位是信息位的反码。例如，若信息位为11001，则码组为1100111001；若信息位为10001，则码组为1000101110。11.4 简单的实用编码简单的实用编码31u正反码的解码p在上例中，先将接收码组中信息位和监督位按模 2 相加，得到一个5位的合成码组。然后，由此合成码组产生一个校验码组。p若接收码组的信息位中有奇数个“1”，则合成码组就是校验码组；若接收码组的信息位中有偶数个“1”，则取合成码组的反码作为校验码组。p最后，观察校
24、验码组中“1”的个数，按下表进行判决及纠正可能发现的错码。11.4 简单的实用编码简单的实用编码32p校验码组和错码的关系例如，若发送码组为1100111001，接收码组中无错码，则合成码组应为1100111001=00000。由于接收码组信息位中有奇数个“1”，所以校验码组就是00000。按上表判决，结论是无错码。校验码组的组成错码情况1全为“0”无错码2有4个“1”和1个“0”信息码中有1位错码，其位置对应校验码组中“0”的位置3有4个“0”和1个“1”监督码中有1位错码，其位置对应校验码组中“1”的位置4其他组成错码多于1个11.4 简单的实用编码简单的实用编码33若传输中产生了差错，使
25、接收码组变成1000111001，则合成码组为100011100101000。由于接收码组中信息位有偶数个“1”，所以校验码组应取合成码组的反码，即10111。由于其中有4个“1”和1个“0”，按上表判断信息位中左边第2位为错码。若接收码组错成1100101001，则合成码组变成110010100110000。由于接收码组中信息位有奇数个“1”，故校验码组就是10000，按上表判断，监督位中第1位为错码。最后，若接收码组为1001111001，则合成码组为100111100101010，校验码组与其相同，按上表判断，这时错码多于1个。p上述长度为10的正反码具有纠正1位错码的能力，并能检测全部
26、2位以下的错码和大部分2位以上的错码。11.4 简单的实用编码简单的实用编码3411.5 线性分组码线性分组码l11.5 线性分组码线性分组码n基本概念u代数码代数码：建立在代数学基础上的编码。u线性码线性码：在线性码中信息位和校验位是由一些线性代数方程联系着的。许用码字的线性组合仍然是许用码字。u线性分组码线性分组码：按照一组线性方程构成的分组码。本节将以汉明码为例引入线性分组码的一般原理。符号表示：一种码若码长是n，其中信息码有k位，称为(n,k)码，如(7,4)码。以下以(7,4)码为例。码向量 A=(a6,a5,a4,a3,a2,a1,a0)信息码向量 m=(a6,a5,a4,a3)接
27、收码向量B=(b6,b5,b4,b3,b2,b1,b0)35n汉明码汉明码能够纠正1位错码且编码效率较高的一种线性分组码u汉明码的构造原理。p在偶校验码中，由于使用了一位校验位a0，它和信息位an-1 a1一起构成一个代数式：在接收端解码时，实际上就是在计算它只能指示有错或无错。若S=0，就认为无错码；若S=1，就认为有错码。现将上式称为校验关系式校验关系式，S称为伴随式(校正校正子子)。由于伴随式S只有两种取值，故它只能代表有错和无错这两种信息，而不能指出错码的位置。1200nnaaa120nnSaaa11.5 线性分组码线性分组码36p若校验位增加一位，即变成两位，则能增加一个类似的校验关
28、系式。由于两个伴随式的可能值有4中组合：00，01，10，11，故能表示4种不同的信息。若用其中1种组合表示无错，则其余3种组合就有可能用来指示一个错码的3种不同位置。(r=2时，n=3，k=1。此码就是000，111。码率低不实用)同理，r个校验关系式能指示1位错码的(2r 1)个可能位置。p一般来说，若码长为n，信息位数为k，则校验位数rnk。如果希望用r个校验位构造出r个校验关系式来指示1位错码的n种可能位置，则要求取等号时，是典型的汉明码。2121rrnkr 或11.5 线性分组码线性分组码37p下面通过一个例子来说明如何具体构造这些校验关系式。p【例】设分组码分组码(n,k)中k=4
29、，为了纠正1位错码，由上式可知，要求校验位数 r 3。若取 r=3，则n=k+r=7。我们用a6 a5 a0表示这7个码元，用S1、S2和S3表示3个校验关系式中的伴随式，则S1、S2和S3的值与错码位置的对应关系可以规定如下表所列：S1 S2 S3错码位置S1 S2 S3错码位置001a0101a4010a1110a5100a2111a6011a3000无错码11.5 线性分组码线性分组码38由表中规定可见，仅当一位错码的位置在a2、a4、a5或a6时，伴随式S1为1；否则S1为零(其余码错与它无关)。这就意味着a2、a4、a5和a6四个码元构成偶校验关系：同理，a1、a3、a5和a6构成偶
30、校验关系：以及a0、a3、a4 和a6构成偶校验关系24561aaaaS13562aaaaS03463aaaaS11.5 线性分组码线性分组码39在发送端编码时，信息位a6、a5、a4和a3的值决定于输入信号，因此它们是随机的。校验位a2、a1和a0应根据信息位的取值按校验关系来确定，即校验位应使上3式中S1、S2和S3的值为0（表示编成的码组中应无错码）：上式经过移项运算，解出校验位给定信息位后，可以直接按上式算出校验位，结果见下表：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa11.5 线性分组码线性分组码40信息位a6 a5 a4
31、a3校验位a2 a1 a0信息位a6 a5 a4 a3校验位a2 a1 a0000000010001110001011100110000101011010010001111010110010100110110000101011011101010011001111101000111000111111111.5 线性分组码线性分组码41接收端收到每个码组后，先计算出S1、S2和S3，再查表判断错码情况。例如，若接收码组为0000011，按上述公式计算可得：S1=0，S2=1，S3=1。由于S1 S2 S3 等于011，故查表可知在a3位有1错码。p按照上述方法构造的码称为汉明码。表中所列的(7,4
32、)汉明码的最小码距d0=3。因此，这种码能够纠正1个错码或检测2个错码。由于码率R=k/n=(2r r 1)/(2r-1)，故当 r增大时，n增加更大，码率接近1。可见，汉明码是一种高效码。11.5 线性分组码线性分组码42n线性分组码的一般原理u线性分组码的构造pH矩阵上面(7,4)汉明码的例子有现在将上面它改写为上式中已经将“”简写成“+”。000034613562456aaaaaaaaaaaa010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa11.5 线性分组码线性分组码43上式可以表示成如下矩阵形式：上式
33、还可以简记为H AT=0T 或A HT=0010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa）（模20001011001110101011101000123456aaaaaaa11.5 线性分组码线性分组码44H AT=0T 或A HT=0式中 A=a6 a5 a4 a3 a2 a1 a00=000右上标“T”表示将矩阵转置。例如，HT是H的转置，即HT的第一行为H的第一列，HT的第二行为H的第二列等等。将H称为校验矩阵校验矩阵。只要校验矩阵H给定，编码时校验位和信息位的关系就完全确定了。101100111010
34、101110100H11.5 线性分组码线性分组码45H是 r n 阶矩阵。H的行数就是校验关系式的数目，它等于校验位的数目r。H的每行中“1”的位置表示相应码元之间存在的校验关系。例如，H的第一行1110100表示校验位a2是由a6 a5 a4之和决定的。H AT=0T若H矩阵可以分成两部分，例如 式中，P为r k阶矩阵，Ir为r r阶单位方阵。我们将具有HP Ir形式的H矩阵称为典型阵典型阵。rPIH00110110101101100111011.5 线性分组码线性分组码46H矩阵的性质：由代数理论可知，H矩阵的各行应该是线性无关的，否则将得不到 r个线性无关的校验关系式，从而也得不到 r
35、个独立的校验位。若一矩阵能写成典型阵形式P Ir，则其各行一定是线性无关的。因为容易验证Ir的各行是线性无关的，故P Ir的各行也是线性无关的。pG矩阵：上面汉明码例子中的校验位公式为也可以改写成矩阵形式：346035614562aaaaaaaaaaaa3456012101111011110aaaaaaa11.5 线性分组码线性分组码47或者写成式中，Q为一个k r阶矩阵，它为P的转置，即 Q=PT 上式表示，在信息位给定后，用信息位的行矩阵乘矩阵Q就产生出校验位。6251403111011011011aaaaaaa21065436543111110101011a a aa a a aa a
36、a aQ11.5 线性分组码线性分组码48如果信息码置于校验码之前，我们称之为系统码系统码。将Q的左边加上1个k k阶单位方阵，就构成1个矩阵G G称为生成矩阵生成矩阵，它是k n阶矩阵。由它可以产生整个码组，即或者因此，如果找到了码的生成矩阵G，则编码的方法就完全确定了。具有GIkQ形式的生成矩阵称为典型生成矩阵典型生成矩阵。由典型生成矩阵得出的码组A中，信息位不变，校验位附加于其后，即为系统码。Q=PT 0110001101001011001001111000QGkI I G34560123456aaaaaaaaaaamAG11.5 线性分组码线性分组码49G矩阵的性质：1)G矩阵的各行是
37、线性无关的。因为由上式可以看出，任一码组A都是G的各行的线性组合。G共有k行，若它们线性无关，则可以组合出2k种不同的码组A，它恰是有k位信息位的全部许用码组。若G的各行有线性相关的，则不可能由G生成2k种不同的码组了。2)实际上，G的各行本身就是一个码组。因此，如果已有k个线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。11.5 线性分组码线性分组码50p错码向量和错误图样 一般说来，A为一个n列的行向量。此向量的n个元素就是码组中的n个码元，所以发送的码组就是A。此码组在传输中可能由于干扰引入差错，故接收码组一般说来与A不一定相同。若设接收码组为一n列的行向量B，即则发送码组
38、和接收码组之差为B A=E(模2)它就是传输中产生的错码行向量错码行向量 式中0121bbbbnnB0121eeeennEiiiiiababe当当,1,011.5 线性分组码线性分组码51因此，若ei=0，表示该接收码元无错；若ei=1，则表示该接收码元有错。B A=E 可以改写成 B=A+E例如，若发送码组A=1000111，错码向量E=0000100，则接收码组B=1000011。错码矩阵有时也称为错误图样错误图样。?11.5 线性分组码线性分组码52p伴随式S当接收码组有错时，E 0，将B当作A代入公式(A H T=0)后，该式不一定成立。在错码较多，已超过这种编码的检错能力时，B变为另
39、一许用码组，则该式仍能成立。这样的错码是不可检测的。在未超过检错能力时，上式不成立，即其右端不等于0。假设这时该式的右端为S，即B H T=S将B=A+E代入上式，可得S=(A+E)H T=A H T+E H T由于A HT=0，所以S=E H T式中S称为伴随式。它能用来指示错码的位置。S和错码E之间有确定的线性变换关系。若S和E之间一一对应，则S将能代表错码的位置。11.5 线性分组码线性分组码53u线性分组码的性质p封闭性封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。这就是说，若A1和A2是一种线性码中的两个许用码组，则(A1+A2)仍为其中的一个码组。这一性质的证明
40、很简单。若A1和A2是两个码组，则有A1 HT=0,A2 HT=0将上两式相加，得出A1 HT+A2 HT=(A1+A2)HT=0所以(A1+A2)也是一个码组。由于线性码具有封闭性，所以两个码组(A1和A2)之间的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即“1”的数目）。因此，码的最小距离就是码的最小重量（除全“0”码组外）。11.5 线性分组码线性分组码54第11章差错控制编码l11.6 循环码循环码n11.6.1 循环码原理u循环性循环性：循环性是指任一码组循环一位（即将最右端的一个码元移至左端，或反之）以后，仍为该码中的一个码组。在下表中给出一种(7,3)循环码
41、的全部码组。例如，表中的第2码组向右移一位即得到第5码组；第6码组向右移一位即得到第7码组。码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a0100000005100101120010111610111003010111071100101401110018111001055第11章差错控制编码一般说来，若(an-1 an-2 a0)是循环码的一个码组，则循环移位后的码组(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a0 an-1 a2 a1)也是该编码中的码组。56第11章差错控制编码u码多项式p码组的多项式表示
42、法把码组中各码元当作是一个多项式的系数，即把一个长度为n的码组表示成例如，上表中的任意一个码组可以表示为其中第7个码组可以表示为这种多项式中，x仅是码元位置的标记，例如上式表示第7码组中a6、a5、a2和a0为“1”，其他均为0。因此我们并不关心x的取值。012211)(axaxaxaxTnnnn012233445566)(axaxaxaxaxaxaxT11010011)(25623456xxxxxxxxxxT57第11章差错控制编码p 码多项式的按模运算在整数运算中，有模n运算。例如，在模2运算中，有1+1=2 0 (模2)，1+2=3 1 (模2)，2 3=6 0 (模2)等等。一般说来，
43、若一个整数m可以表示为式中，Q 整数，则在模 n 运算下，有m p (模n)即，在模 n 运算下，一个整数m等于它被 n 除得的余数。npnpQnm,58第11章差错控制编码在码多项式运算中也有类似的按模运算。若一任意多项式F(x)被一 n 次多项式N(x)除，得到商式Q(x)和一个次数小于n的余式R(x)，即则写为这时，码多项式系数仍按模2 运算，即系数只取 0 和1。例如，x3被(x3+1)除，得到余项1。所以有同理因为)()()()(xRxQxNxF）（模)()()(xNxRxF）（模)1(133xx）（模)1(113224xxxxx xx3+1 x4+x2+1 x4+x x2+x+1应
44、当注意，由于在模2运算中，用加法代替了减法，故余项不是x2 x+1，而是x2+x+1。59第11章差错控制编码u循环码的码多项式p在循环码中，若T(x)是一个长为n的许用码组，则xiT(x)在按模xn+1运算下，也是该编码中的一个许用码组，即若则T(x)也是该编码中的一个许用码组。【证】因为若则（模(xn+1)）所以，这时有）（模)1()()(nixxTxTx012211)(axaxaxaxTnnnnininininniniinininninniaxaxaxaxaxaxaxaxaxaxTx1102211011112211)(ininininninaxaxaxaxaxT1102211)(60第1
45、1章差错控制编码上式中T(x)正是T(x)代表的码组向左循环移位i次的结果。因为原已假定T(x)是循环码的一个码组，所以T(x)也必为该码中一个码组。例如，循环码组其码长n=7。现给定i=3，则其对应的码组为0101110，它正是表中第3码组。由上述分析可见，一个长为n的循环码必定为按模(xn+1)运算的一个余式。ininininninaxaxaxaxaxT1102211)(1)(256xxxxT）（模)1()1()(7235358925633xxxxxxxxxxxxxxTx61第11章差错控制编码u循环码的生成矩阵Gp由上节中公式可知，有了生成矩阵G，就可以由k个信息位得出整个码组，而且生成
46、矩阵G的每一行都是一个码组。例如，在此式中，若a6a5a4a3=1000，则码组A就等于G的第一行；若a6a5a4a3=0100，则码组A就等于G的第二行；等等。由于G是k行n列的矩阵，因此若能找到k个已知码组，就能构成矩阵G。如前所述，这k个已知码组必须是线性不相关的，否则给定的信息位与编出的码组就不是一一对应的。p在循环码中，一个(n,k)码有2k个不同的码组。若用g(x)表示其中前(k-1)位皆为“0”的码组，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且这k个码组是线性无关的。因此它们可以用来构成此循环码的生成矩阵G。GA3456aaaa62第11章差错控制
47、编码p在循环码中除全“0”码组外，再没有连续k位均为“0”的码组，即连“0”的长度最多只能有(k-1)位。否则，在经过若干次循环移位后将得到一个k位信息位全为“0”，但监督位不全为“0”的一个码组。这在线性码中显然是不可能的。因此，g(x)必须是一个常数项不为“0”的(n-k)次多项式，而且这个g(x)还是这种(n,k)码中次数为(n k)的唯一多项式。因为如果有两个，则由码的封闭性，把这两个相加也应该是一个码组，且此码组多项式的次数将小于(n k)，即连续“0”的个数多于(k 1)。显然，这是与前面的结论矛盾的，故是不可能的。我们称这唯一的(n k)次多项式g(x)为码的生成多项式。一旦确定
48、了g(x)，则整个(n,k)循环码就被确定了。63第11章差错控制编码p因此，循环码的生成矩阵G可以写成 p例：在上表所给出的(7,3)循环码中，n=7,k=3,n k=4。由此表可见，唯一的一个(n k)=4次码多项式代表的码组是第二码组0010111，与它相对应的码多项式（即生成多项式）g(x)=x4+x2+x+1。将此g(x)代入上式，得到或)()()()()(21xgxxgxgxxgxxkkG)()()()(2xgxxgxgxxG001011101011101011100)(xG64第11章差错控制编码由于上式不符合G=IkQ的形式，所以它不是典型阵。不过，将它作线性变换，不难化成典型
49、阵。我们可以写出此循环码组，即上式表明，所有码多项式T(x)都可被g(x)整除，而且任意一个次数不大于(k 1)的多项式乘g(x)都是码多项式。需要说明一点，两个矩阵相乘的结果应该仍是一个矩阵。上式中两个矩阵相乘的乘积是只有一个元素的一阶矩阵，这个元素就是T(x)。为了简洁，式中直接将乘积写为此元素。)()()()()()()()()()(452645262456456xgaxaxaxgaxxgaxgxaxgxxgxgxaaaxaaaxTG65第11章差错控制编码u如何寻找任一(n,k)循环码的生成多项式 由上式可知，任一循环码多项式T(x)都是g(x)的倍式，故它可以写成T(x)=h(x)g
50、(x)而生成多项式g(x)本身也是一个码组，即有 T(x)=g(x)由于码组T(x)是一个(n k)次多项式，故xk T(x)是一个n次多项式。由下式可知，xk T(x)在模(xn+1)运算下也是一个码组，故可以写成）（模)1()()(nixxTxTx1)()(1)(nnkxxTxQxxTx66第11章差错控制编码上式左端分子和分母都是n次多项式，故商式Q(x)=1。因此，上式可以化成将T(x)和T(x)表示式代入上式，经过化简后得到上式表明，生成多项式g(x)应该是(xn+1)的一个因子。这一结论为我们寻找循环码的生成多项式指出了一条道路，即循环码的生成多项式应该是(xn+1)的一个(n k
