大学课程《信息论基础与应用》PPT课件:第6章 有噪信道编码.ppt
- 文档编号:18828843
- 上传时间:2023-12-20
- 格式:PPT
- 页数:107
- 大小:1.50MB
大学课程《信息论基础与应用》PPT课件:第6章 有噪信道编码.ppt
《大学课程《信息论基础与应用》PPT课件:第6章 有噪信道编码.ppt》由会员分享,可在线阅读,更多相关《大学课程《信息论基础与应用》PPT课件:第6章 有噪信道编码.ppt(107页珍藏版)》请在冰点文库上搜索。
第六章有噪信道编码,主要内容,信道编码的概念香农第二定理差错控制信道编码方法,第5章结论:
在无噪无损信道上,只要对信源的输出进行恰当的编码,总能以信道容量C无差错地传输信息。
实际信道都有噪声干扰,本章研究香农第二定理,即通信的可靠性问题。
包括:
1.怎么使有噪信道中消息传输错误达到最少?
2.在有噪信道中无错误传输的可达的最大信息传输率是什么?
6.1信道编码的概念,信道编码概述,问题引出什么是信道编码信道编码的作用信道编码的三种情形信道编码的实质,信道编码概述问题引出,互信息能告诉我们什么?
随机变量X,Y统计意义上的依存程度可以获得的信息量不能:
所得信息能否可靠地确定信道输入?
无噪信道编码能告诉我们什么?
无噪无损信道,只要对信源输出进行适当编码,总能以最大信息传输率,无差错的传输信息。
但是:
一般信道总存在噪声或干扰,信息传输会造成损失,信道编码概述问题引出,实际通信中人们对传输要求什么?
传输信息量大传输可靠提出的与信道传输有关的问题:
如何能使信息传输后发生的错误最少?
错误概率与那些因素有关?
有无办法控制?
能控制到什么程度?
无误传输可达的最大信息率是多少?
信道编码概述什么是信道编码,通信系统模型信道编码:
从消息到信道波形或矢量的映射希望通信系统与信道统计特性相匹配的编码,信道编码概述信道编码的作用,信道编码的作用:
在资源、可靠性和传信量之间选择一个好的工作点(有时还要考虑延时)。
资源指的是提供信息传输所付出的代价包括频率、时间、空间、功率等。
但不包括实现复杂度一个好的编码就是要充分利用资源,传递尽可能多的信息,信道编码概述三种情形,给定资源和可靠性要求,通过信道编码尽量提高传输速率给定对信息传输的速率和可靠性要求,通过信道编码尽量减少资源开销给定资源和传输速率,通过编码提高可靠性,信道编码概述编码的实质,利用冗余降低差错概率将所有可能的输入信息(消息)映射到信道符号(波形)空间的点,而这个点的集合要小于(包含于)全信道空间中。
信道编码概述信道编码的基本分类,按码的结构分:
线性码线性分组码(群码)卷积码(线性树码)非线性码按抗干扰模式分抗随机差错码抗突发差错码按编译码理论所用数学工具分代数码几何码组合码按对错误的处理方式分检错码纠错码,错误:
译码输出信源输出产生原因:
噪声干扰研究目的:
减少错误,提高可靠性研究途径:
信道的传递矩阵信道统计特性错误概率,1译码规则,错误概率与译码规则错误概率PE与什么有关信道的统计特性:
当确定了输入和输出对应关系后,也就确定了信道矩阵中哪些是正确传递概率,哪些是错误传递概率。
译码规则:
通信过程一般并不是在信道输出端就结束了,还要经过译码(或判决)过程才到达消息的终端(收信者)。
因此译码过程和译码规则对系统的错误概率影响很大。
译码规则的选择依据最大后验概率准则理想最大似然准则实用,
(一)译码规则,译码函数,译码规则:
rs种译码规则,译码规则,编码,译码,信道译码,An,1,2,4,3,w4,w3,w1,w2,x,x,x,An是接收空间w1,w2,是发送的码字围绕每个码字有一个译码域i如果接收的码字在i中,就认为发送的是码字wi发生错误一般,An中存在一些不属于任何i的区域有时接收码字会被映射到错误的i,进而被译成错误的wi,正确译码,不知如何译码,译码错误,问题:
在输入和信道特性给定的条件下,差错概率将取决于接收矢量空间按什么样的划分准则进行划分划分接收矢量空间的准则译码器的译码准则,
(二)准则一:
最大后验概率译码准则(最小平均错误概率准则),输入ai,正确译码,输入为除ai以外的(r-1)种任何符号,错误译码,正确译码的概率:
错误译码的概率:
平均正确译码概率:
平均错误译码概率:
最大后验概率译码准则(最小错误概率准则),即把每个输出符号均译成具有最大后验概率的那个输入符号的译码函数使信道错误概率最小。
最大后验概率准则(最小错误概率准则):
优点:
理想缺点:
1、后验概率不易得到2、后验概率依赖于输入分布,等概信源,译码规则,最大似然准则,(三)准则二:
最大似然译码准则,平均错误概率的计算,1.求平均错误概率步骤(按列计算):
求联合概率矩阵P(ai)P(bj|ai)中每列除去F(bj)=a*所对应的P(a*bj)以外所有元素之和;再对上述结果求和。
2.采用逐行计算方法:
求矩阵P(ai)P(bj|ai)各行中F(bj)=a*所对应的P(a*bj)以外所有元素之和;再对上述结果求和。
若先验概率P(ai)=1/r,有:
即在等先验概率分布情况下,译码错误概率可用信道矩阵中的元素P(bj|ai)和(除去每列对应于F(bj)=a*的那一项)来表示。
关于最大似然比译码准则的说明,若输入符号等概率,等同最小平均错误概率准则。
直接从信道矩阵的传递概率中去选定译码函数:
收到bj后,译成信道矩阵P的第j列中最大那个元素所对应的信源符号。
本身不再依赖于先验概率P(ai)。
但当先验概率为等概率分布时,它使错误概率PE最小。
最大后验概率译码准则&最大似然译码准则输入等概时二者是一致的此时:
例:
求译码规则和平均错误译码概率。
解:
译码规则,2编码方法,上一节结论:
消息通过有噪信道传输时会发生错误错误概率与译码规则有关噪声干扰:
破坏了信号的内部结构产生畸变而造成信息的损失。
提高信号抗噪声干扰能力:
改造信号使其内部结构具有更强的规律性或相关性,当信号的部分结构被破坏时,仍能根据信号原有的内在规律和相关性来发现甚至纠正错误,恢复原来的信息。
错误概率与编码如何在信息传输率一定的前提下使PE0实际经验:
重复发送可以使PE减小重复次数N很大时,可以使PE0但是:
信息传输率降低信道编码定理:
R一定时,可以找到一种编码方法使PE相当低引入概念:
码字距离,编码方法,例:
如何在信息传输率一定的前提下使PE0,重复码,传输消息:
0,1,0,00,1,11,校验元,若传000,收到误传为100,010,001中的任一种,则认为是传的000,实现了纠错。
重复发送可以使PE减小但是:
信息传输率降低,BSC无记忆,M=2,正确译码正确译码正确译码错误译码错误译码正确译码正确译码正确译码,00010111,000000000111000111111111,000001010011100101110111,000000000000111111111111,00001111,译码状态,译码消息,译码码字,接收分组,发送码字,信息,“0”个数多,就认为发送的是“000”,“1”个数多,就认为发送的是“111”,自动纠正一位错,比特/码符,M是输入消息(符号)的个数,logM表示消息集在等概率条件下每个消息(符号)携带的平均信息量(比特),n是编码后码字的长度(码元的个数),若传输每个码符号平均需要t秒钟,则编码后每秒钟传输的信息量:
对上述重复编码方法可计算得,当n1(无重复),M2,设t1秒时,当n3(重复三次),M2,设t1秒时,n5,M2时,n11,M2时,由此得PE和R的关系,如图所示。
它表明:
尽管可使PE降低很多,但同时也使信息传输率降得很低。
问题:
能否找到一种更好的编码方法,使PE相当低,而R却保持在一定水平?
即有噪信道编码定理。
简单重复编码方法使信息传输率降低的原因,在未重复编码以前,输入端是二个消息的集合。
假设为等概率分布则每个消息携带的信息量是logM=1(比特符号)。
简单重复(n=3)后,可以把信道看成是三次无记忆扩展信道。
这时输入端有8个二元序列可以作为消息(a1,a8),但我们只选择了二个二元序列作为消息,M2。
这样每个消息携带的平均信息量仍是1比特。
而传送一个消息需要付出的代价却是三个二元码符号,所以R就降低到1/3(比特码符号)。
如果在扩展信道的输入端把8个可能作为消息的二元序列都作为消息,M8,则每个消息携带的平均信息量就是3比特,而传递一个消息所得的符号数仍为三个二元码符号,则R就提高到1(比特码符号)。
这时的信道如下图所示。
这时只能规定接收端8个输出符号序列j与i一一对应。
这样,只要符号序列中有一个码元符号发生错误就会变成其他所用的码字,造成译码错误。
只有符号序列中每个符号都不发生错误才能正确传输。
错误概率:
说明:
在一个二元信道的n次无记忆扩展信道中,输入端有2n个符号序列可以作为消息。
如果选出其中的M个作为消息传递,则:
当M取大一些PE、R;M取小一些PE、R。
还存在另外一个问题,M=4时,有70种选取方法,而选取方法不同,错误率也不同。
我们比较下面两种选取方法:
第一种:
000011101110第二种:
000001010100可以计算得第一种方法的错误率为第二种方法的错误率为,比较可知,第一种方法好,仔细观察发现,在第一种方法中,如果000有一位出错,我们就可以判定出错了;而在第二种方法中,如果000中任何一位出错,就变成了其他的合法的码字,我们无法判断是否出错。
再仔细观察,发现第二种方法中,码字之间太“象”了,或者说太“近”了。
我们再讨论一个例子,取M4,n5,这4个码字按如下规则选取:
设输入序列为:
满足方程:
若译码采取最大似然准则:
此码能纠正所有码字中一位码元错误,也能纠正其中两个两位码元的错误。
我们引进这样一个概念:
汉明距离。
在二元码中:
如:
则,在某一码书中,任意两个码字的汉明距离的最小值称为该码C的最小距离。
我们来讨论前边的5种码的距离:
很明显,越大,越小,在M相同的情况下也是一样。
在二元对称信道的情况下,译码规则可以如下:
选择,使之满足,它称为最小距离译码准则,它等价与最大似然译码准则,也就是收到一个码字后,把它译成与它最近的输入码字,这样可以使平均错误率最小。
另外,我们应该选择这样的编码方法:
应尽量设法使选取的M个码字中任意两两不同码字的距离尽量大。
最小距离译码准则,在二元对称信道中最小距离译码准则等于最大似然译码准则。
而在其他信道中,它们不一定相等。
结论,在有噪信道中,传输的平均错误概率PE与各种编、译码方法有关。
编码选用M个消息所对应的码字间最小距离dmin尽可能大的编码方法;译码采用将接收序列bj译成与之距离最近的那个码字a*的译码规则;则只要码长n足够长时,合适地选择M个消息所对应的码字,就可以使错误概率很小,而信息传输率保持一定。
对两种译码准则的评述最大后验概率准则具有很好的直观合理性。
收到y的条件下,最可能发送的是哪个码字,就认为发送的是哪个码字。
最大似然概率准则(最小距离准则)所具有的直观合理性弱一些。
发送哪个码字的条件下,最可能收到y,就认为发送的是哪个码字。
最大似然概率准则(最小距离准则)的实现比最大后验概率准则的实现更简单:
前者只需要看哪个码字与y的Hamming距离最小;后者需要知道各码字的概率分布,然后用贝叶斯公式计算并比较后验概率。
两种准则都可以用在没有编码(直接发送)情况下的纠错译码。
6.2信道编码定理,信道编码定理引出问题:
在有噪信道中,使平均误码率PE尽可能小的情况下,可达到的信息传输率是多少?
答案:
信道容量C信道编码定理信道编码定理的证明证明思路随机编码方法联合典型序列,信道编码定理(香农第二定理):
设R是信息传输的速率,C是离散无记忆信道的信道容量,0是任意小的数,则只要RC就总存在码字长为n,码字数为M=2nR的分组码使译码的平均差错概率PE。
信道编码定理的证明思路:
通常思路:
先构造一个理想的好码,并定义一种译码准则,计算该好码经过译码后的误码率问题:
构建极其复杂且无具体方法N值很大时,误码率计算困难香农采取的方法:
用随机编码方法得到所有可能码的集合在其中随机选择一个码作为信道码利用大数定理计算在集合平均意义上的该码性能利用联合典型序列译码香农采取的方法评价:
不很严格,不是最优,但便于理论分析随机编码方法在后来严格的证明中一直被采用,随机编码方法:
对每一个消息m(m=0,1,M-1),编码为xm=(xm1xm2xmn)其中:
xmi(i=1,2,n)是按照输入字母的概率随机选取,从而得到全部M=2nR个码字,组成码集C(x1x2.xM-1)随机编码方法产生某一特定码字的概率P(Xm)是:
联合典型序列典型序列:
信源输出的随机序列奠定了信源编码的基础联合典型序列:
两个随机变量的自然扩展,是信道编码的基础联合典型序列定义:
联合AEP定理定理解释:
联合典型序列的定义,若x为典型序列,则:
|-logP(x)/n-H(X)|,Xn空间中的典型序列集记为Gn(X)若y为典型序列,则:
|-logP(y)/n-H(Y)|,Yn空间中的典型序列集记为Gn(Y)若(x,y)满足:
|-logP(xy)/n-H(XY)|,则称(x,y)为联合典型序列,XnYn联合空间中的典型序列集记为Gn(XY)。
Gn(XY)=(x,y)XnxYn;|-logP(x)/n-H(X)|-logP(y)/n-H(Y)|;|-logP(xy)/n-H(XY)|,联合渐近等分割性,对于任意小的正数,当n足够大时,则:
(1),
(2),(3)以,和分别表示典型序列集,和中包含的典型序列的数目,则有,说明:
对编码-几乎无失真编码;-均匀分布;|-2NH(XY),联合典型序列的性质,对于任意小的正数,n足够大时,其中(x,y),
(1),
(2)令,即是在给定典型序列y条件下,与y构成联合典型序列对的所有x序列的集合,则同样,在给定典型序列x条件下,与x构成联合典型序列对的所有y序列的集合,则,定理若和统计独立并与p(xy)有相同的边缘分布,即,则并对于任意正数,当n足够大时,有,联合典型序列中两序列统计独立的情况,联合典型序列定义:
设(X,Y)是长为N的随机序列对,则在这些随机序列对中满足下列条件的序列对被称为联合典型序列式中是任意小的数,联合典型序列的全体构成联合典型序列集,记做G,联合AEP定理:
设随机序列对(X,Y)的,则对任意小的数0,我们总能找到足够大的N使全体序列对的集合能被分成满足下述条件的集合G及其补集Gc:
(1)
(2)(3)设(X,Y)是相互独立的随机序列对,但它与(X,Y)有相同的边缘分布,即:
则:
联合AEP定理的解释两个随机变量情况下,序列Xn,Yn及其联合序列XnYn都具有AEP特性联合典型序列对是高概率序列对联合典型序列对出现概率接近相等,且其和接近于1联合典型序列对是一些密切关联的序列对一般与X对应的Y可能是Y空间的任一个,该定理说明:
随N的增大,对应X的Y只能是(X,Y)典型序列对的Y,取其他Y的概率0联合典型序列数目为2NH(XY),典型x,典型Y随机组合的空间为2NH(X)+H(Y),联合典型序列占其中约1/2NI(X;Y),只是很小的一部分故:
当X的数目2NI(X;Y)时,可使PE0给出一种译码方法:
译码时,取与接收矢量联合典型的码字作为输出,这种译码方法可以保证得到很低的误码率。
信道编码定理(香农第二定理):
设R是信息传输的速率,C是离散无记忆信道的信道容量,0是任意小的数,则只要RC就总存在码字长为n,码字数为M=2nR的分组码使译码的平均差错概率PE。
定理证明:
设有M2nR个消息,则1,2nR为消息的标号集。
对M中任一码字w,当等概分布时,有P(w)=2-nR如果发送w,收端序列为y,根据译码函数:
g(y)=w1,2nR为正确译码;g(y)=w1,2nRw不等于w,则为错误译码。
所以,对于XN扩展信道,其平均错误概率因为w的选取是随机的,可设w1,则Pr(E)=PE1=Pg(y)1/x=x
(1)现在的问题是使PE1能否尽可能地最小?
PE1=Pg(y)1/x=x
(1)P(E1CUE2UE3UUE2nR)P(E1C)+P(E1)1,P(E1C)1P(E1)P(Ei)2-nI(X;Y)-3所以PE12-nI(X;Y)-32-nI(X;Y)-R-3,即对于任意小的和,当RI(X;Y)时,PE1任意小,所以当RC时,至少存在一种码书(M,n),其错误概率小于或等于平均值。
信道编码定理证明的几点说明香农只是证明了码的存在性,未给出构造方法随机编码所得的码集很大,通过搜索得到好码的方法实际上很难实现;而且即使找到,码字也是毫无结构的,只能采用查表译码方法,当N很大时,码表的存储量也很难接受,理论性能极限存在性香农信道编码定理作用:
理论极限、渐进性能工程实现上的界限构造性最小距离界限作用:
构造新码、估计新码性能时,说明新码与最好性能的码接近的程度,信道编码的性能界限,香农理论极限:
RC;存在编译码方法使PE0给定PE;存在编译码方法使RC,有噪信道编码逆定理逆定理:
设离散无记忆信道X,P(y/x),Y,其信道容量为C。
当信息传输率RC则无论码长n多长,总也找不到一种编码(M=2nR,n)使译码错误概率任意小。
根据平均互信息的定义,数据处理定理以及无记忆扩展信道的性质,得出:
PE1当RC时,增大n,错误概率远离零值;当RC时,增大n,错误概率趋于零。
这个定理是信道编码的理论依据,可以看出:
信道容量是一个明确的分界点,当取分界点以下的信息传输率时,以指数趋进于0;当取分界点以下的信息传输率时,以指数趋进于1;因此在任何信道中,信道容量都是可达的、最大的可靠信息传输率。
这个定理是一个存在定理,它没有给出一个具体可构造的编码方法,在它的证明过程中,码书是随机的选取的,它有助于指导各种通信系统的设计,有助于评价各种系统及编码的效率。
联合信源信道编码定理,在任意信道中进行数据传输,必须信息传输率小于信道容量RH。
联合这两个定理,就会有这样地问题:
若信源通过信道传输,要做到有效和可靠地传输,是否HC是充分和必要条件。
定理信源信道编码定理若Sn=(S1S2Sn)是有限符号集的随机序列并满足AEP,又信源S极限熵C,则错误概率远离零,即不可能在信道中以任意小的错误概率发送这随机序列。
从香农第一、第二定理可以看出,要做到有效和可靠的传输信息,我们可以将通信系统设计成两部分的组合,即信源编码和信道编码两部分,首先通过信源编码,用尽可能少的信道符号来表达信源,尽可能减少编码后信源的数据的剩余率,然后针对信道,对信源编码后的数据独立的进行信道编码,适当增加一些剩余度,使能纠正和克服信道中引起的错误和干扰。
可以证明,只要满足香农第一定理和第二定理,用两步编码的方法传输信息和一步编码的方法传输信息其效果是一样的。
6.3差错控制概述,错误格式将发生错误看成是因为加入了某种“错误格式”E的结果。
由于随机差错可能发生在n长码字的某1位、某几位,甚至全错,因此其错误格式种类为(只有1个全0时的E,没有差错),在这个可能的错误中,n长码总错误概率为,错误图样,在二元无记忆n次扩展信道中,差错的形式也可以用二元序列来描述。
设发送C=c1,c2,cn,接收Y=y1,y2,yn,两者的差别:
E=CR=e1,e2,en称为错误图样。
6.3差错控制概述,差错控制分类前向纠错反馈重发混合纠错方式信息反馈常用的差错控制码,6.4信道编码方法,通过在传输的信息码元后增加一些多余的码元(称为校验元),纠错编码可以在信息损失或错误后还能在接收端恢复原代码。
6.4.1线性分组码,线性码信息码元与校验码元之间呈线性关系。
非线性码信息码元与校验码元之间不存在线性关系。
分组码把信息序列以每k个码元分组,然后把每组k个信息元按一定规律产生r个多余的校验元,输出序列每组长为nk+r,则每一码字的r个校验元只与本码字的k个信息冗有关,与别的码字的信息位无关,记为分组码(n,k)。
卷积码把信息序列以每ko(通常较小)个码元分段,编码器输出该段的校验元rn-ko不但与本段的ko个信息元有关,而且还与其前面m段的信息元有关,故记为卷积码(n,ko,m)。
1基本概念,线性分组码编码框图如下图所示。
编码是在信道输入端2n个n长的二元序列中找一组2k个码字,使码字的rn-k个校验元与其k个信息元之间满足一定的线性关系,并使码书中码字间最小距离最大。
而译码则采用最大似然译码准则即最小汉明距离译码准则。
2一致监督方程和一致监督矩阵,一致监督方程:
确定信息元得到监督元规则的一组方程。
(7,3)线性分组码码长n=7,信息元k=3,检验元r=n-k=4。
C6c5c4为信息元,c3c2c1c0为监督码元,监督码元由以下方程得出:
一致监督方程。
信息码组(101),即C6=1,C5=0,C4=1;由线性方程组得:
C3=0,C2=0,C1=1,C0=1;即信息码组(101)编出的码字为(1010011)。
设码字C=(c6c5c4c3c2c1c0),有:
HCT=0T0(000),0T是0矢量的转置,即满足:
为一致监督矩阵。
其中:
3线性分组码的生成矩阵,是待编码的信息组,G是一个的矩阵。
对每一个信息组m,由矩阵G都可以求得(n,k)线性码对应的码字。
由于矩阵G生成了(n,k)线性码,称矩阵G为(n,k)线性码的生成矩阵。
例6.6.,3线性分组码的生成矩阵,线性系统码的监督矩阵H和生成矩阵G之间可以直接互换。
例6.7.,4线性分组码的编码,(n,k)线性码的编码就是根据线性码的监督矩阵或生成矩阵将长为k的信息组变换成长为n(nk)的码字。
利用监督矩阵构造(7,3)线性分组码的编码电路:
设码字矢量为C=(C6C5C4C3C2C1C0),码的监督矩阵为,4线性分组码的编码,由HCT=0T得,用几何图形来解释,可将码字看成n维空间上的一点,则重复码(3,1)的码字为三维空间上的点,如图正方体上八个顶角为所有八个可能的接收序列,而对角(000)和(111)正好为发送的两个码字。
5线性分组码的最小距离、检错和纠错能力,最小距离,以码字C为中心,半径为t的汉明球是与C的汉明距离t的向量全体集合SC(t)。
任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin。
5线性分组码的最小距离、检错和纠错能力,汉明球,汉明重量码字重量(汉明重量)(Hammingweight)在二元编码的码字集合中,码字中“1”码元的个数称为这个码字的重量。
记为:
W()。
分组码最小码距与纠检错能力的关系:
一个分组码的最小码距为dmin,则其纠检错能力为:
若检测l个错误,则要求dminl+1;若纠正t个错误,则要求dmin2t+1;若纠正t个错误,同时检测l个错误,则要求dmint+l+1;tl;,伴随式/监督子/校验子:
6线性分组码的伴随式,伴随式仅与错误图样有关,而与发送的具体码字无关。
定义:
汉明码是一类能纠正一位错的线性码。
汉明码参数码长:
n=2r-1信息位数:
k=2r-r-1监督位数:
r=n-k最小码距:
d=3汉明码是具有纠一位错能力的完备码,6.4.2汉明码,汉明码有r位校验元,就有2r-1个不同的非全零矢量,将其按列排成矩阵,则得一致监督矩阵H。
有了矩阵H就可生成码字和进行译码了。
汉明码的信息传输率:
当r很大时,信息传输率R1(比特二元码)。
可见汉明码是一种高效率的纠正一位随机错误的分组码。
汉明码可以方便地用移位寄存器等硬件或计算机软件来实现。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论基础与应用 大学课程信息论基础与应用PPT课件:第6章 有噪信道编码 大学 课程 信息论 基础 应用 PPT 课件 信道编码
![提示](https://static.bingdoc.com/images/bang_tan.gif)