信息论与编码结业论文

1、信息论与编码论文之信源编码 Sylvia 通过对信息论与编码这门课程的学习，我了解到，通信的根本问题是将信源的输出在接收端精确地或近似地重现出来。为此需要解决两个问题。一是信源的输出应如何描述，即如何计算它产生的信息量。另一个是如何表达信源的输出，即信源编码的问题。这两个问题都与信宿对通信质量的要求有关。若要求精确的地重现信源的输出，就要保证信源产生的全部信息无损地递送给信宿，这时的信源编码就是无失真源编码。在很多实际情况下，人们并不要求完全精确地复制出信源的输出，而且在有干扰情况下传输时，要精确地复制信源的输出也是不可能的。不同的信宿对精确度的要求是不同的，例如在电话通信中，有的只要求可懂度

2、足够高就满意了，而有的如广播系统则要求语调和音色也要好，即还要求有足够高的清晰度才行。图像通信中，军用电视和传真电报只传送地图、公文等，而电视广播是为了欣赏而要求更高的质量。一般一对信源-信宿要定出可接收准则或保真度准则。准则定了之后，就可以计算为达到这一要求至少要保留多少有关信源输出的信息量，以及如何表达它们。这就是限定失真的信源编码问题。1信源及其分类信源就是信息的发源地，可以是人、生物、机器或其他事物。信源的具体输出称作消息，它或为离散的符号形式，如人写出的书信，文稿、计算机输出的代码等；或为连续的信号，如人发出的语音、遥感器测得的连续数据等。前者被称作离散信源，后者称为连续信源，相应的

3、输出称作离散消息和连续消息。 由信息量的定义知道，信息中之所以含有信息是由于信源的产生消息的随机性。为此，要研究信源产生信息的大小，必须先研究信源的统计特性。 离散信源的输出可用符号序列 U-2 U-1 ,U0, U1 U2, 表示，其中Ul表示在第l时刻产生的符号，l为整数。Ut为一随机变量，它在有限字母A=a,，ak中选取。这里假定信源匀速地产生符号，若各Ul彼此统计独立，相应信源就称无记忆信源，否则称为有记忆信源。 实际中信源常常是有记忆的，很少能用简单的概率空间来表述。对于有记忆的信源，需要用联合概率空间描述，信源输出可用随机序列或L维随机矢量UL=(u1,u2，uL) Ul 表示，L

