第六章信道编码65.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,作业范例,第三次作业范例,2,6.5,网格编码调制,一、网格编码调制,(TCM),的基本概念,下面将利用一个实例给出,TCM,的基本概念,QPSK,系统：,QPSK,是一个,4,相相移键控系统，它的每个码元传输,2,比特信息。若在接收端判决时因干扰而将信号相位错判至相邻相位，则将出现错码。,现在，将系统改成,8PSK,，它的每个码元可以传输,3,比特信息。但是我们仍然令每个码元传输,2,比特信息。第,3,比特用于纠错码，例如，采用码率为,2/3,的卷积码。,在纠错编码理论中，码组间的最小汉明距离决定着这种编码的纠错能力。,在,TCM,中，由于是直接对于已调信号（现在是,8PSK,信号）解码，码元之间的差别是载波相位之差，这个差别是欧氏距离,。,右图中，画出了,8PSK,信号星座图中的,8,个信号点。图中已假设信号振幅等于,1,，则相邻两信号点的欧氏距离,d,0,等于,0.765,。,两个信号序列的欧氏距离越大，即它们的差别越大，则因干扰造成互相混淆的可能性越小,。,图中的信号点代表某个确定相位的已调信号波形。,为了利用卷积码维特比解码的优点，这时仍然需要用到网格图。但是，和卷积码维特比解码时的网格图相比，在,TCM,中是将这些波形映射为网格图，故,TCM,网格图中的各状态是波形的状态。,基本原则：,将信号星座图划分成若干子集，使子集中的信号点间距离比原来的大。每划分一次，新的子集中信号点间的距离就增大一次。,【,例,】,见右图,A,0,是,8PSK,信号的星座图，其中任意两个信号点间的距离为,d,0,。,这个星座被划分为,B,0,和,B,1,两个子集，在子,集中相邻信号点间的,距离为,d,1,。,A,0,B,0,B,1,C,3,C,1,C,0,C,2,(000)(001),(010)(011)(100)(101)(110)(111),d,0,d,1,d,2,=2,二、,TCM,信号的产生,集划分方法,一种,TCM,编码器的方框图,由上图可见，这个卷积码的约束长度等于,3,。编码器输出的前两个比特,c,1,和,c,2,用来选择星座图划分的路径，最后,1,个比特,c,3,用于选定星座图第,3,级（最低级）中的信号点。,TCM,编码器结构,方框图,原理,将,k,比特输入,信息段分为,k,1,和,k,2,两段；前,k,1,比特通过一个,(,n,1,k,1,m,),卷积码编码器，产生,n,1,比特输出，用于选择信号星座图中,2,n1,划分之一，后面的,k,2,比特用于选定星座图中的信号点。,这表明星座图被划分为,2,n1,个子集，每个子集中含有,2,k2,个信号点。,在上例编码器方框图中,k,1,=,k,2,=1,由于未编码比特有两种取值，所以每个状态下，有两根线。,【,例,】,设初始状态,b,1,b,2,=00,，,k,1,=,k,2,=0,。那么，当输入信号序列,k,1,为“,01101000”,时，移存器状态和输出,c,1,与,c,2,之间的关系示于下表中。,TCM,系统,8PSK,的网格图,移存器状态和输出之间的关系,TCM,系统,8PSK,的网格图,在第,1,个输入码元“,1”,到达后，输出码元,c,1,和,c,2,由“,00”,变成“,01”,，,但是这时的输入信息,位,k,2,可能是“,0”,或“,1”,，,所以输出,c,1,c,2,c,3,可能是,“,010”,或“,011”,，这就是,右图中最高的两条平行,虚线。,在第,1,个输入码元“,1”,进入,b,1,后，,b,1,b,2,的状态由“,00”,(,a,),变到“,10”(,b,),，输出,c,1,c,2,c,3,可能是“,110”,或“,111”,，,b,1,b,2,的状态由,b,变到,d,，如图中虚线所示。依此类推。,A,0,B,0,B,1,C,3,C,1,C,0,C,2,(000)(001),(010)(011)(100)(101)(110)(111),d,0,d,1,d,2,=2,网格图和星座图之间的对应关系,每对平行转移必须对应最下一级划分同一子集中的两个信号点。,【,例,】,图中的“,000”,和“,001”,同属于子集,C,0,，“,100”,和“,101”,同属于子集,C,2,，等等。这些对信号点具有最大的欧氏距离,(,d,2,=2),。,从某一状态出发的所有转移，或到达某一状态的所有转移，必须属于同一上级子集。,【,例,】,图中从状态,a,出发的转移“,000”,、“,001”,、“,010”,和“,011”,都属于子集,B,0,。或者说，此两对平行转移应具有最大可能的欧氏距离。,三、,TCM,信号的解调,TCM,信号的解调算法,通常采用维特比算法，但是现在的网格图表示的状态是波形，而不是码组。,解码器的任务是计算接收信号序列路径和各种可能的编码网格路径间的距离,。若所有发送信号序列是等概率的，,则判定与接收序列距离最小的可能路径（又称为最大似然路径）为发送序列,。,因为卷积码是线性码，它具有封闭性，故要考察的路径距离与所用的测试序列无关,。所以，不失一般性，可以选用全“,0”,序列作为测试序列。,【,例,】,8PSK,信号解码路径,用全“,0”,序列作为测试序列时，如下图中虚线路径,U,所示。图中还用实线示出另一许用波形序列路径,V,，它从全“,0”,序列路径分开又回到全“,0”,序列路径。,若发送序列是全“,0”,序列，但是接收序列有错误，使接收序列路径离开全“,0”,路径然后又回到全“,0”,序列，且中间没有返回状态,a,，则解码器需要比较此接收序列路径和,U,的距离与接收序列路径和,V,的距离之大小。若后者小，则将发生一次错误判决。这里的距离是指欧氏距离。,自由欧氏距离,Fed,自由欧氏距离是指许用波形序列集合中各元素之间的最小距离。它决定了产生错误判决的概率。自由欧氏距离越大，错误判决概率越小。,在上例中，,U,和,V,两条路径间的欧氏距离,d,由下式决定：,上式是按照在欧氏空间求矢量和的方法计算的。因此，,另外一种许用波形序列的路径是，,U,1,WU,3,（见上图）。它和,V,序列相似，从状态,a,开始，离开,U,（虚线路径），再回到状态,a,。这个路径和,U,的距离等于,即,d,2,比较上面两条路径可见，路径,U,1,WU,3,和路径,V,相比，前者和路径,U,的距离更小。并且，可以逐个验证，这是和路径,U,距离最小的许用序列的路径。因此，按照上述定义，上式中的距离就是这种编码的自由欧氏距离。故可以将其写为,d,Fed,=2,另一方面，未编码的,QPSK,信号的相继码元（波形）没有约束。若将其自由欧氏距离作为参考距离,d,ref,，则由下图可知：,所以，可以证明，和未编码,QPSK,系统相比，,8PSK,的,TCM,系统可以获得的渐近编码增益等于,在下表中列出了通过大量仿真计算得出的部分,8PSK/TCM,系统的,(,渐近,),编码增益。,21,小结,1.,差错控制技术的四种分类、,ARQ,系统组成与工作过程、汉明距离、最小汉明距离、纠错能力与最小距离的关系；,2.,奇偶监督码的编码方法；,3.,线性分组码的性质、监督矩阵、生成矩阵的特点及其关系；,4.,循环码的特点、循环码的生成多项式、循环码的生成矩阵；,5.,循环码的多项式运算编码方法；,6.,卷积码编码器的结构、生成矩阵、状态图、网格图。,返回,习题,-,几种典型题型及例题,-,一、已经给出线性分组码的各个码字，要求求出最小码距，并判断其检错、纠错能力。,解法,：根据线性分组码的重要性质：,线性分组码的最小码距等于非零码的最小码重即可求出,。而码重就是指码字中,1,的个数。根据,公式,的检纠错编码定理求解分组码的检错、纠错能力。,【,例,】,已知某,线性分组码,的,8,个码字为,:000000,、,001110,、,010101,、,011011,、,100011,、,101101,、,110110,、,111000,，求该码的最小码距，并判断其纠检错能力。,解：,由于线性分组码的封闭性和码距的定义可得知：,线性分组码的最小码距等于非全零码的最小码重,(P340),。故有：,故由观察法即可得出,由纠错编码定理可得其检纠错能力如下：,(1),能发现,2,个错误码元,(2),能纠正,1,个错误码元,二、关于汉明码的题目,1,、对于,(n,k),汉明码，根据汉明码的定义，可得：,n=2,r,-1,其中,r=n-k,，为汉明码的监督位的数目。所以,k=n-r=2,r,-1-r,。根据编码效率的公式 求编码效率。,2,、汉明码最大的特点是可以纠正,1,位错误。,【,例,】,一个码长为,15,的汉明码，其监督码元有多少位？编码效率是多少？用其作纠错码能够纠正几位错误,?,解：,由汉明码的定义有：,n=2,r,-1=15,故有,r=4,所以编码效率,汉明码能纠正,1,位错误。,三、给出线性码非典型的生成矩阵,G,或监督矩阵,H,1,、要求其对应的典型,H,或,G,解法,:,先将,G,或,H,进行初等行,(,列,),变换化成典型阵的形式，再根据,G,和,H,的转换关系直接写出对应的,H,或,G,。,2,、求其所有系统码字,解法,:,对于所有的线性分组码，都可以用,A=MG,来求码字，码字的个数由,k,确定，个数为,2,k,。假定,k=3,则,M=000,，,001,，,010,，,011,，,100,，,101,，,110,，,111,，共,8,个，则用每个,M,乘以,G,即可得到所有码字。,（注意模,2,加法和乘法的规律，避免出错）,3,、判断其检错、纠错能力,解法,:,根据线性分组码的最小码距等于其非零码元的最小码重即可求的最小码距,d,0,，求出,d,0,即可判断其检错、纠错能力。,【,例,】,已知,(7,3),线性分组码的生成矩阵为,求其监督矩阵，写出该,(7,3),码的系统码，并判断其纠检错能力。,解：,先用初等行变换将生成矩阵化成典型阵，如下所示：,监督矩阵为,K=3,所以共有,2,3,=8,个系统码字，再根据,A=MG,，即可分别求出各个码字，如,M=101,时：,故由线性分组码的性质可得其最小码距,d,0,为,4,，由检纠错编码定理可得：能发现,3,位错误；能纠正,1,位错误；能发现,2,位错误的同时纠正,1,位错误。,其它码字,分别为：,四、给出,(n,k),线性分组码的监督关系方程组求其,H,和,G,；判断某个码是否该分组码的码字。,解法：,首先，根据监督方程写出对应的监督矩阵,H,然后将其化成标准形式，即可求出对应的,G,；,然后，计算伴随式,S=BH,T,，若,S=0,，则,B,是该,(n,k),码的码字，否则,B,不是该,(n,k),码的码字。,五、关于循环码的题目,1,、给出,(n,k),循环码的生成多项式,g(x),求其对应的生成矩阵,G,和监督矩阵,H,。,解法：根据,可求出,G(x),，将其变化成典型矩阵,G,，根据,G,可求出,H,。,2,、求某个信息码元组,M,对应的码字。,解法,1,：因为循环码首先是线性分组码，故可根据,A=MG,求其码字。,解法,2,：利用循环码的性质求解。,根据,M,即可写出,M(x),，则用,x,n-k,M(x)/g(x),即可得到,r(x),则,A(x)=x,n-k,M(x)+r(x),即得,A,。,3,、给出,(n,k),循环码的生成多项式,g(x),再给出接受码组,B(x),要求判断码组在传输中是否出错。,解法：利用循环码,g(x),的重要性质求解：,g(x),为,r=n-k,次码多项式，其次数最低，且所有其它码多项式,A(x),都能被,g(x),整除。假定传输正确，则有,B(x)=A(x),，则必定有,B(x),能被,g(x),整除！,故判断方法如下：用长除法计算,B(x)/g(x),，若能整除则判断传输没有出错。否则肯定出错。,【,例,】,已知某,(7,4),循环码的生成多项式,g(x)=x,3,+x+1,：,(1),监督矩阵,H,和生成矩阵,G;,(2),写出该循环码的所有码字，并求其最小码距；,(3),求,M=1010,时对应的码字；,(4),若,B=1001101,判断其是否是该分组码的码字。,解,:,(1),(2),写出该循环码的所有码字，并求其最小码距；,解：,方法一,：利用,A=MG,求解，其中,M,共有,16,种不同的组合，,求解除所有码字后，即可用观察法得出循环码的最小码距为,3,。,方法二,：利用,求出,A(x),，即可求出,A(x),对应的码字,A,（感兴趣同学自行按方法二求解）,(3),求,M=1010,时对应的码字；,解：,方法一,：直接利用第,(2),小题的结果即可。,方法二,：,方法三,：,方法三容易出错！,(4),若,B=1001101,判断其是否是该分组码的码字。,解：,方法一,：利用长除法,若,S(x)=0,，则判定传输正确，否则传输出错。,故可判定,B,不是该分组码的码字。,方法二,：因为循环码首先是一种线性分组码，所以如果已知,H,，则可以根据,S,T,或,S,是否为,0,来判断，若为,0,则判定,B,是该分组码的码字。,