《通讯原理差错编码控制课件》由会员分享,可在线阅读,更多相关《通讯原理差错编码控制课件(53页珍藏版)》请在金锄头文库上搜索。
1、第十一章第十一章 差错控制编差错控制编码码主要内容主要内容纠错编码的原理纠错编码的原理线性分组码线性分组码循环码循环码重点重点检错、纠错的概念检错、纠错的概念分组码的结构分组码的结构汉明码汉明码循环码循环码通讯原理差错编码控制课件11.1 概述概述11.2 纠错编码的原理纠错编码的原理11.3 常用的简单编码常用的简单编码11.4 线性分组码线性分组码11.5 循环码循环码作业作业11.6 卷积码卷积码通讯原理差错编码控制课件习题习题 11 - 1 11 - 1、5 5、7 7、1414作业作业通讯原理差错编码控制课件11.1 概述概述 检错重发法检错重发法11.1.2 差错控制的方法差错控制
2、的方法11.1.1 编码的目的:提高信号抗加性干扰的能力编码的目的:提高信号抗加性干扰的能力 干扰种类:干扰种类: 加性加性 克服方法:差错控制编码克服方法:差错控制编码 加性干扰的特征:加性干扰的特征:突发信道:出现错码成串集中。突发信道:出现错码成串集中。混合信道:前两者中和。混合信道:前两者中和。乘性乘性 克服方法:均衡器克服方法:均衡器随机信道:出现错码是随机的,相互间统计独立。随机信道:出现错码是随机的,相互间统计独立。反馈校验法反馈校验法前向纠错方法前向纠错方法定义定义误码率标准误码率标准通讯原理差错编码控制课件速率速率( b/s )线路类别线路类别误码率标准误码率标准300电话交
3、换线电话交换线专用线专用线10- - 45510- - 5600电话交换线电话交换线专用线专用线10- - 35510- - 51200电话交换线电话交换线专用线专用线10- - 55510- - 52400专用线专用线10- - 5CCITT 建议的误码率标准建议的误码率标准通讯原理差错编码控制课件检错重发法:在接收端检测出错码时,通知发端重发信号,检错重发法:在接收端检测出错码时,通知发端重发信号,直到接收正确为止。此方法只能判断是否有错直到接收正确为止。此方法只能判断是否有错码,不能判断具体的错码位置。所以,只能检码,不能判断具体的错码位置。所以,只能检错不能纠错,且需要错不能纠错,且需
4、要双向双向通道。通道。前向纠错方法:前向纠错方法:在收端检测出错码时,可以确定错码在收端检测出错码时,可以确定错码的位置,并予纠正。此方法只需要的位置,并予纠正。此方法只需要单向单向通道。通道。实时性好,但设备复杂。实时性好,但设备复杂。反馈校验法:接反馈校验法:接收端将收到的信号原封不动的发回发收端将收到的信号原封不动的发回发端,由发端将其与原发信号相比较,如果端,由发端将其与原发信号相比较,如果有错则重发。这种方法需有错则重发。这种方法需双向双向通道,效率通道,效率低,但设备简单。低,但设备简单。通讯原理差错编码控制课件在信息码序列中加在信息码序列中加监督码元监督码元(也称纠错码)(也称纠
5、错码)自动请求重发系统自动请求重发系统(ARQ)11.1.3 差错控制编码的原理差错控制编码的原理不同的编码方法,有不同的检错或纠错能力,监督码不同的编码方法,有不同的检错或纠错能力,监督码元越多,检、纠错能力越强。元越多,检、纠错能力越强。由于信息码元是随机序列,收端无法预知信号状态,由于信息码元是随机序列,收端无法预知信号状态,因而无法判别接收码是否有错。增加了监督码元之后,因而无法判别接收码是否有错。增加了监督码元之后,监督码和信息码之间存在一种逻辑关系,因此,收端监督码和信息码之间存在一种逻辑关系,因此,收端可以利用这种逻辑关系发现或纠正存在的错码。可以利用这种逻辑关系发现或纠正存在的
6、错码。通讯原理差错编码控制课件自动请求重发系统自动请求重发系统(ARQ)工作工作过程:过程:3 3)重发控制器收到重发命令时,控制输入缓冲储存器重)重发控制器收到重发命令时,控制输入缓冲储存器重发一次当前码组,否则发送后一码组。发一次当前码组,否则发送后一码组。2 2)收端解码器检测出错码时由指令发生器产生重发命令)收端解码器检测出错码时由指令发生器产生重发命令传给发端,同时发出删除命令,删除输出缓冲器内容。传给发端,同时发出删除命令,删除输出缓冲器内容。1 1)收发正常时,重发控制与指令发生器不工作。)收发正常时,重发控制与指令发生器不工作。重发控制重发控制信信源源双双向向通通道道指令发生器
7、指令发生器解码器解码器输出缓存器输出缓存器收收信信者者错误时删除错误时删除编码编码输入缓存器输入缓存器优点:优点:1 1)监督码少,占总码的)监督码少,占总码的( 20% ) 2 2)对各种信道有一定的适应能力。)对各种信道有一定的适应能力。 3 3)成本及复杂性低。)成本及复杂性低。缺点:缺点:1 1)需要双向通道)需要双向通道 2 2)干扰大时系统可能处于)干扰大时系统可能处于重发循环中,效率降低重发循环中,效率降低 3 3)实时性差)实时性差通讯原理差错编码控制课件11.2 纠错编码的基本原理纠错编码的基本原理11.2.1 分组码的概念分组码的概念11.2.2 分组码参数分组码参数通讯原
8、理差错编码控制课件例:例:天气预报天气预报11.2.1 分组码的概念分组码的概念特征:特征:分组码中的监督码元仅监督本码组中的信息码元。分组码中的监督码元仅监督本码组中的信息码元。分组码分组码定义:定义:将将信息码分组,为每组信息码后附加若信息码分组,为每组信息码后附加若干监督码元形成的码集合。干监督码元形成的码集合。分组码检错、纠错能力的体现分组码检错、纠错能力的体现信源信源发送信息码发送信息码晴晴0 0云云0 1阴阴1 0雨雨1 1接收信息码接收信息码判别判别0 1云云10 阴阴0 0晴晴1 0阴阴结论:结论:虽然接收码组有错,但接收端无法识别。虽然接收码组有错,但接收端无法识别。讨论讨论
9、通讯原理差错编码控制课件信源信源 发送信息码发送信息码监督码监督码晴晴0 00云云0 11阴阴1 01雨雨1 10接收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010建立分组码建立分组码 A错错 1 位位接收码组接收码组判别判别011、110、101云、雨、阴云、雨、阴000、101、110晴、阴、雨晴、阴、雨110、000、011雨、晴、云雨、晴、云101、000、011阴、晴、云阴、晴、云错错 2 位位结论:结论:只能检测出只能检测出 1 位错位错码,码,但不能纠正。但不能纠正。禁用码组:非禁用码组:非信息信息码组码组许用码组:有
10、效许用码组:有效信息信息码组码组通讯原理差错编码控制课件结论:结论:能纠正能纠正 1 位错码位错码,或,或检测出检测出 2 位错码位错码。信源信源 发送信息码发送信息码 监督码监督码晴晴0 0000云云0 1011阴阴1 0101雨雨1 1110接收码组接收码组判别判别00001、00010、00100、01000、1000001010、01001、01111、00011、1101110100、10111、10001、11101、0010111111、11100、11010、10110、01110建立分组码建立分组码 B错错 1 位位接收码组接收码组判别判别11000、10100、10010、
11、10001、01100、01010、01001、00110、00101、0001110011、11111、11001、11010、00111、00001、00010、01101、01110、0101001101、00001、00111、00110、11001、11110、11101、10011、10000、1010000110、01010、01100、01111、10010、10100、10111、11000、11011、11111错错 2 位位通讯原理差错编码控制课件 k : 码组中信息码元的数目。码组中信息码元的数目。 n : 码组的总位数,又称为码组长度。码组的总位数,又称为码组长度。
12、r = n - - k :码组中监督码元的数目。:码组中监督码元的数目。结构结构符号符号( n , k ) 码长码长 n = k + r k 个信息位个信息位 r 个监督位个监督位码组重量码组重量码组中码组中 “1 ” 的数目的数目11.2.2 分组码参数分组码参数an-1an-2arar-1a0码距码距 d :两个码组对应位数值不同的码元个数称为:两个码组对应位数值不同的码元个数称为码组间的汉明距离码组间的汉明距离码距与码集合码距与码集合检、纠错能力的关系检、纠错能力的关系通讯原理差错编码控制课件例:例:码组(码组(a2 a1 a0)= 1 1 0 (b2 b1 b0)= 0 1 0码距的几
13、何概念码距的几何概念码距是码距是 1最小码距最小码距 d0 :码集合中任意两两码组间距离的最小值:码集合中任意两两码组间距离的最小值( 0 1 0)( 1 1 0)( 0 0 0)( 1 0 0)( 1 0 1)( 0 0 1)( 0 1 1)( 1 1 1)a1a0a2选许用码组:选许用码组:0 0 0 0 1 1 1 1 0 1 0 1令令 n = 3 , 共有共有 8 个码组个码组沿立方体各边行走,沿立方体各边行走,4 个码个码组的距离均为组的距离均为 2 个边长个边长 d0 = 2通讯原理差错编码控制课件 检测检测 e 个错码,要求最小码距个错码,要求最小码距 纠正纠正 t 个错码,要
14、求最小码距个错码,要求最小码距 纠正纠正 t 个错码、同时检测个错码、同时检测 e 个错码,要求最小码距个错码,要求最小码距码距与码集合检、纠错能力的关系码距与码集合检、纠错能力的关系AB例:例: A = ( 00000 ) 、B = ( 11111 ), d0 = 5 结论:结论:e = 4 或或 t = 2 或或 e = 3、 t = 1 d = 1d = 2d = 3通讯原理差错编码控制课件11.3 常用的简单编码常用的简单编码11.3.1 奇偶监督码奇偶监督码11.3.2 正反码正反码 通讯原理差错编码控制课件 奇数监督码奇数监督码: : 偶数监督码偶数监督码: :监督码元监督码元 1
15、 位位, ,使码组中使码组中“1” 的个数为的个数为奇奇监督码元监督码元 1 位位, ,使码组中使码组中“1” 的个数为偶的个数为偶只能检测奇数个错码只能检测奇数个错码二维奇偶监督码(矩阵码)二维奇偶监督码(矩阵码)能检测部分偶数个错码能检测部分偶数个错码 生成规则:生成规则: 许用码组写成一行(包括信息码和许用码组写成一行(包括信息码和1 位位监督码),设共有监督码),设共有m 行。第行。第 m+1 行为按列增行为按列增加的监督码。(构成监督码行)加的监督码。(构成监督码行) 例例11.3.1 奇偶监督码奇偶监督码一维奇偶监督码一维奇偶监督码 例例监督方程监督方程监督方程监督方程通讯原理差错
16、编码控制课件信源信源发送信息码发送信息码a2 a1 监督码监督码a0晴晴0 00云云0 11阴阴1 01雨雨1 10例例 :一维偶数监督码一维偶数监督码接收码组接收码组判别判别001、010、100010、001、111100、111、001111、100、010错错 1 位位检验满足检验满足检验检验不满足不满足只能检错,不能纠错只能检错,不能纠错通讯原理差错编码控制课件2)当)当 同时出错,则按行按列均不能检测出有错。同时出错,则按行按列均不能检测出有错。 能检测部分偶数个错码适用于突发信道。能检测部分偶数个错码适用于突发信道。 若若仅仅一一行行有有奇奇数数个个错错码码时时,可可通通过过列列
17、确确定定错错码码位置并纠正。位置并纠正。1)设)设 和和 发生错码,按行无法检测出错,而按列可检测。发生错码,按行无法检测出错,而按列可检测。a2 a1 a00 0 00 1 11 0 11 1 00 0 0例例 :二维偶数监督码二维偶数监督码通式通式结论:结论: 方阵码除对构成矩形四角的错码无法检测外,方阵码除对构成矩形四角的错码无法检测外,其余均能检测。其余均能检测。通讯原理差错编码控制课件特征:特征:具有纠正具有纠正 1 位错码、检测位错码、检测 2 位和大部分位和大部分 2 位以上位以上错码的能力错码的能力定义:定义:信息码位数与监督码位数信息码位数与监督码位数相同相同 编码编码规则:
18、规则: 1) 当信息位中有当信息位中有奇奇数个数个“1”时,监督位是信息位的重复。时,监督位是信息位的重复。2) 当信息位中有当信息位中有偶偶数个数个“1”时,监督位是信息位的反码。时,监督位是信息位的反码。1 0 0 0 1 例:例:若信息码为若信息码为 1 1 0 0 1 11.3.2 正反码正反码 则正反码为则正反码为 1 1 0 0 1 1 1 0 0 11 0 0 0 1 0 1 1 1 01)将接收码组中信息码和监督码对应按位模)将接收码组中信息码和监督码对应按位模2 加,得加,得合成码组合成码组2)根据接收码组中信息码含)根据接收码组中信息码含 “1” 的奇偶情况,由合的奇偶情况
19、,由合成码组生成成码组生成校验码组校验码组 3)根据校验码组的值依表判断错码情况,并予检、纠错)根据校验码组的值依表判断错码情况,并予检、纠错译码译码规则:规则:“1”为奇为奇 校验校验 = 合成合成“1”为偶为偶 校验校验 =例例通讯原理差错编码控制课件例:发例:发 1 1 0 0 1 1 1 0 0 1 1)收无错)收无错 信息码中含奇数个信息码中含奇数个“1”2)收有错、为)收有错、为 1 0 0 0 1 1 1 0 0 1合成码组合成码组= 1 1 0 0 1 1 1 0 0 10 0 0 0 0译码判决:译码判决:校验码组校验码组错码情况错码情况 1全全 “0” 无错码无错码 24
20、个个“1”1 个个“0” 信息码中有一位错码,对应信息码中有一位错码,对应校验码组中的校验码组中的“0” 的位置的位置 34 个个“0”1 个个“1” 监督码中有一位错码,对应监督码中有一位错码,对应校验码组中的校验码组中的“1” 的位置的位置 4其他组成其他组成 错码多于错码多于 1 个个 校验码组校验码组 = 合成码组合成码组 = 00000判断接收无错码判断接收无错码合成码组合成码组= 1 0 0 0 1 1 1 0 0 10 1 0 0 0 信息码中含偶数个信息码中含偶数个“1”查表知信息码第二位错查表知信息码第二位错特征:特征:编码效率低编码效率低通讯原理差错编码控制课件11.4 线
21、性分组码线性分组码11.4.1 汉明码的编码原理汉明码的编码原理11.4.2 一般线性分组码的编码原理一般线性分组码的编码原理11.4.3 线性码分组码的数学描述线性码分组码的数学描述通讯原理差错编码控制课件11.4.1 汉明码的编码原理汉明码的编码原理定义:定义:能纠正一位错码,且能纠正一位错码,且编码效率较高编码效率较高的线性分组码的线性分组码问题:问题: 在正反码中,为纠正一位错码,其监督码位数与信息码在正反码中,为纠正一位错码,其监督码位数与信息码位数一样多,能否减少监督码位数但纠错能力不变?位数一样多,能否减少监督码位数但纠错能力不变?如何实现纠错?如何实现纠错?思路:思路:分组码分
22、组码( n , k )只可能出现只可能出现 n 个一位错码事件,若某种逻个一位错码事件,若某种逻辑组合具有辑组合具有n 个状态,就能利用这种逻辑组合描述一位错个状态,就能利用这种逻辑组合描述一位错码事件并予纠正。码事件并予纠正。例:例:分析偶数监督码,寻找逻辑组合分析偶数监督码,寻找逻辑组合汉明码汉明码 监督方程监督方程 则接收时解码是在计算则接收时解码是在计算0 无错无错1 有错有错定义:定义:校正子校正子 S =只能表示出错只能表示出错不能描述错码位置不能描述错码位置一位监督码对应一位监督码对应一个监督方程一个监督方程结论:若增加监督码元,建立多个监督方程,多个校正子就能形结论:若增加监督
23、码元,建立多个监督方程,多个校正子就能形成逻辑组合描述错码位置成逻辑组合描述错码位置通讯原理差错编码控制课件汉明码汉明码确定监督码元位数确定监督码元位数 r确定监督关系表确定监督关系表建立监督方程建立监督方程建立编码方程建立编码方程 分组码分组码( n , k ) 共需共需 n+1 个状态描述无错及个状态描述无错及 n 个有错事件个有错事件为提高编码效率,为提高编码效率, r 取最小值取最小值例:例:已知已知( 7 , 4 )码,码,r = 3 共有共有3个监督方程,构成个监督方程,构成 3个校正子个校正子 S1 S2 S3S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1
24、错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错例例通讯原理差错编码控制课件例:已知例:已知 ( 7 , 4 )汉明码汉明码 ,求码组集合,求码组集合解:解:S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0 1a6 错错 监督方程监督方程 编码方程编码方程 k = 4,信息码组有信息码组有 16 个个a6 a5 a4 a3a2 a1 a00 0 0 00 0 00 0 0 11 1 00 0 1 00 1 10 0 1 11 0
25、 1.1 1 0 00 1 01 1 0 11 0 01 1 1 00 0 11 1 1 11 1 1 r = 3通讯原理差错编码控制课件例:例:汉明码的监督方程为汉明码的监督方程为 矩阵表达式矩阵表达式11.4.2 一般线性分组码的编码原理(矩阵方程)一般线性分组码的编码原理(矩阵方程)记为:记为:H :监督矩阵:监督矩阵A :码组向量:码组向量当当 称称 H 为典型矩阵为典型矩阵(含单位阵)(含单位阵)思路:思路:确定编码矩阵方程,确定编码矩阵方程,构造构造生成矩阵生成矩阵通讯原理差错编码控制课件又又 根据监督方程确定了根据监督方程确定了编码方程编码方程两边同取转置两边同取转置构造构造生成
26、矩阵生成矩阵称称 G 为典型生成矩阵为典型生成矩阵(含单位阵)(含单位阵) 编码矩阵方程编码矩阵方程特点:信息位不变,监督位附加于其后。特点:信息位不变,监督位附加于其后。定义定义系统码:由典型生成矩阵得出的码组系统码:由典型生成矩阵得出的码组 A通讯原理差错编码控制课件生成矩阵生成矩阵G 中中每行均为一个码组,且线性无关每行均为一个码组,且线性无关通讯原理差错编码控制课件译码运算,当译码运算,当S 为校正子。说明为校正子。说明 S 与与E 间有确定的线性关系间有确定的线性关系若若 E 的数目有限的数目有限,能与能与 S 一一对应,一一对应,则则 说明说明 S 能描述错码的位置,具有纠错能力。
27、能描述错码的位置,具有纠错能力。11.4.3 线性码分组码的数学描述线性码分组码的数学描述令令 发码组为发码组为 A、收码组为、收码组为 B 错码图样错码图样 E = B - A收发码组的关系收发码组的关系0 无错无错1 有错有错 令令 B =E + A例例通讯原理差错编码控制课件发码组发码组 A = 1 1 0 0 0 1 0收码组收码组 B = 1 0 0 0 0 1 0 译码运算译码运算例:例: ( 7 , 4 )汉明码汉明码, S1 S2 S30 0 0无错无错0 0 1a0 错错0 1 0a1 错错1 0 0a2 错错1 1 0a3 错错0 1 1a4 错错1 1 1a5 错错1 0
28、 1a6 错错 a5 错错含义:含义:错码图样错码图样 E =(0 1 0 0 0 0 0) 只有一位错码只有一位错码通讯原理差错编码控制课件定义:定义:线性码中任意两个码组之和仍为这种码中的一个码组线性码中任意两个码组之和仍为这种码中的一个码组证:证: 设设 A1 、 A2 为线性码中两个许用码组为线性码中两个许用码组两式相加两式相加是许用码组是许用码组推广:推广:1)两个码组间的距离必是另一码组的重量)两个码组间的距离必是另一码组的重量2)除)除 0 码组之外,码组的最小重量是码集合的最小距离码组之外,码组的最小重量是码集合的最小距离线性分组码具有线性分组码具有封闭性封闭性通讯原理差错编码
29、控制课件11.5 循环码循环码 11.5.1 码多项式码多项式11.5.2 循环码的特性循环码的特性11.5.3 循环码的编码方法循环码的编码方法通讯原理差错编码控制课件码多项式的按模运算码多项式的按模运算11.5.1 码多项式码多项式码多项式码多项式定义:定义:以码组中各码元为系数的多项式以码组中各码元为系数的多项式T( x ) = an-1 x n-1 + an-2 x n-2 + . + a1 x + a0设设 多项式多项式 F( x ) 、除数为、除数为 N( x )模模 N( x )运算运算注:注:多多项式按模项式按模 N( x ) 运算过程中,其系数按运算过程中,其系数按模模2 加
30、加运算。运算。 (系(系 数为二进制,只能取数为二进制,只能取 0 或或 1 )。)。x 仅为码元位置仅为码元位置的标记的标记例例R( x ):余式余式例:例:( 110 0101 ) T( x ) = x 6 + x 5 + x 2 + 1通讯原理差错编码控制课件例:例:解:解:记为:记为:余式余式通讯原理差错编码控制课件定理:若定理:若 T ( x ) 对应一个码长为对应一个码长为 n 的许用码组,的许用码组,证:证: 令令 T(x) 的系数是的系数是 T( x ) 中系数向左循环移位中系数向左循环移位 i 次的结果次的结果11.5.2 循环码的特性循环码的特性码集合中任意一个码组,左移或
31、右移一位得到的新码组码集合中任意一个码组,左移或右移一位得到的新码组必是该码集合中另一码组必是该码集合中另一码组循环码的定义循环码的定义循环码的码多项式循环码的码多项式则则 x i T( x ) 按模按模 x n +1 运算后运算后余式余式T(x) 仍为许用码组。仍为许用码组。例例通讯原理差错编码控制课件例:例: ( 7 , 3 )循环码循环码, 码组为码组为( 110 0101 ),求码多项式,求码多项式T( x ); 验证验证 x 3 T( x ) 按模按模 x 7 +1 运算后余式仍是一个许用码组。运算后余式仍是一个许用码组。解:解: T( x ) = an-1 x n-1 + an-2
32、 x n-2 + . + a1 x + a0 T( x ) = x 6 + x 5 + x 2 + 1 x 3 T( x ) = x 9 + x 8 + x 5 + x 3 余式余式T(x) 对应码组为对应码组为 ( 0101110 ) 是是T (x) 码组左移三位码组左移三位通讯原理差错编码控制课件循环码的生成矩阵循环码的生成矩阵 G11.5.3 循环码的编码方法循环码的编码方法思路:思路:确定编码矩阵方程,确定编码矩阵方程,构造构造生成矩阵生成矩阵码生成多项式码生成多项式 g( x )循环码的监督矩阵循环码的监督矩阵 H码生成多项式码生成多项式 g( x ) 的求解的求解例例G 是是 G(
33、 x ) 的系数矩阵的系数矩阵循环码的检、纠错能力循环码的检、纠错能力与与 n、k 的值相关的值相关循环码的编码方法循环码的编码方法通讯原理差错编码控制课件循环码循环码生成矩阵生成矩阵 G 的数学描述的数学描述已知已知 ( 7 , 4 )汉明码汉明码 G 中每行均为一个码组,且线性无关中每行均为一个码组,且线性无关是线性分组码的共性。是线性分组码的共性。循环码是线性分组码成员之一,其循环码是线性分组码成员之一,其 G 除满足上述除满足上述特性外,每行之间必须满足特性外,每行之间必须满足循环性。循环性。 循环码每个码组对应一个码多项式循环码每个码组对应一个码多项式 以最简方式寻找以最简方式寻找
34、k 个线性无关的码多项式就能建立个线性无关的码多项式就能建立 G( x )通讯原理差错编码控制课件码生成多项式码生成多项式 g( x )定义:定义: g( x )是幂次为是幂次为 ( n- - k ) 的码多项式。(唯一性)的码多项式。(唯一性)分析循环码:循环码分析循环码:循环码( n , k ) 的形成方法是在信息码后加监督码的形成方法是在信息码后加监督码且保持移位循环的特征。且保持移位循环的特征。 除全零码组外,权值最除全零码组外,权值最小的小的信息码组信息码组为为 0 0 .0 0 1 ,且监督位,且监督位 a0 不可能不可能为零为零,否则循环数次后码组前,否则循环数次后码组前 k 位
35、均为零,而监位均为零,而监督位不为零的情况,这不符合监督码的定义督位不为零的情况,这不符合监督码的定义结论:信息码组结论:信息码组 0 0 .0 0 1 对应的码多项式必为对应的码多项式必为( n- k ) 次幂,次幂,且常数项不等于零且常数项不等于零 信息码组信息码组 0 0 .0 0 1 唯一唯一 码多项式唯一,且码多项式唯一,且幂次最低,记为幂次最低,记为 g( x ) 与与 g( x ) 线性无关的线性无关的 k- -1 个个码多项式为码多项式为 x g( x )、 . x k-1g( x ),可组成生成矩阵可组成生成矩阵 G( x ) 通讯原理差错编码控制课件码生成多项式码生成多项式
36、 g( x ) 的求解的求解定理:定理:g( x ) 是是 x n +1 的一个的一个( n - - k ) 次因子。次因子。证:证: g( x ) 是幂次最低的码多项式是幂次最低的码多项式 任意一个码多项式任意一个码多项式 T( x ) 都是都是 g( x ) 倍数倍数令令 T( x ) = h( x ) g( x ) 余式余式为码组为码组 x k g( x ) = x n +1 + T( x ) x n +1 = x k g( x ) + T( x ) 模模 2 加加= x k g( x ) + h( x ) g( x ) = x k + h( x ) g( x ) 得证得证通讯原理差错编
37、码控制课件例:已知例:已知 ( 7 , 3 ) 循环码,求码组集合循环码,求码组集合 、监督矩阵、监督矩阵 H 。解:解: n = 7 x7 + 1 = ( x +1 )( x 6 + x 5+ x 4 + x 3 + x 2+ x + 1 ) = ( x +1 )( x 3 + x 2+ 1 )( x 3 + x + 1 ) g1( x ) = ( x +1 )( x 3 + x 2+ 1 ) = x 4 + x 2+ x + 1 g2( x ) = ( x +1 )( x 3 + x + 1 ) = x 4 + x 3+ x 2 + 1 取取 g( x ) = g1( x ) = x 4
38、+ x 2+ x + 1 通讯原理差错编码控制课件 A = ( a6 a5 a4 a3 a2 a1 a0 ) a6 a5 a4 a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 00 0 1 1) 0 0 1 0 1 1 10 1 0 2) 0 1 0 1 1 1 00 1 1 4) 0 1 1 1 0 0 11 0 0 3) 1 0 1 1 1 0 01 0 1 7) 1 0 0 1 0 1 11 1 0 5) 1 1 1 0 0 1 01 1 1 6) 1 1 0 0 1 0 1监督方程:监督方程: d0 = 4 t = 1 非系统码非系统码通讯原理差错编码控制
39、课件循环码的编码方法循环码的编码方法思路:思路:已知信息码组多项式已知信息码组多项式 m( x ),建立,建立T( x )编码步骤为:编码步骤为:1)生成)生成 x n-k m( x )2)生成)生成 x n-k m( x ) / /g( x ),求余式,求余式 r ( x )3)生成循环码多项式)生成循环码多项式 T ( x )T( x ) = x n-k m( x ) + r( x )a6 a5 a4 a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 00 0 1 1) 0 0 1 0 1 1 10 1 0 2) 0 1 0 1 1 1 00 1 1 4) 0
40、1 1 1 0 0 11 0 0 3) 1 0 1 1 1 0 01 0 1 7) 1 0 0 1 0 1 11 1 0 5) 1 1 1 0 0 1 01 1 1 6) 1 1 0 0 1 0 1例:例:m( x ) = 101 建立建立( 7 , 3 ) 循环码循环码解:解: x n-k m( x ) = 1010000g( x ) = x 4 + x 2+ x + 1 r ( x ) = x 3 + x 2 T( x ) = x 6 + x 4 +x 3 + x 2码组为码组为 1011100 系统码系统码非系统码非系统码通讯原理差错编码控制课件bcda输入输入输出输出开关开关SS 同时
41、上下同时上下( 7 , 3 ) 循环码编码循环码编码通讯原理差错编码控制课件11.6 卷积码卷积码 11.6.1 卷积卷积码的图形描述码的图形描述11.6.2 卷积码的解析描述卷积码的解析描述 k : 信息码元信息码元 n : 码组长度码组长度 N :约束长度:约束长度符号符号( n , k , N )定义:线性非分组码定义:线性非分组码特点:相邻数个码组的编码相互约束特点:相邻数个码组的编码相互约束本码组编码不仅与自身的本码组编码不仅与自身的 k 位信息码有关,位信息码有关, 还与前面还与前面 ( N-1 ) 个码组的信息个码组的信息段段有关有关通讯原理差错编码控制课件11.6.1 卷积卷积
42、码的图形描述码的图形描述m3m2m1输入序列输入序列 m1m2. mj.输出序列输出序列y1jy2jy3j y1jy2jy3j. y1jy2jy3j m1m2m3m1y21y31m2y22y32m3y23y33输入输出序列输入输出序列速度匹配关系速度匹配关系移位寄存器移位寄存器树状图树状图网格图网格图状态图状态图( 3 , 1 , 3 ) 卷积码的编码器卷积码的编码器输出序列的变化规律输出序列的变化规律通讯原理差错编码控制课件树状图树状图00010110101001110100000000011111100101101010010111000011100111001011101aababc10
43、1dbacdabcda :m1m2 = 00b :m1m2 = 01c :m1m2 = 10d :m1m2 = 11寄存器初态寄存器初态m3 m3 m3 m3 m1m2m3y1jy2jy3j 0011011011001001m1m2 0 0通讯原理差错编码控制课件网格图网格图000bcda010110111101000111001特点:相同状态的节点合并特点:相同状态的节点合并100011( 3 , 1 , 3 ) 卷积码卷积码初态初态上支路实线上支路实线下支路虚线下支路虚线从第从第 N 个节点开始图形重复出现个节点开始图形重复出现2N-1 种种通讯原理差错编码控制课件状态图状态图000bcd
44、a010110111101001100011bcdabcda特点:状态稳定后的转移图特点:状态稳定后的转移图例例通讯原理差错编码控制课件010110111100 001 100 110 101例:输入序列为例:输入序列为 11010111,初始状态为,初始状态为 a ,求求 ( 3 , 1 , 3 ) 卷积码。卷积码。 1bcda1010111000111110001100011010101解:利用网格图求输出序列解:利用网格图求输出序列输出输出通讯原理差错编码控制课件11.6.2 卷积码的解析描述卷积码的解析描述生成矩阵生成矩阵 G矩阵形式矩阵形式当初态全为零时,第一、第二比特输入时存在过渡过程当初态全为零时,第一、第二比特输入时存在过渡过程系数矩阵系数矩阵通讯原理差错编码控制课件定义:输入序列矩阵定义:输入序列矩阵 M、输出序列矩阵、输出序列矩阵 Y、生成矩阵、生成矩阵 G半无限矩阵半无限矩阵监督矩阵监督矩阵 H通讯原理差错编码控制课件监督矩阵监督矩阵 H输出序列输出序列 m1 y21 y31 m2 y22 y32 m3 y23 y33监督关系监督关系前前 3 列下移列下移 2 行行前前 6 列决定列决定 ,分析,分析截短矩阵截短矩阵通讯原理差错编码控制课件