差错控制和信道编码课件.ppt

兰州大学信息科学与工程学院电信、通信工程系,通 信 原 理,程琳 兰州大学信息科学与技术学院电信系M.P:+86-0931-6161799Email: or Address：Department of Electronics & Information Science, School of Information Science&Engineering, Lanzhou University, Tianshui Southern Road 222#， Gansu Province，P.R.China,Principles of Communications,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,2,第十三章 差错控制和信道编码,主要内容提要： 差错控制方式及信道编码的基本概念 线性分组码 循环码 卷积码 其它信道编码简介,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,3,本章的教学基本要求,本章要求掌握差错控制的基本方式、信道编码的一些基本概念、线性分组码特性及其设计、循环码特性及其设计、卷积码特性及其设计；其余的内容可根据学时情况酌情加以了解即可。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,4,在实际信道上传输数字信号时，由于信道传输特性不理想以及加性噪声的影响，接收端所收到的数字信号不可避免地会发生错误。产生差错的原因信道的电气特性引起信号幅度、频率、相位的畸变；信号反射；串扰；闪电、大功率电机的启停产生脉冲干扰等。 一般说来，线路传输差错是不可避免的，但要尽量减小其影响。,1. 引言,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,5,1. 引 言,信道差错的几种模式随机差错：差错的出现是随机的，一般而言差错出现的位置是随机分布的。这种情况一般是由信道的加性随机噪声引起的。一般将这种信道称为随机信道。突发差错：差错的出现是一连串出现的。这种情况如移动通信中信号在某一段时间内发生衰落，造成一串差错；光盘上的一条划痕等等。这样的信道我们称之为突发信道。混合差错：既有突发错误又有随机差错的情况。这种信道称之为混合信道。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,6,1.引 言,降低误码的技术措施：为了在已知信噪比情况下达到一定的误比特率指标，首先应该合理设计基带信号，选择调制解调方式，采用时域/频域均衡，使误比特率尽可能降低。但若误比特率仍不能满足要求，则必须采用信道编码（即差错控制编码），将误比特率进一步降低，以满足系统指标要求。随着差错控制编码理论的完善和数字电路技术的发展，信道编码已经成功地应用于各种通信系统中，并且在计算机、磁记录与存储中也得到日益广泛的应用。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,7,1. 引 言,我们研究的是编码和译码，所以完全可以将调制、解调与信道合起来等效成一个等效信道编码信道。 编码信道根据调制解调的不同输入和输出具有不同的类型离散无记忆对称二进制输入二进制输出信道（BSC）离散无记忆二进制输入多进制输出信道离散无记忆多进制输入多进制输出离散无记忆二进制输入连续输出离散有记忆信道,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,8,1.引 言,信道编码的目的：改善数字通信系统的传输质量信道编码(差错控制编码)的基本思路：在发送端将被传输的信息附上一些监督码元，这些冗余的码元与信息码元之间以某种确定的规则相互关联（约束）。接收端按照既定的规则校验信息码元与监督码元之间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而接收端可以发现错误乃至纠正错误。信道编码的任务：构造出以最小多余度（冗余度）代价换取最大抗干扰性能的“好码”。研究各种编码和译码方法是信道编码所要解决的主要问题。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,9,信道编码与信源编码的区别,信源编码尽量减少信源的冗余度。即尽可能用最少的信息比特来表示信源。如话音压缩编码、图象压缩编码。,信道编码在待传输信息中加入冗余信息，以此达到差错控制的目的，从而提高通信系统的可靠性。如纠错编码、检错重发编码等,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,10,2. 差错控制方式及信道编码的基本概念,一、差错控制的三种方式：检错重发（ARQ： Automatic Repeat Request ）在接收端根据编码规则进行检查，如果发现规则被破坏，则通过反向信道要求发送端重新发送，直到接收端检查无误为止。ARQ系统需要反馈信道，效率较低，但是能达到很好的性能。 前向纠错（FEC： Forward Error Correction ） 发送端发送能纠正错误的编码，在接收端根据接收到的码和编码规则，能自动纠正传输中的错误。不需要反馈信道，实时性好，但是随着纠错能力的提高，编译码设备复杂。 混合方式（HEC：Hybrid Error Correction ）结合前向纠错FEC和ARQ的系统，在纠错能力范围内，自动纠正错误，超出纠错范围则要求发送端重新发送。它是一种折中的方案。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,11,差错控制的三种方式,检错重发（ARQ： Automatic Repeat Request ）前向纠错（FEC： Forward Error Correction ） 混合方式（HEC：Hybrid Error Correction ）,发送,接收,可检错和纠错的码序列,发送,接收,可检错和纠错的码序列,应答信号,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,12,差错控制的三种方式 之 ARQ,检错重发 ARQ系统具有各种不同的重发机制停等 ARQ发送方每发完一帧必须等接收方确认后才能发下一帧。Go-back-N ARQ(回退N)发送方可连续发送多帧。若前面某帧出错，从该帧以后的各帧都需重发。（一般与流控结合使用）选择性重传 SARQ发送方可连续发送多帧。若前面某帧出错，只需重发该出错的帧。发送方需要缓存前面所有未被确认的帧。其它不常用的差错控制方式： 信息反馈方式（IRQ）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,13,差错控制的三种方式 之 ARQ,停等ARQ,回退N选择性重传,码组1,ACK,NAK,码组2,ACK,重发码组2,码组3,无错,无错,有错,发送,接收,发现错误,NAK,重发,发现错误,NAK,重发,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,14,二、 信道编码的分类,1、按功能划分为：检错码、纠错码、纠删码（兼检错、纠错）2、按信息位和校验位的约束关系分为：线性码、非线性码3、按信息码元和监督码元的约束关系分为：分组码：监督码仅与本码组信息码有关卷积码：监督码不仅与本码组信息码有关，而且与前面码组的信息码有关。4、按编码后信息码结构是否发生变化分为：系统码：编码前后信息码结构不变非系统码：编码前后信息码结构发生改变5、按码元的进制进行划分：二进制码、多进制码：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,15,三、信道编码的基本概念,分组码：将k比特信息编成n比特一组的码字（码组），记为（n，k）分组码。K位码元，作为信息码元r=n-k位码元，称作冗余码、监督码许用码组：禁用码组：码重W：码字中1的个数。如W(11000)=2; W(010)=1 码距d （汉明距离Hamming） ：两码组中对应位不同的比特（bit）数。如C1:11000，C2:11101,则d(C1，C2)=2,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,16,信道编码的基本概念,最小码距：分组码(n,k)中任何两个码字Ci、Cj之间的码距的最小值，用dmin表示。最小码距是衡量码的一种内在属性 最小码距决定了码的纠错、检错性能若要发现e个独立随机错误，要求dmine+1若要纠正t个独立随机错误，要求dmin2t+1若要发现e个同时又纠正t(et)个独立随机错误，要求dmine+t+1,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,17,四、常用简单检错码,1.奇偶监督码（奇偶校验码）最简单的检错码(1bit校验)，在计算机数据传输中得到广泛应用 传送信息分组(an-1,a1,)+监督位(a0) = 一个传输码组(an-1,a1, a0)偶校验：an-1+an-2 + +a1+a0=0 (mod 2) （即偶数个1）奇校验：an-1+an-2 + +a1+a0=1 (mod 2) （即奇数个1） 可见这种码的最小码距为2，只能检出1个独立随机差错。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,18,简单的检错码,2.二维奇偶监督码（行列监督码）可检测出任一行或任一列上所有奇数个错码,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,19,简单的检错码,3.恒比码 每个码组中的1的个数都是一样的。典型应用：一般用在电传、电报。例如，我国电传机传输汉字时每个汉字用4位阿拉伯数字表示，每个阿拉伯数字用5个比特的码字表示 ，即从32种组合选取10个为阿拉伯数字编码,恒比码的编译码可以采用查表的方法，检错时检查1的个数是否为3,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,20,简单的检错码,4.ISBN国际统一图书编号（例一）在国际图书的发行中，经常用编码的方式来防止书号在通信过程中发生错误，举例如下所述。如通信原理的书号是ISBN 7-5635-0525-3其中第一位数字“7”表示“中国”，“5635”表示出版社，“0525”表示书名编号，最后一位“3”表示校验位。这里所采用的校验方式如下所示：7 5 6 3 5 0 5 2 5 37 12 18 21 26 26 31 33 38 417 19 37 58 84 110 141 174 212 253(模11) 0,若通信过程中统一书号发生了错误，则上述累计和就不能被11整除，从而可以校验出来。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,21,简单的检错码,4.ISBN国际统一图书编号（例二）如通信原理的书号是ISBN 7-118-0429-X其中第一位数字“7”表示“中国”，“118”表示出版社，“01429”表示书名编号，最后一位“X”表示校验位（它是罗马数字10的表示）。这里所采用的校验方式如下所示：7 1 1 8 0 4 2 9 X=107 8 9 17 17 21 23 32 427 15 24 41 58 79 102 134 176 176(模11)=0。 又譬如：ISBN 7030144562，大家可自行分析。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,22,3. 线性分组码,近世代数学有限域的概念：有限个元素的集合，按规定可以进行的代数四则运算，其运算结果仍属于该集合中有限的元素。最简单的有限域 0，1Galois域1+1=0、 1+0=1、 0+1=1、 0+0=0 1x1=1、 1x 0=0、 0 x0 =0、 0 x1 =0定义线性分组码的加法为模2加，乘法为二进制乘法。且码字与码字的运算是各个相应比特位上的上述二进制运算规则。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,23,3. 线性分组码,基本概念码组中监督码与信息码之间满足线性方程；任意两个可用码组之和(逐位模2加)仍为一个可用码组奇偶监督码最简单的线性分组码偶校验时 奇校验时不满足线性分组码的第二个性质。定义校正子（校验子伴随式）接收时进行校验计算： S=0无错； S=1有错（奇数个）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,24,3. 线性分组码,一般情况下：如果码组中有2个监督码，校正子为S=s1,s2可以检测到三种误码状态,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,25,3. 线性分组码,如果码组中有r个监督码，假设码组中有K个信息码，则线性分组码的长度应该为n=K+r。码的结构线性分组码（n，k）的性质封闭性：任意两个码组的和还是许用的码组码的最小距离等于非零码的最小码重,K位信息位,r位监督位,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,26,3. 线性分组码,检错能力：有r个校正子方程可以指示（2r-1）个错误纠错能力：对1位错码，可以指示（2r-1）个错误位置若2r-1n，可以纠正1bit或以上的错码， 即2r-1r+k， 2r-1- rk设k=4，能纠正1位误码的最小r=3，则n=7 （7，4）线性分组码，码组C=c6c5c4c3c2c1c0， 其中c6c5c4c3为信息码，c2c1c0为监督码,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,27,3. 线性分组码,一般分析，对于线性分组码（n,k）,若可记为：（Cn-1 Cn-2 Cn-3 Cn-K Cr-1 Cr-2 Cr-3C1 C0） 现令信息码元与监督码元的约束关系为：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,28,3. 线性分组码,据此可得如下结果：,由上式可得一致监督关系为：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,29,3. 线性分组码,其中的H为：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,30,3. 线性分组码,同样可知：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,31,3. 线性分组码,若令下述关系成立：,对比H和G，可见：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,32,3. 线性分组码,所以可得如下结果：,这里称H为一致监督矩阵；G则是生成矩阵。下面研究一个实际例子。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,33,3. 线性分组码,现以一个(7,3)线性分组码为例n=7,k=3,r=n-k=4编码效率为：R=k/n=3/7 c0=u0 c3=u0 + u2 信息位 c1=u1 监督位 c4=u0 + u1 + u2 c2=u2 c5=u0 + u1 c6=u1 + u2 则C=（c0c1c2c3c4c5c6）=（u0,u1,u2,u0 + u2,u0 + u1 + u2, u0 + u1, u1 + u2 ）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,34,3. 线性分组码,n位的码组，由k个信息位的输入消息u通过一个线性变换矩阵kn阶G来产生，称G生成矩阵G= ，I为k阶单位方阵典型生成矩阵,生成矩阵G,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,35,3. 线性分组码,将监督位线性方程组写为即 可见上述监督关系的线性方程组完全由矩阵H所决定。故将此r n的H矩阵称为监督矩阵H= , I为(n-kr)维（阶）单位方阵 典型监督矩阵,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,36,3. 线性分组码,根据前面所得可推导： G与H生成的空间互为零空间，且G与H可以互相转换。,（即P、Q互为转置矩阵）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,37,3. 线性分组码,校正子（码组伴随式）发送码组C经过传输系统到达接收端时，假设收到的码组为B，B=bn-1bn-2b0差错关系为 B-C=E ， BE=CE =en-1en-2e0，E又称为错误图样。 其中接收时计算校正子为,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,38,3. 线性分组码,编码器若以c0c1c2为信息码,由监督码的生成关系可得c3=1c0 + 0c1 + 1c2 c4=1c0 + 1c1 +1 c2 c5=1c0 + 1c1 +0c2 c6= 0c0 + 1c1 + 1c2,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,39,3. 线性分组码,译码器由校正子关系可得,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,40,3. 线性分组码,译码器,伴随式计算电路,错误图样检测电路,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,41,3. 线性分组码,汉明（海明）码（Hamming）能纠正单个随机错误的线性分组码码长 n=2m-1信息位 k=2m-1-m监督位 n-k=m，且 m3最小距离 dmin=d0=3汉明码是一类高效率的纠错码编码效率 R=k/n=(n-m)/n=1-m/nn很大时，R1,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,42,4. 循环码,基本概念线性分组码的一个子类，比较成熟任何一个可用码组经过循环移位后所得到的码组仍为一个可用码组原码组 C=cn-1 cn-2 c1 c0左移一位 C1=cn-2 cn-3 c0 cn-1右移一位 C2=c1 cn-1 c3 c2移i位 Ci=cn-i-1 cn-i-2 cn-i循环码组 C=cn-1 cn-2 c1 c0 可表示为多项式 C(x)= cn-1 xn-1 + cn-2 xn-2 + c1 x+ c0式中x的幂次表示：码元的位置；码的移位次数,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,43,4. 循环码,基本概念如多项式C(x)= x6 + x4 +x+1C=1010011c6x6可以看作c6从最低位c0左移6次的结果C(x)左移一位记作 C(1)(x)C(1)(x)=cn-2 xn-1 + cn-3 xn-2 + c0 x+ cn-1C(x)左移i位后为C(i)(x)=cn-i-1 xn-1 + cn-i-2 xn-2 + cn-i+1 x+ cn-i,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,44,4. 循环码,循环码多项式的运算特性码长为n的循环码，其码多项式C(x)，则xiC(x)=Q(x) (xn+1)+C(i)(x) 即例如：某循环码组为C=(1100101)，码长n=7，对应的码多项式为C(x)=x6 +x5 + x2 + 1左移一位后xC(x)=x7 +x6 + x3 + x因为C(1)(x) xC(x) (mod（x7+1）)=x6 +x3 + x + 1 （1001011）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,45,4. 循环码,左移2位时x2C(x)=x8 +x7 + x4 + x2 x+1 x7 +1 ) x8 +x7 + x4 + x2 x8 +x x7 + x4 + x2 +x x7 +1 x4 + x2 +x +1C(2)(x)=x4 + x2 +x +1(0010111),2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,46,4. 循环码,生成多项式g(x)对于(n,k)循环码来说，生成多项式g(x)是一个能除尽xn+1的（n-k）阶多项式。阶数低于n并能被g(x)除尽的一组多项式就构成一个(n,k)循环码阶数小于等于(n-1)并能被g(x)除尽的每个多项式都是循环码的可用码组多项式。 所以，循环码完全由其码组长度n和生成多项式g(x)所决定。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,47,4. 循环码,生成多项式g(x)设构成循环码的信息码多项式为u(x)，其阶数不大于(k-1)，则有循环码组为C(x)=u(x) g(x)例如，n=7，g(x)=x4+x3+x2+1是x7+1的一个因式；g(x)最高幂次为4=n-k；则k=3，r=4（即信息码3bit，监督码4bit）。可用码组如下：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,48,4. 循环码,生成多项式g(x)以上是一个（7，3）循环码，最小码距dmin=4，其信息码多项式如下：,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,49,4. 循环码,生成多项式g(x)为了得到g(x)，需对xn+1进行因式分解对于大部分n值， xn+1仅有很少的几个因式；只有很少的几个n值， xn+1才有较多因式设g(x) h(x)= xn+1 或g(x) h(x) 0 mod(xn+1) 以（7，3）循环码为例，n=7 x7+1=(x+1)(x3+x2+1)(x3+x+1),2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,50,4. 循环码,生成多项式g(x)n=7， x7+1=(x+1)(x3+x2+1)(x3+x+1),显然，(7，3)、(7，4)循环码互为对偶码.,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,51,4. 循环码,生成矩阵GC(x)=u(x) g(x) =(uk-1xk-1+uk-2xk-1+u1x+u0) g(x) = uk-1xk-1 g(x) +uk-2xk-2 g(x) +u0 g(x) =uG根据u的不同取值可求得(n,k)循环码的所有2k个码字，但这样所得到的码并非系统码。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,52,4. 循环码,生成矩阵G为了进一步得到系统码，可作如下运算：xn-ku(x)=Q(x)g(x)+r(x)C(x)= xn-ku(x)+r(x)= Q(x)g(x)+r(x)+r(x) = Q(x)g(x)构造系统循环码：只需将信息码多项式升(n-k)阶，然后以g(x)为模求余，所得余式即为监督码多项式“除法求余”过程,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,53,4. 循环码,例如：已知(7,4)系统码的生成多项式为g(x)=x3+x2+1，求其生成矩阵。 解：由 先求出,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,54,4. 循环码,监督矩阵H由于 xn+1=g(x) h(x)生成多项式g(x)=gn-kxn-k+g1x+g0监督多项式h(x)=hkxk+h1x+h0,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,55,4. 循环码,例如，已知(7,3)系统循环码的生成多项式g(x)=x4+x3+x2+1，求生成矩阵G及监督矩阵H。解：由g(x) h(x)=x7+1的关系可得： h(x)=x3+x2+1=h3x3+h2x2+h1x+h0根据前例方法先计算 rn-i (x)xn-imod g(x)可得,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,56,4. 循环码,编码器循环码的特点一：可以采用反馈线性移位寄存器实现编码和伴随式计算以g(x)=x3+x+1的（7，4）循环编码器为例,D0,D1,D2,+,+,门,输入u(x) xn-k,1,2,码字输出,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,57,4. 循环码,编码器以g(x)=x3+x+1的（7，4）循环编码器为例,初态为000门开,四次移位后信息1001全部输出，关门，输出开关倒向2,又循环回到初始状态,信息位,监督位,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,58,4. 循环码,译码器仍以g(x)=x3+x+1生成的（7，4）循环码译码为例,错误图样检测电路只有1套，其译码电路比一般的(7,4)线性分组码大大简化,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,59,4. 循环码,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,60,4. 循环码,循环码检错CRC (Cyclic Redundancy Check, 循环冗余校验)一般能检测的错误：突发长度n-k+1的错误，其中不可检出错误仅占2-(n-k)所有与许用码组码距dmin-1的错误所有奇数个错误CRC码在数据通信及移动通信中得到广泛应用,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,61,4. 循环码,循环码检错：CRC (Cyclic Redundancy Check, 循环冗余校验)常用的CRC码国际标准CRC-12：g(x)=x12+x11+x3+x2+x+1CRC-16: g(x)=x16+x15+x2+1CRC-CCITT: g(x)=x16+x12+x5+1CRC-32: g(x)=x32+x26+x23+x22+x16+x12+x11 +x10+x8+x7+x5+x4+x2+x+1CRC-12用于字符长度为6bit情况，后三种用于8bit字符。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,62,CRC 校验示例,待校验数据：1101,0110,11 g(x) = x4+x+1 , 即10011,1 1 0 1 0 1 1 0 1 1 0 0 0 0,1 0 0 1 1,1 1 0 0 0 0 1 0 1 0,1 0 0 1 1,1 0 0 1 1,1 0 0 1 1,0 0 0 0 1 0 1 1 0,1 0 0 1 1,1 0 1 0 0,1 0 0 1 1,1 1 1 0,余数,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,63,CRC接收端的处理过程,假设收到序列R(X)=1101,1110,1111,10T(x) (出错) 仍然用g(x) = x4+x+1 , 即10011 做除数,非0余数表示有错,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,64,接收端的处理过程（续）,假设收到序列无误，则有 R(X)=T(X)=1101,0110,1111,10 仍然用 g(x) = x4+x+1 , 即10011 做除数,余数为0表示正确接收,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,65,5. 卷积码,卷积码是非分组码的典型代表，亦称连环码。 它是1955年由埃里亚斯（Elias ）最早提出。与分组码的主要差异：卷积码编码器有记忆，在任意给定的时段，编码器的n个输出不仅与此时段的k个输入有关，而且与前m个输入有关卷积码记为（n，k，m）n为输出码元数k为输入码元数m为编码器的存储器数,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,66,5. 卷积码,卷积码编码,输入信息序列u,u,c,u,c,描述时序网络的方法解析表示法离散卷积法、生成矩阵法、码多项式法图形表示法状态图法、树图法、格图法,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,67,5. 卷积码,卷积码编码现以一个二元（2，1，3）卷积码为例,输入信息序列u=(u0u1u2),输出码字序列c= (c0 c0 c1 c1 c2 c2 ),g,有限状态的有记忆系统k=1，即一个输入位n=2，即两个输出位m=3，即三级移位寄存器,输出c = u*g = (c0c1c2),输出c = u*g = (c0 c1 c2 ),g ,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,68,5. 卷积码,卷积码编码离散卷积法以一个二元（2，1，3）卷积码为例由图可知 g1(x)=1+x2+x3 g=(1011) g2(x)=1+x+x2+x3 g=(1111)设u=(10111)，则有 c=(10111) *(1011)=(10000001) c=(10111) *(1111)=(11011101)最后输出的码字为 c=(1101000101010011),生成序列,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,69,5. 卷积码,生成矩阵G生成矩阵法理论分析,生成矩阵G是一个半无限的矩阵编码方程的矩阵形式：c=uG,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,70,5. 卷积码,生成矩阵G,已知 u=(10111),求得 g=(1011),g=(1111) 代入公式，可求得,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,71,5. 卷积码,码多项式表达式 工程应用,u=(10111)=1+x2+x3+x4g=(1011)=1+x2+x3g=(1111)=1+x+x2+x3 则卷积码输出为：c= (1+x2+x3+x4)(1+x2+x3) =1+x7=(10000001)c= (1+x2+x3+x4)(1+x+x2+x3) =1+x+x3+x4+x5+x7=(11011101)输出序列为 C=(1101000101010011),2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,72,5. 卷积码,状态图法描述现以（2，1，2）卷积码为例： k=1，n=2，m=2总的可能状态数为 2km=22=4种，即 00, 10, 01, 11每次可能的输入有两个即 2k=2每次可能的输出状态也只有两个状态图的画法圆圈中的数字状态状态之间的连线和箭头转移方向（分支）分支上的数字转移时输出的码字括号中的数字转移时输入的信息数字,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,73,5. 卷积码,状态图法（2，1，2）卷积码为例：,（2，1，2）卷积码状态转移图,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,74,5. 卷积码,树图法按时间展开,树根,0分支,1分支,a,00,11,00,00,00,11,11,10,01,11,10,01,10,01,00,11,01,10,11,00,01,10,00,11,10,01,00,11,01,10,00,11,00,11,优点：时序关系清晰对每一个信息输入序列有且仅有一个不重复的树枝结构相对应缺点：进行到一定时序后，状态重复且树图越来越复杂,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,75,5. 卷积码,树图法,树根,0分支,1分支,a,00,00,00,00,11,11,01,11,10,01,10,01,00,11,01,10,11,01,10,00,11,10,00,11,01,10,C=(11 10 00 01 10 01 11 00),输入序列为 u=(10111000),2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,76,5. 卷积码,格图法（篱笆图）二维状态,a=00,b=10,c=01,d=11,00,00,00,10,10,10,10,00,00,00,00,在l=3时状态abcd呈现重复,C=(11 10 00 01 10 01 11)所对应的路径,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,77,5. 卷积码,卷积码的译码代数译码（略）概率译码最大似然译码算法即维特比（Viterbi）算法，译码器所选择输出总是能给出对数似然函数值为最大的码字等价于求通过一个加权图的最短路径问题的动态规划解,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,78,5. 卷积码,卷积码的译码最大似然译码算法通信可靠性最大的译码应为平均错误概率最小的译码方式设c为发送码字，c为接收端恢复的码字，而y为接收的码字,求后验概率最大的码字,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,79,5. 卷积码,卷积码的译码最大似然译码算法对于离散无记忆信道 (DMC),对数似然函数,对于离散无记忆信道（DMC）,等效于求最小汉明距离,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,80,5. 卷积码,卷积码的译码维特比（Viterbi）算法建立在格图法的基础上基本思想：依次在不同时刻l=m+1，m+2，m+L，对格图中相应列的每个点，按照最大似然准则比较所有以它为终点的路径，只保留一条具有最大似然值的路径（幸存路径），而去除其它所有路径及其延伸。下一时刻只对幸存路径延伸出的路径重复上述的比较，一直到最后。,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,81,5. 卷积码,卷积码的译码维特比（Viterbi ）算法优越性：局部判决是全局最优化的一部分局部判决及时去掉了大量非最优路径缺点：译码时延大（因为要等全部接收的数据进入译码器以后才能最后算出译码结果）存储量大（因为需要存储2km条幸运路径的全部历史数据）,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,82,5. 卷积码,卷积码的距离特性最小汉明距离 dmin：卷积码中长度为nm (m为约束长度)的编码以后序列之间的距离自由距离 dfree：任意长度卷积码编码后序列之间的最小汉明距离,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,83,6. 其它信道编码简介,1、BCH码一类最重要的循环码，能纠正多个随机错误码长：n=2m-1本原BCH码n= 2m-1 的因子非本原BCH码,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,84,6. 其它信道编码简介,2、纠正突发错误码前面介绍的编码主要针对独立随机差错突发干扰：干扰造成成串的差错，如变参信道中的快衰落干扰等典型的能纠正突发错误编码Fire码一种循环码RS(Reed-Solomon)码 q进制BCH码，还可纠正随机错误,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,85,6. 其它信道编码简介,3、交织码广泛应用于移动通信技术中是一种信道改造技术将原来属于突发差错的有记忆信道改造为基本上是独立差错的随机无记忆信道各类用于无记忆信道纠正独立随机差错的信道编码仍可照样使用,编码器,交织器,突发信道,去交织器,译码器,输入,输出,等效为独立差错随机无记忆信道,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,86,6. 其它信道编码简介,4、级联码广泛用于空间通信及移动通信的GSM和3G中纠正混合型错误由短码构造长码的一类特殊、有效的方法,外编码器（n2,k2）码,信道,输入,输出,内编码器（n1,k1）码,内译码器（n1,k1）码,外译码器（n2,k2）码,编码器,译码器,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,87,6. 其它信道编码简介,5、Turbo码性能逼近理论上最优的香农（Shannon ）的信道编码的极限,2022年12月2日10时35分,兰州大学信息科学与工程学院电信、通信工程系,88,6. 其它信道编码简介,6、高效率信道编码 TCM网格编码调制 （Trellis Coded Modulation）开创了高频谱效