通信原理 第11章 差错控制编码.ppt

《通信原理 第11章 差错控制编码.ppt》由会员分享，可在线阅读，更多相关《通信原理 第11章 差错控制编码.ppt（79页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、通信原理第第11章差错控制编码章差错控制编码 1n信道编码的目的和方法信道编码的目的和方法n差错控制差错控制n信道分类：从差错控制角度看信道分类：从差错控制角度看u随机信道随机信道：错码的出现是随机的：错码的出现是随机的 u突发信道突发信道：错码是成串集中出现的：错码是成串集中出现的u混合信道混合信道：既存在随机错码又存在突发错：既存在随机错码又存在突发错码码 11.1 概述概述2差错控制技术的种类差错控制技术的种类3举例举例明天明天14：0016：00开会。开会。明天明天10：0016：00开会。开会。明天下午明天下午14：0016：00开会。开会。明天下午明天下午10：0016：00开会。

2、开会。明天下午明天下午14：0016：00开两小时会。开两小时会。明天下午明天下午10：0016：00开两小时会。开两小时会。检错检错纠错纠错4l差错控制编码：差错控制编码：纠错编码纠错编码n监督码元：监督码元：在发送端在信息码元序列中增加一些差错在发送端在信息码元序列中增加一些差错控制码元，它们称为监督码元。控制码元，它们称为监督码元。n多余度：多余度：就是指增加的监督码元多少。例如，若编码就是指增加的监督码元多少。例如，若编码序列中平均每两个信息码元就添加一个监督码元，则序列中平均每两个信息码元就添加一个监督码元，则这种编码的多余度为这种编码的多余度为1/3。n编码效率编码效率(码率码率)

3、：设编码序列中信息码元数量为设编码序列中信息码元数量为k，总码元数量为总码元数量为n，则比值，则比值k/n 就是码率就是码率。n冗余度：冗余度：监督码元数监督码元数(n-k)和信息码元数和信息码元数 k 之比。之比。l差错控制以降低信息传输速率为代价换取提高传输可靠差错控制以降低信息传输速率为代价换取提高传输可靠性。性。基本概念基本概念5n停止等待停止等待ARQ系统系统 u系统是工作在半双工状态，时间没有得到充分利用，系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。传输效率较低。接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错

4、码组自动要求重发自动要求重发(ARQ)系统系统 3种种6n拉后拉后ARQ系统系统u需要对发送的数据组和答复进行编号，以便识别。需要对发送的数据组和答复进行编号，以便识别。需要双工信道需要双工信道 接收数据有错码组有错码组910 1110 1112214365798576ACK1NAK5NAK9ACK5发送数据576952143679810 1110 11 12重发码组重发码组7n选择重发选择重发ARQ系统系统u只重发出错的数据组，进一步提高了传输效率。只重发出错的数据组，进一步提高了传输效率。接收数据有错码组有错码组9214365759810 11131412发送数据9958521436710

5、11131412重发码组重发码组NAK9ACK1NAK5ACK5ACK98lARQ的主要优点：和前向纠错方法相比的主要优点：和前向纠错方法相比n监督码元较少即能使误码率降到很低，即码率较高；监督码元较少即能使误码率降到很低，即码率较高；n检错的计算复杂度较低；检错的计算复杂度较低；n检错用的编码方法和加性干扰的统计特性基本无关，能检错用的编码方法和加性干扰的统计特性基本无关，能适应不同特性的信道。适应不同特性的信道。lARQ的主要缺点：的主要缺点：n需要双向信道来重发，不能用于单向信道，也不能用于需要双向信道来重发，不能用于单向信道，也不能用于一点到多点的通信系统。一点到多点的通信系统。n因为

6、重发而使因为重发而使ARQ系统的传输效率降低。系统的传输效率降低。n在信道干扰严重时，可能发生因不断反复重发而造成事在信道干扰严重时，可能发生因不断反复重发而造成事实上的通信中断。实上的通信中断。n在要求实时通信的场合，例如电话通信，往往不允许使在要求实时通信的场合，例如电话通信，往往不允许使用用ARQ法。法。9ARQ系统的原理方框图系统的原理方框图10l分组码举例：分组码举例：n设有一种由设有一种由3位二进制数字构成的码组，若全部用来表位二进制数字构成的码组，若全部用来表示天气，则可以表示示天气，则可以表示8种不同天气。种不同天气。n例如：例如：“000”（晴），（晴），“001”（云），（

