讲义41信源编码

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

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

3、de)(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是单义的，但不是瞬时可译码。(3) 单义可译码定理：设原始信源符号集为S:s1,s2,sn，码元符号集为A:a1,a2,aq，码字集合为W:W1,W2,Wn，其码长分别为L1,L2,Ln；则单义可译码存在的充要条件为码长组合满足Kraft不等式，即 § Kraft不等式不仅是单义可译码的充要条件，也是瞬时可译码的充要条件；§ 这里所说的充要条件是对于码长组

5、合而言，而不是对于码字本身而言，就是说：满足Kraft不等式的码长组合一定能构成单义码，单义码的码长组合一定满足Kraft不等式。§ 有些码字的码长组合满足Kraft不等式，但不是单义码。（编码方法不对）下面看一个例子：n=4, q=2 A:0,1信源符号W1W2W3W4W5W6s10000000s2011011101001s30111101001101110s40111111011011111011§ W1:满足Kraft不等式，但只是单义的，不是瞬时可译码；码长组合为1,2,3,4；§ W2:满足Kraft不等式，是单义的，也是瞬时可译码；码长组合为1,2,3

6、,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条分支，任选一个分支作为W2；§ 继续进行，直至结束；§ 从根到各端点，所经过的状态即为码字

7、；例如：A:0,1, q=2, W:W1,W2,W3,W4 根 根 0 1 1 0 W1 0 1 W1 1 0 W2 W2 0 1 1 0 W3 W4 W3 W4§ 这种方法构成的瞬时可译码是不唯一的；§ 码树图可以用于译码，有根，枝，节点等概念；§ 同样可以用于q元编码；例：S:s1,s2,s9,A=0,1,2, q=3 0 2 W1 1 2 2 W9 0 0 1 0 1 W2 1 2 W5 W6 W8 W3 W4 W7W1=0; W5=20; W9=222;W2=10; W6=21;W3=11; W7=220;W4=12; W8=221;4-1-3 平均码子长

8、度如果一个码组的参数满足Kraft不等式，就一定可以构成无噪声信道下的无失真传输，然而，在一个通信系统中，信源编码的主要目的是提高编码效率，即每个码元符号要携带更多的信息量。因此要定义平均码长的概念。设原始信源的信源空间为S,P=s1s2snp(s1)p(s2)p(sn)其中：对此信源用码元符号集A;a1,a2,aq进行编码，得单义可译码W：W1，W2，Wn。相应得码字长度分别为：Li,(i=1,2,n)。则这个信源编码的平均码长为：这时看一下信息传输效率：每个信道码元所携带的平均信息量。当信源S给定，信源的熵为H(S)，则每个信道码元所携带的平均信息量可以表示为可见，当原始信源一定时，编码后

9、的平均码长越小，信道传信率越高，编码效率越高。§ 编码效率可以用平均码长来描述；§ 每个码字的长度应当与对应的信源符号的先验概率有关。为了提高编码效率，总希望平均码长越小越好，但平均码长能否无限小呢？定理: 平均码长极限定理若一个离散无记忆信源S的熵为H(S)，对其进行q元编码，A:a1,a2,aq，则总可以找到一种无失真的编码方法，构成单义可译码，使其平均码长满足：对于常用的二元编码来说： H(S)L<H(S)+1 下界证明根据平均码长和熵的定义有 由单义可译码的存在定理可知，当满足q-Li1时，取对数后为小于等于0。则有： H(S)-Llogq0 LH(S)/lo

10、gq下界证毕。§ 平均码长最小不能小于极限值，H(S)/logq，若小于，则不存在单义可译码；§ 当下界等号成立时，效率最高时，为p(si)=q-Li可得：当然这要求信源符号的先验概率满足其是以q为底的对数为整数，这就要求信源符号的先验概率为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不等式的条件下，平均码长满足下界。设每个码字的平均码长在以下区间取正整数。考虑到

11、对数为单调递增函数，则有：进而有： 对上式的i连续取和：即：这表明这样选择每个码元的码长可以满足Kraft不等式，然后对所有的i相加，得:即上界证毕。§ 平均码长大于这个上界当然也可以构成单义可译码，但实际上总希望码长小；§ 当一个离散无记忆信源得统计特性确定后，信源熵就确定了，平均编码长度下界也就确定了，编码效率也就确定了，如果进一步提高效率，就要想其它方法。下面得编码定理给出了方法。4-2 编码定理以下是Shannon编码定理的三种形式。它们是进一步提高编码效率的极限定理。 定理一：离散无记忆信源S的N次扩展信源SN，其熵为H(SN)，并且编码器的码元符号集为A:a1,

12、a2,aq，对信源SN进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号si所需要的平均码长满足：说明： H(SN)=NH(S)，根据平均码长的界限定理有：LN为N次扩展信源每个符号的平均码长，原始信源的每符号的平均码长则为则上式可以变为：即得： 当离散无记忆信源S的扩展次数N足够大时，有§ 定理一表明当将离散无记忆信源进行N次扩展后再进行编码，就可以使原始信源每个符号的平均码长接近信源熵H(S)，即达到下限值。§ 这时就不要求原始信源的先验概率满足特殊条件了，但却要求扩展次数N趋于无穷。因此，这也是一个极限定理，（给出一种不现实的方法）。 定理二：离散平

13、稳各态历经有记忆信源S的N次扩展信源S=S1,S2,SN，其熵为H(S)= H(S1,S2,SN)，并且编码器的码元符号集为A:a1,a2,aq，对信源S进行编码，总可以找到一种编码方法，构成单义可译码，使信源S中每个符号所需要的平均码长满足：已知N次扩展信源的熵为H(S)=H(S1,S2,SN)，根据平均的界限定理，将上式除以N得：可以注意到：对于平稳各态历经有记忆信源来说，当信源稳定后，即当N趋于无穷时，每发一个符号携带的平均信息量等于其极限熵。又考虑到lim(1/N)=0，可知：§ 比较定理一和定理二，由于H(S)H，所以，有记忆信源的平均码长的下界将小于无记忆信源的平均码长的

14、下界；§ 对于m阶马尔柯夫信源来说；H=Hm+1(S)，则有：即，记忆长度越长，平均码长的下界就越小。§ 定理一和定理二说明：可以用信源扩展的方法，达到数据压缩的目的，扩展程度越高，编码效率越高。定理三：设信源S的熵为H(S)，无噪声离散信道的信道容量为C。则总可以找到一种编码方法，使信道上的信源符号平均传输速率为C/H(S)-。其中可以是任意小的正数。要使符号平均传输速率大于C/H(S)是不可能的。关于编码定理的说明：§ 在编码前，离散无噪声信道的信道容量为C，C=r0Hmax(S)，Hmax(S)为信源的最大熵，r为符号传输速率，C=Hmax(S)，相当于r0

15、=1。§ 在编码前，离散无噪声信道的实际熵速率为R=r0H(S)，这时的符号传输速率就等于r0，单位是原始信源符号数/每秒。§ 这时的传输效率（编码效率）：实际传输能力/最大传输能力，为： =R/C=H(S)/Hmax(S)对于n个符号的原始信源，如果不进行编码就相当于n元编码，其最大熵为Hmax(S)=logn; 传输效率（编码效率）=R/C=H(S)/Hmax(S)=H(S)/logn。§ 编码后，每个原始信源符号si编成了Li个信道码元组成的码字Wi。编码器的输出可以看成一个新的信源，它有q个信源符号（信道码元），每个信道码元所携带的信息量为H(S)/L。如

16、果将这个新信源记为A，则H(A)=H(S)/L，如果信道码元的符号速率为n1，则信道的实际熵速率为R=r1H(A)=r1H(S)/L。§ 编码器输出的码元符号集共有q个元素，这个新信源的最大熵为当q个信道码元符号为等概率时，即Hmax(A)=logq，信道容量为C=r1Hmax(A)。§ 这时编码器输出端的传输效率（编码效率）为： =R/C=H(A)/Hmax(A)=H(S)/LHmax(A)=H(S)/Llogq 当q=2时，为二元编码，logq=1; 传输效率就为：=R/C=H(S)/L。§ 这时从另一个角度，我们看一下编码定理中定义的符号传输速率，它是指原始

17、信源符号的传输速率：即每秒传输的原始信源符号的个数。 实际符号传输速率为：为r0=R/H(S) (比特/秒)/(比特/符号)=(信源符号/秒) 有：r0=R/H(S)C/H(S);编码定理指出：总可以有方法使R趋进于C，并构成单义可译码，实际上等效于：L趋于H(S)/logq 。或者说：编码后的编码效率趋于1。§ 由平均码长界限定理可知，要构成单义可以码，平均码长有一个下界： § 结合这两个关系，可以得到：单义可译码的信道码元符号在离散无噪声信道上的熵速率（传信率）就相应有一个上界；§ 我们知道logq是信道码元符号集A:a1,a2,aq的最大熵，也就是将A看作信

18、源时，在离散无噪声信道上的信道容量C，所以有： RC§ 这就是说，要编成单义可译码，就不可能使信道传信率（熵速率）大于信道容量。关于Shannon编码第一定理：定理一、定理二和定理三实际上是同一个定理，定理一和定理二是针对一个具体的信源形式，而定理三是一个概括性的。这个定理称为无失真信源编码定理，也称为无噪声信道编码定理。例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

19、=0, W2=1,这时的平均码长为： L=0.2×1+0.8×1=1 信道码元符号/信源符号。这时的信道传信率： R=H(S)/L=0.72193 比特/信道码元符号。§ 对这个信源进行二次扩展，得到S2，对其进行二元编码，得W:W1,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个信源符号则相应的原始信

20、源每个信源符号的平均码长L=L2/2=37/50 信道码元符号/信源符号§ 这时的信道传信率为 R=H(S)/L=0.72193/(37/50)=0.97 比特/信道码元符号。可以看到：经过信源的二次扩展，编码复杂一点，但使传信率（编码效率）明显提高，可知二元编码的信道容量为1比特/码元，当扩展次数增加时，传信率将无限接近信道容量。4-3 Huffman编码上面我们看到，通过无失真信源编码可以使信道传信率无限接近于信道容量，为了评价信源编码的好坏，定义一个参数称为编码效率：编码效率是一个小于等于1的参数，当然编码效率越高越好，只要保证是单义可译码。当编码效率等于1时称为最佳码。4-3

21、-1 Shannon-Fano算法(1) Shannon编码思想：由于概率的不均匀，使编码效率下降，因此，可以根据消息状态的概率来确定各码字的编码长度，概率大的编成短码，概率小的编成长码。最初的Shaanon编码算法是一种简单的按概率编码的方法，对于一个离散无记忆信源，如果其某一状态si的先验概率为p(si)，则就取其码长为： 其X符号表示为取不小于X的整数，即 其实这种方法是满足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;利用码树图的方法可

22、以得到其编码： 0 W1=0 1 0 W2=10 1 0 W3=110 1 W4=111这个例子可以验证其编码效率为1，即为最佳码。但可以发现，这种方法对于多数情况下是不能实现最佳码的，而且编码效率比较低。这种算法称为Shannon算法；后来提出了一种改进方法为Shannon-Fano算法。(2) Fano算法的步骤：把原始信源的符号按概率从大到小重新排列；把信源符号按尽可能概率相等分为q组，分别分配给a1,a2,aq码元；将每个分组再次分组，直至分完；从左至右将分得的码元排列即得码字Wi。算法举例：设有一个离散无记忆信源S；其信源空间为：S:s1s2s3s4s5s6s7s8p(S):0.10

23、.180.40.050.060.10.070.04可知这个原始信源的熵为：H(S)=-p(si)logp(si)=2.55 bit/原始信源符号。而这时的最大熵为：Hmax(S)=log8=3 bit/原始信源符号。编码效率为=R/C=H(S)/Hmax(S)=2.55/3=85%。利用Shannon-Fano算法编码：sip(si)第一次第二次第三次第四次WiLis30.4000002s20.1801012s10.101001003s60.101011013s70.07110011004s50.06110111014s40.05111011104s80.04111111114这时可以用码树图

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

25、ax(A)。这时的编码效率为： 对于二元编码q=2，Hmax(A)=log2=1，同时考虑到H(S)与H(A)的关系，有由于L总是大于等于H(S)，因此编码效率总是小于1。当L趋于H(S)时，编码效率也趋于1。编码效率趋于1的过程，就是L趋于H(S)，和R趋于C的过程。看这个例题的编码效率：其平均码长为L=2.64 信道码元/信源符号。H(S)=2.55 bit/信源符号。所以可见编码效率得到提高。§ 如果将信源做n次扩展后再进行编码，可以进一步提高编码效率。4-3-2 Shannon-Fano算法的最佳条件同样是上面的例子，如果我们将原始信源改变一下，信源空间为：S:s1s2s3s

26、4s5s6s7s8p(S):1/41/41/81/81/161/161/161/16可知这个原始信源的熵为：H(S)=-p(si)logp(si)=2.75 bit/原始信源符号。而这时的最大熵为：Hmax(S)=log8=3 bit/原始信源符号。编码效率为=R/C=H(S)/Hmax(S)=2.75/3=91.7%。利用Shannon-Fano算法编码：sip(si)第一次第二次第三次第四次WiLis11/400002s21/401012s31/81001003s41/81011013s51/16110011004s61/16110111014s71/16111011104s81/1611

27、1111114这时的平均码长为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按概率从大到小排列，作为码树图的叶；将概率最小的两个符号分别分配给“0”和“1”码元，然后其概率相加，合成一个节点，作为一个新的符号，重新与其它符号按概率大小排列；重复这样的步骤，一直到处理完全部状态；从右到左将分配的码元排列后即得相应得编码。算法举例：将上一题的信源编为Huf

28、fman编码。设有一个离散无记忆信源S；其信源空间为：S:s1s2s3s4s5s6s7s8p(S):0.10.180.40.050.060.10.070.04可知这个原始信源的熵为：H(S)=-p(si)logp(si)=2.55 bit/原始信源符号。而这时的最大熵为：Hmax(S)=log8=3 bit/原始信源符号。编码效率为=R/C=H(S)/Hmax(S)=2.55/3=85%。利用Huffman算法编码：s3 0.4 1s2 0.18 1s1 0.1 (0.37) 0 1.0s6 0.1 0 (0.6) 0s7 0.07 0 (0.23) 1s5 0.06 1 (0.13) (0.

29、19) 0s4 0.05 0 (0.09) 1s8 0.04 1编码结果：W3=1 W7=0100W2=001 W5=0101W1=011 W4=00010W6=0000 W8=00011平均码长L=2.61 码元/状态。编码效率为可见Huffman编码比Shannon-Fano编码可以得到更高的编码效率。同样：§ 1/0码元分配是任意的，因此编码的结果是不唯一的；§ 但0/1分配的上下顺序在整个编码过程中应保持一致，否则不能构成单义可译码；(2) q元Huffman算法首先我们看一个例子；设离散信源的信源空间为：对其进行 q=3,A:0,1,2编码。S:s1s2s3s4s

30、5s6p(S):0.240.200.180.160.140.08如果按二元Huffman编码的方法 Li Wi si p(si) S(1) S(2) S(3) 0 0.62 1 1.0 0.38 0.38 2 2 10 s1 0.24 0.24 0 2 11 s2 0.20 0.20 1 2 12 s3 0.18 0.18 2 2 20 s4 0.16 0 2 21 s5 0.14 1 2 22 s6 0.08 2 可知：平均码长为L=2 码元/信源符号。下面我们看一下一种改进方法：还是这一个信源，我们在6个信源符号的后面再加一个概率为0的符号，记为s7,同时有p(s7)=0，这个符号称为虚假符号。将信源按7个符号进行三元编码。 Li Wi si p(si) S(1) S(2) S(3) 0.54 0 2 1 s1 0.24 0.24 0.24 1 1.0 0.22 0.22 2 2 00 s2 0.20 0.20 0 2 01 s3 0.18 0.18 1 2 02 s4 0.16 0.16 2 2 20 s5 0.14 0