《差错控制编码_2课件》由会员分享，可在线阅读，更多相关《差错控制编码_2课件（53页珍藏版）》请在金锄头文库上搜索。
1、 数 字 通 信 原 理 Principles of Digital CommunicationF,中南大学信息科学与工程学院 School of Information Science and Engineering Central South University 主讲：李敏 联系方式： 课件邮箱： txyl_,第七讲 差错控制编码,7.1 基本概念 7.2 纠错编码原理 7.3 常用的简单编码 7.4 线性分组码 7.5 循环码,重点和难点：,差错控制的目的和基本原理； 差错控制方式及其特点； 码重、汉明距离、最小距离的概念和确定； 纠错和检错能力分析 编码效率 汉明码和CRC码,第七
2、讲 差错控制编码,7.1 基本概念,产生误码的原因：,系统特性的不理想： 乘性噪声数字信号波形失真接收端误判形成误码 信道噪声干扰： 加性噪声数字信号变形误码,信道分类(按加性噪声引起的错码分布规律)：,随机信道：白色高斯噪声，误码相互独立； 突发信道：存在突发脉冲干扰，误码在短时间内成串出现，并前后有关； 混合信道：随机信道突发信道,7.1 基本概念,差错类型：,随机差错独立差错： 差错的出现随机，且差错之间是统计独立的 由随机噪声引起 突发差错： 差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关 因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起,7.1 基
3、本概念,提高系统可靠性的途径：,加大发送功率：即提高信噪比，虽简单有效，但功率不可无限增加，实际受到一定的限制； 匹配滤波接收：可抑制白色噪声，使误码率下降； 合理的调制解调方式 PePSKPeDPSKPeFSK相干、ASKPeASK,PSK非相干 差错控制编码：正交编码或纠错编码 正交编码：选择抗干扰能力强的信号集合，使受干扰后不容易混淆，常和调制方式结合在一起； 纠错编码：使信号受干扰而出错后在译码判决时能自动纠正错误。,7.1 基本概念,差错控制方式：,前向纠错（FEC: forward error correction） 检错重发（ARQ: automatic repeat reque
4、st） 混合纠错（HEC: hybrid error correction）,差错控制编码的基本思想：,在发送端被传输的信码序列上附加一些监督码元（冗余码元），使所传输的码字中前后码元产生一定的相关性，具有一定的监督关系，接收端利用这种监督关系来检测，纠正错误。,理论依据：Shannon信道编码定理。,Shannon信道编码定理: 对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。,7.1 基本概念,按监督码元和信息码元关系不同：线性码（Linear Codes）、非线性码（non-L
5、inear Codes） 按对信息元处理的方法不同：分组码（Block Codes）、卷积码（Convolutional Codes） 按纠错类型分：纠随机错误的码、纠突发错误的码 按功能分：检错码、纠错码、纠删码 按码元取值不同：二进制码、多进制码 按编码的数字方式不同：代数码、几何码、算术码 按编码后是否保持原有形式：系统码、非系统码 按码字结构特点：循环码、非循环码,差错控制编码分类,7.2 纠错编码原理,检错和纠错：,检错:知道在若干码元中有错码，但不一定知道错码的准确位置。 纠错：能确定错码的位置，并对其进行纠正。,差错控制编码的基本思想：,发送端按照某种规则在信息序列上附加监督码元
6、，接收端则按照同一规则检查两者间关系 以牺牲通信的有效性（信息传输速率）来提高可靠性 码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多,举例说明：假如要传送晴天、雨天两个消息,编码一: 消息A-“0”；消息B-“1” 若传输中产生错码(01或10)，收端无法发现。 该编码无检错纠错能力。,编码二 消息A-“00”；消息B-“11” 若传输中产生一位错码，则变成“01”或“10”，收端判决为有错,但无法确定错码位置，不能纠正。 该编码具有检出一位错码的能力。,7.2 纠错编码原理,举例说明：假如要传送晴天、雨天两个消息,编码
7、三 消息A-“000”；消息B-“111” 传输中产生一位即使两位错码，收端都能判决传输有错。该编码具有检出两位错码的能力。 在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。,结论 增加冗余，可提高检纠错能力； 增加冗余，会降低传输的信息量，编码效率降低；,7.2 纠错编码原理,7.2 纠错编码原理,几个基本概念 许用码：用于传输信息的码组； 禁用码：在传输信息中不可能出现的码组； 监督位：增加的不携带传输信息的、但具有一定约束的码位； 分组码：将信息码分组，并为每组信息码附加若干监督码的编码； nkr； n为实际传送的码长，k是信息
8、码长；r是监督码长； 码距d：接收码Cr与发送码CL之间不同的码元个数的数目； 码重W：码字中“1”的个数； 最小码距d0：一个码型中任何两个码字之间的最小距离，又称为汉明距离； 最小码重W0：一个码型中任意码字的码重的最小值；,7.2 纠错编码原理,码距与检、纠错能力的关系: 最小码距与检错能力的关系 一个码能检测e个错码，则要求其最小码距 d0e+1 即：若最小码距为d0，则最多能检测d0-1个错码。 最小码距和纠错能力的关系 一个码能纠正t个错码，则要求其最小码距 d02t+1 即：若最小码距为d0，则最多能纠正(d0-1)/2个错码。 最小码距和同时检纠错能力的关系 一个码能纠正t个错
9、码，同时能检测e个错码，则要求其最小码距 d0e+t+1 (et),7.2 纠错编码原理,差错控制编码的效果 假设随机信道中发送“0”码与发送“1”码传错概率相等为Pe,且Pe1,则在码长为n的码组中发生r个错误的概率为： Pn(r)=Cnr Per(1- Pe)n-rn!/r!(n-r)! Per 当码长n=7, Pe=10-3时，则有 P7(1)7 Pe=7 10-3 P7(2)21 Pe2=2.1 10-5 P7(3)35 Pe3=3.5 10-8,7.2 纠错编码原理,编码效率 指一个码组中信息位所占比重，用表示 =k/n，其中k为信息码元的数目，n为码长,可见：若加入的监督位越多，纠
10、错能力越强，编码效率越低； 纠错编码的任务是，根据不同干扰特性设计出纠检错能力最强，效率高的纠错码，且译码设备不太复杂；,7.3常用的简单编码,奇偶校验码奇偶监督码: 奇监督码：使码字加上1位监督位C0后，码字中“1”的个数为奇数个； 偶监督码：使码字加上1为监督位C0后，码字中“1”的个数为偶数个； 只能检测出奇数个错误，不能纠错 应用：以随机错误为主的计算机通信系统，难于对付突发错误 最小码距dmin=2,7.3常用的简单编码,水平奇偶校验码: 【编码规则】 （1）对需要传输的数据，进行奇偶校验编码； （2）将经过奇偶监督编码的码元序列按行排成方阵，每行为一组奇偶校验编码； （3）发送时按
11、照列的顺序传输； （4）接收端仍将码元排成发送时的方阵形式，然后按行进行奇偶校验。,【例】偶校验：0100 1 1000 1 传输时为: 01 10 00 00 11,7.3常用的简单编码,二维奇偶校验码水平垂直奇偶监督码,将奇偶校验码的若干码组排列成矩阵 每一码组写成一行 m个码组m行 m个监督位构成了一监督位列 按列的方向增加第二维校验位 n个监督位构成了一监督位行,检错能力: 检出所有行和列中的奇数个差错 能检出大多数偶数个差错 能检出突发长度不大于方阵行数或列数的突发错误适用于检测突发错误，将使误码减少到原来的11,7.3常用的简单编码,二维奇偶校验码水平垂直奇偶监督码,7.3常用的简
12、单编码,等比码,每个码组中含“1”和“0”的个数的比例恒定，又称等重码、恒比码、定1码； 能检测出所有1位错和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出） 简单，适应于对字母或符号进行编码，常用于电传机传输汉字，以及其他产生固定字符的键盘设备中；,【例】电传机传输数字时广泛采用的五单位数字保护电码，是一种五中取三的恒比码，共有,种组合，代表10个阿拉伯数字。,7.3常用的简单编码,正反码,监督位数与信息位数目相同，且两者相同或相反，取决于信息序列中“1”的个数； 编码规则 当信息位中有奇数个“1”时，监督位是信息位的简单重复； 当信息位中有偶数个“1”时，监督位是信息位的反码；
13、 接收端解码 先将码组中信息位与监督位按位模2加，得到合成码组; 产生校验码组：码组中信息码元有奇数个“1”，则校验码组=合成码组，否则校验码组=合成码组的反码 按照校验码组中“1”的个数进行检错及纠错,7.3常用的简单编码,正反码,7.3常用的简单编码,正反码,举例：电报通信中常用5单位电码来构造正反码 编码 若为11001，则码字为1100111001 若为10001，则码字为1000101110 假设发送码组为1100111001 若接收码组为1100111001，判决为无错传输 若接收码组为1000111001：合成码组01000（先将码组中信息位与监督位按位模2加，得到合成码组）；因
14、码组中信息码元有偶数个“1”，则校验码组为10111；说明信息码元中第二位错码，给以纠正 若接收码组为1100101001：合成码组10000；因码组中信息码元有奇数个“1”，则校验码组为10000 ，说明监督码元中第一位错码 若接收码组为1001111001：合成码组01010；因码组中信息码元有奇数个“1”，则校验码组为01010，说明错码多于1个 码长为10的正反码能够纠正1位差错，并能检测所有2位及以下的错码。,7.4 线性分组码,系统码：信息码元编码后，信息码元本身不变，而只在信息码元后加入监督码元，即前半部分为不变的信息码元，后半部分为监督码元的码型； 线性码：监督码元和信息码元成
15、线性关系的码型； 分组码：监督码元只和本身信息码元有关的码型； 线性分组码：利用代数关系，将信息序列划分为等长的k位序列段，在每一信息段后附加r个监督码元，并使监督码元和信息码元成线性关系，这样构成的码型就叫； 汉明码：纠单个错的线性分组码； 循环码：在严谨的代数基础上构造的、纠错能力强的解编码设备并不复杂的线性分组码； 卷积码：监督码元不仅与本身信息码元有关，且跟其它码元有关的一种码型；,基本概念,7.4 线性分组码,具有封闭性，即任意两许用码组之和仍为一许用码组； 码距的最小值等于最小码重（除全“0”码组以外）； 线性分组码的表示（n，k），码长为n，信息码长为k，监督码长rnk； 一致校
16、验矩阵H(Paritycheck Matrix): 用于说明监督码元与信息码元监督关系的矩阵,线性分组码的特点：,举例：（7，4）码,设码元表示为：C=C6C5C4C3C2C1C0； 由（7，4）码可知：n=7，k=4，r=3； 假设：,中南大学 通信原理,7.4 线性分组码,写成矩 阵形式：,一致校验矩阵H,中南大学 通信原理,7.4 线性分组码,举例：（7，4）码,(n,k)码的所有码字均按H所确定的规则求出 H矩阵的每一行代表一个线性方程的系数， 它表示求一个校验元的线性方程。 H矩阵每一列代表此码元与哪几个校验方程 有关。,k+r =n列,一致校验矩阵H的特性： H是rn阶矩阵，r为监督码元个数，n为码长； H=P|Ir，P是rk阶阵，Ir为r个监督码系数构成的rr阶单位
