讲义41信源编码讲解

1、信息论课程讲义第四章 信源编码4-1 离散信源的信源编码通信的根本目的就是有效而可靠地传输信息。 Shannon 信息论中的一个重要内容就是它 给出了信息传输的有效性和可靠性的极限能力。具体表现为两个编码定理；一般称为 Shannon 第一编码定理(信源编码定理，有效性编码定理)和Shannon 第二编码定理(信道编码定理，抗干扰编码定理) 。4-1-1 编码器 (Encoder)我们前面考虑的信源都是离散化的信源， 实际上没有考虑到编码的问题。 编码的作用可 以分为以下编两点：一些原始信源的符号不适应信道的传输； 原始信源符号的传输效率很低； 码器可以看作这样一个系统，它的输入端为原始信源S

2、，其符号集为 S:s1,s2, ,sn；si(i=1,2, ；n)而信道所能传输的符号集为 A:a 1,a2, ,aq；编码器的功能是用符号集 A 中的 元素，将原始信源的符号 si变换为相应的码字符号 Wi，(i=1,2, ,n，) 所以编码器输出端的 符号集为 W:W 1,W2, ,Wn 。S=原始信源符号集；A= 码元符号集；W=码字符号集； (码组)编码器S:s1,s2, snW:W 1,W2, WnA:a 1,a2, aqWi=w 1,w2, wLi wi a1,a2, aqLi 为码字 Wi 的码元个数，称为码字 Wi 的码字长度，简称码长。q=2 时，称为二元编码，否则称为 q

3、元编码。4-1-2 单义可译码 (Uniquely decodable code)(1) 单义可译码定义：如果一个码组的任一有限长的码字序列 (一串码字) ，只能唯一地被译成一个一个码字， 则称为单义可译码，也称为异前置码。例如： S: s1,s2,s3; A:0,1; W: w1=0, w2=10, w3=11, 为单义可译码。当接收码字序列为： 10011001111 时，可以唯一地译为： w2,w1,w3,w1,w1,w3,w3; 如果码字集合为： W:0,01,11 则为非单义可译码。当接收码字序列为： 10011001111 时，可以译为： x,w1,w1(w2) (2) 瞬时可译码

4、(非续长码)定义： 如果一个码组中的任一个码字都不是另一个码字的续长，或者说， 任何一个码字后加上若干码元后都不是码组中另一个码字。则称为瞬时可译码，也称为非续长码。例如： W：0，10，100，111不是瞬时可译码， 100 为 10的续长。 瞬时可译码一定是单义的，单义可译码却不一定是瞬时可译码。例如： W：0 ， 01是单义的，但不是瞬时可译码。4-1信息论课程讲义(3) 单义可译码定理： 设原始信源符号集为 S:s1,s2, sn， 码元符号集为 A:a1,a2, ,aq，码字集合为 W:W1,W2, Wn ，其码长分别为 L1,L2, ,Ln；则单义可译码存在的充要条件为码长组合 满

5、足 Kraft 不等式，即nq L i1i1Kraft 不等式不仅是单义可译码的充要条件，也是瞬时可译码的充要条件； 这里所说的充要条件是对于码长组合而言，而不是对于码字本身而言，就是说：满 足 Kraft 不等式的码长组合一定能构成单义码，单义码的码长组合一定满足 Kraft 不等式。有些码字的码长组合满足 Kraft 不等式，但不是单义码。 (编码方法不对) 下面看一个例子：n=4, q=2 A:0,1信源符号W1W2W3W4W5W6s10000000s2011011101001s30111101001101110s40111111011011111011W1: 满足 Kraft 不等式，