4、为正整数。概率分布P(uL =a)=P（u1,u 2,uL）=（ak1,ak2,，akL），其中kl(l,K)。 连续信源的输出是连续随机变量或连续随机过程。前者称作时间离散的连续源，其输出为连续随机变量序列U-1，U0，U1 其中每个随机变量Ul的取值为一连续区间，如(a,b）即xA(a,b),其中a和b为实数，且ba。连续随机变量的概率密度以p（u）表示，若信源是有记忆的，就用连续随机矢量及相应的联合概率密度表示。 若信源输出在时间上也是连续的，则用随机过程U（t）描述，称作随机波形源。一个在时间上或频率上为有限的随机过程可以展开成为分量取值为连续的随机矢量表示，一个时间上连续的信源就被化

5、为离散信源了。 若信源输出既有连续分量，又有离散分量时，就称为混合信源。 2. 等长码与等长信源编码定理 设有一个离散无记忆信源，以DMS表示，其字母表为A=a1,a2,，aK,各字母的概率为P1，且概率和为。长为的信源输出序列（，）有的次幂种不同的排列。所谓编码，就是从消息集到码字集上的一种映射。等长码与等长信源编码定理一般说来，若要实现无失真的编码，不但要求信源符号si (i1,2,q)与码字Wi (i1，2，q )是一一对应的，而且要求码符号序列的反变换也是惟一的。也就是说，所编的码必须是惟一可译码。如果所编的码不具有惟一可译码性，就会引起译码错误与失真。对于等长码来说，若等长码是非奇异

6、码，则它的任意有限长N次扩展码一定也是非奇异码。因此等长非奇异码一定是惟一可译码。如果对信源S 的N次扩展信源进行等长编码。设信源S=s0,s1,sq，有q个符号，那么它的N次扩展信源共有qN个符号。又设码符号集为Xx0,x1,xr。现在需要把这些长为N的信源符号序列ai (i1,2,., qN)变换成长度为l的码符号序列Wi。对于任意给定的0，只要满足条件 N/M(H(U)+)/logL ，那么,当M足够大时,上述编码几乎没有失真;反之,若这个条件不满足，就不可能实现无失真的编码。式中H(U) 是信源输出序列的符号熵。3.离散无记忆信源的变长编码定理（仙农第一定理）具体实现唯一可译变长编码的

7、方法很多，但比较经典的方法还是仙农编码法、费诺编码法和霍夫曼编码法。其他方法都是这些经典方法的变形和发展。所有这些经典编码方法，都是通过以短码来表示常出现的符号这个原则来实现概率的均匀化，从而得到高的信息载荷效率；同时，通过遵守克拉夫特不等式关系来实现码字的唯一可译。这个定理是香农信息论中非常重要的一个定理，它指出，要做到无失真的信源编码，信源每个符号所需要的平均码元数就是信源的熵值，如果小于这个值，则唯一可译码不存在，可见，熵是无失真信源编码的极限值。定理还指出，通过对扩展信源进行编码，当N趋向于无穷时，平均码长可以趋进该极限值。 若离散无记忆信源的输出符号序列为， 式中 Ak|k=1,K,

8、符号熵为H(U)，对U进行唯一可译的变长编码，编码字母表B的符号数为L,即B=bl|l=1,L,那么必定存在一种编码方法，使编出的码字Vi(vi1,viNi)，(i=1,V)，具有平均长度嚻： MH(U)/logL嚻MH(U)/logL+1 。若L=K，则当H(U)logKlogL时,必有嚻M；H(U)离logK越远，则嚻越小于M。4.最佳不等长编码Huffman编码是Humffman曾给出的一种编码方法，所得到的码是异字头码，其平均长度最短，是一种最佳码，一般称作Huffman编码。Gomolob曾对它进行改进，使之更加实用。对于给定信源，存在最佳唯一可译二元码，其最小概率的两个码字Ck-1

9、和CK的长度最长且相等，它们之间仅最后一位码元取值不同（一个为0，另一个为1）。对辅助集U为最佳的码，对原始消息集U也是最佳的。Shannon编码不保证概率打的消息一定比概率小的消息用较短的码字，例如，a4的概率小于a2 和a3，但所用的码字却比它们的短。Huffman编码能确保概率大的消息不会比概率小的消息采用更长的码字，所以效率较高。 Shannon-Fano 编码5.算数编码算术编码是图像压缩的主要算法之一。 是一种无损数据压缩方法，也是一种熵编码的方法。和其它熵编码方法不同的地方在于，其他的熵编码方法通常是把输入的消息分割为符号，然后对每个符号进行编码，而算术编码是直接把整个输入的消息

10、编码为一个数，一个满足(0.0 n < 1.0)的小数n。1968年前后，P.Elias发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1967年J.Rissanen提出了算数编码。算术编码的主要思想是计算输入信号源符号序列所对应的区间，然后在区间中任取一点，以其二进制表示适当截断作为序列的编码结果。设信源符号集A=a1,a2,，ak,其相应的概率分布为P（ak）, P（ak）>0(k=1.2,，K)。定义信源符号的分布函数F（ak）=P(ai), ai,akA,其中F（a1）=0. F（ak

11、）将0，1区间分为了K个子区间，每个区间的宽度为P（ak）。算数编码的译码过程就是一系列的比较过程，每一步比较S-F(ui)与P（ui）F(ui+1)的大小，ui为前面已经译出的序列串，F（ui）是ui的分布函数，即ui对应区间的下界，P（ui）F(ui+1)是此区间内下一个输入符号ui+1 所占区间的宽度，对K元信源，译每一个码元最多需要K-1次比较以确定ui+1 是A=a1,a2,，ak中的哪一个。6.LZ编码上述两种信源编码方法都需要精确地知道信源的概率分布，它们对于实际分布与假设分布的偏差很敏感。一旦信源的实际分布与假设的分布有差异，编码性能会急剧下降。但是在实际应用过程当中，确切的获

12、得信源统计特性有事是非常困难的。因此是否存在编码方法，与信源的统计特性无关，只要R>H(U),当编码长度充分大时，错误率可以任意小。这种编码称为通用信源编码。1965年苏联数学家Kolmogolov提出利用信源序列的结构特性来编码。而两位以色列研究者J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的通用压缩算法。将这些算法统称为LZ系列算法。LZ系列算法用一种巧妙的方式将字典技术应用于通用数据压缩领域，而且，可以从理论上证明LZ系列算法同样可以逼近信息熵的极限。设信源符号集Aa1.a2,，ak共K

13、个符号，设输入信源符号序列为u（u1,u2,uL）编码时将此序列分成不同的段。分段的规则为：尽可能取最少个相连的信源符号，并保证各段都不相同。开始时，先去一个符号作为第一段，然后继续分段。若出现与前面相同的符号时，就再取紧跟后面的一个符号一起组成一个段，使之与前面的段不相同。这些分段构成字典。当字典达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号，以便与字典中短语不同，直至信源符号序列结束。这样，不同的段内的信源符号可看成一短语，可得到不同段所对应的短语字典表。编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M（u）个。若编码为二元码，段号所需码长n=log

14、 M（u）（注：代表上取整符号），每个符号需要的码长为log K。单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。7.马尔可夫源多数信源是有记忆的，即当前信源产生的消息符号常与前一时刻产生的消息符号有关。如英语中字母q之后出现了字母u的概率接近于1，而其他字母出现的概率接近于0。为了描述这种关系常引入“状态”概念。信源产生消息符号与信源所处的状态有关。设信源有J个可能的状态，以1,2，J表示，在每一个状态下可能出现的字母为a1,a2,，ak。信源在某个特定状态下每单位时间产生一个特定消息符号，并且当此消息符号产生后就转入一个新的状态。信源输出符号随机序列为u1，

15、u2，ul，马尔可夫性表示为：对任意的0n1<n2<<nl<m, n>0,i0,i1,i2,，i(n-1)i,jE (1)Px(n)=in|x(0)=i0,x(1)=i1,.,x(n-1)=i(n-1)=Px(n)=in|x(n-1)=i(n-1)讨论了以上类型编码后，离散源无失真编码的主要问题有，第一，各种离散源的统计描述及其信源产生一个字母平均给出的信息量，即熵的计算；第二，如何对离散信源输出的字母进行表示，即编码方法；第三，编码所能到达的理论最佳限，即平均每个信源字母所需要的最小码元数目，这由各种信源的编码定理给定。离散无记忆信源的熵值H（U）=H1(U)=H(U)=- P(ak)logP(ak)，平稳源的熵为H（U）=limH(Ul|U1,U2,，UL)=H（U|U），遍历马尔可夫源的熵为H（U）=QiH（U|s1=i）,离散源编码方法有二，一是等长编码，二是不等长编码。等长编码下，信源字母的平均错误概率趋近于0.若源是各态经历的，则长为L的消息序列以概率近于1为典型序列，其自信息量为LH（U）。只要采用NlogD=LH(U)+就能实现任意小的译码错误概率。不等长编码下，可以精确的恢复原来的消息。各态历经源时，设采用不等长编码，若对信源输出L个字母为一组进行编码，