信道编码原理课件.ppt

《信道编码原理课件.ppt》由会员分享，可在线阅读，更多相关《信道编码原理课件.ppt（71页珍藏版）》请在三一办公上搜索。

1、第5章信道编码原理,5.1信道及其数学模型 5.2信道编码的基本概念 5.3译码准则 5.4编码原则 5.5抗干扰信道编码定理及逆定理,5.1信道及其数学模型,有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器。,不研究信号在信道中传输的物理过程，并假定信道的传输特性是已知的，将信道用其输入/输出的统计关系模型来描述，信道的分类方法有：,5.1.1信道分类,（1）按输入输出信号在幅度和时间上的取值分：数字信道

2、或离散信道、模拟信道或波形信道和连续信道。（2）按输入/输出之间关系的记忆性分,可分为无记忆信道和有记忆信道（3）按输入/输出信号之间的关系是否是确定分，可分为有噪声信道和无噪声信道。,基本离散信道允许输入r(任意正整数)种不同的离散符号ai(i1，2，r)，其相应的输出为s(任意正整数)种不同的离散符号bj(j1，2，s)。如图所示。,5.1.2信道数学模型,1.基本离散信道,输入符号集X=a1,a2,ar，输出符号集Y=b1,b2,bs 条件概率p(bj|ai)(i=1,2,r;j=1,2,s)为信道的传递概率注：符号集X和Y之间可完全相同、部分相同或完全不同。符号种数r和s可相等，也可不

3、等。,要完整描述信道的传递特性必须测定rs个条件概率，并将rs个条件概率排列成一个rs阶矩阵,基本离散信道的信道矩阵,(i=1,2,r)。,式中：,注：（1）p(bj|ai)=0时，表示在输入符号为ai(i1，2，r)的前提下，信道不可能输出bj(j1，2，s)；（2）p(bj|ai)1时，表示在输入符号为ai(i1，2，r)的前提下，信道输出bj(j1，2，s)是一个确定事 件。（3）由于噪声的随机干扰使得在信道输入某符号ai(i1，2，r)的前提下，信道输出哪一种符号虽然是不确 定的，但一定是信道输出符号集Y=b1,b2,bs中的 某一种符号。,【例51】二元对称信道简记为BSC(Bina

4、rySymmetricChannel)，其输入/输出符号均取值于0，1，若r=s=2，且a1=b1=0，a2=b2=1，有转移概率,则BSC的信道转移概率矩阵P为,0 1,二元对称信道转移图如图52所示。可见，这些转移概率满足,图52二元对称信道转移图,【例52】二元删除信道简记为BEC(BinaryErasureChannel)，它的输入X取值于0，1，输出符号Y取值于0，2，1，因r=2，s=3，则信道转移矩阵为,0 2 1,信道转移图如图所示,设基本离散信道的输入符号集为X=a1,a2,ar，输出符号集为Y=b1,b2,bs，传递概率为p(Y|X)=p(bj|ai)；又设多符号离散平稳信

5、源X=X1X2XN其每一时刻的随机变量Xk(k=1,2,N)均取自信道的输入符号集X=a1,a2,ar,可知信源X=XX2Xn共有rN种不同的消息，某一具体的消息可表示为,（53）,式中：ai1,ai2,aiNX=a1,a2,ar；i1，i2，iN=1，2，r(i=1,2,rN)。,2.离散无记忆扩展信道,基本离散信道的N次扩展信道：,图54N次扩展信道,输出的随机变量序列Y=Y1Y2YN共有sN种不同的消息，其中某一具体的消息可表示为,式中：,j1，j2，jN=1，2，s(j=1,2,sN)。,基本离散信道的N次扩展信道：（1）从整个传递作用的效果来看，信道的输入是X=X1X2XN，输出是Y

