北邮-通信原理-第九章-信道编码.ppt

第九章 信道编码,主要内容,信道编码的基本概念和分类两种主要的信道编码分组码卷积码其他类型编码和编码界限（工程应用）,章节,信道编码的基本概念线形分组码循环码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)最小码距：把某种编码中各个码组间距离的最小值定义为最小码距dmin,9.1 信道编码的基本概念,码重，码距，最小码距码距的几何解释（图）,9.1 信道编码的基本概念,一种编码的最小码距直接关系到这种编码的检错和纠错能力（图）为检测e个误码，要求最小码距为纠正t个误码，要求最小码距为纠正t个误码，同时检测e（et），要求最小码距,9.1 信道编码的基本概念,两种简单的信道编码(n,1)重复码（以(3,1)重复码为例）许用码组(000),(111)dmin=n可纠1位错或检2位错用来纠错时，出现错误的概率为,9.1 信道编码的基本概念,两种简单的信道编码(n,n-1)奇偶校验码（以(4,3)偶校验为例）最后一位为校验位（例）偶校验：码字中1的个数为偶数；奇校验：码字中1的个数为奇数最小码距为2只能用于检错：只能检奇数个错误，无法检偶数个错误,9.1 信道编码的基本概念,两种简单的信道编码(n,1)重复码编码效率1/n，dmin=n随着n的增大，检错、纠错能力越来越强，但编码效率越来越低(n,n-1)奇偶校验码编码效率1-1/n，dmin=2随着n的增大，编码效率越来越高，但只能检奇数个错误,9.1 信道编码的基本概念,有限域定义：一个有限个元素的集合，进行规定的代数四则运算后，结果仍是属于该集合的元素（自封闭性）。GF(2)：集合0,1对规定的模二和“”及点乘“”运算是自封闭的，所以是一个有限域，称之为二元域,9.1 信道编码的基本概念,有限域GF(2k)：以0,1中的元素构成的所有长度为k的序列所组成的集合，对规定的模二和“”及点乘“”运算也是自封闭的。,9.2 线性分组码,定义分组：将k个信息位作为一组进行编码，变换成长度为n（nk）的二进制码组线性：信息码元与监督码元的约束关系是一组线性代数方程。记为（n，k）码，编码效率=k/n，冗余度为1-=1-k/n,9.2 线性分组码,数学定义分组：线性：线性编码f就是从矢量空间GF(2k)到另一个矢量空间GF(2n)的一组线性变换。它可以用线性代数中的有限维矩阵来表示。,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位，可产生2n个错误图样；而校正子S是(n-k)维矢量，只有2n-k种组合的校正式；这样对每一种校正式，都有2k个错误图样与之对应,9.2 线性分组码,二进制对称信道（BSC）下的译码在输入信息0、1等概的情况下，二进制对称信道下的最优译码准则等效为最小汉明距离准则在译码时，得到伴随式S后，应该选择与S对应的2k个可能的错误图样中重量最小的进行译码若收到的码字为Y，得到的伴随式为S，若S对应的码重最小的错误图样是E，那么译码输出就是C=YE,9.2 线性分组码,利用监督矩阵进行译码例,9.2 线性分组码,利用监督矩阵进行译码若接收码字中只有一个码元出现差错，比如yi出错，则校正子S等于监督矩阵第i列。比较(7,4)码的监督矩阵和码重最小的E,9.2 线性分组码,汉明码汉明码是一种能纠正一位错码的线性分组码主要参数：码长n=2m-1信息位k=2m-1-m监督位n-k=m最小码距dmin=3，纠错能力t=1码效率R=k/n=1-m/n=1-m/(2m-1)当n很大时，R趋近于1，所以汉明码是一类高效率的纠错码。,9.2 线性分组码,汉明码当m=3时，n=7，k=4。之前的(7,4)码就是汉明码。特点：监督矩阵中的n=2m-1列正好是m位码元的2m种组合中除全0组合外的其它组合，且每种组合出现一次。每种组合对应该列对应的码元出现传输错误时的校正子。,9.2 线性分组码,汉明码的译码电路利用最小码重错误图样进行译码的电路实现（图）利用校正子与错码位置的对应关系，也可以使用地址译码器来帮助实现译码,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位后的码字ci和码多项式ci(x),9.3 循环码,循环移位特性的多项式描述c的码字多项式c(x)乘以xi,9.3 循环码,循环移位特性的多项式描述上面的表达式说明码字循环移位i位后的多项式ci(x)在模xn+1的运算下与xic(x)是相同的在循环码的研究中可以用xic(x)代替ci(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)=x4+x2+x+1，g=(0010111),9.3 循环码,循环码的生成矩阵非系统循环码变换为系统循环码也可以用矩阵变换的办法，但只能用简单行变换，不能用列的交换,9.3 循环码,循环码的生成多项式g(x)为n-k次多项式，则xkg(x)为n次多项式c(x)为许用码组，所以必是g(x)的倍数生成多项式g(x)必是xn+1的因式，为寻找生成多项式指出了方法,9.3 循环码,循环码的生成多项式举例：寻找(7,3)循环码的生成多项式g(x)，其次数为n-k=4,9.3 循环码,循环码的生成多项式对任意n，有：若取x+1为生成多项式，构成的循环码是简单的偶监督码(n,n-1)。最小码距dmin=2若用xn-1+xn-2+x+1为生成多项式，构成的(n,1)循环码信息位个数为1，校验码个数为n-1。容易知道实际就是重复码。,9.3 循环码,循环码的生成多项式(7,k)循环码,9.3 循环码,循环码的监督多项式循环码的生成多项式g(x)是xn+1的因式h(x)称为此循环码的监督多项式举例，(7,3)循环码,9.3 循环码,循环码的监督矩阵,9.3 循环码,循环码的监督矩阵由上面的式子，可知循环码的监督矩阵可表示为容易验证，由g(x)移位得到的生成矩阵与上面的监督矩阵相乘得到0阵,9.3 循环码,循环码的监督矩阵举例：(7,3)循环码，g(x)=x4+x2+x+1，h(x)=x3+x+1,9.3 循环码,循环码的监督矩阵系统循环码的监督矩阵例:(7,3)系统循环码,9.3 循环码,系统循环码的编码器系统循环码的编码方式是将信息码多项式升n-k次幂后除以生成多项式，然后将所得余式置于升幂后的信息多项式之后,9.3 循环码,系统循环码的编码器举例：(7,4)系统循环码的生成多项式为g(x)=x3+x+1，输入信息多项式为u(x)=x3+1,9.3 循环码,系统循环码的编码器多项式除法电路可以用带反馈的线性移位寄存器来实现（图）与采用手算进行多项式长除运算的过程类似用除法电路进行系统码的编码的过程（表）（板书）,9.3 循环码,系统循环码的译码器校正子,9.3 循环码,系统循环码的译码器校正子与错误图样的关系,9.3 循环码,系统循环码的译码器校正子的一个重要性质：一码组移位i次后的码组的校正子等于原码组的校正子在除法电路中移位i次的结果,9.3 循环码,系统循环码的译码器举例：(7,4)系统循环码的生成多项式为g(x)=x3+x+1,9.3 循环码,系统循环码的译码器上面的性质使得译码器需要识别的错误图样的数目大大减小（如果某(n,k)码可纠正m个错误，则识别错误图样数目由 减为）；(7,4)码的识别数由7减为1。,9.3 循环码,系统循环码的译码器译码器电路（图）译码过程（板书）一次译码需要2n个节拍才能完成。所以真正的译码电路需要两个除法电路（图）,9.3 循环码,码字的扩展与收缩：可增加信息位、校验位来增加码字长度，减少信息位、校验位来减少码字长度（图）,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的检错能力错误图样总个数:2k+r无法检出的错误图样个数:2k-1无法检出的错误图样的比例:(2k-1)/2k+r=1/2r,9.4 BCH码,BCH码由Bose，Chaudhuri和Hocquenghem发现属于循环码纠错能力强，能纠正多个随机错误构造方便（我们不从理论上研究BCH码的性质，只学习如何使用BCH码）,9.4 BCH码,BCH码的构造其生成多项式为t为纠错个数，mi(x)为最小多项式，LCM表示取最小公倍式其能纠正t个随机差错，最小码距,9.4 BCH码,本原BCH码码长非本原BCH码码长n为2m-1的因子,9.4 BCH码,最小多项式表（表）阶数m表示码长n=2m-1中的m十进制数字表示mi(x)中的i最小多项式用8进制数表示，如最小多项式后的字母意义：ABCD表示非本原多项式，EFGH表示本原多项式,9.4 BCH码,BCH码构造举例例：码长15的BCH码，能纠正3个错误,9.4 BCH码,表（本原BCH码）表（非本原BCH码）（学会根据需要查找）,9.4 BCH码,Golay码(23,12)非本原BCH码，生成多项式为码距为7，能纠正3个随机错误是GF(2)上纠多个随机差错的唯一一个完备码，监督码元得到了最充分的利用,9.4 BCH码,RS（Reed-Solomon，里德-所罗门）码一种非二进制BCH码，编码的单位是符号；一个符号由m个二进制码元组成，即为2m进制纠正t个符号错误的RS码的参数：码长n=2m-1个符号（即m(2m-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个输出端（kn），K-1节移位寄存器（共需k(K-1)个寄存器单元）。称为(n,k,K)卷积码通常称K为约束长度（一般来说，约束长度越大，则码字纠错性能越好）码的效率：k/n编码前，k(K-1)个寄存器单元全部复位清零,9.5 卷积码,卷积码与分组码的区别编码：分组码的当前的一组输出（n个码元）只与当前的一组输入（k个输入信息位）有关（无记忆性）；而卷积码的当前的一组输出（n个码元）不仅与当前的一组输入（k个输入信息位）有关，还与前面的K-1组输入（k(K-1)个输入信息位）有关（记忆性）。即卷积码的当前一组输出（n个码元）共与kK个输入信息位有关,9.5 卷积码,卷积码与分组码的区别性能：在编码结构相当的情况下，卷积码的性能优于分组码，因而是作为前向纠错码的好的选择之一。研究成熟度：分组码有好的代数工具，研究比较成熟透彻；卷积码没有好的代数工具，研究不是很透彻。,9.5 卷积码,卷积码的表示方法图形表示法状态图法树图法格图法解析表示法离散卷积法生成矩阵法码多项式法,9.5 卷积码,状态图状态：k(K-1)个寄存器单元中存储的数据表示状态（共有2k(K-1)种状态）卷积编码是个Markov链：当前输出和下一步的状态决定于当前的状态和当前输入k位输入：输入的可能组合有2k种状态转移：对每一种状态，均有2k种状态转移方式（对应2k种输入和输出）,9.5 卷积码,状态图举例：(2,1,3)卷积码,9.5 卷积码,状态图举例：(2,1,3)卷积码,9.5 卷积码,树图状态图的缺点：时序关系不清晰，整个编码过程看不清楚卷积码的树图就是将编码过程的所有的状态转移的可能性用树的方式表示一个节点表示一个状态（节点级数l表示经过了l个输入，树根总是全零状态）；一个分支表示当有一种输入时从一个节点到下一级某个节点的状态转移,9.5 卷积码,树图举例：(2,1,3)卷积码,9.5 卷积码,格图树图缺点：当级数lK-1后，树图中的2k(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 卷积码,码多项式法将输入序列、生成序列和输出序列分别用码多项式表示，容易验证，输出码多项式等于输入码多项式和生成序列码多项式的乘积,9.5 卷积码,码多项式法举例：(2,1,4)卷积码（图）,9.5 卷积码,生成矩阵法：以(2,1,4)卷积码为例推导,9.5 卷积码,生成矩阵法：以(2,1,4)卷积码为例推导,9.5 卷积码,生成矩阵法：推广到一般(n,k,K)卷积码(n,k,K)卷积码的生成序列一般表示式为其中gli,j表示每组k个输入比特中第i个比特经延迟l后的输出与每组n个输出比特中第j个比特的模2和器件的输入端的连接关系；为1表示有连接，为0表示没有连接,9.5 卷积码,生成矩阵法：推广到一般(n,k,K)卷积码生成矩阵为,9.5 卷积码,生成矩阵法：推广到一般(n,k,K)卷积码举例：(3,2,2)卷积码（图）,9.5 卷积码,生成矩阵法：推广到一般(n,k,K)卷积码举例：(3,2,2)卷积码（图）,9.5 卷积码,卷积码的译码方法代数译码：根据卷积码的本身编码结构进行译码，译码时不考虑信道的统计特性 概率译码：这种译码在计算时要考虑信道的统计特性门限译码序贯译码维特比译码（最佳译码，最大似然译码）,9.5 卷积码,最大后验概率（MAP）译码,9.5 卷积码,最大似然（ML）译码若发送码字等概出现，MAP等价于ML,9.5 卷积码,最大似然（ML）译码对于无记忆信道称上式中的取对数部分为对数似然函数，简称似然函数（或度量值）,9.5 卷积码,编码信道硬输出：解调器将信号硬判决为0或1软输出：输出模拟量或经多电平量化的值,9.5 卷积码,举例（2PSK）V1(t)=s(t)+n(t)是软输出，或对其进行Q=2m2的多电平量化也是软输出V2(t)是硬输出，对V1(t)进行了硬判决,9.5 卷积码,维特比译码硬判决译码：对应于解调器的硬输出软判决译码：对应于解调器的软输出,9.5 卷积码,维特比硬判决译码对于二进制对称信道（BSC）,9.5 卷积码,维特比硬判决译码似然函数译码准则（因为P1/2）维特比硬判决译码准则等效为最小汉明距离准则,9.5 卷积码,维特比硬判决译码若节数为n，则编码路径总共约有2n条，有必要求出所有路径的似然函数（汉明距离）吗？,Example-Principle of Optimality,EE Bld,FacultyClub,N,N,S,S,.5,.8,.7,.5,1.2,.8,.2,.3,.5,.8,1.2,1.0,1.3,Professor X chooses an optimum path on his trip to lunch,Optimal:6 addsBrute force:8 adds,N bridgesOptimal:4(N+1)addsBrute force:(N-1)2N adds,Find optimal path to each bridge,9.5 卷积码,维特比硬判决译码（幸存路径）,00,00,10,State i,State i-1,4,2,0,1,3,Search previous states,9.5 卷积码,维特比硬判决译码（幸存路径举例）,shortest path-Hamming distance to s2,9.5 卷积码,维特比硬判决译码（最小汉明距离路径）,First step,Trace though successive states,s0,s1,s2,s3,9.5 卷积码,维特比硬判决译码（最小汉明距离路径：举例）,y：11 01 01 10 01,9.5 卷积码,维特比硬判决译码（收尾）一般来讲，不收尾也可以译码，但缺点是最后会有多条幸存路径，最后几个比特可能出现错误编码时加入确定的收尾比特，使得使得最后的状态是确定的状态（一般是全零状态），这样最后只有一条幸存路径，它对应的就是译码序列对于k=1，只需要在编码时加入m个尾比特0就可以使最后状态回到全零状态,9.5 卷积码,维特比硬判决译码（收尾：举例）,9.5 卷积码,维特比硬判决译码（总结）对每个状态需存储两种信息：幸存路径的度量值（硬判决译码中是汉明距离）和对应的译码序列ACS：对第i+1节的每个节点（状态），对从第i节的所有节点中可能进入该节点的2k条路径作度量值的累加；比较这些度量值；选择度量值最大（汉明距离最小）的路径为幸存路径；更新存储信息。,9.5 卷积码,维特比硬判决译码（总结：过程）初始化：对第0节节点存储信息初始化（全零状态汉明距离为0，其他状态汉明距离为无穷大。因为全零状态是确定的初始状态）ACS的循环操作：以第0节存储信息为基础进行ACS得到到达第1节各节点的幸存路径并更新各状态的存储信息；重复直到最后译码输出：最后确定状态（全零状态）存储的译码序列即为最终的译码输出,9.5 卷积码,维特比截短译码（传统方法的缺点）要全部接收数据进入译码器并进行完全部运算后才可以输出译码结果，因而时延（编码长度n）很大需要存储所有状态的全部历史数据，信息存储量大（译码序列：n2km）,9.5 卷积码,维特比截短译码（依据：汇聚特性）译码中，各状态的幸存路径的先前部分通常会汇聚为一条（图）,所有路径汇聚,9.5 卷积码,维特比截短译码在第i时刻，可以将i-L时刻前的路径结果直接输出，而在存贮空间中不再保存i-L时刻前的译码序列内容（将其输出）。这里的L就被称做译码深度维特比截短译码不是传统的维特比译码（最大似然译码），其性能有所下降当L5m时，性能已经非常接近最大似然译码,9.5 卷积码,维特比截短译码（优点）时延降低：由n降为L存储量减小：译码序列存储量由n2km减为L2km,9.5 卷积码,维特比软判决译码（直接输出：2PSK）直接以V1(l)作为软输出yl其中cl=0,1,9.5 卷积码,维特比软判决译码（直接输出：2PSK）求最大似然函数等价于求最小欧氏距离若去掉公有项，则,9.5 卷积码,维特比软判决译码（多电平量化）以V1(l)经多电平量化后的值作为软输出yl2PSK：将 作为度量值，或将其加上一个常数使之恒为非负,9.5 卷积码,维特比软判决译码（多电平量化举例）c=(111,000,001,001,111,001,111,110)y=(101,100,001,011,110,110,111,110),9.5 卷积码,维特比软判决译码（总结）解调直接输出可以看作是多电平量化的一种译码过程与硬判决译码一样，唯一的区别是度量值不同也具有汇聚特性，可以使用维特比截短译码性能优于硬判决译码，增益有1.52.0dB3比特量化即基本足够,9.5 卷积码,卷积码的距离特性码的距离特性与纠错能力有密切关系分组码：最小距离dmin卷积码最小距离dmin：长度为nK的编码后序列之间的最小汉明距离（用于门限译码，不讨论）自由距离dfree：任意长度的编码后序列的最小汉明距离（用于维特比译码）分组码与卷积码的区别：卷积码没有固定的长度的码字,9.5 卷积码,卷积码的距离特性由卷积码的编码器结构，可知卷积码具有线性性质这样，卷积码的码序列之间的自由距离就等于非全零码序列的最小码重,9.5 卷积码,卷积码的距离特性（自由距离dfree）求自由距离dfree可以转化为求任意长非全零码序列的最小码重进一步转化：由于一条编码路径的码重在与全0路径汇聚以后不再增加（若在分离码重继续增加，显然不是最小码重），所以求dfree就是找到从全零状态出发后重新汇聚到全零状态的编码路径的最小码重求法：格图法（图）,9.5 卷积码,卷积码的距离特性(n,k,K)卷积码的构造方法有多种，通过求生成函数可以求得它们的自由距离（解析方法）随着k，K的增大，状态数目指数增加，求生成函数变得越来越复杂好码的寻找：通过计算机搜索,9.5 卷积码,卷积码的距离特性Heller给出的编码效率为1/n的卷积码（即(n,1,K)卷积码）的dfree的上界在上式的基础上，Daut等人给出了编码效率为k/n的卷积码的dfree的修正上界，以及搜索的相应号码的列表,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)分组交织收发时延：2MN,9.7 交织码,卷积交织框图（9.7.3）与分组交织相比：存储器数量减少一半；收发时延减少一半,9.7 交织码,伪随机交织分组交织和卷积交织的缺点：其读写规则不变（呈周期性），这样在特定情况下，会使周期的独立随机差错变成周期的突发差错伪随机交织的解决方法：码元序列顺序的打乱是伪随机的，即读写规则是变化的（没有周期性）,