7、云），“010”（阴），（阴），“011”（雨），（雨），“100”（雪），（雪），“101”（霜），（霜），“110”（雾），（雾），“111”（雹）。（雹）。n其中任一码组在传输中发生错码，将变成另一个信息码其中任一码组在传输中发生错码，将变成另一个信息码组。接收端无法发现错误。组。接收端无法发现错误。11.2 纠错编码的基本原理纠错编码的基本原理11n若只准许使用若只准许使用4种来传送天气：种来传送天气：“000”晴晴 “011”云云 “101”阴阴 “110”雨雨000、101、110011接收端接收端发送端发送端 错一个错一个错错三个三个100肯定出错了肯定出错了（禁用码组）禁用码组

8、）000错错两个两个011、110、101正确正确不能肯定出错不能肯定出错（许用码组）许用码组）00012n 检错和纠错检错和纠错u上面这种编码只能检测错码，不能纠正错码。要能够纠上面这种编码只能检测错码，不能纠正错码。要能够纠正错误，还要增加多余度。正错误，还要增加多余度。u若规定许用码组只有两个：若规定许用码组只有两个：“000”（晴），（晴），“111”（雨），（雨），其他都是禁用码组，则能够检测两个以下错码，其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。或能够纠正一个错码。000接收端接收端发送端发送端 错一个错一个100肯定第一位出错了肯定第一位出错了（禁用码组）禁用

9、码组）错两个错两个只能检错，不能纠错只能检错，不能纠错13u分组码信息码监督码分组码信息码监督码 信息位监督位晴000云011阴101雨110分组码的结构分组码的结构14n分组码的符号：分组码的符号：(n,k)un 码组的总位数，又称为码组的长度（码长），码组的总位数，又称为码组的长度（码长），uk 码组中信息码元的数目，码组中信息码元的数目，un k r 码组中的监督码元数目，或称监督位数目。码组中的监督码元数目，或称监督位数目。n总的码组数总的码组数2n个个，许用码组，许用码组2k个个，禁用码组，禁用码组2r个。个。n编码的任务：编码的任务：从总码组中选出许用码组；从总码组中选出许用码组；

10、n译码的任务：译码的任务：用相应的规则，判断、校正码组。用相应的规则，判断、校正码组。分组码的一般结构分组码的一般结构15n分组码的码重和码距分组码的码重和码距u码重码重：把码组中：把码组中“1”的个数目称为码组的重量。的个数目称为码组的重量。u码距码距：把两个码组中对应位上数字不同的位数称为：把两个码组中对应位上数字不同的位数称为码组的距离。码距又称码组的距离。码距又称汉明距离汉明距离。“000”晴，晴，“011”云，云，“101”阴，阴，“110”雨，雨，4个码组之间，任意两个的距离均为个码组之间，任意两个的距离均为2。u最小码距最小码距d0：各个码组之间距离的最小值。：各个码组之间距离的

11、最小值。上面的编码的最小码距上面的编码的最小码距d0=2。16n每个码组的每个码组的3个码元的值个码元的值(a2,a1,a0)就是此立方体各就是此立方体各顶点顶点的坐的坐标。标。n码距：各顶点之间沿立方体各边行走的几何距离。码距：各顶点之间沿立方体各边行走的几何距离。nn维空间中单位正多面体顶点间的汉明距离。维空间中单位正多面体顶点间的汉明距离。(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)a2a0a1码距的几何意义码距的几何意义17 码距和检纠错能力的关系码距和检纠错能力的关系p为检测为检测e个错码，要求最小码距个错码，要求最

12、小码距 d0 e+1 0123BA汉明距离汉明距离ed018p为了纠正为了纠正t个错码，要求最小码距个错码，要求最小码距d0 2t+1BtA汉明距离012345td0码距和检纠错能力的关系码距和检纠错能力的关系19p为纠正为纠正t个错码，同时检测个错码，同时检测e个错码，要求最小码距个错码，要求最小码距 纠检结合：纠检结合：在纠错范围在纠错范围t内，则纠错，超出则检错。内，则纠错，超出则检错。例如：例如：d05，1、只检错：、只检错：e4；2、只纠错：、只纠错：t2；3、纠检结合：、纠检结合：t1，e3ABe1tt汉明距离码距和检纠错能力的关系码距和检纠错能力的关系2011.3 纠错编码的性能