6、=Y1Y2YN。（2）与基本离散信道相比，N次扩展信道的输入符号数由r种扩展为rN种,输出符号数由s种扩展为sN种。,N次扩展信道的传递矩阵,式中：,(i=1,2,rN)。,离散无记忆信道的N次扩展信道,即,【例53】已知某二进制对称离散无记忆信道。设信道的输入符号集为X=0,1，输出符号集为Y=0,1，信道的矩阵为,其中：，求此离散无记忆信道的二次扩展信道的信道矩阵。,解：二次扩展信道的信道矩阵为,注：离散无记忆信道的二次扩展信道同样也是对称信道。,5.2信道编码的基本概念,信息传输的有效性与可靠性是辨证统一的，信道编码的主要目的就是改善传输系统的质量，从而达到传输既有效、又可靠的目的。,5

7、.2.1基本概念,1）差错类型 1独立随机差错:在无记忆信道中出现，数据流中发生的错误彼此无关。2突发错误:在有记忆信道中，数据流中一个错误的发生,带来一连 串错误的发生。3混合差错,2）信道编码分类：纠独立随机差错码、纠突发差错码和纠混合差错码。3）信道编码的基本思路：根据一定的规律在待发送的信息码中加入一些多余的码元，以保证传输过程的可靠性。其任务就是构造出以最小多余度代价换取最大抗干扰性能的“好码”。,4）好的错误控制编码方案的目标：(1)用可以纠正的错误个数来衡量纠错能力;(2)快速有效地对消息进行编码;(3)快速有效地对接收到的消息进行译码;(4)单位时间内所能传输的信息比特数尽量大

8、(即有少的冗余度)。上述第(1)个目标是最基本的。为了增加一个编码方案的纠错能力，必须引入更多的冗余度。但增加的冗余度会造成实际信息传输速率的降低。因此第(1)个和第(4)个目标不完全相容。另外，为了能纠正更多的错误，编码策略会变得更复杂，于是第(2)个和第(3)个目标也很难达到。,1.译码规则（译码函数）,使每一种可能的输出符号bj(j=1,2,s)与一个惟一的输入符号ai(i=1,2,r)一一对应。函数F(bj)=ai即为译码函数或译码规则。,5.2.2平均错误概率,依据一定的判决准则设计一个单值函数,注：（1）对输入符号集为X=a1,a2,ar，输出符号集为Y=b1,b2,bs的信道来说

9、，一共可构成rs种不同的译码规则。,例：二进制对称信道，其输入符号集为X=0,1,输出符号 集为Y=0,1，则可构成rs=22=4种译码规则。译码规则(1)：F(0)=0,F(1)=0译码规则(2)：F(0)=0,F(1)=1译码规则(3)：F(0)=1,F(1)=0译码规则(4)：F(0)=1，F(1)=1,例：若已知二进制对称信道传递矩阵为,注：（2）不同的译码规则会引起不同的可靠程度。,如采取译码规则(2)，F(0)=0,F(1)=1，则信道输出端出现“0”和“1”的正确译码概率分别是：,这意味着从统计的观点看，在这种译码规则下信道输出端出现的四个符号“0”(或“1”)中，只能有一个能得

10、到正确译码。,如采用译码规则(3)。F(0)=1,F(1)=0，则信道输出端出现“0”和“1”的正确译码概率分别是：,这意味着从统计的观点看，在这种译码规则下信道输出端出现的四个符号“0”(或“1”)中有三个能得到正确译码。,当信道的输入符号是ai，在信道输出端接收到某符号bj(j=1,2,s)后，正确译码的概率prj为是在信道输出端出现bj(j=1,2,s)的前提下，推测信道输入符号ai的后验概率，即,2.正确译码概率Prj,当信道的输入符号是ai，在信道输出端接收到某符号bj(j=1,2,s)后，错误译码的概率pej为信道输出端出现bj(j=1,2,s)的前提下，推测信道输入的符号是除了a

