极速赛车APP下载

无失真信源编码定理

电脑杂谈  发布时间:2019-07-07 07:15:51  来源:网络整理

无失真信源编码定理_无失真信源编码答案_信息论无失真信源编码

5.1 5.2 5.3 5.4 5.5ε5.6  信源编码:以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送,使单位时间内传送的平均信息量增加,从而提高通信的有效性。 信道编码:是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码:是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发,“加密”可视为增熵的过程,“解密”可视为减熵的过程。5.1  信源编码理论是信息论的一个重要分支,其理论基础是信源编码的两个定理。 无失真信源编码定理:是离散信源/数字信号编码的基础; 限失真信源编码定理:是连续信源/模拟信号编码的基础。 信源编码的分类:离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码:独立信源编码,可做到无失真编码; 连续信源编码:独立信源编码,只能做到限失真信源编码; 相关信源编码:非独立信源编码。

信息论无失真信源编码_无失真信源编码答案_无失真信源编码定理

5.1 编码器可以看作这样一个系统,它的输入端为原始信源S,其符号集为为编码器的功能是用符号集X中的元素,将原始信源的符号变换为相应的码字符号输出端的符号集为{ ,;而信道所能传输的符号集,所以编码器称为码字, 为码字长度,简称码长。的码元个数,称为码字的码字12{ ,,...,}qSS SS12{ ,,..., }rXx xx12,...,}qSS SS12{ ,,...,}rXx xx12:{,,...,}qCW WW12:{,,...,}qCW WWiSiwiwiLiwiw5.1 1、二元码:码符号集X={0,1},如果要将信源通过二元信道传输,必须将信源编成二元码,这也是最常用的一种码。2、等长码:若一组码中所字的长度都相同,称为等长码。3、变长码:若一组码中所字的长度各不相同,称为变长码。4、非奇异码:若一组码中所字都不相同,称为非奇异码。5.1 5、奇异码:若一组码中有相同的码字,称为奇异码。6 、同价码: 每个码字占相同的传输时间7、码的N次扩展:若码, 码则称码B为码C的N次扩展码。8、唯一可译码:若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列,则称此码为唯一可译码。

无失真信源编码答案_信息论无失真信源编码_无失真信源编码定理

12:{,,...,}qCW WW12:{(...)}iiiiNBBW WW5.1 例:如果有四个信源符号{s1无失真信源编码定理,s2,s3,s4},采用二元编码,l=2,则可以编成s1=00,s2=01,s3=10,s4=11。如果我们要对信源的N次扩展信源进行编码,也必须满足, 两边取对数得:qN表示平均每个信源符号所需的码符号个数。NNllrlogloglqr若对信源进行等长编码,则必须满足其中,l是码长,r是码符号集中的码元数,q信源符号个数。lqr5.2 例:对英文电报得32个符号进行二元编码,根据上述关系:log32log25l 我们继续讨论上面得例子,我们已经知道英文的极限熵是1.4bit,远于5bit,也就是说,5个二元码符号只携带1.4bit的信息量无失真信源编码定理,实际上,5个二元符号最多可以携带5bit信息量。我们可以做到让平均码长缩短,提高信息传输率5.2 我们举例说明:设信源31241234( )( )( )( )( )sP ssP ssP ssP sSP s41( ) 1iiP s而其依赖关系为:21124334(/ )( /)(/)(/)1,(/ )0jiP ssP ssP ssP ssP ss其余5.2 若不考虑符号间的依赖关系,可得码长l=2若考虑符号间的依赖关系,则对此信源作二次扩展23 421 24 3(1 2(2 1(2 13 44 3))())( )s sP s ss sP s ss sP s ss sP s sSP s可见,由于符号间依赖关系的存在,扩展后许多符号出现的概率为0,此信源只有4个字符,可得码长但平均每个信源符号所需码符号为'1() 1ijijP s s,'2l lN5.2 我们仍以英文电报为例,在考虑了英文字母间的相关性之后,我们对信源作N次扩展,在扩展后形成的信源(也就是句子)中,有些句子是有意义的,而有些句子是没有意义的,我们可以只对有意义的句子编码,而对那些没有意义的句子不进行编码,这样就可以缩短每个信源符号所需的码长。

无失真信源编码答案_无失真信源编码定理_信息论无失真信源编码

等长信源编码定理给出了进行等长信源编码所需码长的极限值。5.2 5.3 ε(本节略)本节的主要是为了证明信源编码定理,而引入了一种渐近等分割性和ε典型序列的重要概念。5.3一个熵为H(S)的离散无记忆信源,若对其N次扩展信源进行等长r元编码,码长为l,对于任意大于0,只要满足log当N无穷大时,则可以实现几乎无失真编码,反之,若:( ) 2log则不可能实现无失真编码,当N趋向于无穷大时,译码错误率接近于1。( )lH SNrlH SNr5.4 •定理5.3的条件式可写成:左边表示长为而右边代表长为N的序列平均携带的信息量。因此,只要码字传输的信息量大于信源序列携带的信息量,总可以实现无失真编码 。log( )lrNH S的码符号所能载荷的最大信息量,l•定理5.3的条件式也可写成:令:logN率大于信源的熵,才能实现无失真编码。log( )lrH SN'lRr称之为编码信息率。可见,编码信息5.4 最佳编码效率为:'( )R( )( )H SH SH S1( )H S为了衡量编码效果,引进'( )R( )logH SH SlNr 称为编码效率。