13、纠错编码的性能10-610-510-410-310-210-1编码后PeCDEAB信 噪 比 (dB)21n偶数监督码：偶数监督码：监督位只有监督位只有1位，它使码组中位，它使码组中“1”的数目的数目为偶数。为偶数。式中式中a0为监督位，其他位为信息位。为监督位，其他位为信息位。n奇数监督码：奇数监督码：n特点特点u能够检测奇数个错码，无法检测偶数个错码能够检测奇数个错码，无法检测偶数个错码u适合检随机差错，连续多个突发性误码不能检知适合检随机差错，连续多个突发性误码不能检知u没有纠错能力没有纠错能力11.4简单的实用编码简单的实用编码11.4.1 奇偶监督码奇偶监督码2211.4.2 二维奇

14、偶监督码（方阵码）二维奇偶监督码（方阵码）第一维监督位第二维监督位23u二维奇偶监督码的性能二维奇偶监督码的性能p有可能检测有可能检测偶数个偶数个错码。错码。p由于方阵码只对构成矩形四角的错码无法检测，故由于方阵码只对构成矩形四角的错码无法检测，故其检错能力较强，使其检错能力较强，使Pe下降至原来的下降至原来的10.01。p适于检测适于检测突发错码突发错码。p二维奇偶监督码不仅可用来检错，还可以用来纠正二维奇偶监督码不仅可用来检错，还可以用来纠正一些错码。一些错码。例如，仅在一行中有奇数个错码时。例如，仅在一行中有奇数个错码时。24u在恒比码中，每个码组均含有相同数目的在恒比码中，每个码组均含

15、有相同数目的“1”（或（或“0”）。）。“1”的数目与的数目与“0”的数目之比保持恒定。的数目之比保持恒定。u这种码在检测时，只要计算接收码组中这种码在检测时，只要计算接收码组中“1”的数目是的数目是否对，就知道有无错码。否对，就知道有无错码。u恒比码的主要优点是简单和适于用来传输电传机或其恒比码的主要优点是简单和适于用来传输电传机或其他键盘设备产生的字母和符号。对于信源来的二进制他键盘设备产生的字母和符号。对于信源来的二进制随机数字序列，这种码就不适合使用了。随机数字序列，这种码就不适合使用了。11.4.3 恒比码恒比码25n正反码的编码：正反码的编码：u监督位数目与信息位数目相同，监督码元

16、与信息码监督位数目与信息位数目相同，监督码元与信息码元相同或者相反则由信息码中元相同或者相反则由信息码中“1”的个数而定。的个数而定。n其编码规则为：其编码规则为：u当信息位中有奇数个当信息位中有奇数个“1”时，监督位是信息位的简时，监督位是信息位的简单重复；单重复；u当信息位有偶数个当信息位有偶数个“1”时，监督位是信息位的反码。时，监督位是信息位的反码。n例如，若信息位为例如，若信息位为11001，则码组为，则码组为1100111001；若信息位为若信息位为10001，则码组为，则码组为1000101110。n可纠错。长度为可纠错。长度为10的正反码具有纠正的正反码具有纠正1位错码的能力，

17、位错码的能力，并能检测全部并能检测全部2位以下的错码和大部分位以下的错码和大部分2位以上的错码。位以上的错码。11.4.4 正反码正反码26n基本概念基本概念u代数码代数码：利用代数关系式产生监督位的编码。：利用代数关系式产生监督位的编码。u线性码线性码：信息位和监督位是由一些线性代数方程：信息位和监督位是由一些线性代数方程联系着的。联系着的。u线性分组码线性分组码：按照一组线性方程构成的分组码：按照一组线性方程构成的分组码。11.5 线性分组码线性分组码27n汉明码汉明码能够纠正能够纠正1位错码位错码且编码效率较高的一种线性分组码且编码效率较高的一种线性分组码u偶数监督码：偶数监督码：使用了

18、一位监督位使用了一位监督位a0u接收端解码时，计算接收端解码时，计算u若若S=0，就认为无错码；若，就认为无错码；若S=1，就认为有错码。，就认为有错码。u监督关系式：监督关系式：u校正子：校正子：S 28n一个校正子检错，两个校正子可纠错一个校正子检错，两个校正子可纠错u校正子的校正子的4中组合：中组合：00，01，10，11，能表示，能表示4种不同种不同的信息。若用其中的信息。若用其中1种组合表示无错，则其余种组合表示无错，则其余3种组合种组合就有可能用来指示一个错码的就有可能用来指示一个错码的3种不同位置。种不同位置。nr个校正子能指示个校正子能指示1位错码的位错码的(2r 1)个可能位

