信息理论与编码-第六章-信道编码

第1章：概述,第2章：信源熵,第3章：信道容量,第4章：信息率失真函数,第5章：信源编码,第6章：信道编码,第7章：密码体制的安全性测度,6.1信道编码的概念6.2线形分组码6.3循环码6.4卷积码,6.1.1信道编码的作用和分类6.1.2：编码信道6.1.3：检错和纠错原理6.1.4：检错和纠错方式和能力,信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号线路编码如何避免少量差错信号对信息内容的影响纠错编码,广义信道编码=特定信道上传输信息而进行的传输信号或信号格式的设计与实现,描述编码用于对特定数据信号的描述约束编码用于对特定信号特性的约束扩频编码用于扩展信号频谱为近似白噪声谱并满足某些相关特性纠错编码用于检测与纠正信号传输过程中因噪声干扰导致的差错,1,2,3,4,6.1.1：信道编码的作用和分类6.1.3编码信道6.1.3：检错和纠错原理6.1.4：检错和纠错方式和能力,消息,编码信道模型,n-1,当码字C和接受向量R均由二元序列表时，称编码信道为二进制信道C=(c0,c1,cn-1)如果对于任意的n都有：P(r/c)=p(ri/ci)则称此二进制信道为无记忆二进制信道。p(0/1)=p(1/0)=p0则称此信道为无记忆二进制对称信道BSC,i=0,BSC输入输出关系等效为,差错图案：随机序列或，,第位上的一个随机错误：,长的突发错误：第至第位之间有很多错误,对于一个BSC信道总有转移概率1/2，比特传输中发生差错数目越少，概率越大，即,从而总认为发生差错的图案是差错数目较少的图案,二元软判决信道,用多个比特（理想情况下为实数）表示每一个无记忆编码信道的二元符号输出,信道干扰z为零均值正态分布的随机变量，噪声干扰功率为均方差，z的概率分布为。对于BPSK调制，二元输入符号为二元符号取值为+1或-1,6.1.1：信道编码的作用和分类6.1.2：编码信道6.1.3检错和纠错原理6.1.4：检错和纠错方式和能力,检纠错是根据信道输出序列自身判断是否可能是发送的，或纠正导致不等于的错误。冗余编码：码字的长度一定大于消息的长度,编码码率：每个码字的序列符号（或码元）平均传送的消息比特数,偶（或奇）校验方法：实现检纠错目的的一个基本方法。,一个偶校验位是对消息使得如下校验方程成立的二进制符号，即,一个偶校验码码字,一个码率为的偶校验码，所有可能的的全体,校验方程为1表明一定有奇数个差错，校验方程为0表明可能有偶数个差错,m0+m1+m2+mk1+p=0（mod2）称c=(m0,m1,m2mk-1,p)为一个偶校验字确定校验位P的编码方程为：P=m0+m1+mk-1,编码可以产生多个奇偶校验位，即一个校验位可以由消息位的部分或全部按某种校验方程产生，例如对阵列消息进行垂直与水平校验以及总校验的码字和其码率分别为,重复消息位：实现检纠错目的第二个基本方法,一个重复码是一个码率为的码，仅有两个码字和，传送1比特（）消息。,重复码可以检测出任意小于个差错的错误图案，纠正任意小于个差错的错误图案。,纠1位差错的3重复码,等重码或定比码：实现检纠错的第三个方法。,设计码字重量恒为常数，即,例如一种用于表示0至9数字的5中取3等重码如表（6.1.1）所示，其码率为,5中取3等重码,5中取3等重码可以检测出全部奇数位差错，对某些码字的传输则可以检测出部分偶数位差错,6.1.1：信道编码的作用和分类6.1.2：编码信道6.1.3：检错和纠错原理6.1.4检错和纠错方式和能力,纠错码的应用方式：前向纠错方式（FEC），自动请求重发（ARQ）方式，混合纠错（HEC）方式以及信息反馈（IRQ方式）,FEC与ARQ纠错应用方式,常用汉明距离来描述检纠差错的数目，对于两n长向量u，v汉明距离为：,最小汉明距离（最小码距d）：任意两码字之间的汉明距离的最小值,定理对一个最小距离为纠错码，如下三个结论仅有其中任意一个结论成立，,（1）可以检测出任意小于等于个差错；,（2）可以纠正任意小于等于个差错；,（3）可以检测出任意小于等于l同时纠正小于等于t个差错，其中l和t满足,最小码距与检纠错能力,差错概率：通信作为一个统计过程时，纠检错能力的统计特性。,FEC方式纠错码的码字差错概率,：发送码字的先验概率,：码字数，对于充分随机的消息源,对BSC信道,最大化等价于最小化，最小差错概率译码等价为使接收向量与输出码字距离最小的最小距离译码，即,信息比特信噪比：传输一个比特信息所需的最小信噪比,比特差错概率（又称误码率）与信噪比的关系如下图所示，采用纠错码后，达到同样比特差错概率实际需要的信噪比减小量称为编码增益。,编码增益,6.2线性码,6.2.1线性分组码的描述,6.2.2线性分组码的译码,6.2.3码例与码的重构,6.2.1线性分组码的描述6.2.2线性分组码的译码6.2.3码例与码的重构,一个（n,k）线形分组码C是称为码字c的n维向量的集合C=c|c=mG其中m为任意的k维向量并称为消息向量。G是k行n行列秩为k（nk）的矩阵并称为生成矩阵，,对于二元编码，和是二元向量，是一个二元矩阵，向量与矩阵，矩阵与矩阵之间的基本运算是模二加和模二乘运算。,表6.2.1模二加/乘法表,例6.2.13重复码是一个（3，1）线性分组码,例6.2.2（4，3）偶校验码是一个（4，3）线性分组码,当生成矩阵给定时线性分组码有如下性质：（1）零向量一定是一个码字，称为零码字；（2）任意两码字的和仍是一个码字；（3）任意码字是的行向量的线性组合；（4）线性分组码的最小距离等于最小非零码字重量。,由偶校验码的检错概念，可以通过计算接收向量的所有校验方程值是否为0来判断传输是否可能有错，那么必有一个矩阵满足,显然的每一列或的每一行确定了一个可能的分组码的校验方程，的线性不相关行数最少要等于该码的所有可能的校验方程数，称这样的矩阵为线性分组码的一致校验矩阵。,由的每一行都是一个码字有,由现行空间的理论，当H的行秩为r时，H作为一个(n,k)线性分组码的生成矩阵所生成的码是与G对应空间正交的r维线性子空间，称为(n,k)线性分组码的对偶码或对偶空间，并且有如下的维数关系成立,T,定理：任何满足下式的n维向量a均是一（n,k）线形分组码的码字aH=其中满足公式的H矩阵形式不唯一，但一个码的对偶码是惟一的。,T,系统码：生成矩阵具有如下形式,在码字集合不变的情况下，任何一个线性分组码都可以一对一的去对应一个系统码。,对于系统码相应的一致校验矩阵,注意与仍然满足。,以线性分组码的一致校验矩阵为生成产生的线性分组码称为原线性分组码的对偶码。,例6.2.3一个（5，3）线性分组码的,其中到的行初等变换过程为（表示第i行），,（5，3）线性分组码码例,由一致校验矩阵可以比较容易确定线性分组码的最小码距,定理线性分组码的最小码距为，当且仅当其一致校验矩阵H中任意列线性无关，某列线性相关。,该定理实际给出了计算线性分组码最小码距的一种方法。,6.2.1线性分组码的描述6.2.2线性分组码的译码6.2.3码例与码的重构,译码的概念,检错译码：译码器输出为当前接收向量r和r是否有差错的标志s，即。,纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。,纠错译码的译码成功状态：译码器能够在达到译码码字差错概率最小条件下输出一个确切的码字，即。,纠错译码的译码失败状态：译码器不能输出一个确切的码字，通常此时的输出y与检错译码输出相同。,定义：,(n,k）线形分组码的伴随式是一个r(r=n-k)维向量s,，则传输中一定有错误发生,，则传输中要么无差错发生，要么差错图案恰好为一个码字。,定理可纠t错的q元线性分组码满足,伴随式纠错译码的通用译码方法,（1）按最可能出现的个差错图案，计算相应的伴随式，并构造伴随式差错图案表；（2）对接收向量计算伴随式；（3）查表得；（4）纠错计算。,6.2.1线性分组码的描述6.2.2线性分组码的译码6.2.3码例与码的重构,常见的线形分组码有重复码，汉明码，里德-穆勒码，戈雷码（1）汉明码：,二元Hamming码是一种的完备码，满足,其中列向量为全部可能的非零元组。,Hamming码的对偶码是一个线性分组码，称为最大长度码，由于所有非零码字的重量均为，又称为等距码或单形（simplex）码。,例6.2.4一个二元（7，4）Hamming码的系统码形式的矩阵和校验矩阵分别为,等价的编码方程为,伴随式计算方程,（2）Hadamard码,Hadamard码是由Hadamard矩阵派生出的一种纠错码。,阶实Hadamard矩阵由元素为+1，-1的矩阵递归定义为,例如,Hadamard矩阵为正交矩阵，即中的任意不同两行（列）的点积为0，即,超正交矩阵：Hadamard矩阵中的第1列（全+1列）去掉后由于任两行的点积为-1。,将Hadamard矩阵元素+1/-1映射为0/1，则Hadamard矩阵映射后的行向量为一个二元向量，以这些二元向量的部份或全体就构成标准0/1二元意义上的分组码，并称为Hadamard码。具体的Hadamard码的选择构成有正交码、双正交码和超正交码三种形式。,（A）正交码：以的全部行向量的0/1映射向量为码字。,（B）双正交码：以和-的全部行向量的0/1映射向量为码字。,（C）超正交码：以的全部行向量的0/1映射向量为码字。,可以证明正交码、双正交码和超正交码均是线性分组码。,例6.2.5（7，3）超正交码的超正交矩阵和生成矩阵G分别为,(3)里德-穆勒（Reed-Muller）,阶码是一种线性分组码，满足,例6.2.6的阶RM码的各个子矩阵有,码的对偶码仍是一个Reed-Muller码，为码。,（4）戈雷码二元戈雷码是一种就纠3个错的完备线形分组码，满足：n=23k=12,由于,因此某种二元（23,12）码一定可以纠正任意小于等于3个差错，所以,6.3循环码,6.3.1循环码的多项式描述,6.3.2循环码的生成矩阵,6.3.4多项式运算电路,6.3.3系统循环码,6.3.5循环码的编码电路,6.3.6循环码的伴随多项式与检测,6.3.7BCH码与RS码,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,更好的设计和实现线性分组码的方法是引入特定的数学结构来界定某一类线性分组码。循环码即是采用循环移位特性界定的一类线性分组码。,6.3.1循环码的多项式描述,定义如果一个线性分组码的任意一个码字c(n元组)都是另外一个码字c的循环移位,称此线性分组码为一个循环码.,将循环码的码字用多项式c(x)，称为码多项式（简称码式）表示后，循环码集合表示C(x),例6.3.2如下确定的CA是线性循环码，CB是非循环的线性分组码，CC是非线性的循环码。,，,定理：（n,k）循环码C(x)中存在唯一的一个非零的，首一的和最低次为r（rn）的码多项式g(x)满足：g(x)=xr+gr-1xr-1+.+g1X+g0g00r=n-k并且c(x)是码式当且仅当c(x)是g(x)的倍式,定义由上述定理确定的码式g(x)称为循环码(n,k)的生成多项式.,因此(n,k)循环码的构造是如何构造生成多项式g(x)。,循环码由生成多项式的倍式组成,定理：g(x)是（n,k）循环码的生成多项式，当且仅当g(x)是xn-1的r=n-k次因式。,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,6.3.2循环码的生成矩阵和校验矩阵,(n,k)循环码的生成矩阵为,(n,k)循环码的校验矩阵为,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,6.3.3系统循环码,循环码的系统码码式为,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,6.3.4多项式运算电路,因为多项式,表示时间序列,所以多项式的计算表现为对时间序列的操作.,多项式a(x)与b(x相加电路,a(x)与g(x)的一般乘法电路,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,非循环码编码器根据多项式乘法电路和循环码码式是生多项式倍式原理，多项式乘法电路(图6.3.4)是循环码的非系统码电路，又称为循环码乘法编码电路,图6.3.4,2.系统编码电路循环码系统编码电路由乘法电路，求余式电路以及加法开关电路组成,如图6.3.14所示,电路工作过程如表6.3.2所示.,图6.3.14,表6.3.2循环码系统码编码电路工作过程,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,循环码的译码分成检错译码与纠错译码两类.,1.检错译码原理,2.纠错译码循环码的纠错译码要达到码的最小距离依赖于具体的循环码的结构.,6.3.1循环码的多项式描述6.3.2循环码的生成矩阵6.3.3系统循环码6.3.4多项式运算电路6.3.5循环码的编码电路6.3.6循环码的伴随多项式与检测6.3.7BCH码与RS码,BCH码是一类能够先确定纠错能力t，然后设计码长和生成多项式的码。对于任意的整数m和可达到纠错数t，都可以构造出一个设计距离为d0的二元本原BCH码满足：n=2m-1,r=n-kmt,dmind0=2t+1,RS码是多元BCH码的一个子类，码字向量的每个分量可以表示为m比特，其基本参数为：码长：n=2m-1(符号)=m(2m-1)（比特）校验位长：r=n-k=2t(符号)=m2t其中t为RS码可以纠正的差错符号数.,6.4卷积码,6.4.2卷积码的多项式描述,6.4.3卷积码的状态转移图与格描述,6.4.4维特比（Viterbi）译码算法,6.4.1卷积码的矩阵描述,6.4.1卷积码的矩阵描述6.4.2卷积码的多项式描述6.4.3卷积码的状态转移图与格描述6.4.4维特比（Viterbi）译码算法,卷积码编码：,二元线性卷积码：,是仅由模二加运算组成的布尔函数,卷积编码的离散卷积表达式,卷积码的记忆长度（段）：,线性卷积码的矩阵（或向量）描述：,序列为,6.4.1卷积码的矩阵描述6.4.2卷积码的多项式描述6.4.3卷积码的状态转移图与格描述6.4.4维特比（Viterbi）译码算法,6.4.2卷积码的多项式描述,消息段序列的多项式表示,编码输出段序列的多项式表示,定理线性,卷积码的多项式生成矩阵,对,满足,的,幂次项系数等于,生成序列,的第,个分量，,1,即,的最大次数等于卷积码的记,忆长度,，即,2,例6.4.5前述例（2,1,2）卷积码重画如图,6.4.1卷积码的矩阵描述6.4.2卷积码的多项式描述6.4.3卷积码的状态转移图与格描述6.4.4维特比（Viterbi）译码算法,卷积码与分组码的明显区别是卷积码编码器要存储m段信息，这些信息数据既要因新的输入而改变，又要影响当前的编码输出，因此称存储表达这些数据的参量为卷积编码器的内部状态，简称状态。,状态：既要因新的输入而改变，又要,影响当前的编码输出的数据。,卷积编码器有效的存贮单元数为,其中,为每个输入移位寄存器的,有效级数（寄存单元数）。因此二元卷积,码的状态变量记为状态向量,或简记为,状态数：二元,卷积码共有,个不同的状态，记为,状态转移：当状态为,（或,）时，,输入段,（或,）产生编码输出段,（或,），并使该,状态改变（称为,转移）到新的状态,（或,）。,状态转移方程：,与,的关系,输出方程：,与,的关系,尽管卷积码有,个状态，但是由于每段,的输入为,比特只有,种状态的变,化，每个状态只转移到,个状态的某个,子集（,个状态）中去，每个状态,也只能由某,个状态的状态子集转移,而来。,例6.4.10,状态转移图（闭合形）,状态转移图（开放形）,状态转移方程和输出方程分别为,卷积编码器工作过程：,*卷积编码器工作初态为（全0状态）,*消息段序列产生输出段序列,*消息段序列产生状态序列,栅格图或篱笆图：开放形的状态转移图按时间顺序级联,编码路径：状态序列在栅格图中形成一条有向路径,一个卷积码码字：有向路径始于全0状态，又终于时的一条有向路径,对于的卷积码，常用实线表示时输入产生的转移分支，用虚线表示时输入产生的转移分支,例6.4.13前述例6.4.1（2，1，2）码的栅格图及几条路径例,路径A消息A（100）输出A（111011）路径B消息B（10110）输出B（1110000101）路径C消息C（110100）输出C（1101100111）,（1）卷积码的一个分支或转移是栅格图（或状态图）中接续状态的容许连接。（2）卷积码的一条路径是可容许连接的分支串。（3）卷积码的码字是始于零状态并首次终于零状态的路径。,结论,6.4.1卷积码的矩阵描述6.4.2卷积码的多项式描