信息论无失真信源编码_无失真信源编码定理_无失真信源编码答案

极速赛车APP下载①设计和实现基于哈夫曼算法的编码和译码功能,系统功能包括:产生哈夫曼编码,输入电文进行编码生成码文,将码文译成电文,对输入电文和译文作对比等。后者的操作对象是三元而非二元数字,三元golay码将每6个三元符号分为一组,编码生成5个冗余校验三元符号,这样由11个三元符号组成的三元golay码码字可以纠正2个错误。误码率计算困难香农采取的方法:用随机编码方法得到所有可能码的集合,在其中随机选择一个码作为信道码,利用联合典型序列译码,利用大数定理计算在集合平均意义上的该码性能2.2 证明从早期的粗糙定性证明到后来给定精确差错概率指数上下限的严格数学证明。

即时码也称为非延长码,前缀条件码。5.5 :如果一个码组中的任一个码字都不是另一个码字的续长,或者说,任何一个码字后加上若干码元后都不是码组中另一个码字,则称为即时码。所有的码非奇异码唯一可译码即时码5.5 2、即时码的树图构造法我们可以用树图的形式构造即时码,如01001111010010001码4的树图10110000101001000码3的树图树根——码字的起点树枝数——码的数节点数——码字的一部分节数——码长端点——码字满树——等长码非满树——变长码5.5 在每个节点上都有r个分枝的树称为整树,否则称为非整树。即时码的树图还可以用来译码5.5 3、克拉夫特(Kraft)不等式5.4所对应的码长为对于码符号为l l的任意即时码,,则必定满足:112{ ,,...,}qXlix xx12q, ,...,qr1li反之,若码长满足上式,则一定存在这样的即时码 。可以根据即时码的树图构造法来证明。后来,B.McMillan证明了对于唯一可译码也必须满足上面的不等式,5.5 定理5.6 若存在一个码长为定存在一个同样长度的即时码。

唯一可译码,则一这说明,其他唯一可译码在码长方面并不比即时码占优。所以在讨论唯一可译码时,只需要讨论即时码就可以了。12, ,,ql ll5.5 设信源11,22W......qnapW Wap,...,xpXPl l编码后的码字为:12qL码长为: 1( )2, ,...,ql则这个码的平均长度为:1qiiiP S l平均每个码元携带的信息量即编码后的信息传输率为:( )LH SR若有一个唯一可译码,它的平均码长于其他唯一可译码的长度,则称此码为紧致码或最佳码,无失真信源编码的基本问题就是寻找紧致码。5.5 5.8 离散无记忆信源S的N次扩展信源编码器的码元符号集为A:总可以找到一种编码方法,构成单义可译码,使信源S中每个符号si所需要的平均码长满足,其熵为,并且对信源进行编码,NS()NH SNS12{ ,,...,}q ( )( )1NloglogNH SLNH Srrlim( )rNLH S当则得:N 5.6 这个定理是香农信息论中非常重要的一个定理,它指出,要做到无失真的信源编码,信源每个符号所需要的平均码元数就是信源的熵值,如果于这个值,则唯一可译码不存在,可见,熵是无失真信源编码的极限值。

定理还指出,通过对扩展信源进行编码,当N趋向于无穷时,平均码长可以趋进该极限值。还可以证明,如果我们不确切知道信源的概率分布,我们用估计的概率分布去进行编码时,平均码长会加长,但是如果估计的偏差不大的话,平均码长也不会增加太多(定理4.9的内容)。5.6 ( )( )1NlogloglogNH SLNH Srrr由得: ( )log( )NLNH SrH SNLN定义:就是编码后每个信源符号所携带的平均信息量'logNLNRr第一定理可以表述如下:若变长码,若R若从信道角度讲,信道的信息传输率( )log当平均码长达到极限值时,编码后信道的信息传输率为: log就存在唯一可译则不存在唯一可译变长码。'( )RH S'( )H S5.6 ( )LH SR因为:NLNH SLr所以logRrRr若信道的信息传输率R不大于信道容量C,总能对信源的输出进行适当的编码,使的在无噪无损信道上能无差错的以最大信息传输率C传输信息,若R于C,则无差错传输是不可能的。编码效率:L码的剩余度: 1 在二元无噪无损信道中:5.6 ( )rH s ( )LH s 在二元无噪无损信道中信息传输率:( )LH sR例:12( )3/4 1/4ssSP S其熵为:H(S)=0.811我们令s1=0,s2=1,这时平均码长率为。

0。811二次扩展信源进行编码:s1s1s1s2s2s1s2s22+227/322,编码的效1L  5。6 即时码0101101119/163/163/161/16i()iP 9/16*1 3/16*2 3/16*3 1/16*3L27/16L L +0。961  作业: 5。1 5。2 5。4 5。6(选做) 谢谢


本文来自电脑杂谈,转载请注明本文网址:
http://www.0531mai.com/a/tongxinshuyu/article-111068-1.html

    相关阅读
    发表评论  请自觉遵守互联网相关的政策法规,严禁发布、暴力、反动的言论

    极速赛车APP 极速赛车手机官网 极速赛车APP下载 极速赛车手机官网 极速赛车手机官网 极速赛车APP 极速赛车APP 极速赛车手机版下载 极速赛车APP下载 极速赛车APP下载