19、置。个可能位置。n若码长为若码长为n，信息位数为，信息位数为k，则监督位数，则监督位数rnk。n用用r个监督位构造出个监督位构造出r个监督关系式来指示个监督关系式来指示1位错码的位错码的n种可种可能位置，则要求能位置，则要求29n设分组码设分组码(n,k)中中k=4，为了纠正，为了纠正1位错码，要求监督位数位错码，要求监督位数 r 3。若取。若取 r=3，则，则n=k+r=7。n用用a6 a5 a0表示这表示这7个码元，用个码元，用S1、S2和和S3表示表示3个监督关个监督关系式中的校正子。系式中的校正子。S1 S2 S3错码位置S1 S2 S3错码位置0 0 1a01 0 1a40 1 0a

20、11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码30n仅当一位错码的位置在仅当一位错码的位置在a2、a4、a5或或a6时，校正子时，校正子S1为为1；否则否则S1为零。为零。a2、a4、a5和和a6四个码元构成偶数监督关系：四个码元构成偶数监督关系：n同理同理S1 S2 S3错码位置S1 S2 S3错码位置0 0 1a01 0 1a40 1 0a11 1 0a51 0 0a21 1 1a60 1 1a30 0 0无错码31u无错码：无错码：监督位应使上监督位应使上3式中式中S1、S2和和S3的值为的值为0 n编码：给定信息位后，可以直接按上式算出监督位编码：给定信息位

21、后，可以直接按上式算出监督位32信息位a6 a5 a4 a3监督位a2 a1 a0信息位a6 a5 a4 a3监督位a2 a1 a00000000100011100010111001100001010110100100011110101100101001101100001010110111010100110011111010001110001111111编码：编码：33解码解码p计算计算p查表判断错码情况。查表判断错码情况。若接收码组为若接收码组为0000011，计算可得：，计算可得：S1=0，S2=1，S3=1。查表可知在。查表可知在a3位有位有1错码。错码。u(7,4)汉明码的最小码距汉明

22、码的最小码距d0=3。能够纠正。能够纠正1个错码或检个错码或检测测2个错码。个错码。u由于码率由于码率k/n=(n-r)/n=1 r/n，故当，故当n很大和很大和r很小时，很小时，码率接近码率接近1。汉明码是一种高效码。汉明码是一种高效码。34nH矩阵监督矩阵u上面上面(7,4)汉明码的例子有汉明码的例子有改写为改写为上式中已经将上式中已经将“”简写成简写成“+”。线性分组码的一般原理线性分组码的一般原理35表示成矩阵形式：表示成矩阵形式：简记为简记为H AT=0T 或或A HT=036H AT=0T 或或A HT=0式中式中 A=a6 a5 a4 a3 a2 a1 a00=000uH称为称为

23、监督矩阵监督矩阵。u只要监督矩阵只要监督矩阵H给定，编码时监督位和信息位的关系就给定，编码时监督位和信息位的关系就完全确定了。完全确定了。37pH的行数就是监督关系式的数目的行数就是监督关系式的数目r。pH的每行中的每行中“1”的位置表示相应码元之间存在的监督的位置表示相应码元之间存在的监督关系。例如，关系。例如，H的第一行的第一行1110100表示监督位表示监督位a2是由是由a6 a5 a4之和决定的。之和决定的。pH矩阵可以分成两部分矩阵可以分成两部分P为为r k阶矩阵，阶矩阵，Ir为为r r阶单位方阵。阶单位方阵。将具有将具有P Ir形式的形式的H矩阵称为矩阵称为典型阵典型阵。pH矩阵的

24、各行应该是线性无关的，否则将得不到矩阵的各行应该是线性无关的，否则将得不到r个线个线性无关的监督关系式性无关的监督关系式H矩阵的性质：矩阵的性质：38 写成矩阵形式：写成矩阵形式：Q为一个为一个k r阶矩阵，阶矩阵，Q=PTn在信息位给定后，用信息位的行矩阵乘矩阵在信息位给定后，用信息位的行矩阵乘矩阵Q就就产生出监督位。产生出监督位。生成矩阵生成矩阵G矩阵矩阵39l将将Q的左边加上的左边加上1个个k k阶单位方阵，就构成阶单位方阵，就构成1个矩阵个矩阵G lG称为称为生成矩阵生成矩阵，因为由它可以产生整个码组，因为由它可以产生整个码组，l具有具有IkQ形式的生成矩阵称为形式的生成矩阵称为典型生