6、但只是单义的，不是瞬时可译码；码长组合为1,2,3,4；W2: 满足 Kraft 不等式，是单义的，也是瞬时可译码；码长组合为1,2,3,4；W3: 满足 Kraft 不等式，不是单义的，也不是瞬时可译码；码长组合为1,2,3,3；W4: 满足 Kraft 不等式，是单义的，也是瞬时可译码；码长组合为1,2,3,3；W5: 不满足 Kraft 不等式，不可能为单义的；码长组合为1,2,2,3；W6: 满足 Kraft 不等式，是单义的，也是瞬时可译码；为等长码；(4) 用码树图构成瞬时可译码从根开始，画出 q 条分支，任选一个分支作为 W1 ； 在另一个分支上再分出 q 条分支，任选一个分支作

7、为 W2；继续进行，直至结束； 从根到各端点，所经过的状态即为码字；例如： A:0,1, q=2, W:W1,W2,W3,W4根根这种方法构成的瞬时可译码是不唯一的； 码树图可以用于译码，有根，枝，节点等概念；同样可以用于 q 元编码； 例： S:s1,s2, s9,A=0,1,2, q=34-2信息论课程讲义W1=0;W5=20; W9=222;W2=10;W6=21;W3=11;W7=220;W4=12;W8=221;4-1-3 平均码子长度如果一个码组的参数满足 Kraft 不等式，就一定可以构成无噪声信道下的无失真传输， 然而， 在一个通信系统中， 信源编码的主要目的是提高编码效率，

