第五章 信道编码2

第五章信道编码,信道编码的基本概念和基本原理线性分组码循环码、卷积码和秩距离码突发错误的纠正级连码、交织码及TCM码纠错码的应用,编码信道：包括信道编码器、实际信道、信道译码器。该模型是研究信道纠错编码和译码的模型，集中研究通信可靠性。通信可靠性问题：消息通过信道传输的时候，如何选择编码方案来减少差错。首先与信道统计特性有关，其次与编码方法、译码方法也有关系。,第一节信道编码的基本概念和基本原理,信道是信号从信源传送到信宿的通路。由于信道有干扰，使得传送的数据流(码流)中产生误码。误码的处理技术有纠错、交织、线性内插等。信道编码的目的是提高信息传输或通信的可靠性。信道编码的任务是降低误码率，使系统具有一定的纠错能力和抗干扰能力，提高数据传输效率。信道编码的过程是在源数据码流中加插一些码元，达到在接收端进行检错和纠错的目的。在带宽固定的信道中，总的传送码率是固定的，由于信道编码增加了数据量，其结果只能是以降低传送有用信息码率为代价了。,一、信道编码概念,目的：降低错误译码概率PE。对象：信息序列（设码元间彼此无关且等概出现）。,方法：在传输的信息码之中按一定规律产生一些附加数字，经信道传输，在传输中若码字出现错误，收端能利用编码规律发现码的内在相关性受到破坏，从而按一定的译码规则自动纠正或发现错误，降低误码率。,一、信道编码概念,实质：在保持一定传输信息速率条件下，通过增加一定的码元多余度，使输出的码字具有特定的相关性，从而使收端易于发现或纠正由于信道噪声而引起的传输错误。,q=rk个k维矢量,信息序列,许用码组,编码过程,M,C,校验元,信息序列,码字,编码规则,rk个,传输模式,PE信道传输特征PE译码方法,C2kCiC2n-1,许用码组,禁用码组,不可检出错误传输,正确传输,可检出错误传输,二、信道编码的基本原理（检错、纠错原理）,寻找一种编码方法，使所加的监督码元最少，而检错纠错能力又高，且便于实现。,理论基础：香农第二定理对于一个给定的有扰信道，如信道容量为C，只要发送端以低于C的速率R发送信息，则一定存在一种编码方法，使编码错误概率p随码长n的增加，按指数下降到任意小的值。也就是说，可以通过编码使通信过程实际上不发生错误，或使错误控制在允许数值之下。即：,信息传输率,E(R),随机编码指数,码长,Pexp-nE(R),E(R)意义：n给定，则最佳编码的P上界既定。,适用于DMC，有记忆信道及连续信道;,香农第二定理说明：,PE0，可靠编码条件：,有噪信道编码逆定理设离散无记忆信道X，p(y|x)，Y的信道容量为C，R是信息传输率，当RC时，则无论码长N多长，总找不到一种编码，使译码的平均错误概率任意小。,表述二、设某信道有r个输入符号，s个输出符号，信道容量为C。只要码长N足够长，总可以在输入的rN个符号的集合中找到M（M2N(C-)，为任意小的正数）个码字，分别代表M个等可能性的消息，组成一个码以及相应的译码规则，使信道输出端的平均错误译码概率PE达到任意小。,1)差错类型1随机错误:数据流中发生的错误彼此无关,表现为错误之间的无相关性.2突发错误:数据流中一个错误的发生,带来一连串错误的发生,表现为误错之间的相关性.2)差错控制的途径1增加信道容量措施扩展带宽、提高发送功率、降低噪声2编码措施减小码率、增加码长、交织器、纠错码3传输方式措施重复发送、反馈重发、多进制信号,三、差错控制,需要双向信道，和前向信道有相同的通信容。引入较大的停顿（不实时）。可以纠正任何错误。,1反馈检验法(IRQ),3)差错控制的分类,2检错重发法（ARQ）,自动请求重发也需要反向信道，但容量可以降低，也会引入停顿,3前向纠错（FEC）,不需要双向信道不会引入停顿靠纠错编码,3混合纠错检错（HEC）,4)差错控制编码的基本原理,如用三位二进制编码来代表八个字母000A100E001B101F010C110G011D111H不管哪一位发生错误，都会使传输字母错误如用三位字母传四个字母000A011B101C110D发生一位错误，准用码字将变成禁用码字，接收端就能知道出错，但是不能纠错。,如用三位字母传二个字母000A111B检三个错误，纠正一个错误。大数法则纠错。结论具有检错或纠错的码组，其所用的比特数必须大于信息码组原来的比特数引入余度。,5）、检错、纠错能力,码重(weight)一个码组中“1”的数目码距(distance)两个码组之间对应位置上1、0不同的位数，又叫汉明(Hamming)距。10110码重：3011002距离：3,为检查出个错误，要求最小码距为为纠正个错误，要求最小码距为为纠正个错误，同时检查出个错误，要求最小码距为纠正个错误和p个删除，要求最小码距为：,检错、纠错能力,按功能分检错码纠错码纠删码（发现不可纠正的错误时，可发出指示或删除）按信息码元和监督码元之间的校验关系分线性码非线性码按信息码元和监督码元之间的约束方式分分组码卷积码,6）、差错控制编码分类,卷积码,非线性码,线性码,纠错码,分组码,循环码,非循环码,纠随机错误码,纠突发错误码,纠随机和突发错误码,纠同步错误码,纠错码分类,第二节线性分组码,表示：(n,k)n:帧（组）长k/n:编码效率特点监督码只用来监督本帧中的信息位分类线性码信息码与监督码之间为线性关系非线性码不存在线性关系,一、基本概念,分组码的监督方程矩阵形式,监督矩阵H矩阵称为典型形式，各行一定是线性无关的。而一个非典型形式的经过初等变换运算可以化成典型形式，通过监督矩阵可以知道监督码和信息码的监督关系。,生成矩阵，通过监督矩阵可以得到生成码组。如果输入码组为A=0011,编码器输出码字为:C=AG,由这种方式得到的生成矩阵称为典型生成矩阵，由它产生的分组码必定为系统码，也就是信息码字保持不变，监督位附加其后，每行一定是线性无关的，每行都是一个生成码组。,定理：设二元线性分组码CI是由监督矩阵H所定义的，若X和Y为其中的任意两个码字，则X+Y也是CI中的一个码字。线性码的封闭性,对偶码：以G作监督矩阵，以H为生成矩阵，得到另一个码CJ（n，n-k）线性码。CJ为原码CI的对偶码。它们的码矢彼此正交，两个子空间是互为零化空间。,缩短码：将分组码最左边i位为0的消息和对应的码字挑选出来，把最左边的0删去，构成（n-i，k-i）线性分组码。纠错检错能力与原码相同。,缩短码的监督矩阵：（n，k）一致监督矩阵删去最左边一列。缩短码的生成矩阵：（n，k）生成矩阵删去最左边一列和最上面的一行。,二、汉明码能纠正单个错误的线性分组码,汉明码的监督矩阵H的列为所有非零的r维向量组成，一旦r给定，就可以构造出具体的（n，k）汉明码。,例1：构造一个二元的（7，4，3）汉明码。,分析：r=n-k=3,除0以外的所有2r个元素构成矩阵H的列。,截短汉明码,(n,k)(n-x,k-x)如(15,11)(12,8)监督矩阵H是将原H的前3列去掉截短汉明码的最小码距至少和原来码的码距相同，因为监督位没有变。,能纠t个错误的(n,k)应满足取等号时为完备码不同结构的线性码其纠错能力不同，能力和dmin有关，dmin越大越好。,如果在汉明码基础上，再加上一位对所有码字进行校验的监督位监督码字由r位增加到r+1位信息位不变码长码结构纠1位错，检测2位错如（8，4），（16，11）,扩展汉明码,扩展汉明码的监督矩阵,编码器的实现上例m=(m1m2m3m4)m1,m2,m3,m40,1Ci=mGCi=(c1c2c3c4c5c6c7)=(m1m2m3m4m1+m2+m3m2+m3+m4m1+m2+m4)m1c1m2c2m3c3m4c4c5c6c7,+,+,+,三、线性分组码的编码,根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n（nk）的码字。,四、线性分组码的译码,当给定接收码字R时，译码器的错误译码概率表示经过译码后平均接受到一个码字所产生的错误大小。平均错误概率：,1、最大似然译码1)编码译码过程源数据码流划分为信息组m,编码译码过程如下:信息组m码字Ci接收字RCi的估值干扰2)译码发送码字Ci,接收字R;译码器根据编码规则和信道特性,对接收码字R作出判决,此过程称为译码.译码器的基本任务就是根据一套译码规则或算法,由接收字R给出与发送信息组m的最好估计值.由于m与C之间是一一对应的,这就等价于译码器根据R对C的估计.,编码器,译码器,信道,3)最佳译码在已知接收字R的条件下,找出可能性最大的发送码字Ci作为译码的估值,令这种译码方法叫做最佳译码或最大后验译码(MAP)根据Bayes公式式中p(Ci)发送码字Ci的概率p(R)接收字R的概率p(R|Ci)先验概率,如果以下条件成立码C中的qk个码字以等概率发送,p(Ci)=1/qkp(R)对于任何R都有相同的值,p(R)=1/qn则后验概率p(Ci|R)最大,等同于先验概率p(R|Ci)最大.4)最大似然译码在已知接收字R的条件下,使得先验概率最大的译码方法称为最大似然译码对于无记忆信道,若Ci=(ci1,ci2,cin),R=(r1,r2,rn)则最大似然函数,对数似然函数5)最小距离译码对于BSC信道,最大似然译码可以简化为最小距离译码.码C中任一码字Ci与R的距离为d,则d表示Ci在BSC信道传输过程中码元传错的个数.因此此时的似然函数,结论(1-p)n是常数,而p/(1-p)1)的余数相同;或称为a和b对于模m同余.最小非负剩余:a=r(modm);0rn-k+1，则（n-k）循环码不能检测概率为2-（n-k）（能检测的概率为1-2-（n-k）,5循环码的伴随多项式：,假设发送的码多项式C(x)和错误图样多项式e(x)以及接收的码多项式R(x)分别为：,则对于加性信道有：R(x)=C(x)+e(x)设g(x)为码的生成多项式，由于码字多项式C(x)能被g(x)除尽，故有：R(x)modg(x)=e(x)modg(x),定义伴随多项式为：S(x)=e(x)modg(x),根据伴随式的定义，若无错误传输，则S(x)=0，否则S(x)0，由此可实现循环码的检错。因为g(x)的次数为n-k，e(x)的次数为n-1，所以伴随式的最高次数为n-k-1，那么S(x)共有n-k项，故有2n-k种可能的伴随式。若满足2n-kn+1，则循环码具有纠错能力。,例7：前例中的（7，3）循环码，若接收到的码字为1100100，判断是否为许用码字。,解：接收码字1100100码多项式为：R(x)=x6+x5+x2，g(x)=x4+x2+x+1由伴随式S(x)=R(x)modg(x)=e(x)modg(x)，有S(x)=x6+x5+x2mod(x4+x2+x+1)=1S(x)0，该码字不是（7，3）循环码的许用码字。,6循环码的编码器,步骤：用xn-k乘以信息多项式M(x)。用g(x)除以xn-kM(x)得到余式b(x)。作码字b(x)+xn-kM(x)多项式。(7,4)系统循环码为例:u=(1001)即,7循环码的译码器,译码三步伴随式S的计算由S得到错误图样纠正,生成多项式g(x)去除接收码字R(x),校正子S的计算,5.5卷积码(连环码),在分组码中,任何特定的时间单位内编码器所产生的n个码元的码组,仅取决于该时间单位内k个消息位.存在着另一种码,由编码器在特定的时间内所产生的码元不但取决于这个特定时间段内进入的信息组,而且也与前面的时间段内的信息组有关,这种码称为卷积码.卷积码的编码可用移位寄存器来完成,卷积码有多种描述方法，分为两类解析描述法：生成矩阵法，离散卷积法，生成多项式法。解析法多用于编码。图形描述法：包括状态图、数图、网格图等。译码采用图形法，尤其是网格图。,一、定义：对于任一给定时刻，编码器的一个输出码字不仅与该时刻的当前输入码字有关，还与编码器的移位寄存器中存储的前面m个输入信息码字有关。因此卷积码记为(n0,k0,m0)卷积码。n0为输出的每个码字的位数；k0为输入的每个信息码字的位数；m0为移位寄存器中存储的信息码字个数（级连的移位寄存器个数）,定义：m0为卷积码的记忆长度。(m0+1)为卷积码的码字约束长度，相应的比特（码元）约束长度为(m0+1)n0。卷积码的码率为R=k0/n0，它也表示卷积码的编码效率。,卷积码可以是线性码，但不是分组码，卷积码是有记忆的编码,例8：给出一个（3，2，1）卷积码编码器的原理图,该编码器由2个移位寄存器构成。编码器每个并行输入一个2位信息码字：则并行输出一个3位卷积码字：Pi为监督元，有：可见，卷积码当前码字的监督元不仅与当前输入的信息元有关，还与前次输入的2个信息码元有关。,二、卷积码的生成序列卷积码的生成序列设卷积码编码器输入码序列（待编码的信息序列）为Uu0(1)u0(2)u0（k0）u1(1)u1(2)u1(k0)us(1)us(2)us(k0)编码器输出码序列为Cc0(1)c0(2)c0(n0)c1(1)c1(2)c1(n0)cs(1)cs(2)cs(n0)则编码器输出码序列中任一子码可以由如下卷积关系给出：,gt(i,j)为非系统卷积码的生成序列,系统码的生成矩阵系统卷积码序列中，对应于前k0位，生成序列g(i,j)中有k0k0个生成序列是固定的，即:,（i，jk0）,对应后(n0-k0)个监督位，k0(n0-k0)个生成序列需要给定,以便确定每个子码中n0-k0个监督元,则码字:,g(i,j)为系统卷积码的生成序列,例9：（3，1，2）系统卷积码的生成序列为：,则其任一码字为：,三、卷积码的生成矩阵和监督矩阵卷积码的生成矩阵上例中,假设输入为：U=(u1,u2,u3,),则输出为：C=(u1u1u1,u2u2u2,u3u3u3+u1,u4u4u4+u2),写成矩阵形式：C=UG,卷积码的基本生成矩阵。,生成矩阵可以改写为：,Ik0为k0k0阶单位矩阵0为k0k0阶全0方阵pl为k0(n0-k0)阶矩阵。,考虑一个约束长度内的码序列：U=u0u1u2um0得到卷积码的初始截短码组C：C=c0c1c2cm0,截短码组的生成矩阵:g=Ik0p00p10pm0,例10：（3，1，2）系统卷积码的生成序列为：,卷积码的监督矩阵(n0，k0，m0)码的基本监督矩阵为：,式中：h(n0-k0)n0N阶矩阵。(n0，k0，m0)码的监督矩阵为,式中：(n0-k0)Nn0N阶矩阵。,(n0，k0，m0)码的监督矩阵为,【例512】设(3，1，2)系统码的生成序列为g(1,1)1g(1,2)g0(1,2),g1(1,2),g2(1,2)g(1,3)g0(1,3),g1(1,3),g2(1,3)求该码的监督矩阵。由公式式得(3，1，2)码的监督矩阵