25、成矩阵典型生成矩阵。l由典型生成矩阵得出的码组由典型生成矩阵得出的码组A中，信息位的位置不变，监督中，信息位的位置不变，监督位附加于其后。这种形式的码称为位附加于其后。这种形式的码称为系统码系统码。40uG矩阵的性质：矩阵的性质：pG矩阵的各行是线性无关的。矩阵的各行是线性无关的。pG的各行本身就是一个码组。因此，如果已有的各行本身就是一个码组。因此，如果已有k个个线性无关的码组，则可以用其作为生成矩阵线性无关的码组，则可以用其作为生成矩阵G，并由它生成其余码组。并由它生成其余码组。41p错码矩阵和错误图样错码矩阵和错误图样 发送的码组发送的码组A：设接收码组设接收码组B：发送码组和接收码组之

26、差为发送码组和接收码组之差为B A=E(模模2)它就是传输中产生的它就是传输中产生的错码错码行行矩阵，矩阵，称为称为错误图样错误图样 B=A+E例：若发送码组例：若发送码组A=1000111，错码矩阵错码矩阵E=0000100，则接收码组则接收码组B=1000011。42 校正子矩阵校正子矩阵S u当接收码组有错时，当接收码组有错时，E 0，将，将B当作当作A代入公式代入公式(A H T=0)后，该式不一定成立。后，该式不一定成立。B H T=S将将B=A+E代入上式，可得代入上式，可得S=(A+E)H T=A H T+E H T S=E H TuS称为称为校正子矩阵校正子矩阵。它能用来指示错

27、码的位置。它能用来指示错码的位置。uS和错码和错码E之间有确定的线性变换关系。若之间有确定的线性变换关系。若S和和E之间一一之间一一对应，则对应，则S将能代表错码的位置。将能代表错码的位置。43u封闭性封闭性：一种线性码中的任意两个码组之和仍为这种一种线性码中的任意两个码组之和仍为这种码中的一个码组。码中的一个码组。u【证证】若若A1和和A2是两个码组，则有是两个码组，则有A1 HT=0,A2 HT=0将上两式相加，得出将上两式相加，得出A1 HT+A2 HT=(A1+A2)HT=0所以所以(A1+A2)也是一个码组。也是一个码组。u由于线性码具有封闭性，所以两个码组由于线性码具有封闭性，所以

28、两个码组(A1和和A2)之间之间的距离（即对应位不同的数目）必定是另一个码组的距离（即对应位不同的数目）必定是另一个码组(A1+A2)的重量（即的重量（即“1”的数目）。的数目）。u码的最小距离就是码的最小重量码的最小距离就是码的最小重量（除全（除全“0”码组外）。码组外）。线性分组码的性质线性分组码的性质44l11.6.1 循环码原理循环码原理n循环性循环性：任一码组循环一位以后，仍为该码中的一个码：任一码组循环一位以后，仍为该码中的一个码组。组。n(7,3)循环码循环码码组编号信息位监督位码组编号信息位监督位a6a5a4a3a2a1a0a6a5a4a3a2a1a01000000051001

29、01120010111610111003010111071100101401110018111001011.6 循环码循环码45一般情况一般情况:若若(an-1 an-2 a0)是循环码的一个码组，则循环移位是循环码的一个码组，则循环移位后的码组后的码组(an-2 an-3 a0 an-1)(an-3 an-4 an-1 an-2)(a1 a0 an-1 a2)(a0 an-1 a2 a1)也是该编码中的码组。也是该编码中的码组。46p把码组中各码元当作是一个多项式的系数把码组中各码元当作是一个多项式的系数p长度为长度为n的码组的码组(an-1 an-2 a0)表示成表示成 例如例如:n=7“

30、1100101”表示为表示为:码组的多项式表示法码组的多项式表示法47n 码多项式的码多项式的按模运算按模运算u模模2运算运算1+1=2 0 (模模2)，1+2=3 1 (模模2)，2 3=6 0 (模模2)u模模 n 运算运算 一个整数一个整数m可以表示为可以表示为 式中，式中，Q 整数整数则则 m p (模模n)在模在模 n 运算下，一个整数运算下，一个整数m等于它被等于它被 n 除得的余数。除得的余数。循环码的运算循环码的运算48p任意多项式任意多项式F(x)码多项式系数仍按模码多项式系数仍按模2 运算，即系数只取运算，即系数只取 0 和和1。p例例1，x3被被(x3+1)除，得到余项除