8、即每个码元符号要携带更 多的信息量。因此要定义平均码长的概念。设原始信源的信源空间为S,P=s1s2snp(s1)p(s2)p(sn)n其中： p ( si )aq进行编码，得单义可译码 W ：W1 ，W2，Wn 。相 ,。n)则这个信源编码的平均码长为：nLp(si )Lii1 这时看一下信息传输效率：每个信道码元所携带的平均信息量。 当信源 S给定，信源的熵为 H(S) ，则每个信道码元所携带的平均信息量可以表示为H (S)R H (X)A;a1,a2,Li,(i=1,2,i1 对此信源用码元符号集 应得码字长度分别为：L可见，当原始信源一定时，编码后的平均码长越小，信道传信率越高，编码效

9、率越高。编码效率可以用平均码长来描述； 每个码字的长度应当与对应的信源符号的先验概率有关。为了提高编码效率，总希望平均码长越小越好，但平均码长能否无限小呢？ 定理 : 平均码长极限定理 若一个离散无记忆信源 S的熵为 H(S)，对其进行 q 元编码， A:a1,a2, aq，则总可以 找到一种无失真的编码方法，构成单义可译码，使其平均码长满足：H ( S ) H ( S ) L1 log q log q对于常用的二元编码来说：H(S) LH(S)+1下界证明 根据平均码长和熵的定义有4-3信息论课程讲义H(S) Llog qp ( si )log p(si) p(si)Li log qi 1

10、i 1np(si)log i1np(si )log i1nlog q Lii1由单义可译码的存在定理可知，当满足np(si )p( si ) log( q Li )i1Liqlogp(si )Lini 1 p(si ) pq(si )q-Li1 时，取对数后为小于等于0。则有：H(S)-Llogq 0L H(S)/logq 下界证毕。平均码长最小不能小于极限值，H(S)/logq ，若小于，则不存在单义可译码；当下界等号成立时，效率最高时，为-Lip(si)=q可得：Lilog p(si) log qlogq p(si) log q1p(si)当然这要求信源符号的先验概率满足其是以q 为底的对

11、数为整数， 这就要求信源符号的先验概率为 p(si)=q -Li 形式，如果满足这一条件，编出的码字称为最佳码。例如： S:s1,s2,s3,s4; P(S):1/2,1/4,1/8,1/8 时，编码后码长为 1,2,3,3 ，这时平均码长将 为 L=H(S)=1.74 码元 / 符号。 上界证明 我们考察在满足 Kraft 不等式的条件下，平均码长满足下界。 设每个码字的平均码长在以下区间取正整数。(i1, 2 ,. n)log q p(si) Li log q p(si ) 1考虑到对数为单调递增函数，则有：1 Liqp ( si )qp ( si )( i1,2 ,.,n)进而有：对上式

12、的p( si) q Lii 连续取和：np(si )i1p( si)qni1Li(ini11,2 ,., np(si )q即：这表明这样选择每个码元的码长可以满足n1i1Kraft 不等式，然后对所有的Liqi 相加，得 :4-4信息论课程讲义n n np(si)Li p( si )log q p(si) p(si)i 1 i 1 i 1即H (S)L H q(S) 1 1q log q上界证毕。平均码长大于这个上界当然也可以构成单义可译码，但实际上总希望码长小； 当一个离散无记忆信源得统计特性确定后，信源熵就确定了，平均编码长度下界也 就确定了，编码效率也就确定了，如果进一步提高效率，就要想

13、其它方法。下面得 编码定理给出了方法。4-2 编码定理以下是 Shannon 编码定理的三种形式。它们是进一步提高编码效率的极限定理。 定理一 ：离散无记忆信源 S 的 N 次扩展信源 SN ，其熵为 H(SN)，并且编码器的码元 符号集为 A:a 1,a2, aq ，对信源 SN 进行编码， 总可以找到一种编码方法， 构成单义可译码， 使信源 S中每个符号 si 所需要的平均码长满足：lim L Hq(S)Nq说明：H(SN)=NH(S) ，根据平均码长的界限定理有：H(SN ) LH(SN ) 1L N 1log q log qLN为 N次扩展信源每个符号的平均码长，原始信源的每符号的平均

14、码长则为LNL则上式可以变为：即得：NH(SN ) LNH(SN ) 1N log qNN log q NH (S)H (S) 1Llog qlog q N当离散无记忆信源S 的扩展次数 N 足够大时，有lim LNH(S) log qHq(S)定理一表明当将离散无记忆信源进行 N 次扩展后再进行编码，就可以使原始信源每 个符号的平均码长接近信源熵 H(S) ，即达到下限值。这时就不要求原始信源的先验概率满足特殊条件了， 但却要求扩展次数 N 趋于无穷。 因此，这也是一个极限定理， (给出一种不现实的方法) 。 定理二 ：离散平稳各态历经有记忆信源 S 的 N 次扩展信源 S=S 1,S2,

15、SN ，其熵为 H(S)= H(S1,S2, SN)，并且编码器的码元符号集为 A:a1,a2,aq，对信源 S进行编码，总 可以找到一种编码方法，构成单义可译码，使信源S 中每个符号所需要的平均码长满足：4-5信息论课程讲义lim LNlog qH ( S )1log q 1H ( S)N log q可以注意到：对于平稳各态历经有记忆信源来说， 每发一个符号携带的平均信息量等于其极限熵。1lim H(S1,S2,.SN) lim H(SN 1 / S1, S2,.SN ) HN N N又考虑到 lim(1/N)=0 ，可知：LNNH ( S) N log q 当信源稳定后，即当N 趋于无穷时

16、，已知 N 次扩展信源的熵为 H(S)=H(S 1,S2, ,SN)，根据平均的界限定理，H ( S )LNlog q将上式除以 N 得：Hlim L N log qH(S)H，所以，有记忆信源的平均码长的下界将小于H =Hm+1(S) ，则有：H m 1比较定理一和定理二，由于 无记忆信源的平均码长的下界； 对于 m 阶马尔柯夫信源来说；lim N log q即，记忆长度越长，平均码长的下界就越小。定理一和定理二说明：可以用信源扩展的方法，达到数据压缩的目的，扩展程度越 高，编码效率越高。定理三 ：设信源 S 的熵为 H(S)，无噪声离散信道的信道容量为 C。则总可以找到一 种编码方法，使信

17、道上的信源符号平均传输速率为C/H(S)- 。其中可以是任意小的正数。要使符号平均传输速率大于 C/H(S) 是不可能的。关于编码定理的说明 ：在编码前， 离散无噪声信道的信道容量为 C，C=r0Hmax(S)，Hmax(S)为信源的最大熵， r 为符号传输速率， C=H max(S) ，相当于 r0=1。在编码前， 离散无噪声信道的实际熵速率为 R=r0H(S) ，这时的符号传输速率就等于 r0，单位是原始信源符号数 /每秒。这时的传输效率(编码效率) ：实际传输能力 /最大传输能力，为： =R/C=H(S)/H max (S)对于 n 个符号的原始信源，如果不进行编码就相当于n 元编码，其

18、最大熵为Hmax(S)=logn; 传输效率(编码效率) =R/C=H(S)/H max(S)=H(S)/logn 。 编码后，每个原始信源符号 si 编成了 Li 个信道码元组成的码字 Wi 。编码器的输出 可以看成一个新的信源，它有 q 个信源符号(信道码元) ，每个信道码元所携带的 信息量为 H(S)/L 。如果将这个新信源记为 A ，则 H(A)=H(S)/L ，如果信道码元的符 号速率为 n1，则信道的实际熵速率为 R=r 1H(A)=r 1H(S)/L 。 编码器输出的码元符号集共有 q个元素，这个新信源的最大熵为当 q 个信道码元符 号为等概率时，即 Hmax(A)=logq ，

19、信道容量为 C=r1Hmax(A) 。4-6信息论课程讲义这时编码器输出端的传输效率(编码效率)为： =R/C=H(A)/H max(A)=H(S)/LH max(A)=H(S)/Llogq当 q=2 时，为二元编码， logq=1; 传输效率就为： =R/C=H(S)/L 。 这时从另一个角度，我们看一下编码定理中定义的符号传输速率，它是指原始信源 符号的传输速率：即每秒传输的原始信源符号的个数。实际符号传输速率为：为 r0=R/H(S) ( 比特/秒)/(比特/符号)=(信源符号 /秒) 有： r0=R/H(S) C/H(S);编码定理指出：总可以有方法使 R 趋进于 C，并构成单义可译码

20、， 实际上等效于： L 趋于 H(S)/logq 。或者说：编码后的编码效率趋于 1。由平均码长界限定理可知，要构成单义可以码，平均码长有一个下界：H (S )Llog q结合这两个关系，可以得到：单义可译码的信道码元符号在离散无噪声信道上的熵速率(传信率)就相应有一个上界；H (S)H (S)LH (S)log qlog q我们知道 logq 是信道码元符号集 A:a1,a2, a的q最大熵， 也就是将 A 看作信源时， 在离散无噪声信道上的信道容量 C，所以有：RC这就是说，要编成单义可译码，就不可能使信道传信率(熵速率)大于信道容量。关于 Shannon 编码第一定理：定理一、 定理二和

21、定理三实际上是同一个定理， 定理一和定理二是针对一个具体的信源 形式， 而定理三是一个概括性的。 这个定理称为无失真信源编码定理， 也称为无噪声信道编 码定理。例 4-1：有一个离散无记忆信源， S:s1,s2, P(S):0.2, 0.8, 其原始信源熵为： H(S)=1/5log5+4/5log(5/4)=0.72193 bit/ 信源符号 (si) 用二元信道码元符号 A:0,1 进行编码，得到码字 W:W1=0, W2=1, 这时的平均码 长为： L=0.2 1+0.81=1 信道码元符号 /信源符号。这时的信道传信率：R=H(S)/L=0.72193 比特 /信道码元符号。对这个信源

22、进行二次扩展，得到 S2，对其进行二元编码，得 W:W 1,W2,W3,W4 。SiP(Si)WiS1=S1S11/25000S2=S1S24/25001S3=S2S14/2501S4=S2S216/251这时的平均码长为：L2=(16/25)1+(4/25)2+(4/25)3+(1/25)3=37/27 信道码元符号 /2 个信源符号 则相应的原始信源每个信源符号的平均码长L=L 2/2=37/50 信道码元符号 /信源符号4-7信息论课程讲义这时的信道传信率为R=H(S)/L=0.72193/(37/50)=0.97 比特 /信道码元符号。 可以看到：经过信源的二次扩展，编码复杂一点，但使

23、传信率(编码效率)明显提高， 可知二元编码的信道容量为 1比特 /码元，当扩展次数增加时，传信率将无限接近信道容量。4-3 Huffman 编码上面我们看到， 通过无失真信源编码可以使信道传信率无限接近于信道容量， 为了评价 信源编码的好坏，定义一个参数称为编码效率：RC编码效率是一个小于等于 1 的参数，当然编码效率越高越好，只要保证是单义可译码。 当编码效率等于 1 时称为最佳码。4-3-1 Shannon-Fano 算法(1) Shannon 编码思想： 由于概率的不均匀， 使编码效率下降， 因此， 可以根据消息状态的概率来确定各码字的 编码长度，概率大的编成短码，概率小的编成长码。最初

24、的 Shaanon 编码算法是一种简单的按概率编码的方法，对于一个离散无记忆信源， 如果其某一状态 si 的先验概率为 p(si)，则就取其码长为：1Li logp(si)其X符号表示为取不小于 X 的整数，即11log Li log 1p(si) p(si )W2=10W3=110其实这种方法是满足 Kraft 不等式的一种直接的应用； 例如：一个离散信源 S:s1,s2,s3,s4 p(S):1/2,1/4,1/8,1/8 这时有： L1=log2=1; L2=log4=2; L3=L4=log8=3; 利用码树图的方法可以得到其编码：W4=111这个例子可以验证其编码效率为下是不能实现最

25、佳码的，而且编码效率比较低。1，即为最佳码。但可以发现，这种方法对于多数情况这种算法称为 Shannon算法；后来提出了一种改进方法为 Shannon-Fano 算法。(2) Fano 算法的步骤： 把原始信源的符号按概率从大到小重新排列； 把信源符号按尽可能概率相等分为q 组，分别分配给 a1,a2, aq码元； 将每个分组再次分组，直至分完； 从左至右将分得的码元排列即得码字Wi 。4-8信息论课程讲义 算法举例 ：设有一个离散无记忆信源 S；其信源空间为：S: s1 s2 s3 s4 s5 s6 s7 s8p(S): 0.1 0.18 0.4 0.05 0.06 0.1 0.07 0.0

26、4 可知这个原始信源的熵为：H(S)=- p(si)logp(si)=2.55 bit/ 原始信源符号。 而这时的最大熵为： Hmax(S)=log8=3 bit/ 原始信源符号。 编码效率为 =R/C=H(S)/H max(S)=2.55/3=85% 。利用 Shannon-Fano 算法编码：sip(si)第一次第二次s30.4000s20.1801s10.1010s60.1010s70.0711s50.0611s40.0511s80.0411第三次第四次WiLi00201201003110130011004011101410111041111114这时可以用码树图描述：注意： 1，0 码

27、元分配是任意的，因此编码的结果是不唯一的；0/1 分配的上下顺序也是不唯一的，能构成不同的单义可译码；(3) 关于编码效率编码前信源熵为 H(S) ，最大熵为 Hmax(S)，熵速率为 R=rH(S) ，信道容量为 C=rH max(S)； 这时的编码效率为：R H ( S )11 C H max ( S )编码后一个信源状态 si对应于一个码子 Wi，Wi 的码长为 Li ， W 的平均码长为 L， 一个码元的熵为 H(A)=H(S)/L ，其最大熵为 Hmax(A)=logq ，熵速率和信道容量分别为 R=rH(S)/L, C=rH max(A) 。这时的编码效率为：R H (A) H(

28、A)0 C Hmax(A) log q对于二元编码 q=2， Hmax(A)=log2=1 ，同时考虑到 H(S)与 H(A) 的关系，有4-9信息论课程讲义L由于 L 总是大于等于 H(S) ，因此编码效率总是小于 1。当 L 趋于 H(S) 时，编码效率也 趋于 1。编码效率趋于 1的过程，就是 L 趋于 H(S) ，和 R 趋于 C 的过程。 看这个例题的编码效率： 其平均码长为 L=2.64 信道码元 /信源符号。 H(S)=2.55 bit/ 信源符号。所以H(S)9.66%R H 2( A) H ( S) C H 2 max ( A ) L可见编码效率得到提高。如果将信源做 n 次

29、扩展后再进行编码，可以进步提高编码效率。4-3-2 Shannon-Fano 算法的最佳条件同样是上面的例子，如果我们将原始信源改变一下，信源空间为：S: s1s2s3s4s5s6s7s8p(S): 1/4 1/4 1/8 1/8 1/16 1/16 1/16 1/16 可知这个原始信源的熵为： H(S)=- p(si)logp(si)=2.75 bit/ 原始信源符号。 而这时的最大熵为： Hmax(S)=log8=3 bit/ 原始信源符号。编码效率为 =R/C=H(S)/H max(S)=2.75/3=91.7% 。利用 Shannon-Fano 算法编码：sip(si)第一次第二次第三

30、次第四次WiLis11/400002s21/401012s31/81001003s41/81011013s51/16110011004s61/16110111014s71/16111011104s81/16111111114这时的平均码长为 L= p(si)Li=2.75 信道码元 /信源符号。编码效率为： =H(S)/L=2.75/2.75=1 ， 表明 R=C。4-3-3 Huffman 算法这种算法比 Shannon-Fano 算法的效率还要高，称为最佳编码算法。(1) 二元 Huffman 算法的步骤 将信源 S 的 n 个符号状态 s1,s2, sn按 概率从大到小排列，作为码树图的

31、叶； 将概率最小的两个符号分别分配给“ 0”和“ 1”码元，然后其概率相加，合成一个节 点，作为一个新的符号，重新与其它符号按概率大小排列； 重复这样的步骤，一直到处理完全部状态； 从右到左将分配的码元排列后即得相应得编码。 算法举例 ：将上一题的信源编为 Huffman 编码。设有一个离散无记忆信源 S；其信源空间为：4-10信息论课程讲义S: s1 s2s3s4s5s6p(S): 0.1 0.180.4 0.050.060.1可知这个原始信源的熵为：H(S)=- p(si)logp(si)=2.55 bit/原始信源符号。而这时的最大熵为： Hmax(S)=log8=3 bit/ 原始信源

32、符号。 编码效率为 =R/C=H(S)/H max(S)=2.55/3=85% 。利用 Huffman 算法编码：s7s80.070.041.0编码结果：W3=1W2=001W1=011W6=0000 平均码长 L=2.61W7=0100W5=0101W4=00010W8=00011码元 /状态。编码效率为R H 2( A) H (S) 2.55C H 2 max ( A ) L 2.6197 .8%可见 Huffman 编码比 Shannon-Fano 编码可以得到更高的编码效率。同样：S:s1s2s3s4s5s6p(S):0.240.200.180.160.140.081/0 码元分配是任

33、意的，因此编码的结果是不唯一的；但 0/1 分配的上下顺序在整个编码过程中应保持一致，否则不能构成单义可译码； (2) q 元 Huffman 算法 首先我们看一个例子；设离散信源的信源空间为：对其进行 q=3,A:0,1,2 编码。如果按二元 Huffman 编码的方法LiWisi222222101112202122s1s2s3s4s5s60.62 10.38 24-11S(3)01.0信息论课程讲义可知：平均码长为 L=2 码元 /信源符号。 下面我们看一下一种改进方法： 还是这一个信源，我们在 6 个信源符号的后面再加一个概率为0 的符号，记为 s7同,时有 p(s7 )=，0这个符号称为虚假符号。将信源按7个符号进行三元编码。LiWisip(s