1、11.1 概述概述11.2 纠错编码的基本原理纠错编码的基本原理11.3 纠错编码的性能纠错编码的性能11.4 简单的实用编码简单的实用编码11.5 线性分组码线性分组码11.6 循环码循环码11.7 卷积码卷积码11.8 Turbo码码 11.9 低密度奇偶校验码低密度奇偶校验码11.10 网格编码调制网格编码调制11.1 概述一、按照加性干扰引起的一、按照加性干扰引起的错码分布错码分布规律的不同规律的不同信信道道随机随机信道信道(random channel)突发突发信道信道(burst channel)混合混合信道信道(mixed channel)错码错码的出现是的出现是随机随机的，的，
2、而且错码之间是统计而且错码之间是统计独立独立的。的。例例由正态分布白噪声引起的错码由正态分布白噪声引起的错码 错码错码是是成串成串集中出现的，集中出现的，即在一些短促的时间段内会出现大量错码，即在一些短促的时间段内会出现大量错码，而在这些短促的时间段之间存在较长的无错而在这些短促的时间段之间存在较长的无错码区间。码区间。成串成串出现的错码称为出现的错码称为突发错码突发错码。主要原因：主要原因：脉冲干扰脉冲干扰，【例】电火花，【例】电火花 信道中的信道中的衰落衰落现象。现象。既存在既存在随机随机错码又存在错码又存在突发突发错码错码二、二、差错控制技术差错控制技术 (1)检错检错(error de
3、tection)重发重发(retransmission)：在发送码元序列进行在发送码元序列进行检错检错编码，编码，接收端检测接收端检测有有无无错码，错码，利用利用反向信道反向信道通知发送端，通知发送端，有错有错时发送端时发送端重发重发，直到正确接收为止。直到正确接收为止。(2)前向纠错前向纠错(Forward Error Correction,FEC):在发送码元序列进行在发送码元序列进行纠错纠错编码，编码，这时接收端能将错码恢复其正确取值。这时接收端能将错码恢复其正确取值。不不需要需要反向反向信道，信道，也没有时延，故也没有时延，故实时性实时性好。好。设备要比检测重发设备复杂。设备要比检测重
4、发设备复杂。(3)反馈反馈(feedback)校验校验(checkout)：在发送在发送不不用用编码编码，接收端将接收到的码元原封不动地接收端将接收到的码元原封不动地转发回转发回发送端。发送端。在发送端将它和原发送码元比较。在发送端将它和原发送码元比较。若发现有若发现有不同不同，就认为接收端收到的序列中就认为接收端收到的序列中有错码有错码，发送端立即发送端立即重发重发。原理和设备都很简单。原理和设备都很简单。但是需要但是需要双向信道双向信道，传输效率也较低，每个码元都需要占用两次传输时间。传输效率也较低，每个码元都需要占用两次传输时间。(4)检错删除检错删除(deletion)：它和它和检错重
5、发检错重发的区别的区别在于在于，在接收端发现错码后，在接收端发现错码后，立即将其删除，立即将其删除，不不要求要求重发重发。在发送端需要在信息码元序列中增加差错控制码元，在发送端需要在信息码元序列中增加差错控制码元，称为称为监督监督(cheek)码元。码元。这些这些监督码元监督码元和和信息码元信息码元之间有之间有确定确定的关系，的关系，使接收端有可能利用这种关系使接收端有可能利用这种关系发现发现或或纠正纠正可能存在的可能存在的错码错码。设编码序列中信息码元数量为设编码序列中信息码元数量为k，总码元数量为总码元数量为n，则，则编码效率编码效率(码率）为码率）为k/n；冗余度冗余度(redundan
6、cy)为为(n-k)/n三、三、ARQARQ系统系统 采用检错重发法的通信系统通常称为采用检错重发法的通信系统通常称为自动要求重发自动要求重发(Automatic Repeat reQuest，ARQ)系统。系统。11.2 纠错编码的基本原理许用码组许用码组000、011、101、110禁用码组禁用码组001、010、100、111一、一、“分组码分组码”的一般概念的一般概念 将将信息码信息码分组，分组，为每组信码附加若干为每组信码附加若干监督码监督码的编码称为分组码的编码称为分组码(block code)。监督码元监督码元仅仅监督监督本码组本码组中的信息码元。中的信息码元。(n,k)分组码分
7、组码，n称为称为码组码组的长度的长度(码长码长)，k是码组中是码组中信息码元信息码元的数目，的数目，n-k=r为码组中的为码组中的监督码元监督码元数目，或称监督位数目。数目，或称监督位数目。把码组中把码组中“1”的的个数个数目称为码组的重量，简称目称为码组的重量，简称码重码重(cod weight)。把把两个两个码组中对应位上数字码组中对应位上数字不同不同的的位数位数称为称为码组的距离码组的距离，简称，简称码码距距,码距又称汉明距离。码距又称汉明距离。把某种把某种编码编码中各个码组之间中各个码组之间距离距离的的最小值最小值称为称为最小码距最小码距(d0)。3位的编码组位的编码组码距就对应于各顶
8、点之间码距就对应于各顶点之间沿沿立方体立方体各边各边行走的几何距离。行走的几何距离。4个准用码组之间的距离均为个准用码组之间的距离均为2。二、检错和纠错能力：二、检错和纠错能力：(1)为为检测检测e个错码，个错码，要求要求最小码距最小码距：10 ed (2)为为纠正纠正t个错码，个错码，要求要求最小码距最小码距：120 td (3)为为纠正纠正t个错码，同时个错码，同时检测检测e个错码个错码要求要求最小码距最小码距：10ted11.3 纠错编码的性能1)若接收若接收信噪比信噪比保持保持等于等于7dB，在编码前误码率约等于在编码前误码率约等于810-4(图中图中A点点)，在采用纠错编码后，误码率
9、降至约在采用纠错编码后，误码率降至约410-5(图中图中B点点)。不用增大发送功率就能降低误码率约一个半数量级。不用增大发送功率就能降低误码率约一个半数量级。2)若保持若保持误码率误码率在在10-5不变，不变，未采用编码时，约需要信噪比未采用编码时，约需要信噪比9.5dB(图中图中C点点)。在采用编码时，约需要信噪比在采用编码时，约需要信噪比7.5dB(图中图中D点点)。节省功率节省功率2dB。通常称这。通常称这2dB为编码增益。为编码增益。上面两种情况付出的代价是上面两种情况付出的代价是带宽带宽增大。增大。0nEb0nTPs)/1(0TnPsBsRnP0若希望若希望提高提高传输速率传输速率R
10、B，势必使信噪比势必使信噪比下降下降，误码率误码率增大增大。假设系统原来工作在图中假设系统原来工作在图中C点，点，提高速率后由提高速率后由C点升到点升到E点。点。加用纠错编码后，加用纠错编码后，仍可以将误码率降到原来的水平仍可以将误码率降到原来的水平(D点点)。这时付出的代价仍是这时付出的代价仍是带宽增大带宽增大。11.4 简单的实用编码11.4.1奇偶监督码奇偶监督码 监督位监督位只有只有1位位 1)偶数偶数监督码监督码使码组中使码组中“1”的数目为的数目为偶数偶数0021aaann121,aaann为为信息位信息位;0a为为监督位监督位;能够检测能够检测奇数奇数个个错码错码。2)奇数奇数监
11、督码监督码码组中码组中“1”的数目为的数目为奇数奇数1021aaann11.4.211.4.2二维奇偶监督码二维奇偶监督码(方阵码方阵码)把奇偶监督码的若干码组排列成矩阵，把奇偶监督码的若干码组排列成矩阵，每一码组写成一每一码组写成一行行 再按列的方向增加第二维再按列的方向增加第二维监督位监督位.012101212021222110111211ccccaaaaaaaaaaaannmmmnmnnnnn 能够检测能够检测奇奇数个错码数个错码;有可能检测有可能检测偶偶数个错误。有一些偶数错码不可能检测出数个错误。有一些偶数错码不可能检测出(如如构成矩形的构成矩形的4 4个错码就检测不出个错码就检测不
12、出););适于检测适于检测突发错码突发错码。不仅可用来不仅可用来检错检错，还可用来，还可用来纠正纠正一些错码。一些错码。11.4.3 恒比码恒比码 每个码组均含有每个码组均含有相同相同数目的数目的“1”(和和“0”)主要优点是简单和适于用来传输电传机或其他键盘设备产生主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。的字母和符号。对于信源来的二进随机数字序列，这种码就不适合使用了。对于信源来的二进随机数字序列，这种码就不适合使用了。11.4.4 正反码正反码 能够能够纠正纠正错码的编码错码的编码监督位数目与信息位数目相同监督位数目与信息位数目相同.例例码长码长n10，信息位，信
13、息位k=5，监督位，监督位r=5.编码编码规则为：规则为：（1）当）当信息位信息位有有奇奇数个数个“1”时，监督位是信息位的时，监督位是信息位的重复重复；（2）当）当信息位信息位有有偶偶数个数个“1”时，监督位是信息位的时，监督位是信息位的反码反码。例如，若信息位为例如，若信息位为11001，则码组为，则码组为1100111001；若信息位为若信息位为10001，则码组为，则码组为1000101110。接收端接收端解码解码的方法为：的方法为：(1)将接收码组中信息位和监督位按将接收码组中信息位和监督位按位位模模2相加，得到一个相加，得到一个5位位的的合成码组合成码组；(2)若接收码组的若接收码
14、组的信息位信息位中有中有奇奇数个数个“1”，则合成码组就是，则合成码组就是校验码校验码组组；若接收码组的若接收码组的信息位信息位中有中有偶偶数个数个“1”，则取合成码组的，则取合成码组的反反码作码作为为校验码组校验码组。观察校验码组中观察校验码组中“1”的个数，按表判决及纠正可能发现的的个数，按表判决及纠正可能发现的错码错码。a)发送发送码组为码组为1100111001，接收码组接收码组中中无错无错码码则则合成码组合成码组应为应为00000由于接收码组信息位中有由于接收码组信息位中有奇奇数个数个“1”，校验码组校验码组就是就是00000。按表判决，按表判决，无无错码。错码。b)若接收码组成若接
15、收码组成1000111001，则则合成码组合成码组为为01000由于接收码组中信息位有由于接收码组中信息位有偶偶数个数个“1”，校验码组校验码组取合成码组的取合成码组的反码反码，即，即10111。由于其中有由于其中有4个个“1”，1个个“0”，按表判断，按表判断信息位信息位中左边第中左边第二二位位为为错错码。码。c)若接收码组成若接收码组成1100101001，则则合成码组合成码组为为10000由于接收码组中信息位有由于接收码组中信息位有奇奇数个数个“1”，校验码组校验码组就是就是10000。由于其中有由于其中有4个个“0”，1个个“1”，按表判断，按表判断监督码监督码中左边第中左边第一一位位
16、为为错错码。码。d)若若接收码组接收码组成成1001111001，则则合成码组合成码组为为01010由于接收码组中信息位有由于接收码组中信息位有奇奇数个数个“1”，校验码组校验码组就是就是01010。按表判断按表判断错错码多于码多于1个。个。长度为长度为10的正反码具有的正反码具有纠正纠正1位错码的能力，位错码的能力，并能并能检测检测全部全部2位位以下以下的错码和大部分的错码和大部分2位位以上以上的错码。的错码。11.5 线性分组码 在线性码中信息位和监督位是由一些在线性码中信息位和监督位是由一些线性线性代数方程联系着代数方程联系着 1.汉明汉明（Hamming）码码的构造原理。的构造原理。汉
17、明码是一种能够汉明码是一种能够纠纠正正一一位位错错码且编码码且编码效率效率较较高高的线性分组码。的线性分组码。偶数偶数监督码监督码的一位监督位和信息位构成一个代数式的一位监督位和信息位构成一个代数式 在在接收端接收端解码时计算解码时计算021aaaSnn有错无错,1,0监督关系监督关系式，式，S称为称为校正子校正子。(1)r与与n的关系的关系 1)一一位位S的取值只有这样的取值只有这样两两种，种，只能代表只能代表有有错和错和无无错，错，不不能指出错码的能指出错码的位位置。置。2)两两个校正子的可能值有个校正子的可能值有4种不同信息。种不同信息。若用其一表示若用其一表示无无错，则其余错，则其余3
18、种用来指示种用来指示一位错一位错码的码的3种种不同不同位置。位置。3)r个监督关系式个监督关系式,能指示能指示一位错码一位错码的的2r-1个可能位置。个可能位置。nr1212rkr或 (2)如何具体构造这些监督关系式如何具体构造这些监督关系式 设分组码设分组码(n,k)中中k=4.为了为了纠纠正正一一位错码。监督位数位错码。监督位数r3,若取若取 r 3，则，则 n k r 7。规定规定校正子校正子的值与错码的值与错码位位置的对应关系如下：置的对应关系如下：0123456aaaaaaa码组 1)仅当仅当一一错码位置在错码位置在a2,a4,a5 或或a6时，校正子时，校正子S1=1；否则；否则S
19、1=024561aaaaS 2)仅当仅当一一错码位置在错码位置在a1,a3,a5 或或a6时，校正子时，校正子S2=1；否则；否则S2=013562aaaaS 3)仅当仅当一一错码位置在错码位置在a0,a3,a4 或或a6时，校正子时，校正子S3=1；否则；否则S3=003463aaaaS (3)发送端编码发送端编码监督位使监督位使S1，S2，S3的值为的值为零零（表示编成的码组中应无错码）（表示编成的码组中应无错码）02456aaaa01356aaaa00346aaaa(11.5-6)解出监督位解出监督位4562aaaa3561aaaa3460aaaa(11.5-7)若接收码组为若接收码组为
20、0000011计算可得计算可得校正子校正子024561aaaaS113562aaaaS103463aaaaS表表114可知在可知在a3位有一错码。位有一错码。线性分组码满足线性分组码满足封闭性封闭性.表表11-5中所列的中所列的(7,4)汉明码的汉明码的最小码距最小码距d0=3，能能纠正纠正一个错码或检测两个错码。一个错码或检测两个错码。汉明码的编码效率汉明码的编码效率nk/nrn/)(nr/1当当n很大时，则编码效率接近很大时，则编码效率接近1。汉明码是一种汉明码是一种高高效码。效码。2.线性分组码的一般原理线性分组码的一般原理式式(11.5-6)改写改写000101110123456aaa
21、aaaa001010110123456aaaaaaa010011010123456aaaaaaa模模2加法加法0001001101010101100101110123456aaaaaaa简记为TTAH0其中100110101010110010111H 0123456aaaaaaaA 0 0 00将将H称为称为监督矩阵监督矩阵。H的的行行数就是监督位的数目数就是监督位的数目r。H是是rn矩阵矩阵.3.系统系统线性分组码的线性分组码的编码编码的方法的方法100110101010110010111H0THA或 rIP110110110111krP100010001rrrI具有具有PIr形式的形式的H
22、称为典型称为典型监督矩阵监督矩阵。式式(11.5-7)改写成改写成3456012110110110111aaaaaaa 1101010111113456012aaaaaaa Qaaaa3456TrkPQ码的码的生成矩阵生成矩阵 QIGknk1101000101010001100101110001由生成矩阵产生整个码组由生成矩阵产生整个码组34560123456GaaaaaaaaaaaA具有具有IkQ形式的形式的G称为典型生成矩阵。称为典型生成矩阵。典型生成矩阵得出的码组典型生成矩阵得出的码组A为为系统码系统码。要求要求G矩阵的矩阵的k行是线性行是线性无关无关的。的。任一码组任一码组A都是都是G
23、的各行的的各行的线性组合线性组合。可组合出可组合出2k种不同的码组种不同的码组A，恰是有恰是有k位位信息位信息位的全部码组；的全部码组；4.线性分组码的线性分组码的译码译码的方法的方法线性分组码线性分组码(n,k)，发送发送的码组的码组021aaaAnn接收接收码组为码组为021bbbBnn发送码组和接收码组之发送码组和接收码组之差差EBA传输中产生的传输中产生的错错码行矩阵码行矩阵(错误图样错误图样)021eeeEnn)(,1)(,0该位接收码元有错当该位接收码元无错当iiiiibabaeEAB校正子THBS若若S和和E之间一一对应，则之间一一对应，则S将能代表将能代表错码错码的的位置位置。
24、TTHEHATHE 封闭性封闭性：是指一种线性码中的任意两个码组之和仍为这种码中的一个码是指一种线性码中的任意两个码组之和仍为这种码中的一个码组。组。两个码组之间的两个码组之间的距离距离必是另一码组的必是另一码组的重量重量。故码的最小距离即是码的故码的最小距离即是码的最小重量最小重量（除全（除全“0”码组外）。码组外）。951循环码原理循环码原理 是是一种一种线性分组码线性分组码中。中。具有具有循环性循环性:循环码中任一码组循环一位以后，仍为该码中的一个码组。循环码中任一码组循环一位以后，仍为该码中的一个码组。码组中各码元当作是一个码组中各码元当作是一个多项式多项式的的系数系数，即把一长为即把
25、一长为n的码组表示成的码组表示成012211)(axaxaxaxTnnnn第第7 7码码组可以表示为组可以表示为1)(2567xxxxT这种多项式有时称为这种多项式有时称为码多项式码多项式。1.码多项式的按码多项式的按模模运算运算 整数运算中，有模整数运算中，有模n运算。若一整数运算。若一整数m可以表示为可以表示为npnpQnm,在模在模n运算下，一整数运算下，一整数m等于其被等于其被n除得之余数。除得之余数。)(npm模若一任意多项式若一任意多项式F(x)被一被一n次多项式次多项式N(x)除，得到商式除，得到商式Q(x)和一和一个次数个次数小小于于n的余式的余式R(x)()()()(xRxQ
26、xNxF)()()(xNxRxF模1 24xx13xxxx 412xx)1(1 1 3224xxxxx模在在(n,k)循环码中，若循环码中，若T(x)是一个是一个许用码组许用码组，)1()()(nixxTxTx模设012211)(axaxaxaxTnnnn)1()(11011110111111nininiininiininnininnixaxaxaxaxaxaxaxaxaxaxTx模)(1101111ininiininaxaxaxaxaxT还是一个还是一个许用码组许用码组。)()(xTxT是的码组向的码组向左左循环移位循环移位i次的结果。次的结果。表表11-5中中第第7码组。码组。1)(256
27、xxxxT3,7in)1()(2563xxxxxTxi3589xxxx)1(7235xxxxx模对应的码组为对应的码组为0101110，正是第，正是第3码组。码组。2循环码的循环码的生成矩阵生成矩阵G 在在(n,k)循环码中，循环码中，用用g(x)表示其中前表示其中前k-1位皆为位皆为“0”的码组的码组.g(x)唯一的次数为唯一的次数为(n k)次次,必须是一个必须是一个常数项常数项不为不为“0”多项式多项式.称这唯一的称这唯一的(n k)次多项式次多项式g(x)为码的为码的生成多项式生成多项式。一旦确定了一旦确定了g(x)，则整个，则整个(n,k)循环码就被确定了。循环码就被确定了。g(x)
28、，x g(x)，x2 g(x)，xk-1 g(x)是是k个线性无关的码组个线性无关的码组.循环码的循环码的生成矩阵生成矩阵G)()()()()(21xgxxgxgxxgxxGkk例例表表 11-5所给出的循环码中所给出的循环码中,对应的生成多项式为对应的生成多项式为1)(24xxxxg1)()()()(2423523462xxxxxxxxxxxxgxxgxgxxG111010001110100011101G此生成矩阵此生成矩阵不不是典型的。是典型的。此循环码组此循环码组)()(456xGaaaxT)()()(2456xgxxgxgxaaa)()()(4526xgaxxgaxgxa)()(452
29、6xgaxaxa 所有码多项式所有码多项式T(x)都可被都可被g(x)整除整除，任一次数任一次数不大于不大于(k-1)的多项式乘的多项式乘g(x)都是都是码多项式码多项式。3如何寻找任一如何寻找任一(n,k)循环码的循环码的生成多项式生成多项式 任一循环码多项式任一循环码多项式T(x)为为)()()(xgxhxTg(x)也是一个也是一个码组码组，)()(xgxT为为(n k)次次多项式。多项式。)(xTxk为为n 次多项式。次多项式。1)(11)(nnkxxTxxTx)(1)(xTxxTxnkT(x)一定是一个一定是一个码组码组),()()(xgxhxT有)()(1xgxhxxkng(x)是是
30、(xn+1)的一个的一个因式因式。g(x)是是(xn+1)的一个的一个(n k)次因式。次因式。例例(x7+1)可以分解为可以分解为)1)(1)(1(13237xxxxxx 为了求为了求(7,3)循环码的生成多项式循环码的生成多项式g(x)，要找到一个要找到一个(n k)=4次的因子。次的因子。1)1)(1(2423xxxxxx1)1)(1(2343xxxxxx选用的生成多项式不同，选用的生成多项式不同，产生出的循环码码组也不同。产生出的循环码码组也不同。表表11115 5生成生成多项式多项式为为1)(24xxxxg9.5.2 循环码的编、解码方法循环码的编、解码方法 1.系统系统循环码的编码
31、方法循环码的编码方法(n,k)循环码的循环码的信息码多项式信息码多项式为为m(x),m(x)次数小于次数小于k.编码步骤：编码步骤：(1)用用xn-k乘乘m(x)。(2)用用g(x)除除xn-km(x)，得到，得到商商Q(x)和和余式余式r(x)，)()(xgxmxkn)()()(xgxrxQ(3)编出的编出的码组码组T(x)为为)()()(xrxmxxTkn例例(7,3)循环码循环码,信息码为信息码为110，生成多项式为，生成多项式为1)(24xxxxg求相应的求相应的码组。码组。2循环码的循环码的解码解码方法方法 (1)检错检错解码原理解码原理在接收端可以将接收码组在接收端可以将接收码组R
32、(x)()()()()(xgxrxQxgxRa)若余式若余式0)(xr传输中传输中未未发生错误，发送码组为发生错误，发送码组为)()(xRxTb)若余式若余式0)(xr传输中发生错误，发送码组为传输中发生错误，发送码组为)()(xRxT (2)纠错纠错解码原理解码原理接收码组接收码组)()()(xExTxR)()()()()()(xgxExgxTxgxR)()()(xgxrxq)()()()()(xgxrxpxgxE余式相同。余式相同。每个每个可可纠正的错误图样必须与一个纠正的错误图样必须与一个特定余式特定余式有一一对应关系。有一一对应关系。从上述余式从上述余式唯一唯一地决定错误图样，地决定错
33、误图样，从而从而纠正纠正错码。错码。纠错步骤纠错步骤:(l)用用g(x)除接收码组除接收码组R(x)=T(x)+E(x)，得出余式，得出余式r(x)；(2)按余式按余式r(x)，用查表的方法或通过某种计算得到错误图样用查表的方法或通过某种计算得到错误图样E(x);(3)原发送码组原发送码组T(x)=R(x)+E(x).这种解码方法称为这种解码方法称为捕错解码法捕错解码法。还有还有大数逻辑解码大数逻辑解码等算法。等算法。11.6.3截短循环码截短循环码 在设计纠错编码方案时，在设计纠错编码方案时，信息信息位数位数k、码长码长n和和纠错能力纠错能力都是都是预先预先给定的。给定的。并并不一定不一定有
34、恰好满足这些条件的有恰好满足这些条件的循环码循环码存在。存在。设设(n,k)循环码循环码，它共有，它共有2k种码组，种码组，现使其前现使其前i(0ik)个信息位个信息位全为全为“0”，然后从中然后从中删去删去这这i位全位全“0”的信息位，的信息位，于是它变成于是它变成仅仅有有2k-i种码组。种码组。最终得到一个最终得到一个(n-i,k-i)的线性码。的线性码。将这种码称为将这种码称为截短循环码截短循环码(truncated cyclic code)。截短循环码与截短前的循环码截短循环码与截短前的循环码至少至少具有具有相同相同的的纠错纠错能力，能力，并且截短循环码的编解码方法仍和截短前的方法一样
35、。并且截短循环码的编解码方法仍和截短前的方法一样。例例原原(15,11)循环码能够纠正循环码能够纠正1位错码，位错码，从从211种码组中选出种码组中选出前两前两信息位均为信息位均为“0”的码组，的码组，构成一个新构成一个新(13,9)截短循环码截短循环码。此此(13,9)截短循环码截短循环码，也能够纠正，也能够纠正1位错码。位错码。11.6.4 BCH码码 BCH码能够纠正码能够纠正多个多个错码的循环码，错码的循环码，它是以它是以3位发明这种码的人名位发明这种码的人名(Bose，Chaudhuri，Hocguenghem)命名的。命名的。BCH码码本原本原BCH码码非本原非本原BCH码码g(x
36、)中含有中含有最高最高次数为次数为m的的本原多项式本原多项式，且且码长码长为为n=2m-1，(m3，为正整数，为正整数)g(x)中不含有这种中不含有这种本原多项式本原多项式，且且码长码长为为n是2m-1的一个的一个因子因子P348生成多项生成多项式系数是式系数是八进制八进制数数字字P349 BCH码的码的码长码长n与与监督位监督位、纠错个数纠错个数 t之间的关系：之间的关系：对于正整数对于正整数m(m3)和正整数和正整数tm/2，a)必定存在一个必定存在一个码长码长为为n=2m-1，监督位监督位为为n-k1，且除得尽，且除得尽(2m-1)，则为非本原则为非本原BCH码。码。生成多项式系数是生成
37、多项式系数是八进制八进制数字数字 1)具有具有循环循环性质的性质的汉明码汉明码就是能纠正单个随机错误的就是能纠正单个随机错误的本原本原BCH码。码。2)在在表表11-7中的中的(23,12)码称为码称为戈莱戈莱(Golay)码。码。它能纠正三个随机错码，它能纠正三个随机错码，并且容易解码，实际应用较多。并且容易解码，实际应用较多。3)BCH码的长度都为奇数。码的长度都为奇数。为了得到偶数长度的码，并增大检错能力，为了得到偶数长度的码，并增大检错能力，可以在可以在BCH码生成多项式中码生成多项式中乘乘上一个因式上一个因式(x+1)，从而得到从而得到扩展扩展BCH码码(n+1,k)。扩展扩展BCH
38、码相当于在原码相当于在原BCH码上码上增加增加了一个了一个校验位校验位，因此因此码距码距比原比原BCH码码增增加加1。扩展扩展 BCH码已经码已经不不再具有再具有循环性循环性。例例扩展戈莱码扩展戈莱码(24,12)，其最小码距为其最小码距为8，码率为码率为1/2，能够纠正能够纠正3个错码和检测个错码和检测4个错码。个错码。11.6.5 RS码码 是用其发明人的名字是用其发明人的名字Reed和和Solomon命名的。命名的。是一类具有是一类具有很强很强纠错能力的纠错能力的多进制多进制BCH码。码。若若码长码长为为n的的m进制进制RS码，有码，有1 mn12 q的整数2q 对于能够对于能够纠正纠正
39、t个错误的个错误的RS码，码，其其监督监督码元数目为码元数目为tr2这时的这时的最小最小码距码距120 tdRS码的码的生成生成多项式为多项式为)()()(22txxxxg是伽罗华域是伽罗华域GF(2q)中的中的本原元本原元码长码长)()12(二进制码元qqn监督码监督码)(二进制码元qtr 能够能够纠正纠正码组中码组中t个个不不超过超过q位位连续连续的的二进制二进制错码，错码，RS码适用于存在码适用于存在突发错误突发错误的信道的信道 卷积码卷积码(convolutional code)是一种是一种非分组码非分组码。把把k比特的比特的信息信息段编成段编成n个比特的个比特的码组码组，监督码元监督
40、码元不仅不仅和和当前当前的的k比特比特信息信息段有关，段有关，而且还同而且还同前面前面m=(N-1)个个信息段信息段有关。有关。所以一个码组中的监督码元所以一个码组中的监督码元监督监督着着N个个信息段信息段。将将N称为称为编码约束编码约束(constraint)度度，并将并将nN称为称为编码约束长度编码约束长度。将卷积码记作将卷积码记作(n,k,N)。码率码率为为k/n。11.7.1 卷积码的基本原理卷积码的基本原理(3,1,3)卷积码卷积码的编码器，的编码器，其码率等其码率等1/3。设输入设输入信息信息比特序列是比特序列是112iiiibbbb则当则当输入输入bi时，时，此编码器此编码器输出
41、输出cidieiiibc 2iiibbd21iiiibbbebi为为当前当前输入信息位；输入信息位；bi-1和和bi-2为移存器存储的为移存器存储的前两前两信息位信息位是一种是一种线性码线性码P350 在输出中信息位在在输出中信息位在前前，监督位在监督位在后后，是是系统码系统码。编码编码约束长度约束长度nN=9。11.7.2卷积码的代数表达卷积码的代数表达 1.监督矩阵监督矩阵H 在第在第1个信息位个信息位b1进入编码器之进入编码器之前前，各级移存器都处于各级移存器都处于“0”状态，状态，则则监督位监督位di、ei和和信息位信息位bi之间的关系之间的关系图图11-911bd 11be 22bd
42、 122bbe133bbd1233bbbe244bbd2344bbbe011db011eb022db0221ebb0331dbb03321ebbb0442dbb04432ebbb(11.7-2)0101001001000011000001000101001001011000001101001011000101011444333222111edbedbedbedb图图11-9图图11-9监督矩阵为监督矩阵为101001001000011000001000101001001011000001101001011000101011H监督矩阵监督矩阵H是一个是一个有有头头无无尾的尾的半半无穷矩阵无穷矩阵
43、图图11-9n=3,k=1,N=31010010010110000011010010110001010111H截短截短监督矩阵监督矩阵212223212221IPOPOPIPOPIP(11.7-6)n=3,k=1,N=3图图11-910012I为为(n-k)=2阶阶单位方阵单位方阵)3,2,1(,iPi为为(n-k)k=21阶阶矩阵矩阵2O为为(n-k)=2阶阶全零方阵全零方阵(n,k,N)卷积码的卷积码的截短监督截短监督矩阵矩阵具的形式：具的形式：knknNknNknNknknknknknknIPOPOPOPIPOPOPIPOPIPH1211231211H1的的末行末行称为称为基本监督矩阵基
44、本监督矩阵knknNknNknNIPOPOPOPh121只要给定了只要给定了h，则，则H1也就随之决定了也就随之决定了2.生成矩阵生成矩阵G(11.7-2)444333222111edcedcedcedc图图11-9)()()()()(2342441231331222111bbbbbbbbbbbbbbbbbbb0000000000001110000000001001110000001101001110000001101001114321bbbb此码的此码的生成矩阵生成矩阵000000000000111000000000100111000000110100111000000110100111G它
45、也是一个它也是一个半半无穷矩阵无穷矩阵截短截短生成矩阵生成矩阵1110000001001110001101001111G112111312111QIQOQIQOQOQI1I为为k=1阶阶单位方阵单位方阵iQ为为k(n-k)=12阶矩阵阶矩阵TiiPQNi,2,1PP值值一般一般截短生成矩阵截短生成矩阵1211213211QIQOQIQOQOQIQOQOQOQIGkNkkNkkkNkkkkG1中中第一行第一行称为称为基本生成矩阵基本生成矩阵NkkkkQOQOQOQIg321这就是卷积码的这就是卷积码的代数代数表述表述11.7.3 卷积码的卷积码的解码解码代数解码代数解码概率解码概率解码(最大似然
46、解码最大似然解码)大数逻辑解码大数逻辑解码(门限解码门限解码)维特比维特比(Viterb)算法算法 1.大数逻辑大数逻辑解码解码 这里的错码检测是采用二进制码的这里的错码检测是采用二进制码的大数逻辑大数逻辑解码算法。解码算法。它利用一组它利用一组正交校验方程正交校验方程进行计算。进行计算。“正交正交”定义是：定义是：若被校验的若被校验的那个那个信息位出现在校验方程组的每一个方程中，信息位出现在校验方程组的每一个方程中，而而其他的其他的信息位至多在一个方程中出现，信息位至多在一个方程中出现，则称这组方程为则称这组方程为正交校验方程正交校验方程。例例(2,1,6)卷积码编码器。卷积码编码器。当输入
47、序列为当输入序列为4321bbbb监督位监督位为为632165215414332211bbbbcbbbcbbcbcbcbc监督监督关系式关系式632166521554144333222111bbbbcSbbbcSbbcSbcSbcSbcSSi(i=16)称为称为校正子校正子正交校验方程组正交校验方程组6316262521554144111bbbccSSbbbcSbbcSbcS只有信息位只有信息位b1出现在出现在每个每个方程中，方程中，监督位和其他信息位均最多只出现一次。监督位和其他信息位均最多只出现一次。在接收端解码时，考察在接收端解码时，考察b1c1至至b6c6等等12个个码元码元，仅仅当当
48、b1出错时，出错时，校验方程组校验方程组中才可能有中才可能有 3个或个或 3个以上方程等于个以上方程等于“1”。从而能够纠正从而能够纠正b1的错误。的错误。1)当当信息位信息位出现一个错码时，出现一个错码时，仅当它位于信息位移存器的第仅当它位于信息位移存器的第6、3、2和和1级时，级时，才使校正子等于才使校正子等于“1”。这时的校正子序列为这时的校正子序列为100111；2)当当监督位监督位出现一个错码时，出现一个错码时，校正子序列将为校正子序列将为100000。由此可见，当校正子序列中出现第一个由此可见，当校正子序列中出现第一个“1”时，时，表示已经检出一个错码。表示已经检出一个错码。后面的
49、几位校正子则指出是信息位错了，还是监督位错了。后面的几位校正子则指出是信息位错了，还是监督位错了。此卷积码除了能够纠正两位在约束长度中的随机错误外，此卷积码除了能够纠正两位在约束长度中的随机错误外，还能纠正部分多于两位的错误。还能纠正部分多于两位的错误。2.卷积码的几何表述卷积码的几何表述 1)码树图码树图(code tree diagram)(3,1,3)卷码卷码 a)编码编码 初始状态初始状态000作为作为码树码树的的起点起点。输入信息位为输入信息位为“0”，则状态向，则状态向上上支路移动；支路移动；输入信息位为输入信息位为“1”，则状态向，则状态向下下支路移动。支路移动。b)解码解码 按
50、照汉明距离最小的准则沿上面的码树进行搜索。按照汉明距离最小的准则沿上面的码树进行搜索。例如，若接收码元序列为例如，若接收码元序列为 111 010 010 110 码树搜索解码法码树搜索解码法并不实用并不实用，因为随着信息序列的增长，因为随着信息序列的增长，码树分支数目按码树分支数目按指数指数规律增长；规律增长；在上面的码树图中，只有四个信息位，在上面的码树图中，只有四个信息位，分支已有分支已有24=16个。个。表表接收码元序列为接收码元序列为 1110100101102)状态图状态图(state diagram)(3,1,3)卷码卷码虚线虚线表示输入信息位为表示输入信息位为“1”时状态转变的