31、，得到余项1。所以有。所以有p例例2，xx3+1 x4+x2 +1 x4 +x x2+x+149u在循环码中，在循环码中，T(x)是一个长为是一个长为n的许用码组，若的许用码组，若则则T (x)也是该编码中的一个许用码组。也是该编码中的一个许用码组。u【证证】因为因为（模（模(xn+1)）T (x)正是正是T(x)代表的码组向左循环移位代表的码组向左循环移位i次的结果。次的结果。循环码的码多项式循环码的码多项式50例，循环码组例，循环码组1100101其码长其码长n=7。现给定。现给定i=3，则，则其对应的码组为其对应的码组为0101110，它正是表中第，它正是表中第3码组。码组。n结论：结论

32、：一个长为一个长为n的循环码必定为按模的循环码必定为按模(xn+1)运算的一个余式。运算的一个余式。51u生成矩阵生成矩阵G的每一行都是一个码组。的每一行都是一个码组。u在循环码中，一个在循环码中，一个(n,k)码有码有2k个不同的码组。个不同的码组。p只需找到一个码组即可，其他码组都可循环得到只需找到一个码组即可，其他码组都可循环得到p若用若用g(x)表示其中前表示其中前(k-1)位皆为位皆为“0”的码组的码组，则，则g(x)，x g(x)，x2 g(x)，xk-1 g(x)都是码组，而且都是码组，而且这这k个码组是线性无关的。因此它们可以用来构成个码组是线性无关的。因此它们可以用来构成此循

33、环码的生成矩阵此循环码的生成矩阵G。pg(x)必须是一个常数项不为必须是一个常数项不为“0”的的(n-k)次多项式，次多项式，且唯一且唯一ug(x)为码的为码的生成多项式生成多项式循环码的生成矩阵循环码的生成矩阵G52p循环码的生成矩阵循环码的生成矩阵Gp例：例：(7,3)循环码中，循环码中，n=7,k=3,n k=4。唯一的一个唯一的一个(n k)=4次码多项式代表的码组是第二码组次码多项式代表的码组是第二码组0010111，对应的码多项式（即对应的码多项式（即生成多项式生成多项式）g(x)=x4+x2+x+1。或或53写出此循环码组写出此循环码组p所有码多项式所有码多项式T(x)都可被都可

34、被g(x)整除整除p而且任意一个次数不大于而且任意一个次数不大于(k 1)的多项式乘的多项式乘g(x)都是码都是码多项式。多项式。54如何寻找任一如何寻找任一(n,k)循环码的生成多项式循环码的生成多项式u任一循环码多项式任一循环码多项式T(x)都是都是g(x)的倍式，的倍式，T(x)=h(x)g(x)u生成多项式生成多项式g(x)本身也是一个码组，即有本身也是一个码组，即有T (x)=g(x)u码组码组T (x)是一个是一个(n k)次多项式，次多项式，xk T (x)是一个是一个n次次多项式多项式。xk T (x)在模在模(xn+1)运算下也是一个码组运算下也是一个码组商式商式Q(x)=1

35、55p生成多项式生成多项式g(x)应该是应该是(xn+1)的一个的一个(n k)次因子。次因子。p例如，例如，(x7+1)可以分解为可以分解为 p为了求为了求(7,3)循环码的生成多项式循环码的生成多项式g(x)，从上式中找，从上式中找到到(n k)=4次的因子。这样的因子有两个，即次的因子。这样的因子有两个，即56总结：生成多项式总结：生成多项式g(x)必须满足必须满足lg(x)是一个是一个(n k)次多项式次多项式lg(x)的常数项不为的常数项不为0lg(x)是是(xn+1)的一个因子的一个因子57u编码编码um(x)为信息码多项式为信息码多项式p用用xn-k乘乘m(x)。这一运算实际上是

36、在信息码后附加。这一运算实际上是在信息码后附加上上(n k)个个“0”。例：例：m(x)=x2+x 110 xn-k m(x)=x4(x2+x)=x6+x5 1100000 p用用g(x)除除xn-k m(x)，得到商，得到商Q(x)和余式和余式r(x)，即，即11.6.2 循环码的编解码方法循环码的编解码方法58例如，若选定例如，若选定g(x)=x4+x2+x+1，则，则 相当于相当于p编出的码组编出的码组T(x)为为T(x)=xn-k m(x)+r(x)上例中，上例中，T(x)=1100000+101=110010159n解码：检错和纠错。解码：检错和纠错。n检错解码检错解码u当传输中未发

