信息论基础与编码—无失真信源编码ch05.article

《信息论基础与编码—无失真信源编码ch05.article》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、信息论基础与编码一无失真信源编码Contents无失真信源编码基本概念1定长无失真信源编码23渐进等同分割性54定长无失真信源编码定理65变长无失真编码85.1Kraft不等式85.2唯一可译码判决准则96变长无失真信源编码定理107无失真信源编码技术11Huffman编码12Shannon编码12Shannon-Fano-Elias编码12Fano编码12Huffman编码的几个问题13算数编码14游程编码15通用编码15几种编码方案的性能对比221无失真信源编码基本概念?对于信源来说有两个基本问

2、题：如何计算信源输出的信息量；如何有效地表示信源输出，即在不失真或允许一定失真的条件下，如何用尽可能少的符号来表示信源，以便提高信息传输的效率。?编码实质上是对信源的原始符号按照一定的数学规则进行的一种变换。S:{S仁—信源编码器2,…，州}?X:{X1,X2,・・・，Xr}Figured:信源编码器楔?増鶴寸7養巳鹦应的亀貉黠誇N的信源符号序列)变换成曲组成Wio?编码的一些基本槪-这种码符号序列Wi称为码字；长度称为码字长度简称码长；全体码字的集合C称为码。-若码符号集合为X二{0,1},则所得

3、的码字都是二元序列，称为二元码或二进码O-若一个码中所有码字的码长都相等，则称为等长码；否则为变长码。-若一个码中无重复码字，则称为非奇异码；否则为奇异码。-若码符号集合中每个码符号所占的传输时间都相同，则所得的码称为同价码。-若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯一可译码。若某个唯一可译码在译码时无需参考后续的码符号即时码；否则断，将码符号序列译成相应的信源符号序列。则称此码为为非即时码。即时码巒为逗点码、非延长码。2定长无失真信源编码?对一个信源进行定长编码

4、时每个信源符号所需要的二进制符号个数(码长)将由信源符号的个数唯一决定：L>Ho(X)=log2

5、KIIDefinition1.X的原始编码鳌定义为:Ho(X)=log2IKII(1)?当信源符号个数正好是2的幕次时,可以得到数L=Ho(X)；?否则L=?Ho(X)?0此时实际码长略大于信源的最大嫡，效率离，可以通过对信源进行扩展的方法来提高编码效率。?另一种提高编码效率的手段为近似无失真编码。?无失真编码可分为严格无失真和近似无失真两种熾?严格无失真编码是一个信源符号到码字的一一映射；而近似无失真

6、舸将一些不同的信源符号映射为相同的码字，因此一旦信源真的产生了这些被淆的信源符号，就会产生一次译码失败。我们通胡来表示信源产生被混淆的符号的概率。当&足够小时，这种近似无失真的编码滋:瞬生产中也就可以近似认为是无失真的了。Example2.给定一8符号信源：[[]aX_bcde4§]h-=111311114441664646464P(X)当要求&二0时对此信源进行二进制等长编码，每个信源符号豁3个二进制码符号,即L二3bit.我们注意到Pr{se{a,b,c,d}}=15/16,因此如果我们愿意承饮

7、6的译码失败概率的话，就可以将信源的転个符号忽略，只对前个符号编码，此时L=2bit，信源得到了有效的压縮?为此，我们定义两个新的概念Definition3X的子集：（最小&充分子集）.X&为包含元素个数最少的、满足下述条件的、Pr{xg>1-6Definition4（基本编码容犀X的基本编码容地:H&X)=log2ft

8、,xn),其中xne{0,1},概率分布为po二0.9。令r(x)为序列X1的个数，则N-r(x)r(x)P(X)=P0P1为了策H&X)我仍绸确定相的Xe娥最小&充分子集将包含r(x)=0,1,2...直到rmax(^-1的所有序列和r(x)=5的的部分序列。下图给出了N=4和10以及N二10,210,410,610,810,1010时的基本编码容量和6的关系Figure3:基本编码容麵&的关系II〃儿讣)002040.6081Figure4:基本编码容麗N=10N=210Ns4102610N=B

9、1ON=1010&的关系III?由前面的三幅图可以看出，当N较小时H&X)的取值严重赖◎而当N足够大时，H&X)基本与6无关,且其值逼m(x).渐进等同分辔?没=X1X2…XN是离散无记忆信源输出的一个特定序列,则对?e>0,6>0,总可以找到一个整数No,使得当N?No时，有：{—JO9-PU-)}Pr(X)->1-8⑹<6N芻驛隣器霍亀WP(x)/Nf即长度N的符号序列中平?其中£和6的关系可以由弱大数定理得到：F耳⑺N5?我们将满足上述条件的序列集合狗典型列集合