版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、1第11章 差错控制编码11.1 概述11.2 纠错编码的基本原理11.3 常用的简单编码11.4 线性分组码11.5 循环码11.6 卷积码211.1 概述一、差错控制编码 在发送端被传输的信息序列上附加一些监督码元,这些多余码元与信息码元之间以某种确定的规则相互关联(约束),接收端按照既定的规则检验信息码元与监督码元之间的关系.3二、差错控制方法1、检错重发2、前向纠错发收检错码应答信号发收纠错码43、混合纠错发收纠检错应答信号*常用检错重发系统: 停发等候重发,返回重发和选择重发5(1)停发等候重发12331TI23发接收ACKNAK发现错误这是一种半双工的通信方式,原理简单,效率低.6
2、(2)返回重发1 2 3 4 5 6 2 3 4 5 6 7 8 91 2 3 4 5 6 2 3 4 5 6 7 8 9发接收发现错误NAK从码组2开始重发 (传输效率最高,需复杂的控制,收、发数据缓存)选择重发7 8 9 10 11 12重发码组2711.2 纠错编码的基本原理一、分类 1、按差错控制编码的功能功能:检错码、纠错码、纠删码。 2、按信息码元和附加的监督码元之间的检验关系:检验关系:线性码、非线性码。 3、按信息码元和监督码元之间的约束方约束方式:式:分组码、卷积码。8二、编码原理:二、编码原理:例:3位二进制数构成的码组表示天气全用用4种 用2种全用用4种 用2种000晴晴
3、晴100雪001云101霜阴010阴110雾雨011雨云111雹雨91、组成:信息位+监督位。2、分组码: 将信息码分组,为每组信码附加若干监督码的编码,称为分组码。在分组码中,监督码元仅监督本码组的中的信息码元。 分组码用(n,k)表示,n码组长度, k 信息位数,n k = r 监督位数。3、两个概念:(1)码重“1”的数目称为码组的重量(2)码距两个码组对应位上数字不同的位数称为码组距离(汉明距离)。 各码组间距离的最小值为最小码距 d0 104、检、纠错能力。(1)为检测 e 个错码,要求 d0 e + 1(2)为纠正 t 个错码,要求 d0 2 t + 1(3)为纠正 t 个错码,同
4、时检测 e 个错码,要求 d0 e + t +1Bd0BA12BA12BB345d011AB1te若随机信道中,发送“0”和发送“1”时的错误概率相等,为P,且P1,则码长为n 的码组恰好发生r个错码的概率为: rrnrrnnPrnrnPPCrp)!( !)1 ()(12当 n=7 P=10-3时 P(1) 710-3 P(2) 2.110-5 P(3) 3.510-8 可见,采用差错控制编码,即使仅能纠正这种码组中的1 2个错误,也可以使误码率下降几个数量级.1311.3 常用的简单编码1、奇偶监督码 无论信息位有多少,监督位只有一位,使码组中“1”的数目为偶(或奇)数。 接收端奇数监督码偶
5、数监督码10021aaann 这种码能够检测奇数个错码,适用检测随机错误142、二维奇偶监督码 把上述奇偶监督码的若干码组排列成矩阵,每一码组写成一行,然后,再按列的方向增加第二维监督位10111211aaaann20212221aaaannmmmnmnaaaa01210121ccccnn153、恒比码 每个码组均含有相同数目的“1”(和“0”).由于“1”的数目与“0”的数目之比保持恒定,故得此名.4、正反码 是一种简单的能够纠正错码的编码,监督位数目与信息位数目相同,监督位与信息位相同或相反,由信息码中的“1”的个数而定. 1611.4 线性分组码一、基本概念:1、定义:线性分组码中信息码
6、元和监督码元是用线性方程联系起来的。2、主要性质 (1)任意两许用码组之和(模2和、异或关系)仍为一许用码组. (封闭性) (2)码的最小距离等于非零码的最小重量173、特点:奇偶监督码是一种最简单的线性码,偶校验时(1)S称为校正子,又称伴随式. S=0无错,S=1 有错.(2)由r个监督方程式计算得r个校正子,可以用来指示2r-1种错误。对于一位误码来说,就可以指示2r-1个误码位置.021aaaSnn18设分组码(n,k)中k=4,为纠正一位错码,要求r3, 则 n=k+r=7S1S2S3错码位置S1S2S3错码位置001a0101a4010a1110a5100a2111a6011a30
7、00无错19024561aaaaS013562aaaaS003463aaaaS4562aaaa3561aaaa3460aaaa码长 n=2r 1,信息位 k= 2r 1 r,监督位r,这种线性分组码称为汉明码。二、编码原理:二、编码原理:1、校正子方程组、校正子方程组20编码速率=2、监督矩阵:nrrrnkrrr11211212000101110123456aaaaaaa001010110123456aaaaaaa010011010123456aaaaaaa表示成矩阵形式(nr阶)1001101010101100101110123456aaaaaaa=000PIr21简记为 或 H称为监督矩阵
8、,H确定,则编码时监督位和信息位的关系就完全确定了。 P为r k 阶 Ir为 r r 阶单位方阵 具有 P Ir 形式的H矩阵称为典型阵。3、生成矩阵:TTHA00TAH012aaa=1101101101113456aaaa22或012aaa3456aaaa1101010111113456aaaaQQIGk生成矩阵(nk阶)0123456aaaaaaa3456aaaaGA3456aaaaG23具有 形式的生成矩阵称为典型生成矩阵。 由典型生成矩阵得出的码组A中,信息位不变,监督位附加其后,这种码称为系统码。QIGk24例:设 且有3个接收码组 验证3个接收码组是否发生差错? 若在某码组中有一位
9、错码,指出哪一位。100101010110001011H1011101B1101012B1100003B25解:1)B1无错B2错B3错2) B2中,S1=a5+a4+a2=1S3=a5+a3+a0=1,相交叉判断a5错 B3中,S2=a4+a3+a1=1S3=a5+a3+a0=1,相交叉判断a3错26三、线性码的重要性质1、封闭性 任意许用两个码组之和仍为许用码组2、两个码组之间的距离必是另一码组的重量,故最小码距即码的最小重量(除全0码外)2711.5 循环码一、特点:1、循环码是一种重要的线性分组码,易于实现,性能较好.2、循环码除具有线性码的一般性质外,还具有循环性,即循环码中任一码组
10、循环一位以后,仍为该码中的一个码组.3、长为n的码组可表示成码多项式012211)(axaxaxaxTnnnn284、码多项式的模运算 若F(x) = N(x) Q(x) + R(x) 则:F(x) R(x)(模等) ( 模 N(x)、商Q(x) 、余数R(x) ) 例: )1(113224xxxxx模xxxx11243xx 412xx295、结论:在循环码中,若 T(x)是一个长为n的许用码组,则xi T(x)在按模xn +1运算下,也是一个许用码组。 即 若 则 T(x)也是一个许用码组) 1()()(nixxTxTx模30二、生成多项式:二、生成多项式:在循环码中,一个(n,k)码有2k
11、个不同码组1、(n,k)循环码的生成多项式g(x)是一个常数项为1的r=n-k次多项式2、g(x)是循环码中次数最低的多项式(全0码除外)3、 g(x)为xn+1的一个r次因子(可以有多个)4、 g(x)可以整除xn+1及任何一个码组5、 g(x)的码重就是码组的最小码距012211)(axaxaxaxTnnnn31三、生成矩阵三、生成矩阵G假如输入信息码元mk-1 mk-2 m0 则)()()()()(21xgxxgxgxxgxxGkk)()()(021xGmmmxTkkG生成矩阵不一定是典型的,但根据矩阵性质将其线性变换,可以化成典型矩阵形式G=Ik.Q32四、生成多项式g(X)的确定 T
12、(x) = h(x) g(x) 又 g(x)为一个码组, 故xkg(x)在模xn+1运算下也为一码组, 故可写成1)()(1)(nnkxxTxQxxgx33 故故 g(x) 是是 xn+1的一个的一个n k次因式次因式。 例: )(1)(xTxxgxnk)()()()()(1xhxxgxgxhxgxxkkn) 1)(1)(1(13237xxxxxx都可作为(7,3)循环码的生成多项式34五、编、解码方法1、编码步骤:*根据给定的(n,k)选定生成多项式g(x)即从xn+1的因子中选一n-k次多项式作为g(x).*所有码多项式T(x)都可被g(x)整除,据此对给定的信息位m(x)进行编码.1.
13、信息码后附加n-k个02. 3. )( xmxkn )()()()()(xgxrxQxgxmxkn)()()(xrxmxxTkn35监督位信息位例 (7,3)循环码 m(x)=x2+x, g(x)= x4 +x2+ x+1 解 5637)(xxxmx1)()(2456xxxxxxgxmxkn1112422xxxxxxr(x)11001011)(256xxxxT362、解码 将接收码组R(x)用g(x)去除,若未发生错误, R(x)能被g(x)整除, 发生错误则有余项.3711.6 卷积码(n,k,N) 监督位不仅与当前段的k个信息位有关,而且与前N-1段的信息有关, N称为卷积码的约束长度。一
14、、编码原理:以(3,1,3)码为例1、编码器模型图: M3 M2 M1+输入序列 mjy1y2y338 每输入一个比特信息,编码器输出三个比特信息,编码效率Rc=1/3。2、生成码多项式: g1=1 g2=1+x2 g3=1+x+x23、编码输出序列: 假设输入信息码为10110,则其延时多项式为m(x)=1+x2+x339那么:y1=m.g1=1+x2+x3,对应码序列10110 y2=m.g2=(1+x2+x3)(1+x2)=1+x2+x3+x2+x4+x5 =1+x3+x4+x5,对应码序列100111(溢出) y3=m.g3=(1+x2+x3)(1+x+x2)=1+x2+x3+x+x3
15、+x4+x2 +x4+x5=1+x+x5,对应码序列110001(溢出)则:总的输出码序列为 111 001 100 110 01040二、卷积码的图解表示法: (3,1,3)卷积码编码器 a 状态m1m2为00, b 状态m1m2为01, c 状态m1m2为10, d 状态m1m2为11。 M3 M2 M1+输入序列 mjy1y2Y3411、(、(3,1,3)卷积码的树状图)卷积码的树状图000000111000111001110000111001110011100010101aababcdabcdabcd1110011100111000101010001110011100111000101
16、01bcdabcdabcdabcda向上表示输入向上表示输入0;向下表示输入向下表示输入1横线上数码表示一个码组的三位422、(3,1,3)卷积码的网格图abcd000000000000000111111111111111011011011001001001001110110110110010010010101101101100实线表示输入0,虚线表示输入1433、(3,1,3)卷积码的状态图aabbccda111110101000011100001010abcd11100011010110000101101044例:例:在前述编码器中,若起始状态为a,输入序列为11010,求输出序列和状态变化路径abcd0000000000000001111
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024年度特许经营合同详细条款解析3篇
- 2024年度商场促销灯光音响设备租赁合同
- 2024年度网站建设维护合同
- 2024年度机场航站楼瓷砖铺设合同
- 2024年度建筑装饰门窗安装合同
- 2024年度信息技术服务合同标的及技术支持具体规定
- 2024年度煤矿煤质检测与分析合同
- 2024年度特许经营合同:连锁品牌加盟合作3篇
- 2024年度大型设备安装与维护合同2篇
- 2024年度版权转让合同:某作家与出版社图书出版权转让协议
- 文件评审表(标准样本)
- 2024至2030年工业软件系列专题之中国先进过程控制(APC)产业链全景与机会洞察专题研究报告
- 《无人机法律法规知识》课件-第1章 民用航空法概述
- 三年级上册数学教案-第八单元 分数的初步认识 西师大版
- 全国职业院校技能大赛高职组(酒水服务赛项)备赛试题库(含答案)
- 北京市工商行政管理系统2024年面向应届毕业生公开招聘事业单位工作人员历年(高频重点复习提升训练)共500题附带答案详解
- 2024年医师定期考核必刷题库附含参考答案
- 经外周静脉穿刺中心静脉置管(PICC)操作技术专家共识解读
- 2024年大学生安全知识竞赛考试题库500题(含答案)
- 2024数据中心浸没式液冷系统单相冷却液技术指标和测试方法
- 学科辅导与个性化学习计划三篇
评论
0/150
提交评论