37、生错误时，接收码组当传输中未发生错误时，接收码组R(x)必定能被必定能被g(x)整除整除以余式是否为零来判别接收码组中有无错码。以余式是否为零来判别接收码组中有无错码。u误码数超过了编码的检错能力时，有错码的接收误码数超过了编码的检错能力时，有错码的接收码组也有可能被码组也有可能被g(x)整除。这时的错码就不能检出整除。这时的错码就不能检出了。这种错误称为了。这种错误称为不可检错误不可检错误。60u纠错解码纠错解码p用生成多项式用生成多项式g(x)除接收码组除接收码组R(x)，得出余式，得出余式r(x)。p按余式按余式r(x)，用查表的方法或通过某种计算得到错，用查表的方法或通过某种计算得到错

38、误图样误图样E(x)；例如，通过计算校正子；例如，通过计算校正子S和查表，就可和查表，就可以确定错码的位置。以确定错码的位置。p从从R(x)中减去中减去E(x)，便得到已经纠正错码的原发送，便得到已经纠正错码的原发送码组码组T(x)。捕错解码法捕错解码法。6111.6.3 其它循环码n截短循环码截短循环码u(n,k)截短为截短为(n-i,k-i)nBCH码码(Bose-Chaudhuri-Hocguenghem)u纠正多个错码的循环码纠正多个错码的循环码u可以在给定纠错能力的条件下寻找到生成多项式。可以在给定纠错能力的条件下寻找到生成多项式。nRS码码 (Reed-Solomon)u具有很强纠

39、错能力的多进制具有很强纠错能力的多进制BCH码码u特别适用于存在突发错误的信道，如移动通信网等特别适用于存在突发错误的信道，如移动通信网等衰落信道中。衰落信道中。u因为它是多进制纠错编码，所以特别适合用于多进因为它是多进制纠错编码，所以特别适合用于多进制调制的场合。制调制的场合。62u非分组码非分组码u更适用于前向纠错，因为对于许多实际情况它的更适用于前向纠错，因为对于许多实际情况它的性能优于分组码，而且运算较简单。性能优于分组码，而且运算较简单。u把把k个比特的信息段编成个比特的信息段编成n个比特的码组个比特的码组u监督码元不仅和当前的监督码元不仅和当前的k比特信息段有关，而且还比特信息段有

40、关，而且还同前面同前面m=(N 1)个信息段有关。个信息段有关。u一个码组中的监督码元监督着一个码组中的监督码元监督着N个信息段。个信息段。N称为称为编码编码约束度约束度，nN称为编码称为编码约束长度约束长度。u将卷积码记作将卷积码记作(n,k,N)。码率则仍定义为。码率则仍定义为k/n。11.7 卷积码卷积码63u编码器原理方框图编码器原理方框图编码输出每次输入k比特1k1k1k1k 1 k2k3kNk 12nNk级移存器n个模2加法器每输入k比特旋转1周11.7.1 卷积码的基本原理卷积码的基本原理64u例：例：(n,k,N)=(3,1,3)卷积码编码器卷积码编码器p输入信息序列是输入信息

41、序列是bi-2 bi-1 bi bi+1，p当输入当输入bi时，此编码器输出时，此编码器输出3比特比特ci di eibi-2bi输入bibi-1编码输出dicieiM2M3M1ci-2di-2ei-2ci-1di-1ei-1cidieibi-2bi1bitt输入输出65n编码器工作状态编码器工作状态M1 (bi)1101000M3M2(bi-2bi-1)00011110011000ci di ei111110010100001011000状态状态abdcbcabi-2bi输入bibi-1编码输出dicieiM2M3M16611.7.3 卷积码的解码卷积码的解码l分类：分类：n代数解码代数解码

42、：利用编码本身的代数结构进行解码，：利用编码本身的代数结构进行解码，不考虑信道的统计特性。不考虑信道的统计特性。p大数逻辑解码（门限解码）大数逻辑解码（门限解码）n概率解码（最大似然解码）概率解码（最大似然解码）：它基于信道的统计：它基于信道的统计特性和卷积码的特点进行计算。特性和卷积码的特点进行计算。p维特比算法维特比算法（基于卷积码的几何表述方法）（基于卷积码的几何表述方法）67u卷积码的几何表述卷积码的几何表述p码树图码树图：以：以(3,1,3)码为例码为例状态 M3 M2 a 0 0 b 0 1 c 1 0 d 1 10001110011100111000101010001110011

43、10011100010101000100111011001101110010111000001110c2d2e2信息位 1 1 0 1ba起点信息位000111abcdabcdabcdabcd上半部下半部10aabcdabcdcdab011001c3d3e3c1d1e1c4d4e468p状态图：状态图：移存器前一状态M3 M2当前输入信息位 bi输出码元cidiei移存器下一状态M3 M2a(00)01000111a(00)b(01)b(01)01001110c(10)d(11)c(10)01011100a(00)b(01)d(11)01010101c(10)d(11)abcd00011110

