《通信原理差错控制编码》由会员分享,可在线阅读,更多相关《通信原理差错控制编码(80页珍藏版)》请在金锄头文库上搜索。
1、联合战术通信教研组 张伟明理工大学通信工程学院数字通信原理数字通信原理1第7章 差错控制编码7.1 概述7.2 纠错编码的基本原理7.3 常用的简单编码7.4 线性分组码7.5 循环码7.6 卷积码7.7 伪随机序列 7.8 现代编码技术 27-1 概述n信源编码:为了提高数字信号的有效性而采取的编码, 又称有效性编码;n信道编码:为了提高数字通信的可靠性而采取的编码, 又称可靠性编码、抗干扰编码、纠错编码或差错控制编 码。n信道编码原理:在原始数字信号中加入带有规律性的码 元,信道译码器利用这些规律性来鉴别是否发生错误, 或进行错误纠正。37-1 概述编码的本质:增加冗余度,牺牲有效性以提高
2、可靠性。编码的方法:对原信息进行变换,加入附加信息(即监督码)。例: (4,1)重复码0: 0000 1: 11114随机错误:零星分布的错误突发错误:集中出现的错误突发信道:以突发错误为主随机信道:以随机错误为主混合信道:两种错误均较明显对错误的处理方式:检错、纠错、纠检结合一、差错及信道分类5发端收端前向纠错FEC纠错码发端收端检错重发ARQ(Automatic Repeat reQuest)检错码确认信号ACK发端收端信息反馈IF信息信号信息信号发端收端混合纠错HEC检错和纠错码确认信号ACK二、差错控制的基本工作方式67-2 纠错编码的基本原理 用两位编码可表示4种天气: 信息位晴00
3、云01阴10雨11监督位0110增加1位监督位,则可检测1位错误。3位编码共有8个码组,上述4种为许用码组(合法码组 ),其它4种为禁用码组。7(1) 码长、码重和码距n码长n:码组(码字)中码元的数目。n码重w:码组中非0码元的数目。n码距d:两个等长码组之间对应位不同的数目称 为这两个码组的的汉明距离,简称码距。例如码组C1=11010,则码长n=5,码重w=3;C1=11010与码组C2=10100之间的距离为d=3。n两个二进制码组模二相加得到的新码组的重量就 是这两个码组之间的距离。1.纠错码的基本概念82.分组码的纠(检)错能力与d0的关系最小码距d0:所有码组之间的最小码距,决定
4、码的纠检错能力。(1)检测e个随机错误:(2)纠正t个随机错误:(3)纠正t个同时检测e(t)个随机错误:ABd0eAABd0ttA Bd0ABetAB92.分组码的纠(检)错能力与d0的关系以(n,1)重复码为例:A、B两种消息用“1”、“0”表示,编为(2,1)重复码为“11”及“00”d0为2,可检测1位错编为(3,1)重复码为“111”及“000”d0为3,用于检错时,可检出2位错用于纠错时,根据最大似然准则,可纠正1位错编为(4,1)重复码为“1111”及“0000”d0为4,用于检错时,可检出3位错用于纠错时,可纠正1位错的同时检出2位错10对纠错码的基本要求是:n纠错和检错能力尽
5、量强;n编码效率尽量高;n码长尽量短;n编码规律尽量简单。 3.对纠错编码的基本要求及效用编码效率:码元中信息元所占的比例,通常用R=k/n 来表示114.纠错编码的效用采用差错控制编码,即使仅能检测或纠正码组中12个错误 ,也可以使误码率下降几个数量级。这就表明,即使是较简单 的差错控制编码也具有较大实际应用价值。 码长为n的码组中恰好发生r个错码的概率为 :当码长n7,pe=103时,则有 121.奇偶监督码(奇偶校验码):在n1个信息元后面附加一个监督元,使得长n的码 子中1的个数保持为奇数或偶数的码称为奇偶监督码 。7.3 常用的简单编码 偶校验码监督方程:奇校验码监督方程:d0=2,
6、可检测1位错及其它奇数个错13码长为5的偶监督码序 号码 字序 号码 字信息码元监督元信息码元监督元0 0 0 0 00 8100011 0 0 0 11 91 0 0 102 0 0 1 01101 0 1 003 0 0 1 10111 0 1 114 0 1 0 01121 1 0 005 0 1 0 10131 1 0 116 0 1 1 00141 1 1 017 0 1 1 11151 1 1 1014又称行列监督码或矩阵码。它同时对水平方向及垂直 方向的码元实施奇偶监督。2.二维奇偶监督码1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1
7、1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 00 0 1 0 1 1 1 0 0 0 1 1 1 1 00L5,m10的行列监督码15突发错误:逐行传输时,能检测长度b m+1=11的突发错误;逐列传输时,能检测长度bL+1=6的突发错误;2.二维奇偶监督码1 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 1 00 0 1 0 1 1 1 0 0 0 1 1 1 1 00随机错误:所有1、2、3
8、及其它奇数个错;大部分偶数个错;不能检矩形4个顶点的偶数个错163.恒比码:数字码 字 0 1 2 3 4 5 6 7 8 901101 01011 11001 10110 11010 00111 10101 11100 01110 10011又称等重码或定1码,码字中1 和0的位数保持恒定比例。我 国电传通信采用3:2数字保护 码,也称为5中取3恒比码。3:2数字保护码能够检测所有奇数个错误及部 分偶数个错误;不能检测 “1”错为“0”与“0”错为 “1”成对出现的错码。 实际使用经验表明,它能使差 错减至原来的十分之一左右。177.4 线性分组码(系统)分组码的结构 187.4 线性分组码
9、7.4.1 线性分组码的特点 码字用 表示,监督码元与信息码元之间的关系可用如下线性 方程组表示(以(7,3)分组码为例): 线性分组码的封闭性:码字集中任意两个 码字对应位模2加后得到的组合仍然是该 码字集中的一个码字。 因此,线性分组码的最小码距必等于码字 集中非全0码字的最小重量。(7,3)码的码字表序 号码 字信息元监督元00 0 00 0 0 010 0 11 1 0 120 1 00 1 1 130 1 11 0 1 041 0 01 1 1 051 0 10 0 1 161 1 01 0 0 171 1 10 1 0 0197.4.2 线性分组码的编码 简记为 :监督方 程组改
10、写为:此(7,3)分组 码的监督矩阵:207.4.2 线性分组码的编码217.4.2 线性分组码的编码 线性分组码的监督矩阵H由r行n列组成,r=n-k,且这r行是线性 无关的。监督矩阵具有形式: ,其中 为 的单位 矩 阵。P是 的矩阵。从而可通过以下矩阵运算由信息元求监督元: 或 227.4.2 线性分组码的编码 线性分组码的典型生成矩阵为: ,其中 是 的 单位矩阵。所以有由典型生成矩阵生成的码是系统码: 如 时,通过生成矩阵求得的码字为 :237.4.2 线性分组码的编码 例:已知(7,3)线性分组码监督矩阵 为求: (1)监督元与信息元之间的关系式; (2)生成矩阵; (3)此码的全
11、部码字; (4)此码的码距 及纠、检错能力; (5)此码的编码效率。247.4.2 线性分组码的编码 解:4个监督元和3个信息元之间的关系为 序 号码 字 信息元监督元 00 0 00 0 0 0 10 0 11 1 1 0 20 1 01 1 0 1 30 1 10 0 1 1 41 0 00 1 1 1 51 0 11 0 0 1 61 1 01 0 1 0 71 1 10 1 0 0生成矩阵 除全零码字以外的7个码字的重量最小值即为此 (7,3)分组码的最小码距。最小码距 如 :257.4.2 线性分组码的编码 例:重复码是最简单的一类线性分组码。(n,1)重复码总共 只有2个码字,一个
12、全0码字,另一个是全1码字。如(5,1 )重复码的两个码字分别为“00000”和“11111”。试求出 (5,1)重复码的监督矩阵和生成矩阵。解:267.4.3 线性分组码的译码 S是1行r列矩阵,它与错误图样有对应关系,而与发送码字无关 。故能确定传输中是否发生了错误及错误的位置。发送码字:接收码字:发送码字和接收码字之差:错误图样 :码字与监督矩阵约束关系:若传输发生错误时:伴随式:277.4.3 线性分组码的译码 以前面所列举的(7,3)码为例: 1求出错误图样E与伴随式S之间的关系。错1位的7种错误图 样所对应的伴随式,刚好对应 中的7行。编 号错码位置ES11000000111020
13、1000000111300100001101400010001000500001000100600000100010700000010001伴随式和错误图样的对应关系:287.4.3 线性分组码的译码 2计算接收码字的伴随式,然后查上面表得错误图样。 如接收码字为B1100111,则其伴随式为: 查上面表得错误图样E1000000 ,可见 接收码字中b6有错误。3用错误图样纠正接收码字中的错误。 297.4.3 线性分组码的译码 例:已知(7,3)线性分组码监督矩阵为 (1)检验“1100111”是否为码字; (2)当译码器接收到“1100111”时,求译码器的输出 。 纠正后的码字: 译码器
14、输出:前3位信息码元“100”。 307.4.4 汉明码31n(1)加多少位监督元可满足要求,最经济?n(2)r位监督元如何加?有没有一般规则?n以r=3为例编码器k位信息元n位码字k位信息元n-k=r位监督元取“”号最经济:在纠1位错情况下冗余最小31a4错a3错无错a2错a1错a6错a5错a0错s2 s1 s01 1 11 1 01 0 10 1 11 0 00 0 00 1 00 0 1r=3n=7, k=4信道编码器?4位信息元7位发送码组对应标识译码器7位接收码组7.4.4 汉明码32a4错a3错无错a2错a1错a6错a5错a0错s2 s1 s01 1 11 1 01 0 10 1 11 0 00 0 00 1 00 0 1r=3n=7, k=4S2=a6+a5+a4+a2S1=a6+a5+a3+a1S0=a6+a4+a3+a0a6+a5+a4+a20a6+a5+a3+a10a6+a4+a3+a00a2a6+a5+a4a1a6+a5+a3a0a6+a4+a31、列出所有差错情况;2、确定一一对应标识;3、找出监督码元与信息码元关系;S2=a6+a5+a4+a2S1=a6+a5+a3+a1S0=a6+a4+a3+a07.4.4 汉明码333434序 号码字序 号码字 信息元监督元信息元监督元 0000000081000111 10001011910011