11、i以外的其他任何可能的输入符号的后验概率，即,式中：e表示除了F(bj)=ai以外的所有可能的输入符号的集合。,3.错误译码概率Pej,注：,4.平均错误译码概率Pe,注：（1）平均错误译码的概率Pe：表示在信道输出端每收到一个符号其产生错误译码的可能性的大小。（2）平均错误译码的概率Pe可作为信道传输可靠性的衡量标准；（3）平均错误译码的概率Pe取决于信道输出随机变量的概率空间P(Y)、信道的后验概率分布P(X|Y)以及译码规则；（4）选择合适的译码规则可降低平均错误译码的概率。,描述了平均错误译码概率Pe与信道疑义度H(X|Y)的内在联系，即,H(XY)H(Pe)十Pe1oga(r-1),

12、5.2.3费诺不等式,（2）费诺不等式表明，在收到信道输出随机变量后，对输 入随机变量仍然存在的平均不确定性H(X|Y)由两部分 组成：第一部分是收到输出随机变量后，按选择的译 码规则译码时，是否产生错误译码的平均不确定性 H(Pe)；第二部分是当平均错误译码概率为Pe时，到底 是哪一个信源符号被错误译码的最大平均不确定性 Pe1oga(r-1)。,注：（1）不论采用什么准则选择译码规则，费诺不等式都是普 遍成立的。,按什么准则来选择合适的译码规则使其平均错误译码概率Pe达到最小，是提高由给定信源、给定信道组成的信息传输系统的可靠性的关键问题。,5.3 译码准则,5.3.1最大后验概率译码准则

13、,证明：设基本离散信道传递矩阵为,1.对于给定信源和给定信道来说，后验概率和信道输出随机变量Y的概率分布都是固定不变的,(516),由,可得rs个确定的后验概率，构成后验概率矩阵,（518）,(517),由给定的信源X的概率分布和信道的传递概率，可求得信道输出随机变量Y的s个概率分量,(519),式(517)和式(519)表明，对于给定信源和给定信道来说，后验概率和信道输出随机变量Y的概率分布也都是固定不变的。,推导：平均错误译码概率Pe为：,（520）,达到最大。,2.最大后验概率译码准则,对于给定信源和给定信道，即p(bj)(i=1,2,s)和p(ai|bj)(i=1,2,r；j=1,2,

14、s)是固定不变的，要使Pe最小，势必要使,达到最大。若把这个最大者所对应的信源符号记为a*，即有,(i1，2，r；j=1,2,s),（522）,（521）,而要使式(520)达到最大，势必要使,这就是说，要使平均错误译码概率Pe达到最小，势必有,因此，译码规则为,(524),式(524)就是最大后验概率译码准则。它表明，若p(a*|bj)(j=1,2,s)是信道输出端收到符号bj(j=1,2,s)后，所推测出的信道输入(信源输出)符号ai(i=1,2,r)的r个后验概率p(ai|bj)(i=1,2,r;j=1,2,s)中的最大者，则可把接收符号bj(j=1,2,s)翻译成a*。,3.由最大后验

15、概率译码函数F(bj)=a*(j=1,2,s)构成的译码规则能使平均错误译码概率达到最小值,(525),注：（1）最小平均错误译码概率Pemin取决于给定信源和给定信道的统计特性。（2）当信源和信道给定后，信息传输可靠性的最高程度也就确定了。而这个最高的可靠程度必须依靠最大后验概率准则来选则译码规则才能得以实现。,推导：若信道输入符号(信源输出符号)ai(i=1,2,r)先验等概，即满足,（526）,(527),的条件时，因为,5.3.2最大似然译码准则,1.最大似然译码准则,可有,(i=1,2,r；j=1,2,s),(528),则选择译码规则,(529),可把bj(j=1,2,s)翻译成信源

16、符号a*a1,a2,ar，即信道输入符号(信源输出符号)ai(i=1,2,r)先验等概时，选择上述译码规则的准则称之为最大似然译码准则。,2.最大似然准则是在满足信道输入符号(信源输出符 号)先验等概的特定条件下的最大后验概率准则，平均错误译码概率Pe同样能够达到最小值Pemin,(530),注：（1）在信道输入符号(信源输出符号)先验等概的特定条件下，采用最大似然准则选择译码规则所得的最小平均错误译码概率Pe min取决于等概信源所含符号数r和信道的传递特性。（2）在信道的输入符号(信源的输出符号)先验等概的特定条件下，若信道输入符号数(信源输出符号数)r固定不变，可通过改变信道的传递特性，