44、1110010011100001输入输入0：实线：实线输入输入1：虚线：虚线69p网格图网格图110110110110011011011010010010101101101001001001001abcdabcd000000000000000111111111111111100100100abcdabcd11001000111110070维特比解码算法维特比解码算法n基本原理基本原理u将接收到的信号序列和所有可能的发送信号序列将接收到的信号序列和所有可能的发送信号序列比较，选择其中汉明距离最小的序列认为是当前比较，选择其中汉明距离最小的序列认为是当前发送信号序列。发送信号序列。u(n,k,N)

45、=(3,1,3)卷积码卷积码p信息位：信息位：1101，为了使移存器的信息位全部移，为了使移存器的信息位全部移出，在信息位后面加入出，在信息位后面加入3个个“0”，p信息位：信息位：1101000p编码后序列：编码后序列：111 110 010 100 001 011 000p接收序列为：接收序列为：111 010 010 110 001 011 000p约束度约束度N=3，第，第1步考察步考察nN 9比特比特71l4种状态共有种状态共有8条到达路径条到达路径l将到达每个状态的两条路径的汉明距离作比较，将距离将到达每个状态的两条路径的汉明距离作比较，将距离小的一条路径保留，称为小的一条路径保留

46、，称为幸存路径幸存路径。这样就剩下。这样就剩下4条路条路径了。径了。解码第一步：解码第一步：考察考察nN 9比特比特110110110110011011011010010010101101101001001001001abcdabcd00000000000000011111111111111110010010072l接收序列为：接收序列为：111 010 010序号序号路径路径对应序列对应序列汉明距离汉明距离幸存否幸存否1aaaa000 000 0005否否2abca111 001 0113是是3aaab000 000 1116否否4abcb111 001 1004是是5aabc000 111

47、 0017否否6abdc111 110 0101是是7aabd000 111 1106否否8abdd111 110 1014是是解码第一步：解码第一步：考察考察nN 9比特比特73l计算计算4条幸存路径上增加条幸存路径上增加1级后的级后的8条可能路径的汉明距离。条可能路径的汉明距离。解码第二步：考察后继解码第二步：考察后继3比特比特110序号序号路径路径原幸存路径原幸存路径的距离的距离新增新增路径段路径段新增新增距离距离总距离总距离幸存否幸存否1abca+a3aa25否否2abdc+a1ca23是是3abca+b3ab14否否4abdc+b1cb12是是5abcb+c4bc37否否6abdd+

48、c4dc15是是7abcb+d4bd04是是8abdd+d4dd26否否l最小的总距离等于最小的总距离等于2，其路径是，其路径是abdc+b74l最小的总距离等于最小的总距离等于2，其路径是，其路径是abdc+b，l相应序列为相应序列为111 110 010 100，它和发送序列相同，对应，它和发送序列相同，对应发送信息位发送信息位1101。abcd011010010101001abcd111100100110110解码第二步：考察后继解码第二步：考察后继3比特比特11075l信息位：信息位：1101000l编码后序列：编码后序列：111 110 010 100 001 011 000l接收序

49、列为：接收序列为：111 010 010 110 001 011 000110011010010101101001001abcdabcd000 111100100000 011011001101继续解码继续解码76n在上例中卷积码的约束度在上例中卷积码的约束度N=3，需要存储和计算，需要存储和计算8条条路径的参量。路径的参量。n维特比解码算法的复杂度随约束长度维特比解码算法的复杂度随约束长度N按指数形式按指数形式2N增长。增长。n故维特比解码算法适合约束度较小（故维特比解码算法适合约束度较小（N 10）的编码。）的编码。维特比解码算法维特比解码算法7711.8 其它信道编码其它信道编码nTur

50、bo码码u由于其性能接近信息理论上能够达到的最好性能，由于其性能接近信息理论上能够达到的最好性能，所以在编码理论上是带有革命性的进步。所以在编码理论上是带有革命性的进步。n低密度奇偶校验码低密度奇偶校验码 (LDPC)u线性分组码，和线性分组码，和Turbo码性能相近，广泛应用于移动码性能相近，广泛应用于移动通信、无线局域网和光纤通信等领域。通信、无线局域网和光纤通信等领域。n网格编码调制网格编码调制(TCM)u将纠错编码和调制相结合将纠错编码和调制相结合u能同时节省发送功率和带宽。能同时节省发送功率和带宽。78作业作业l11-2l11-3l11-4l11-6l11-7l11-8l11-12l