资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第九章 信道编码,牛凯,niukai,主要内容,信道编码的基本概念和分类,两种主要的信道编码,分组码,卷积码,其他类型编码和编码界限,（工程应用）,章节,信道编码的基本概念,线形分组码,循环码,BCH,码,卷积码,其他编码类型,纠正突发错误码、交织码、级联码、,Turbo,码、高效率信道编码,TCM,9.1,信道编码的基本概念,为什么需要信道编码？,在数字信号的传输中，实际信道不是理想的，存在噪声和干扰，会导致接收端的误判，这样就产生了差错。,可采取的办法：,合理设计基带信号,选择调制、解调方式,采用均衡技术,增大发送功率,仍然达不到要求，就需要信道编码,9.1,信道编码的基本概念,信道分类（按差错出现类型）,独立随机差错信道,差错随机出现，且相互独立（无记忆性）,原因：由高斯白噪引起（信道本身的传输特性比较理想）,太空信道、卫星信道、同轴电缆、光缆信道、视距微波信道,9.1,信道编码的基本概念,信道分类（按差错出现类型）,突发差错信道,差错成串出现（记忆性）,原因：信道传输特性不理想（衰落和码间干扰），有大的脉冲干扰,短波信道、移动通信信道、散射信道、明线和电缆信道,混合信道,9.1,信道编码的基本概念,信道编码的构造,在发送端，在待发送的信息序列中加入一些多余的码元（监督码元），这些监督码元和信息码元之间以某种确定的规则相互关联，即满足一定的约束关系。,在接收端，按既定的规则检验信息码元与监督码元之间的约束关系。约束关系被破坏就意味着传输中有差错（检错）；借助于约束关系甚至还可以纠正错误（纠错）。,9.1,信道编码的基本概念,信道编码分类（按纠正错误类型分类）,纠独立随机差错码：,分组码和卷积码中的大部分种类,纠突发差错码：分组码和卷积码中的几类、交织码,纠混合差错码：级联码,9.1,信道编码的基本概念,信道编码分类（按约束关系分类）,线性码：信息码元与监督码元之间的约束关系是线性关系，即满足一组线性方程式,非线性码：约束关系不是线性关系。（缺少理论和应用上的研究）,9.1,信道编码的基本概念,信道编码分类（按编码方式分类）,分组码：将信息序列分成独立的若干组进行编码。编码后，一组中的码元只与本组的原始信息码元有关，而与其他组的信息码元无关。,分组码用符号（,n,，,k,）表示。,k,是一组中信息码元的数目，,n,是码元总数目，则监督码元有,n-k,位,编码效率,k/n,，编码冗余度,1-k/n,非分组码：卷积码是其中最主要的一类。,9.1,信道编码的基本概念,信道编码分类（按编码后是否包含原始信息码元分类）,系统码：编码后的信息序列中包含原始信息码元（位置可能变化）,非系统码：编码后的信息序列中不包含原始信息码元,9.1,信道编码的基本概念,在数字通信系统中，利用信道编码可提高系统可靠性，控制差错。其控制差错的方式主要分为三种。,前向纠错（,FEC,）：发端发送有一定纠错能力的码，若传输中产生的差错的数目在码的纠错能力内，收端可以纠正。,优点：单向通信（不需要反馈信道），实时性好。,缺点：码的构造复杂，译码电路复杂。,9.1,信道编码的基本概念,反馈重传（,ARQ,）：发端发送有一定检错能力的码，收端译码时如发现有错，则通知发端重发，直到正确接收。也称为检错重传或自动请求重复。,优点：检错比较简单，码的效率和结构简单，译码电路简单。,缺点：需要反馈信道，不能单向通信；实时性差。,三种类型：等待式,ARQ,、退,N,步,ARQ,，选择重传,ARQ,。,9.1,信道编码的基本概念,混合差错控制（,HEC,）：是,FEC,和,ARQ,的结合。,需要反馈信道。实时性和译码复杂性是,FEC,和,ARQ,两种方式的折衷。,9.1,信道编码的基本概念,检错和纠错的基本原理,例,1,：一个由,3,位二进制数字构成的码组，共有,8,种组合。若用其表示不同的天气，如：,000,（晴）、,001,（云）、,010,（阴）、,011,（雨）、,100,（雪）、,101,（霜）、,110,（雾）、,111,（雹）。,任一码组在传输中产生传输中产生一个或多个错误，都会变成另一个信息码组。无法检错和纠错。,原因：码组中只有信息码元，没有监督码元,9.1,信道编码的基本概念,检错和纠错的基本原理,例,2,：利用,2,位二进制数字的,4,种组合表示,4,种天气，再加,1,位奇偶校验位。,可以检测出传输中的,1,个或,3,个错误（无法检测,2,个错误，无法纠错）,原因：监督码元的引入使得,8,个组合中只有,4,个是许用组合，其余,4,个是禁用组合,9.1,信道编码的基本概念,码重，码距，最小码距,码重：在分组码中，把一个码组,/,字（,A,）中所含,1,的数目定义为码组,/,字重量，简称码重，记为,W(A),码距：把两码组,A,、,B,中对应位置上码元不同的数目定义为两码组的距离，简称码距或汉明距，记为,d(A,B,),最小码距：把某种编码中各个码组间距离的最小值定义为最小码距,d,min,9.1,信道编码的基本概念,码重，码距，最小码距,码距的几何解释（图）,9.1,信道编码的基本概念,一种编码的最小码距直接关系到这种编码的检错和纠错能力（图,9.1.2,）,为检测,e,个误码，要求最小码距,为纠正,t,个误码，要求最小码距,为纠正,t,个误码，同时检测,e,（,e,t,），要求最小码距,9.1,信道编码的基本概念,两种简单的信道编码,(n,1),重复码（以,(3,1),重复码为例）,许用码组,(000),(111),d,min,=n,可纠,1,位错或检,2,位错,用来纠错时，出现错误的概率为,9.1,信道编码的基本概念,两种简单的信道编码,(n,n-1),奇偶校验码（以,(4,3),偶校验为例）,最后一位为校验位（例,9.1.2,）,偶校验：码字中,1,的个数为偶数；奇校验：码字中,1,的个数为奇数,最小码距为,2,只能用于检错：只能检奇数个错误，无法检偶数个错误,9.1,信道编码的基本概念,两种简单的信道编码,(n,1),重复码,编码效率,1/n,，,d,min,=n,随着,n,的增大，检错、纠错能力越来越强，但编码效率越来越低,(n,n-1),奇偶校验码,编码效率,1-1/n,，,d,min,=2,随着,n,的增大，编码效率越来越高，但只能检奇数个错误,9.1,信道编码的基本概念,有限域,定义：一个有限个元素的集合，进行规定的代数四则运算后，结果仍是属于该集合的元素（自封闭性）。,GF(2),：集合,0,1,对规定的模二和“,”,及点乘“,”,运算是自封闭的，所以是一个有限域，称之为二元域,9.1,信道编码的基本概念,有限域,GF(2,k,),：以,0,1,中的元素构成的所有长度为,k,的序列所组成的集合，对规定的模二和“,”,及点乘“,”,运算也是自封闭的。,9.2,线性分组码,定义,分组：将,k,个信息位作为一组进行编码，变换成长度为,n,（,nk,）的二进制码组,线性：信息码元与监督码元的约束关系是一组线性代数方程。,记为（,n,，,k,）码，编码效率,=,k/n,，冗余度为,1-,=1-k/n,9.2,线性分组码,数学定义,分组：,线性：,线性编码,f,就是从矢量空间,GF(2,k,),到另一个矢量空间,GF(2,n,),的一组线性变换。它可以用线性代数中的有限维矩阵来表示。,9.2,线性分组码,线性分组码的码距,两个码组的距离必等于另一个码组的码重,编码的最小码距等于非零码的最小重量（决定该编码的纠错能力）,9.2,线性分组码,例：,(7,3),线性分组码,9.2,线性分组码,例,将,(9-1),表示成矩阵形式,9.2,线性分组码,(,n,k,),线性分组码可以由,k,个输入信息位通过一线性变换矩阵,G,（,k,行,n,列）产生，,G,称为该线性分组码的生成矩阵,若,G,能分解成两个子矩阵，其中,I,为,k,维单位方阵，则称该线性分组码,c,为系统码或组织码，,G,为该系统码的典型生成矩阵,9.2,线性分组码,例,将,(9-2),表示成矩阵形式,9.2,线性分组码,(,n,k,),线性分组码的监督关系（,n-k,个线性监督方程）用,H,矩阵（,n-k,行,n,列）表示，,H,称为该线性分组码的监督矩阵,若,H,可以分解成两个子矩阵，其中,I,是,(,n-k,),维单位方阵，则称该线性分组码,c,为系统码或组织码，,H,为该线性分组码的典型监督矩阵,9.2,线性分组码,生成矩阵,G,与监督矩阵,H,之间的关系,生成矩阵,G,与监督矩阵,H,可以互相转换。知道了其中一个，另一个就容易求得,9.2,线性分组码,对偶码,定义：若把,(,n,k,),码的监督矩阵,H,作为,(,n,n-k,),码的生成矩阵,G,，把,(,n,k,),码的生成矩阵,G,作为,(,n,n-k,),码的监督矩阵,H,，则这样的,(,n,k,),码和,(,n,n-k,),码互为对偶码,9.2,线性分组码,系统码与非系统码,系统码的广义定义：只要编码前的信息码元以不变的形式在码组中的,k,位出现，都可称为系统码。否则，就是非系统码,对线性分组码而言，在检纠错方面，系统码和非系统码是完全一样的。,9.2,线性分组码,系统码与非系统码,任何一个线性分组,(,n,k,),码都可等价于一个系统码,非系统码的生成矩阵可通过初等行变换和列交换得到等价的系统码的生成矩阵,初等行变换：矩阵的两行交换位置；将矩阵的一行加到另一行,列交换：矩阵的两列交换位置,思考：为什么？,9.2,线性分组码,例,9.2,线性分组码,例,9.2,线性分组码,线性分组码的编码实现,由生成矩阵，非常容易得到线性分组码的电路实现方式,9.2,线性分组码,伴随子（校正子）,9.2,线性分组码,伴随子（校正子）,校正子只与传输差错,E,有关，可见错误图样和校正子之间有确定的关系,码组有,n,位，可产生,2,n,个错误图样；而校正子,S,是,(,n-k,),维矢量，只有,2,n-k,种组合的校正式；这样对每一种校正式，都有,2,k,个错误图样与之对应,9.2,线性分组码,二进制对称信道（,BSC,）下的译码,在输入信息,0,、,1,等概的情况下，二进制对称信道下的最优译码准则等效为最小汉明距离准则,在译码时，得到伴随式,S,后，应该选择与,S,对应的,2,k,个可能的错误图样中重量最小的进行译码,若收到的码字为,Y,，得到的伴随式为,S,，若,S,对应的码重最小的错误图样是,E,，那么译码输出就是,C=Y,E,9.2,线性分组码,利用监督矩阵进行译码,例,9.2.5,9.2,线性分组码,利用监督矩阵进行译码,若接收码字中只有一个码元出现差错，比如,y,i,出错，则校正子,S,等于监督矩阵第,i,列。,比较,(7,4),码的监督矩阵和码重最小的,E,9.2,线性分组码,汉明码,汉明码是一种能纠正一位错码的线性分组码,主要参数：,码长,n=2,m,-1,信息位,k=2,m,-1-m,监督位,n-k,=m,最小码距,d,min,=3,，纠错能力,t=1,码效率,R=,k/n,=1-m/n=1-m/(2,m,-1),当,n,很大时，,R,趋近于,1,，所以汉明码是一类高效率的纠错码。,9.2,线性分组码,汉明码,当,m=3,时，,n=7,，,k=4,。之前的,(7,4),码就是汉明码。,特点：监督矩阵中的,n=2,m,-1,列正好是,m,位码元的,2,m,种组合中除全,0,组合外的其它组合，且每种组合出现一次。每种组合对应该列对应的码元出现传输错误时的校正子。,9.2,线性分组码,汉明码的译码电路,利用最小码重错误图样进行译码的电路实现（图,9.2.4,）,利用校正子与错码位置的对应关系，也可以使用地址译码器来帮助实现译码,9.3,循环码,循环码,是线性分组码的一个重要子类,BCH,码是其主要的一大类,汉明码、,R-M,码、,Golay,码、,RS,码等可变换或纳入循环码内，,Goppa,码的一个子类也属于循环码,用反馈线性移位寄存器可以容易的实现其编码和得到伴随式,由于数学上的特性，译码方法简单,9.3,循环码,循环码的循环移位特性,循环码具有线性分组码的一般特性,循环移位特性：任一许用码组经过任意位的循环移位后得到的码组仍是一个许用码组,9.3,循环码,定义：,循环移位推广：,9.3,循环码,举例：（,7,3,）码,9.3,循环码,循环码的多项式描述,码字的多项式描述，一个,n,元码字可以用一次数不超过,n-1,的多项式唯一的表示,其中，我们不关心,x,的具体取值，其次数只表示相应码元的位置,称这样的,c(x,),为,c,的码字多项式,9.3,循环码,多项式的加法,注意多项式加法与向量加法的对应关系,9.3,循环码,多项式的乘法,注意多项式乘法与矩阵乘法的对应关系,9.3,循环码,模运算,整数的模运算,码字多项式的模运算（其中,p(x,),次数为,n,，,r(x,),次数小于,n,）,9.3,循环码,模运算,码字多项式的模运算举例,9.3,循环码,循环移位特性的多项式描述,码字,c,及其码多项式,c(x,),其左移,i,位后的码字,c,i,和码多项式,c,i,(x,),9.3,循环码,循环移位特性的多项式描述,c,的码字多项式,c(x,),乘以,x,i,9.3,循环码,循环移位特性的多项式描述,上面的表达式说明码字循环移位,i,位后的多项式,c,i,(x,),在模,x,n,+1,的运算下与,x,i,c(x,),是相同的,在循环码的研究中可以用,x,i,c(x,),代替,c,i,(x,),9.3,循环码,循环码的生成矩阵,循环码中除全,0,码组外必然有一个且仅有一个前,k-1,位均为,0,的码组，且其最后一位为,1,存在性：循环码属于线性分组码，必可以变换为一个系统码；系统码的信息码元可以有,k-1,位,0,不存在前,k,位均为,0,的非全,0,码组：,k,位输入信息码元为,0,则编码后必定是全,0,码组,唯一性：如果有两个码组满足此条件，由线性分组码对运算的封闭性，两个码组相加前,k,位为0,此码组最后一位为,1,：若为,0,则移位后会成为前,k,位为,0,的非全,0,码组,9.3,循环码,循环码的生成矩阵,(,n,k,),线性分组码的生成矩阵（,k,行,n,列）的每一行均为一个许用码组，且线性无关,利用循环码的唯一的前,k-1,位为,0,的非全,0,码组,g(x,),，容易得到生成多项式：将,g(x,),和其依次循环移位直到,k-1,次的各个码组,g,(1),(x),，,g,(2),(x),，,，,g,(k-1),(x),，分别作为生成矩阵的,k,行（容易知道它们互不相关），即得到生成矩阵,g(x,),（次数为,n-k,）称为循环码的生成多项式,9.3,循环码,循环码的生成矩阵,举例：若已知某,(7,3),循环码的一个码字为,(0111001),，则其循环移位,4,次后的码字,(0010111),也是一许用码字，易得生成矩阵,9.3,循环码,循环码的生成矩阵,(,n,k,),循环码的每个码字的码多项式都是,g(x,),的倍数,凡次数小于,n,的多项式，若能被,g(x,),除尽，则必是该循环码的码多项式,9.3,循环码,循环码的生成矩阵,用上面的办法所产生的生成矩阵所表示的循环码不是系统循环码,系统循环码的生成矩阵的形式为,第,i,行也为一许用码字，多项式表示为,9.3,循环码,循环码的生成矩阵,系统循环码的生成矩阵的多项式表示,9.3,循环码,循环码的生成矩阵,系统循环码的生成矩阵举例：,(7,3),循环码的生成多项式,g(x,)=x,4,+x,2,+x+1,，,g=(0010111),9.3,循环码,循环码的生成矩阵,非系统循环码变换为系统循环码也可以用矩阵变换的办法，但只能用简单行变换，不能用列的交换,9.3,循环码,循环码的生成多项式,g(x,),为,n-k,次多项式，则,x,k,g(x,),为,n,次多项式,c(x,),为许用码组，所以必是,g(x,),的倍数,生成多项式,g(x,),必是,x,n,+1,的因式，为寻找生成多项式指出了方法,9.3,循环码,循环码的生成多项式,举例：寻找,(7,3),循环码的生成多项式,g(x,),，其次数为,n-k,=4,9.3,循环码,循环码的生成多项式,对任意,n,，有：,若取,x+1,为生成多项式，构成的循环码是简单的偶监督码,(n,n-1),。最小码距,d,min,=2,若用,x,n-1,+ x,n-2,+x+1,为生成多项式，构成的,(n,1),循环码信息位个数为,1,，校验码个数为,n-1,。容易知道实际就是重复码。,9.3,循环码,循环码的生成多项式,(7,k),循环码,9.3,循环码,循环码的监督多项式,循环码的生成多项式,g(x,),是,x,n,+1,的因式,h(x,),称为此循环码的监督多项式,举例，,(7,3),循环码,9.3,循环码,循环码的监督矩阵,9.3,循环码,循环码的监督矩阵,由上面的式子，可知循环码的监督矩阵可表示为,容易验证，由,g(x,),移位得到的生成矩阵与上面的监督矩阵相乘得到,0,阵,9.3,循环码,循环码的监督矩阵,举例：,(7,3),循环码，,g(x,)=x,4,+x,2,+x+1,，,h(x,)=x,3,+x+1,9.3,循环码,循环码的监督矩阵,系统循环码的监督矩阵,例,:(7,3),系统循环码,9.3,循环码,系统循环码的编码器,系统循环码的编码方式是将信息码多项式升,n-k,次幂后除以生成多项式，然后将所得余式置于升幂后的信息多项式之后,9.3,循环码,系统循环码的编码器,举例,：,(7,4),系统循环码的生成多项式为,g(x,)=x,3,+x+1,，输入信息多项式为,u(x,)= x,3,+1,9.3,循环码,系统循环码的编码器,多项式除法电路可以用带反馈的线性移位寄存器来实现（图,9.3.2,）,与采用手算进行多项式长除运算的过程类似,用除法电路进行系统码的编码的过程（表,9.3.3,）（板书）,9.3,循环码,系统循环码的译码器,校正子,9.3,循环码,系统循环码的译码器,校正子与错误图样的关系,9.3,循环码,系统循环码的译码器,校正子的一个重要性质：,一码组移位,i,次后的码组的校正子等于原码组的校正子在除法电路中移位,i,次的结果,9.3,循环码,系统循环码的译码器,举例：,(7,4),系统循环码的生成多项式为,g(x,)=x,3,+x+1,9.3,循环码,系统循环码的译码器,上面的性质使得译码器需要识别的错误图样的数目大大减小（如果某,(,n,k,),码可纠正,m,个错误，则识别错误图样数目由 减为 ）；,(7,4),码的识别数由,7,减为,1,。,9.3,循环码,系统循环码的译码器,译码器电路（图,9.3.3,）,译码过程（板书）,一次译码需要,2n,个节拍才能完成。所以真正的译码电路需要两个除法电路（图）,9.3,循环码,码字的扩展与收缩：可增加信息位、校验位来增加码字长度，减少信息位、校验位来减少码字长度（图,9.3.4,）,9.3,循环码,CRC,（,Cyclic Redundancy Check,）,:,循环冗余校验,检错能力很强,实现简单,CRC,校验已成为国际标准，在数据通信和移动通信中广为使用,9.3,循环码,CRC,的检错原理,c(x,),能被生成多项式,g(x,),整除，如接收到的,y(x,),不能被,g(x,),整除，意味着传输出错,编码电路与循环码一样(图9.3.5),译码电路检查对,g(x,),的整除性(图9.3.6),9.3,循环码,CRC,的检错原理,9.3,循环码,CRC,的检错原理,9.3,循环码,注意：,CRC,并不一定是循环码,因为,g(x,),可以对任意信息码长,k,的分组进行编码，作为生成多项式,9.3,循环码,CRC,的检错能力,错误图样总个数:2,k+r,无法检出的错误图样个数:2,k,-1,无法检出的错误图样的比例,:(,2,k,-1,)/,2,k+r,=1/2,r,9.4 BCH,码,BCH,码,由,Bose,，,Chaudhuri,和,Hocquenghem,发现,属于循环码,纠错能力强，能纠正多个随机错误,构造方便,（我们不从理论上研究,BCH,码的性质，只学习如何使用,BCH,码）,9.4 BCH,码,BCH,码的构造,其生成多项式为,t,为纠错个数，,m,i,(x,),为最小多项式，,LCM,表示取最小公倍式,其能纠正,t,个随机差错，最小码距,9.4 BCH,码,本原,BCH,码,码长,非本原,BCH,码,码长,n,为,2,m,-1,的因子,9.4 BCH,码,最小多项式表（表）,阶数,m,表示码长,n=2,m,-1,中的,m,十进制数字表示,m,i,(x,),中的,i,最小多项式用,8,进制数表示，如,最小多项式后的字母意义：,ABCD,表示非本原多项式，,EFGH,表示本原多项式,9.4 BCH,码,BCH,码构造举例,例,9.4.1,：码长,15,的,BCH,码，能纠正,3,个错误,9.4 BCH,码,表,9.4.1,（本原,BCH,码）,表,9.4.2,（非本原,BCH,码）,（学会根据需要查找）,9.4 BCH,码,Golay,码,(23,12),非本原,BCH,码，生成多项式为,码距为,7,，能纠正,3,个随机错误,是,GF(2),上纠多个随机差错的唯一一个完备码，监督码元得到了最充分的利用,9.4 BCH,码,RS,（,Reed-Solomon,，里德,-,所罗门）码,一种非二进制,BCH,码，编码的单位是符号；一个符号由,m,个二进制码元组成，即为,2,m,进制,纠正,t,个符号错误的,RS,码的参数：,码长,n=2,m,-1,个符号（即,m(2,m,-1),比特）,信息位数,k=n-2t,个符号（即,m(n-2t),比特）,监督位数,2t,个符号（即,2mt,比特）,最小码距,d=2t+1,个符号（即,m(2t+1),比特）,纠正突发错误的能力强,9.5,卷积码,简单介绍,不是分组码,1955,年，由,P. Elias,提出,没有进行理论研究的好的数学工具,纠错性能和码字构成之间的直接关系没找到,性能好的码的构成不能从理论上推导得到，只能用计算机搜索,9.5,卷积码,编码器一般结构,9.5,卷积码,编码器一般结构,9.5,卷积码,编码器一般结构,有,k,个输入信息端，,n,个输出端（,kK-1,后，树图中的,2,k(K-1),个状态开始重复出现,格图是从,l=K,开始，合并重复出现的状态,格图特点：保持了时序的清晰性，表达也比较简洁,格图是研究维特比译码算法的重要工具,9.5,卷积码,格图举例：,(2,1,3),卷积码,9.5,卷积码,离散卷积法：以,(2,1,4),卷积码为例说明,输出的各个分支所构成的系统都是线性时不变系统；而线性时不变系统可以用冲激相应来表示（长为,K,），且输出是输入与冲激相应的卷积,9.5,卷积码,离散卷积法,举例：,(2,1,4),卷积码,9.5,卷积码,离散卷积法,举例：,(2,1,4),卷积码（图,9.5.3,）,相应的冲激相应也叫生成序列,9.5,卷积码,码多项式法,将输入序列、生成序列和输出序列分别用码多项式表示，容易验证，输出码多项式等于输入码多项式和生成序列码多项式的乘积,9.5,卷积码,码多项式法,举例：,(2,1,4),卷积码（图,9.5.3,）,9.5,卷积码,生成矩阵法：以,(2,1,4),卷积码为例推导,9.5,卷积码,生成矩阵法：以,(2,1,4),卷积码为例推导,9.5,卷积码,生成矩阵法：推广到一般,(,n,k,K,),卷积码,(,n,k,K,),卷积码的生成序列一般表示式为,其中,g,l,i,j,表示每组,k,个输入比特中第,i,个比特经延迟,l,后的输出与每组,n,个输出比特中第,j,个比特的模,2,和器件的输入端的连接关系；为,1,表示有连接，为,0,表示没有连接,9.5,卷积码,生成矩阵法：推广到一般,(,n,k,K,),卷积码,生成矩阵为,9.5,卷积码,生成矩阵法：推广到一般,(,n,k,K,),卷积码,举例：,(3,2,2),卷积码（图,9.5.4,）,9.5,卷积码,生成矩阵法：推广到一般,(,n,k,K,),卷积码,举例：,(3,2,2),卷积码（图,9.5.4,）,9.5,卷积码,卷积码的译码方法,代数译码：根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性,概率译码：这种译码在计算时要考虑信道的统计特性,门限译码,序贯译码,维特比译码（最佳译码，最大似然译码）,9.5,卷积码,最大后验概率（,MAP,）译码,9.5,卷积码,最大似然（,ML,）译码,若发送码字等概出现，,MAP,等价于,ML,9.5,卷积码,最大似然（,ML,）译码,对于无记忆信道,称上式中的取对数部分为对数似然函数，简称似然函数（或度量值）,9.5,卷积码,编码信道,硬输出：解调器将信号硬判决为,0,或,1,软输出：输出模拟量或经多电平量化的值,9.5,卷积码,举例（,2PSK,）,V,1,(t)=,s(t)+n(t,),是软输出，或对其进行,Q=2,m,2,的多电平量化也是软输出,V,2,(t),是硬输出，对,V,1,(t),进行了硬判决,9.5,卷积码,维特比译码,硬判决译码：对应于解调器的硬输出,软判决译码：对应于解调器的软输出,9.5,卷积码,维特比硬判决译码,对于二进制对称信道（,BSC,）,9.5,卷积码,维特比硬判决译码,似然函数,译码准则（因为,P5m,时，性能已经非常接近最大似然译码,9.5,卷积码,维特比截短译码（优点）,时延降低：由,n,降为,L,存储量减小：译码序列存储量由,n2,km,减为,L2,km,9.5,卷积码,维特比软判决译码（直接输出：,2PSK,）,直接以,V,1,(l),作为软输出,y,l,其中,c,l,=0,1,9.5,卷积码,维特比软判决译码（直接输出：,2PSK,）,求最大似然函数等价于求最小欧氏距离,若去掉公有项，则,9.5,卷积码,维特比软判决译码（多电平量化）,以,V,1,(l),经多电平量化后的值作为软输出,y,l,2PSK,：将 作为度量值，或将其加上一个常数使之恒为非负,9.5,卷积码,维特比软判决译码（多电平量化举例）,c=(111,000,001,001,111,001,111,110),y=(,1,01,100,0,01,0,11,11,0,110,1,11,1,1,0),9.5,卷积码,维特比软判决译码（总结）,解调直接输出可以看作是多电平量化的一种,译码过程与硬判决译码一样，唯一的区别是度量值不同,也具有汇聚特性，可以使用维特比截短译码,性能优于硬判决译码，增益有,1.52.0dB,3,比特量化即基本足够,9.5,卷积码,卷积码的距离特性,码的距离特性与纠错能力有密切关系,分组码：最小距离,d,min,卷积码,最小距离,d,min,：长度为,nK,的编码后序列之间的最小汉明距离（用于门限译码，不讨论）,自由距离,d,free,：任意长度的编码后序列的最小汉明距离（用于维特比译码）,分组码与卷积码的区别：卷积码没有固定的长度的码字,9.5,卷积码,卷积码的距离特性,由卷积码的编码器结构，可知卷积码具有线性性质,这样，卷积码的码序列之间的自由距离就等于非全零码序列的最小码重,9.5,卷积码,卷积码的距离特性（自由距离,d,free,）,求自由距离,d,free,可以转化为求任意长非全零码序列的最小码重,进一步转化：由于一条编码路径的码重在与全,0,路径汇聚以后不再增加（若在分离码重继续增加，显然不是最小码重），所以求,d,free,就是找到从全零状态出发后重新汇聚到全零状态的编码路径的最小码重,求法：格图法（图）,9.5,卷积码,卷积码的距离特性,(,n,k,K,),卷积码的构造方法有多种，通过求生成函数可以求得它们的自由距离（解析方法）,随着,k,，,K,的增大，状态数目指数增加，求生成函数变得越来越复杂,好码的寻找：通过计算机搜索,9.5,卷积码,卷积码的距离特性,Heller,给出的编码效率为,1/n,的卷积码（即,(n,1,K),卷积码）的,d,free,的上界,在上式的基础上，,Daut,等人给出了编码效率为,k/n,的卷积码的,d,free,的修正上界，以及搜索的相应号码的列表,9.7 交织码,长突发差错带来的问题,线性分组码和卷积码主要用于无记忆信道，即用于纠正独立随机差错,线性分组码和卷积码中的少数种类可以用于纠正突发差错，但一般仅限于单个短的突发差错,9.7 交织码,交织码的原理,它实际上是一种信道改造技术，将产生突发差错的有记忆信道近似改造成产生独立随机差错的无记忆信道,原理框图（图9.7.1）,9.7 交织码,交织码的原理,交织器（发送端）用于将原有的码元序列的顺序打乱；去交织器（接收端）则用于恢复码元序列的顺序,本质上，去交织器将从信道接收的码元序列的顺序打乱了。这样信道产生的突发差错的顺序也被打乱，变成了近似的独立随机差错,这样由交织器、突发信道、去交织器组成的编码信道就完成了信道改造的功能，使信道变成了近似的独立随机差错信道,9.7 交织码,交织的种类,分组交织,卷积交织,伪随机交织,9.7 交织码,分组交织,框图（图9.7.2）,交织器和去交织器中各有一存储矩阵,在接收端进行交织时，将码元序列以一定规则,f1,写入存储矩阵，再以另一一定规则,f2,读出,在接收端进行去交织时，将接收码元序列以规则,f2,写入存储矩阵，再以规则,f1,读出,9.7 交织码,分组交织（举例）,交织器列写入，行读出,9.7 交织码,分组交织（举例）,去交织器行写入，列读出,9.7 交织码,分组交织,把具有,M,列,N,行的存储矩阵的交织称为(,M,N),分组交织,收发时延：2,MN,9.7 交织码,卷积交织,框图（9.7.3）,与分组交织相比：存储器数量减少一半；收发时延减少一半,9.7 交织码,伪随机交织,分组交织和卷积交织的缺点：其读写规则不变（呈周期性），这样在特定情况下，会使周期的独立随机差错变成周期的突发差错,伪随机交织的解决方法：码元序列顺序的打乱是伪随机的，即读写规则是变化的（没有周期性）,
展开阅读全文