17、使最小平均错误译码概率进一步下降，从而进一步提高信息传输的最高可靠度。实际上，这就是抗干扰信道编码的基本理论依据。,【例54】设某信道的信道矩阵为,解：(1)因信道输入符号非先验等概，故只能采用最大后验概率准则选择译码规则。由式(517)计算出后验概率矩阵,根据最大后验概率准则,并考虑信道输出符号bj(j=1,2,3)与信道输入符号ai(i=1,2,3)一一对应，则选择译码规则,采用最大后验概率准则选择译码规则的最小平均错误译码概率Pe min的具体计算值为,(2)因信道输入符号a1、a2、a3先验等概，故采用最大似然准则选择译码规则。按最大似然准则得到译码规则,并考虑信道输出符号bj(j=1

18、,2,3)与信道输入符号ai(i=1,2,3)要一一对应，则选择译码函数为,采用最大似然准则选择译码规则的最小平均错误译码概率Pe min的具体计算值为,注：（1）上例中最小平均错误译码概率(Pemin0.5667)意味着在信道的输出端接收100个符号中,大约近57个符号要发生错误译码。显然,这不符合人们对信息传输可靠性的要求,应设法使平均错误译码概率最小值Pemin继续下降。（2）对于给定信源来说，要使平均错误译码概率最小值Pemin继续下降，必须进行信道编码，以改变信道的统计特性。,【例55】已知二元对称离散无记忆信道的信道矩阵为,5.4编码原则,5.4.1编码的功能,解：因为信源先验等概

19、，采用最大似然准则选择译码规则,F(0)=0；F(1)=1,在这种译码规则下，平均错误译码概率Pe达到最小值，即,Pe min=10-2，意味着从平均的意义上来说，信道输出端每收到100个符号，就可能有一个符号发生错误译码。显然，不符合信息传输可靠性要求。,注：（1）实际表明，对输入符号进行重复编码，可提高信息传输的可靠性。例如，在信道输入端对输入符号“0”和“1”进行重复编码，离散无记忆信道的输入符号就不再是单个符号“0”和“1”，而是变成由三个符号组成的符号序列1=000和8=111，它们是二元信源的N3次扩展信源中的两个“符号”。3次扩展信源X=X1 X2 X3=1,2,3,4,5,6,

20、7,8中的rN=23=8个“大符号”(消息)分别为:,针对三次扩展信源X=X1X2X3，基本离散无记忆信道转变为离散无记忆信道的三次扩展信道，输出符号集由随机变量Y的符号集Y=0,1转变为随机序列Y=Y1Y2Y3的“大符号”集，分别为：,离散无记忆信道的三次扩展信道的信道矩阵为,由式（530）可得最小平均错误译码概率，即,所以经过简单重复信道编码以后，平均错误译码概率Pe的最小值Pe min降低两个数量级，信息传输的可靠性有了明显的提高。,（2）随机编码中码字的不同选择会导致不同的最小平均错误译码概率Pemin 若选1=000代表信源符号“0”；选2=001代表信源符号“1”。这时，相应的三次

21、扩展离散无记忆信道的信道矩阵就变为,根据最大似然准则选择的译码规则为：,上述译码规则的最小平均错误译码概率为,1.设信道的输入消息数为M，信道随机编码的码字长度为N，则当信道的M个输入消息先验等概时，信道编码的每一码号所携带的平均信息量，即码率,(比特码符号),5.4.2最小汉明距离译码准则,（2）简单重复编码以减少平均错误译码概率Pemin的方法是以降低信息传输率R作为代价的，即“牺牲有效性，换取可靠性”。例55中，当M=2时，若N=1，Pe min=0.01；若 N=3,Pe min310-4；若N=11,Pe min510-10。当M=2，N分别为1、3、5、11时,码率R分别为1、1/

