分组码与卷积信道码

,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,分组码与卷积信道码读书报告,专业：通信与信息系统,学号：,0820080087,姓名：顾杰,第八章：分组码与卷积信道码,本章主要内容：,1,、线性分组码,2,、卷积码,3,、*带限信道的编码调制,-,网格编码调制,什么是线性分组码？,若编码规则仅局限在本码组之内，即本码组的校验元仅与本码组的信息元相关，则称这类码为分组码。,对于分组码，如果校验元和信息元的关系是一种线性关系，即能够用一线性代数方程表示，那么称这种分组码为线性分组码。,线性分组码的表示,线性分组码一般用符号,(n,k),表示，其中,n,为码字的长度，,k,为每个码字中信息码元的数目。,定义 为线性分组码的码率 ，即,线性分组码的基本特性,设 是某,(n,k),分组码的任意两个码字，这两个码字的差别是用对应元素上不相同元素的个数来衡量的，这种度量称为码字间的,Hamming,距离，记作 。个码字集合中的最小值称为该码的最小,Hamming,距离，用 表示。,定义一个码字中所有非零元素的个数为该码字的,Hamming,重量。线性分组码的最小,Hamming,距离等于最小,Hamming,重量。,线性分组码的生成矩阵和奇偶校验矩阵,在,(n,k),线性分组码中，假设 为编码器的输入信息码元序列，为编码器的输出序列，则编码器的输入输出关系可以表示为：,式中，,G,为该线性分组码的生成矩阵。,任何矩阵都可以表示成生成矩阵行向量的线性组合。生成矩阵可化成“系统形式”：,线性分组码的生成矩阵和奇偶校验矩阵,校验矩阵常用符号,H,表示，一种码的校验矩阵等于该码的对偶码的生成矩阵，因此对于,(n,k),线性分组码，它的校验矩阵,H,和生成矩阵,G,满足,这里的,0,代表一个由全零元素组成的 维矩阵。,假定,(n,k),线性分组码是系统码，则其校验矩阵可表示为：,式中,为,P,的转置矩阵。,几种特殊的线性分组码,H,amming,码,Hadamard,码,Golay,码,循环码,在线性分组码中，有一种重要的码称为循环码。它除了具有线性分组码的一般特点外，还具有循环性：循环码中任一码字的码元循环移位（左移或右移）后仍是该码的一个码字。其编码和译码的电路较简单，且检、纠错能力较强，目前已成为研究最深入、理论最成熟、应用最广泛的一类线性分组码。,循环码,理论研究时常用多项式来表示循环码，即有：,式中：为循环码的任一码字。对于二进制码，多项式的每个系数不是,0,就是,1,。,可以用一个,n-k,次的生成多项式 产生一个循环码。,(n,k),循环码的生成多项式一定是多项式 的因子，其通式为：,循环码,定义一个消息多项式 如下：,这里 代表,k,位信息比特。则由该,k,位信息比特生成的码字为：,可以证明上式满足循环特性。,BCH,是循环码中一种重要的码型，能够纠正多比特错误。,线性分组码的最佳软判决译码,线性分组码的最佳软判决译码是通过使用匹配率滤波器作为最佳接收机并后接一个译码器实现的，译码器用来生成与,M,种码字对应的,M,个判决变量。,令 表示发送任一指定码字后匹配滤波器的,n,个输出取样。假设信号采用,BPSK,传输，则当码字的第,j,比特是,1,时：,当码字的第,j,比特是,0,时：,其中 表示传输码字的一个比特所需的信号能量，变量 表示取样瞬间的高斯白噪声。,线性分组码的最佳软判决译码,根据已知的,M,中可能发送的码字和接收到 值，最佳译码器形成,M,个相关度：,式中：便是第,i,个码字第,j,个位置上的比特。最佳译码器选择相关度均值最大的码字作为译码输出。,最佳软判决译码的算法比较简单，但当码字数量很大时计算量就会变得无法接受，巨大的计算量降低了其在工程中适用度。,线性分组码的硬判决译码,针对软判决译码巨大的计算量，硬判决译码将模拟样值量化，然后用数字方式实现译码，这种方法的一种实现方式是最小距离译码，也称最大似然译码。,译码方案：来自解调器的与接收码字对应的,n,个比特被送往译码器，译码器将接收的码字和,M,种可能发送的码字进行比较，把与接收码字汉明距离最小的判决为译码码字。,线性分组码的硬判决译码,使用校验矩阵,H,是一种有效的硬判决译码方法。假定 是发送码字，,Y,是解调器输出的接收码字，一般,Y,可以表示为：,其中，,e,代表一个任意的二进制差错矢量，那么,式中，,(,n-k,),维矢量,S,叫做差错图案的伴随式。由于,S,H,Y,是可知的，所以最终可以求出发送码字 。,硬判决译码和软判决译码的性能比较,软判决译码和硬判决译码码字差错概率比较,软判决译码差错概率上边界：,硬判决译码差错概率精确值：,在 范围内，硬判决译码和软判决译码的码字差错概率性能约相差,2dB,，且软判决译码性能较好。,硬判决译码和软判决译码的性能比较,软判决译码和硬判决译码单位比特最小信噪比 比较,在码率 趋近于零的极限时，硬判决译码和软判决译码的信噪比 值相差约为,2dB,。随着码率的增大，两种译码技术的单位比特最小信噪比 差值越来越小，当 时，差值约为,1.5dB,。,卷积码的定义,线性码分为分组码和卷积码，卷积码又称连环码，由埃里亚斯于,1955,年首次提出。,若本码组的校验元不仅与本码组的信息元相关，而且还与本码组相邻的前几个码组的信息元相关，则称这类码为卷积码。,卷积码的表示,卷积码一般用符号 表示，称,m,为编码存贮，它表示输入信息子组在编码器中滞留的单元时间；称,m+1,为编码约束度，表示编码过程中相互约束的子码个数；称 为编码约束长度，表示编码过程中互相约束的码元个数。,卷积码的描述方法,解析表示法,1,、离散卷积法,2,、生成矩阵法,3,、码多项式法,图形表示法,1,、树图法,2,、网格图法,3,、状态图法,卷积码的树图表示,码率为,1/3,，,K=3,卷积码的树图,卷积码的网格图和状态图表示,110,110,110,110,011,011,011,010,010,010,101,101,101,001,001,001,001,a,b,c,d,a,b,c,d,000,000,000,000,000,111,111,111,111,111,100,100,100,a,b,c,d,000,111,101,110,010,011,100,001,码率为,1/3,，,K=3,卷积码的网格图,码率为,1/3,，,K=3,卷积码的状态图,卷积码的编码,编码输出,每次输入,k,比特,1,k,1,k,1,k,1,k,1,k,2,k,3,k,Nk,1,2,n,Nk,级,移存器,n,个模2,加法器,每输入,k,比特,旋转1周,卷积码编码器,卷积码的译码,卷积码有三种主要的译码方法：序列译码、门限译码和最大似然译码。,1957,年伍成克拉夫,(,Wozencraft,),提出了一种有效的译码方法，即序列译码。,1963,年梅西,(Massey),提出了一种性能稍差，但比较实用的门限译码方法。,1967,年维特比,(,Viterbi,),提出了最大似然译码法，它又称为维特比译码。门限译码是一种代数译码法，序列译码和维特比最大似然译码都是概率译码。,代数译码利用编码本身得代数结构进行解码，并不考虑信道的统计特性。比如门限译码，它以分组码理论为基础，其主要特点是算法简单，易于实现，但是它的误码性能要比概率译码差。它的译码方法是从线性码的监督子出发，找到一组特殊的能够检查信息位置是否发生错误的方程组，从而实现纠错译码。,概率译码的基本思想是：把已经接收到的序列与所有可能的发送序列相比较，选择其中汉明距离最小的一个序列作为发送序列。维特比译码是目前用得较多的一种译码方法。它是一种最大似然译码，其译码的复杂性均随,m,按指数增长。最大似然译码对存储器级数较小的卷积码很容易实现，被广泛地应用于现代通信中。随着大规模集成电路技术的发展，对存储器级数较大的卷积码也可以采用最大似然译码。目前维特比译码已经得到了广泛的应用。,卷积码的最佳译码,-,维特比算法,不像分组码那样有固定的长度,n,，卷积码基本是一个有限状态机，因此它的最佳译码器是一个最大似然序列估计器。卷积码的译码就是遍历网格图找出最可能的序列。根据解调器后的译码器执行软判决或硬判决，遍历网格图时所用的度量可以是,Hamming,距离，也可以是欧氏距离。,维特比译码算法的实现,基本原理,：,译码器将接收到的序列和所有可能的发送序列作比较，选择其中汉明距离最小的序列当作是现在的发送序列。,例：,假设卷积码为,(n,k,m)=(3,1,2)码,现在的发送信息位为1101,为了使移存器中的信息位全部移出，在信息位后面加入了3个“0”，即1101000,编码后的发送序列：111 110 010 100 001 011 000,接收序列：111,0,10,010,1,1,0 001 011 000(,红色为错码,),对于,(3,1,2)卷积码，发送序列的约束长度,，,所以首先需考察3个信息段，,即考察接收序列的前,3n=,9位“111 010,010,”。,维特比译码算法的实现,解码第1步,由网格图可见，沿路径每一级有4种状态,a,b,c,和,d,。每种状态只有两条路径可以到达。故4种状态共有8条到达路径。,比较网格图中的这8条路径和接收序列之间的汉明距离。例如，由出发点状态,a,经过3级路径后到达状态,a,的两条路径中上面一条为“000 000 000”。它和接收序列“111 010 010”的汉明距离等于5；下面一条为“111 001 011”,它和接收序列的汉明距离等于3。,110,110,110,110,011,011,011,010,010,010,101,101,101,001,001,001,001,a,b,c,d,a,b,c,d,000,000,000,000,000,111,111,111,111,111,100,100,100,维特比译码算法的实现,将这8个比较结果列表如下：,比较到达每个状态的两条路径的汉明距离，将距离小的一条路径保留，称为幸存路径。这样，就剩下4条路径了，即表中第2,4,6和8条路径。,是,4,111 110 101,abdd,8,否,6,000 111 110,aabd,7,是,1,111 110 010,abdc,6,否,7,000 111 001,aabc,5,是,4,111 001 100,abcb,4,否,6,000 000 111,aaab,3,是,3,111 001 011,abca,2,否,5,000 000 000,aaaa,1,幸存否？,汉明距离,对应序列,路径,序号,维特比译码算法的实现,解码第2步：继续考察接收序列中的后继3个比特“110”,计算4条幸存路径上增加1级后的8条可能路径的汉明距离。计算结果列于下表中。,表中总距离最小为2，其路径是abdc+b，相应序列为111 110 010 100。它和发送序列相同，故对应发送信息位1101。,否,6,2,dd,4,abdd+d,8,是,4,0,bd,4,abcb+d,7,是,5,1,dc,4,abdd+c,6,否,7,3,bc,4,abcb+c,5,是,2,1,cb,1,abdc+b,4,否,4,1,ab,3,abca+b,3,是,3,2,ca,1,abdc+a,2,否,5,2,aa,3,abca+a,1,幸存否？,总距离,新增距离,新增,路径段,原幸存路径的距离,路径,序号,维特比译码算法的实现,按照上表中的幸存路径画出的网格图示于下图中。,图中粗线路径是距汉明离最小,(,等于2,),的路径。,a,b,c,d,011,010,010,101,001,a,b,c,d,111,100,100,110,110,维特比译码算法的实现,在编码时，信息位后面加了3个“0”。若把这3个“0”仍然看作是信息位，则可以按照上述算法继续解码。这样得到的幸存路径网格图示于下图中。图中的粗线仍然是汉明距离最小的路径。,110,011,010,010,101,101,001,0