信息论与编码原理-信源编码

第5章信源编码编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。一般称无失真信源编码定理为第一极限定理；信道编码定理（包括离散和连续信道）称为第二极限定理；限失真信源编码定理称为第三极限定理。第5章信源编码由于信源符号之间存在分布不均匀和相关性，使得信源存在冗余度，信源编码的主要任务就是减少冗余，提高编码效率。第5章信源编码信源编码的基本途径有两个：使序列中的各个符号尽可能地互相独立，即解除相关性；使编码中各个符号出现的概率尽可能地相等，即概率均匀化。第5章信源编码信源编码的基础是信息论中的两个编码定理：无失真编码定理限失真编码定理∆无失真编码只适用于离散信源∆对于连续信源，只能在失真受限制的情况下进行限失真编码第5章信源编码本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。5.1编码的定义信源编码器信道码表图5-1信源编码器示意图5.1编码的定义信源编码是指信源输出符号经信源编码器编码后转换成另外的压缩符号无失真信源编码：可精确无失真地复制信源输出地消息5.1编码的定义将信源消息分成若干组，即符号序列xi，xi＝(xi1xi2…xil…xiL)，xilA={a1，a2，…，ai，…，an}每个符号序列xi依照固定码表映射成一个码字yi，yi＝(yi1yi2…yil…yiL)，yilB={b1，b2，…，bi，…，bm}这样的码称为分组码，有时也叫块码。只有分组码才有对应的码表，而非分组码中则不存在码表。5.1编码的定义如图5-1所示，如果信源输出符号序列长度L＝1，信源符号集A(a1，a2，…，an)信源概率空间为)()()(2121nnapapapaaaPX若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码5.1编码的定义码可分为两类：一、固定长度的码，码中所有码字的长度都相同，如表5-1中的码1就是定长码二、可变长度码，码中的码字长短不一，如表中码2就是变长码。5.1编码的定义不同的码符号序列，如表5-1所示。表5-1变长码与定长码信源符号ai信源符号出现概率p(ai)码表码1码2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)111115.1编码的定义（1）奇异码和非奇异码若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。如表5-2中的码1是奇异码，码2是非奇异码。5.1编码的定义表5-2码的不同属性信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/81101100000015.1编码的定义（2）唯一可译码任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码5.1编码的定义唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。5.1编码的定义即时码：只要收到符号就表示该码字已完整，可以立即译码。即时码又称为非延长码，任意一个码字都不是其它码字的前缀部分，有时叫做异前缀码。5.1编码的定义码奇异码非分组码分组码非奇异码非唯一可译码非即时码即时码(非延长码)唯一可译码5.1编码的定义通常可用码树来表示各码字的构成010101010101010101010101010101二进制码树5.1编码的定义012012012012012012三进制码树5.1编码的定义唯一可译码存在的充分和必要条件各码字的长度Ki应符合克劳夫特不等式：11niKim－5.1编码的定义例：设二进制码树中X(a1，a2，a3，a4)，K1＝1，K2＝2，K3＝2，K4＝3，应用上述判断定理：18922222322141iKi因此不存在满足这种Ki的唯一可译码。5.1编码的定义a1=1010101a2=01a3=011a4=000{1，01，001，000}惟一可译码；{1，01，101，000}不是惟一可译码；均满足克劳夫特不等式122222332141iKi5.1编码的定义克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。5.2无失真信源编码信源输出X＝(X1X2…Xl…XL)，Xl{a1，a2，…，ai，…，an}编码为Y＝(Y1Y2…Yk…YkL)，Yk{b1，b2，…，bj，…，bm}。要求能够无失真或无差错地译码，同时传送Y时所需要的信息率最小5.2无失真信源编码Yk平均每个符号的最大信息量为logmKL长码字的最大信息量为KLlogm则传送一个信源符号需要的信息率平均为MLmLKKLlog1logLKmM5.2无失真信源编码所谓信息率最小，就是找到一种编码方式使最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真的译码？若小于这个信息率是否还能无失真地译码K5.2无失真信源编码无失真的信源编码定理定长编码定理变长编码定理5.2无失真信源编码定长编码定理K是定值且惟一可译码5.2无失真信源编码由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1X2…Xl…XL，可用KL个符号Y1，Y2，…，Yk，…，（每个符号有m种可能值）进行定长编码。对任意0，0，只要则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，而L足够大时，译码几乎必定出错)(logXLLHmLK2)(logXLLHmLK5.2无失真信源编码定长编码定理说明，)()(logXXHLHmKLL码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。5.2无失真信源编码反之，当时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。)(XLHK)(XLHK5.2无失真信源编码式中为自信息方差为一正数。当和均为定值时，只要L足够大，Pe可以小于任一正数。即，22)(LPeX})]()({[)(22XxXHIEi)(2X222)(LX5.2无失真信源编码当信源序列长度L满足时，能达到差错率要求22)(XL22)(LPeX5.2无失真信源编码在连续信源的情况下，由于信源的信息量趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。5.2无失真信源编码定义为编码效率，即信源的平均符号熵为H(X)，采用平均符号码长为来编码，所得的效率。编码效率总是小于1，且最佳编码效率为KHL)(XK0,)()(XXLLHH5.2无失真信源编码编码定理从理论上阐明了编码效率接近1的理想编码器的存在性，它使输出符号的信息率与信源熵之比接近于1，即L取无限长1log)(mLKHLLX5.2无失真信源编码例设离散无记忆信源概率空间为比特/符号04.005.006.007.01.01.018.04.087654321aaaaaaaaPX＝55.2log)(81iiippXH5.2无失真信源编码对信源符号采用定长二元编码，要求编码效率为90％，若取L＝1，则可算出＝2.5590%=2.8比特/符号Pe＝0.04太大＝K5.2无失真信源编码28.0,90.0)()(XHXH＝228122)(82.7)]([)(log)]([)(bitXHppxIDXiiii若要求译码错误概率610－87622210108.91028.082.7)(XL5.2无失真信源编码变长编码定理在变长编码中，码长K是变化的根据信源各个符号的统计特性，如概率大的符号用短码，概率小的用较长的码，使得编码后平均码长降低，从而提高编码效率。（统计匹配）5.2无失真信源编码单个符号变长编码定理：若离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式1log)(log)(mXHKmXH5.2无失真信源编码离散平稳无记忆序列变长编码定理：对于平均符号熵为HL(X)的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率满足不等式其中为任意小正数。)()(XXLLHKH5.2无失真信源编码用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。5.2无失真信源编码编码效率总是小于1，可以用它来衡量各种编码方法的优劣。为了衡量各种编码方法与最佳码的差距，定义码的剩余度为KXHmLKXHLLL)(1log)(115.2无失真信源编码例设离散无记忆信源的概率空间为414321aaPX5.2无失真信源编码符号/811.034log434log41)(bitXH若用二元定长编码(0，1)来构造一个即时码：。平均码长＝1二元码符号/信源符号1,021aaK5.2无失真信源编码编码效率为811.0)(KXH输出的信息效率为R＝0.811比特/二元码符号5.2无失真信源编码长度为2的信源序列进行变长编码（编码方法后面介绍），其即时码如下表aip(ai)即时码a1a19/160a1a23/1610a2a13/16110a2a21/161115.2无失真信源编码322722KK162731613163216311692＝＋＋＋K二元码符号/信源序列二元码符号/信源符号5.2无失真信源编码961.027811.0322编码效率信息效率R2＝0.961比特/二元码符号5.2无失真信源编码L＝3R3＝0.985比特/二元码符号L＝4R4＝0.991比特/二元码符号985.03991.045.2无失真信源编码定长二元码编码，要求编码效率达到96％时，允许译码错误概率510－222122)(4715.0)]([)(log)(bitXHppXiii752221013.41004.0)96.0()811.0(4715.0＝－L5.2无失真信源编码最佳变长编码凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合称为最佳变长码。5.2无失真信源编码能获得最佳码的编码方法主要有：香农（Shannon）费诺（Fano）哈夫曼（Huffman）等5.2无失真信源编码香农（Shannon）编码将信源消息符号按其出现的概率大小依次排列确定满足下列不等式的整数码长Ki。nppp211loglog22iiipKp－5.2无失真信源编码3.为了编成唯一可译码，计算第i个消息的累加概率4.将累加概率Pi变换成二进制数。5.取Pi二进数的小数点后Ki位即为该消息符号的二进制码字。11ikkiapP5.2无失真信源编码例设信源共7个符号消息，其概率和累加概率如下表所示。5.2无失真信源编码信源消息符号ai符号概率(ai)累加概率Pi-logp(ai)码字长度Ki码字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.64711111105.2无失真信源编码14.3)(71iiiKapK码元/符号831.014.361.2)(KXHR比特/码元5.2无失真信源编码费诺编码方法费诺编码属于概率匹配编码(1)将信源消息符号按其出现的概率大小依次排列：。(2)将依次排列的信源符号按概率值分为两大组，使两个组的概率