22、3、1/5、1/11。,注：（1）信道随机编码的有效性取决于信道的输入消息数M和码字长度N。在随机编码中，只要保持M和N固定不变，就能使由不同选择所构成的不同信道编码具有相同的有效性。,2.最小汉明距离译码准则 在随机编码中，在消息数M和码字长度N保持不变的条件下，应遵循什么原则挑选码字才能得到尽可能小的最小平均错误译码概率Pemin?,因为消息数固定为M，码字长度固定为N且是由0和1组成的码序列，所以离散无记忆信道的N次扩展信道有M2N个传递概率，它们是:,(533),其中,在M个消息先验等概的条件下，采用最大似然准则选择译码规则。对j(j=1,2,2N)来说，若有,即,(i=1,2,M;j

23、=1,2,2N),考虑到在一般情况下,都有，且，所以有,即选择译码规则为,(537),(536),上述两个式子就是用汉明距离表述的最大似然准则，即最小汉明距离译码准则。（输入消息等概的条件下）,(538),3.最小汉明距离译码准则下的最小平均错误译码概率,(539),亦可表示为：,注：（1）采用最大似然准则选择译码规则所得的最小平均错误译 码概率Pe min取决于：先验等概的消息数M；随机编码的码字长度N；离散无记忆信道N次扩展信道的输出序列j(j=1,2,2N)与译码函数规定的翻译码字*之间的汉明距离d(*,j);j(j=1,2,2N)与除了翻译码字(j)=*以外的其他码字i(i*)之间的汉

24、明距离d(i,j)(i*)。,注：（2）在保持一定的码率R的前提下(即保持先验等概的消息数M和码字长度N不变的前提下)，最小平均错误译码概率Pe min取决于汉明距离d(*,j)(*1,2,M;j=1,2,2N)和d(i,j)(i*；j=1,2,2N)。（3）信道编码的任务：保持码率R在一定水平(保持M和N不变)的前提下，采用正确的方法选择M个码字，使最小平均错误译码概率Pe min尽量小。,在从rN个长度为N的码符号序列l(l=1,2,rN)中选择M个作为代表消息的码字的原则是：M个码字中，任何两个不同的码字间的汉明距离要尽量大。若令dmin(k,h)kh表示M个码字中任何两个不同的码字(k

25、,h)之间的最小汉明距离，即,（540）,5.4.3 编码原则,dmin(k,h)kh要尽量的大，即挑选出来的M个码字之间越不相似越好。,定理5-1 抗干扰信道编码定理（香农第二定理）设某信道有r个输入符号，s个输出符号，信道容量为C。当信道的信息传输率RC时，只要码长N足够长，总可以在输入集合中(含有rN个长度为N的码符号序列)找到M(M2N（C-），为任意小的正数)个码字，分别代表M个等可能性的消息，组成一个信道编码，选择相应的译码规则，使信道输出端的译码过程的最小平均错误译码概率Pemin达到任意小。,5.5 抗干扰信道编码定理及逆定理,注：（1）定理指出：总能找到一种抗干扰信道编码，只

26、要其码长N足够长，它的最小平均错误译码概率Pemin就可任意小，信道信息传输率(码率)R可无限接近信息容量C。（2）这个定理是一个存在定理，指出错误率趋于0的编码方法是存在的。（3）定理表明，在错误率趋于0的同时，还可以使R趋于C，这是具有理论指导意义的。,定理52抗干扰信道编码定理的逆定理 设某信道有r个输入符号，s个输出符号，信道容量为C。若选用码字个数(消息数)M(M=2N（C+），令为任意小的正数)，则无论码长N多大，也不可能找到一种编码，使平均错误译码概率Pe任意小。,注：（1）逆定理指出：要使信道的信息传输率超过信息容量C，而又要求无错误地传输消息，这是不可能的。（2）信道容量C是在信道中可靠地传输消息的最大信息传输率。,