差错控制编码课件.ppt

数 字 通 信 原 理 Principles of Digital Communication,中南大学信息科学与工程学院Central South UniversityCollege of Information Science and Engineering,数字通信原理,2022年12月2日星期五,第一讲 绪论第二讲 信息论基础和信号分析第三讲 模拟调制技术第四讲 信源编码技术第五讲 数字基带传输第六讲 数字调制技术第七讲 差错控制编码,数字通信原理,2022年12月2日星期五,目 录,第七讲 差错控制编码,7.1 基本概念7.2 纠错编码原理7.3 常用的简单编码7.4 线性分组码7.5 循环码,7.1 基本概念,7.1.1 产生误码的原因和信道分类一、原因系统特性的不理想： 乘性噪声数字信号波形失真接收端误判形成误码信道噪声干扰： 加性噪声数字信号变形误码二、信道分类 按加性噪声引起的错码分布规律的不同分类：随机信道：存在白色高斯噪声，误码相互独立；突发信道：存在突发脉冲干扰，误码在短时间内成串出现，并前后有关；混合信道：随机信道突发信道；,三、差错类型随机差错独立差错差错的出现随机，且差错之间是统计独立的由随机噪声引起存在这种差错的信道称为随机信道无记忆信道突发差错差错在短时间成串出现，而在其间又存在较长的无差错区间，且差错之间相关因脉冲噪声，也可能是由存储系统中磁带的缺陷或读写头接触不良引起存在这种差错的信道称为突发信道有记忆信道,加大发送功率 即提高信噪比，虽简单有效，但功率不可无限增加，所以实际上受到一定的限制；匹配滤波接收：可一直白色噪声，使误码率下降；合理的调制解调方式PePSKPeDPSKPeFSK相干、ASKPeASK,PSK非相干差错控制编码：正交编码或纠错编码正交编码：选择抗干扰能力强的信号集合，使受干扰后不容易混淆，常和调制方式结合在一起；纠错编码：使信号受干扰而出错后在译码判决时能自动纠正错误。,7.1.2 提高系统可靠性的途径,差错控制编码的基本思想 在发送端被传输的信码序列上附加一些监督码元（冗余码元），使所传输的码字中前后码元产生一定的相关性，具有一定的监督关系，接收端利用这种监督关系来检测，纠正错误。,反馈纠错/ARQ又叫检错重发法、自动请求重发方式；接收端按一定规则对收到的码组进行有无错误的判别。若发现有错，则通知发送端重发，直到正确收到为止。,7.1.3 常用的差错控制方式,要求：双向信道或反馈信道；发送和接收端都有缓存器；,具体实现时，通常有3种形式：（1）停发等候重发方式,发端在Tw时间内送出一个码组，收端收到后检查如果未发现错误，则发回一个认可信号（ACK）给发送端，发送端收到ACK信号再发下一个码组若检测到错误，则发回一个否认信号（NAK），发送端收到NAK信号后重发前一码组，并再次等候ACK信号或NAK信号发送两个码组之间有停顿时间Ti，影响了传输效率,（2）返回重发方式,与停发等候重发方式不同，其发送端不停地送出一个个连续码组，不再等候收端返回的ACK信号一旦收端发现错误并返回NAK信号，则发端从下一码组开始重发前面的N个码组N的大小取决于信号传递及处理所带来的延时,（3）选择重发方式,也是连续不断地发送码组，收端检测到错误后发回NAK信号。与(2)不同的是，发端并不重发错误码组后的所有码组，而只重发有错的那个码组三者比较： (3)传输效率最高，但成本最贵：控制机制复杂，发端和收端都要有数据缓冲器；(2) (3)需要全双工数据链路，而(1) 只要求半双工的数据链路。,发送端：,接收端：,优点只需少量的多余码元（一般为总码元的520）就能获得极低的误码率；要求使用的检错码基本上与信道的差错统计特性无关，即对各种信道的不同差错特性，有一定的自适应能力；其检错译码器与前向纠错法中的纠错译码器相比，成本和复杂性均低得多；缺点有反向信道，不能用于单向传输系统，也难以用于广播（一发多收）系统，并且实现重发控制比较复杂；当信道干扰增大时，整个系统可能处于重发循环中，因而通信效率降低，甚至不能通信；不太适合严格实时传输的系统；,前向纠错/FEC基本原理：发送端将信息序列编码成能够纠正错误的码，接收端根据编码规则进行检查，如果有错自动纠正；优点无需反馈信道，特别适合只能提供单向信道场合；自动纠错，不要求检错重发，延时小，实时性好；缺点纠错码必须与信道的错误特性密切配合；若纠错较多，则编、译码设备复杂，传输效率低；,混合纠错/HECFEC与ARQ的结合基本原理：发端发出同时具有检错和纠错能力的码，收端收到后，检查错误情况：如果错误在纠错能力之内，则自动纠正；若超出纠错能力，但在检错能力之内，则经反向信道要求重发。在实时性和译码复杂性方面是FEC和ARQ的折衷。,信息反馈/IRQ又叫反馈校验方式；基本原理：收端把收到的数据序列全部经反向信道送回发端，发端比较发出和送回的数据序列，从而发现有否错误，并把有错误的数据序列再次传送，直到发端没有发现错误；优点：不需要纠错、检错的编、译码器，设备简单。缺点需要和正向信道相同的反向信道，实时性差发端需要一定容量的存储器以存储发送码组仅适应于传输速率较低，信道差错率较低，具有双向传输线路及控制简单的系统,按监督码元和信息码元关系不同：线性码（Linear Codes）、非线性码（non-Linear Codes）按对信息元处理的方法不同：分组码（Block Codes）、卷积码（Convolutional Codes）按纠错类型分：纠随机错误的码、纠突发错误的码按功能分：检错码、纠错码、纠删码按码元取值不同：二进制码、多进制码按编码的数字方式不同：代数码、几何码、算术码按编码后是否保持原有形式：系统码、非系统码按码字结构特点：循环码、非循环码,7.1.4 差错控制编码分类,7.2 纠错编码原理,理论依据：Shannon信道编码定理。定理指出：对于一给定的有干扰信道，若其信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率P随着码长n的增加，按指数下降到任意小的值。,纠错编码的基本思想：发送端按照某种规则在信息序列上附加监督码元，接收端则按照同一规则检查两者间关系以牺牲通信的有效性（信息传输速率）来提高可靠性码的检错和纠错能力是用信息量的冗余来换取的。一般说来，添加的冗余越多，码的检错、纠错能力越强，但信道的传输效率下降也越多。,举例说明：假如要传送晴天、雨天两个消息编码一消息A-“0”；消息B-“1”若传输中产生错码(01或10)，收端无法发现，该编码无检错纠错能力。编码二消息A-“00”；消息B-“11”若传输中产生一位错码，则变成“01”或“10”，收端判决为有错（因“01”“10”为禁用码组），但无法确定错码位置，不能纠正。该编码具有检出一位错码的能力。这表明增加一位冗余码元后码具有检出一位错码的能力,举例说明：假如要传送晴天、雨天两个消息编码三消息A-“000”；消息B-“111”传输中产生一位即使两位错码，都将变成禁用码组，收端判决传输有错。该编码具有检出两位错码的能力。在产生一位错码情况下，收端可根据“大数”法则进行正确判决，能够纠正这一位错码。该编码具有纠正一位错码的能力。这表明增加两位冗余码元后码具有检出两位错码及纠正一位错码的能力。结论增加冗余，可提高检纠错能力；增加冗余，会降低传输的信息量，编码效率降低；,几个基本概念许用码：用于传输信息的码组；禁用码：在传输信息中不可能出现的码组；监督位：增加的不携带传输信息的、但具有一定约束的码位；分组码：将信息吗分组，并为每组信息码附加若干监督码的编码；nkr；n为实际传送的码长，k是信息码长；r是监督码长；码距d：接收码Cr与发送码CL之间不同的码元个数的数目；码重W：码字中“1”的个数；最小码距d0：一个码型中任何两个码字之间的最小距离，又称为汉明距离；最小码重W0：一个码型中任意码字的码重的最小值；,码距与检、纠错能力的关系最小码距与检错能力的关系 一个码能检测e个错码，则要求其最小码距d0e+1即：若最小码距为d0，则最多能检测d0-1个错码。最小码距和纠错能力的关系一个码能纠正t个错码，则要求其最小码距d02t+1即：若最小码距为d0，则最多能纠正(d0-1)/2个错码。最小码距和同时检纠错能力的关系一个码能纠正t个错码，同时能检测e个错码，则要求其最小码距 d0e+t+1 (et),差错控制编码的效果假设随机信道中发送“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-3P7(2)21 Pe2=2.1 10-5P7(3)35 Pe3=3.5 10-8,编码效率指一个码组中信息位所占比重，用表示=k/n，其中k为信息码元的数目，n为码长,可见：若加入的监督位越多，纠错能力越强，编码效率越低；纠错编码的任务是，根据不同干扰特性设计出纠检错能力最强，效率高的纠错码，且译码设备不太复杂；,7.3 常用的简单编码,奇偶校验码奇偶监督码奇监督码：使码字加上1位监督位C0后，码字中“1”的个数为奇数个；偶监督码：使码字加上1为监督位C0后，码字中“1”的个数为偶数个；只能检测出奇数个错误，不能纠错应用：以随机错误为主的计算机通信系统，难于对付突发错误最小码距dmin=2,二维奇偶校验码水平垂直奇偶监督码将奇偶监督码推广到二维。即在每一行进行奇偶校验，同时在矩阵中每一列进行奇偶校验，发送时按列的顺序传输接收端将码元排成发送时的方阵形式，再分别按行、按列进行奇偶校验能够发现某行、某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误；并有可能检测出偶数个错误（在行上检测不出，但有可能在列上检测出），但当偶数个错误刚好分布在矩阵的四个顶点时，则检测不出可纠正一些错误适用于检测突发错误，将使误码减少到原来的11,等比码每个码组中含“1”和“0”的个数的比例恒定，又称等重码、恒比码、定1码；能检测出所有1位错和奇数个错误，并能部分检测出偶数个错误（成对交换错则检测不出）简单，适应于对字母或符号进行编码，常用于电传机传输汉字，以及其他产生固定字符的键盘设备中；举例,正反码监督位数与信息位数目相同，且两者相同或相反，取决于信息序列中“1”的个数；编码规则当信息位中有奇数个“1”时，监督位是信息位的简单重复；当信息位中有偶数个“1”时，监督位是信息位的反码；接收端解码先将码组中信息位与监督位按位模2加，得到合成码组产生校验码组：码组中信息码元有奇数个“1”，则校验码组=合成码组，否则校验码组=合成码组的反码按照校验码组中“1”的个数进行检错及纠错,举例：电报通信中常用5单位电码来构造正反码编码若为11001，则码字为1100111001若为10001，则码字为1000101110假设发送码组为1100111001若接收码组为1100111001，判决为无错传输若接收码组为1000111001：合成码组01000；因码组中信息码元有偶数个“1”，则校验码组为10111；说明信息码元中第二位错码，给以纠正若接收码组为1100101001：合成码组10000；因码组中信息码元有奇数个“1”，则校验码组为10000 ，说明监督码元中第一位错码若接收码组为1001111001：合成码组01010；因码组中信息码元有奇数个“1”，则校验码组为01010，说明错码多于1个码长为10的正反码能够纠正1位差错，并能检测所有2位及以下的错码。,7.4 线性分组码,基本概念系统码：信息码元编码后，信息码元本身不变，而只在信息码元后加入监督码元，即前半部分为不变的信息码元，后半部分为监督码元的码型；线性码：监督码元和信息码元成线性关系的码型；分组码：监督码元只和本身信息码元有关的码型；线性分组码：利用代数关系，将信息序列划分为等长的k位序列段，在每一信息段后附加r个监督码元，并使监督码元和信息码元成线性关系，这样构成的码型就叫；汉明码：纠单个错的线性分组码；循环码：在严谨的代数基础上构造的、纠错能力强的解编码设备并不复杂的线性分组码；卷积码：监督码元不仅与本身信息码元有关，且跟其它码元有关的一种码型；,线性分组码的特点,具有封闭性，即任意两许用码组之和仍为一许用码组；码距的最小值等于最小码重（除全“0”码组以外）；线性分组码的表示（n，k），码长为n，信息码长为k，监督码长rnk；一致校验矩阵H(Paritycheck Matrix)用于说明监督码元与信息码元监督关系的矩阵；,举例： （7，4）码,设码元表示为：C=C6C5C4C3C2C1C0；由（7，4）码可知：n=7，k=4，r=3；假设：,举例： （7，4）码,则可写成矩阵形式：,为一致校验矩阵H,一致校验矩阵H的特性：H是rn阶矩阵，r为监督码元个数，n为码长；H=P|Ir，P是rk阶阵，Ir为r个监督码系数构成的rr阶单位矩阵，此时称H为典型形式监督矩阵，各行线性无关；若接收到码字R与H的转置乘积为0，则说明接收到的码字R是正确的，即 RHT=0，则R正确；最小码距d0=n-k+1=r+1（最小码距的上界）,生成矩阵G在给定信息位的条件下，确定码字的矩阵；举例：（7，4）码,生成矩阵G,生成矩阵G的特性：G是kn阶矩阵，k为信息码元个数，n为码长；G=Ik|Q，Q是rk阶阵，Ir为k个信息码系数构成的kk阶单位矩阵，此时称G为典型形式生成矩阵，各行线性无关；G=Ik|Q； H=P|Ir 所以，QPT， PQT 即：G和H可相互确定，且都唯一确定码字；对偶码：一码型A的H是另一码型B的G，或A码型的G是B码型的H，则称A是B的对偶码；线性分组码的封闭性，即任意n个码字之模2和仍是线性分组码内的许用码字。（证明）线性分组码的最小距离等于最小码重d0=Wmin。（证明）,汉明码能纠正单个错误的高效率线性分组码，为汉明码。特点：监督位有r位，则码长n=2r-1，k=2r-1-r；最小码距为3，纠错能力为1；编码效率较高， =k/n =(2r-1-r)/( 2r-1) =1-r/( 2r-1) 所以，当n增大，r增大，但也增加；汉明码是一种完备码，能纠正一个错码，能检测两个错码；,线性分组码的译码和校正子设发送的码字为C=Cn-1Cn-2C0 接收的码字为R=Rn-1Rn-2R0，则当RHT=0 RC，说明正确接收；若传输过程发生误码，设收发码组之差为E,则 E=En-1En-2E0=R-C Ei1 第i位有错，即Ri不等于Ci 0 第i位没有错，即RiCiE为错误图样，即发送数据序列与接收序列对应码位的模和；R=C+E(模2)，可知，S=RHT= EHT，称S为校正子或伴随式或校验子，为1r阶行矩阵，它最多能指出2r-1种错误。以（7，4）汉明码为例，设发送码组A=（0001011），接收码组R=（0000011），则收端译码过程如下：计算校正子S=RHT=0000011HT=011T查表得a3为错误位置，即可纠正,线性分组码不能检错的概率但错误码组刚好等于任意许用码组时，校正子S=0，不能检测出错误设信道的误码率为pe，线性分组码的最大检错个数为D，则不能检错概率为其中，Wi表示该码中重量为i的码组数目。,7.5 循环码,特点除线性分组码的特点外，还具有循环性，即任意许用码组循环移位后仍是许用码组（除全“0”码组外）码多项式为进一步说明循环码的性质和构造而设计的，是把码长为n的码组中的各码元当作n-1次多项式的系数而构成的。码多项式表示 若码组A=（an-1，an-2，a1，a0)，则其相应的码多项式为：A(x)= an-1xn-1+ an-1xn-1+ + a1x+ a0如码组（1100101）对应的码多项式可表示为 A7(x)= 1x6+1x5+0 x4+0 x3+1x2+0 x+1=x6+x5+x2+1码多项式与码组的关系：本质上是一回事，仅是表示方法的不同而已,码多项式的模运算 一般来说，若一整数m可以表示为,则称在模n运算下，有m p（模n）即：模n运算中，整数m等于被n除所得的余数；,码多项式的模运算也类似：,定理1：若T(x)是n长循环码中的一个码多项式，则xiT(x)按模xn1运算的余式必为循环码中的另一个码多项式；即若 xi A(x)Ai(x) （模xn+1） 则 Ai(x) 也是一许用码组，且为A(x)码组向左循环移位i次的结果。 （证明）生成多项式g(x)和生成矩阵Gg(x)是循环码中前k-1位为0的码字的码多项式，即为(n-k)阶码多项式；定理2：在循环码中，(n-k)阶码多项式有且仅有一个；定理3：循环码中，所有码多项式都能被g(x)整除；推论：次数不大于k-1次的任何多项式与g(x)的乘积都是码多项式；定理4：循环码的生成多项式g(x)是xn+1的一个因式；生成多项式的常数项必须不为“0”。,根据循环性，xg(x)，x2 g(x)， ， xk-1g(x)都是许用码组，连同g(x)共k个许用码组，构成码的生成矩阵G(x)：,注：该生成矩阵并不是典型形式的，但可通过线性变换变换成典型的生成矩阵。,循环码的编码过程和译码过程编码(设信息码多项式为m(x)确定g(x);信息码元左移r位，得M(x)= xn-km(x)；M(x)除以g(x)，求余数R(x)；T(x)= xn-km(x)+R(x)例，对(7,3)循环码编码设(7,3)循环码的生成多项式为g(x)=x4+x2+x+1,待编码信息位为110,则m(x)=x2+x,xn-km(x)=x4(x2+x) =x6+x5而 即余式r(x)=x2+1于是，对应码组A(x)= x6+x5+ x2+1 1100101,循环码的编码过程和译码过程可见，上例编出的循环码就是系统码。于是，以多项式形式表示的系统循环码的生成矩阵为：其中,rn-i(x)是g(x)除xn-i (i=1,2,，k)所得的余式。,编码实现(见图P251，图93)译码：设发送码字T(x)=xrm(x)+R(x)，接收码字为A(x)检错：用g(x)去除接收到的码组A(x)，根据余式r(x)是否为0，判断传输正误；当超出检错能力，也有r(x)=0，称不可检错误；组成见P252，图94；纠错：较之检错要复杂得多要求每个可纠正的错误必须与一个特定的余式建立一一对应关系，这样才能纠正错码，计算错误图样来判断错码位置；常用循环码有费尔码(Fire)，能纠三个随机错误的高莱码(Golay)，是(23,12)码；另外还有一种为BCH码，可纠多个错；RS码等；,例1：设（7,4）线性码的生成矩阵 当信息位为0001时，试求其后的监督位。例2：求上例的监督矩阵；例3：试求(7,3)循环码的生成多项式和生成矩阵。,例题,例4：已知（7，4）循环码的全部码组为：试写出该循环码的生成多项式g(x)和生成矩阵G，并将G化成典型矩阵。,例题,缩短循环码在(n，k)循环码的2k个码组集合中，选择前i个信息位为0的所有码组（共2k-i个），组成一个新的码组集合，这一新的码组集合就构成了(n-i，k-i)码，称它为(n，k)的缩短循环码。例如要构造一个能够纠正一位错误的(12，8）码，我们可以从（15，11）汉明码中挑出前三位均为0的码组来构成。,在(n，k)的缩短循环码中，每一个码组必定能被g(x)除尽（注： g(x)是原循环码的生成多项式）每一个码组是原来循环码的码组，只是这码组的前i个信息码元为0，所以它必定能被g(x)除尽。换言之，所有次数小于n-i次，且能被g(x)除尽的多项式都是(n-i，k-i)缩短循环码的码多项式。在(n，k)的缩短循环码中，所有码组的前i位为0，故发送时可不发送这i个0，仅传输后面的n-i位码元。(n-i，k-i)码的纠检错能力不低于原来的(n，k)循环码的纠检错能力。缩短循环码的所有码组是原来循环码组集合中的一部分，且监督码元位数没变。,缩短循环码的生成矩阵可从原循环码的典型生成矩阵中除去前i行和前i列得到。例如（7，3）循环码的一种典型生成矩阵为：除去其第一行第一列，便得到（6，2）缩短循环码的生成矩阵G（6,2）。缩短循环码的码组之间并不一定存在循环关系。,循环码的检错能力能检出全部的单个错误：对应一位错码的错码多项式E(x)=xi，而多于一项的生成多项式g(x)=+1，显然xi除以g(x)的余数不会等于0，也即能检测出全部单个错码。能检出全部离散的二位错：对应的错码多项式E(x)=xi+xj=xi(1+xj-i)，只要选取的g(x)不能除尽(xj-i+1)，且(n-k)(j-i)能检出全部的奇数个错码：含有奇数项错码的多项式必不含(x+1)因子，只要选取的g(x)含有(x+1)因子能检测所有长度不超过(n-k)的突发错误：突发长度不大于b的突发错误对应的错码多项式 为E(x)=xi(eb-1xb-1+ eb-2xb-2+e1x+1)= xi E1(x)由于g(x)除不尽xi； g(x)为n-k次多项式，只要E1(x)的次数b-1不超过(n-k-1)次， g(x)便除不尽E1(x)。也就是说，能检测长度不超过(n-k)的突发错误。,循环码的检错能力在突发长度b大于(n-k)的错误中，若b=n-k+1，则(n，k)循环码不能检测概率为2-(n-k-1)；若bn-k+1，则不能检测概率为2-(n-k）。设错码多项式为E(x)= xi E1(x) ，E1(x)的次数为(b-1)，必有x0 和xb-1项，还应有b-2项xj，因此共有2b-2种不同的多项式。只有E1(x)有g(x)的因子时，即E1(x)= g(x) Q(x)时，这种错码才不能检测出来。g(x)为(n-k)次，所以Q(x)定为b-1-(n-k)次；当b-1=n-k（即b=n-k+1），则Q(x)=1，此时仅有一个E1(x)= g(x)的错误图样不可检测，占突发错误图样总数的1/2b-2=2-(n-k-1),