第三章无失真离散信源编码

1、第三章 无失真离散信源编码13.1 基本概念信 源编 码 器信道基本符号(0、1)N个消息集合X=a、b、c z、空格N个代码组集合C=c1、 c2、cN23.1 基本概念信源编码是以提高通信的有效性为目的编码。 信源编码适合信道传输减少冗余度33.1 基本概念 由于信源编码可以不考虑抗干扰问题，所以由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。它的数学模型比较简单。43.1 基本概念l输入是信源符号集输入是信源符号集:l x为编码器所用的编码符号集，包含为编码器所用的编码符号集，包含r个元素个元素 ，称为，称为码符号码符号(码元码元) 。l由码符号由码符号 组成的输出序列组成的

2、输出序列 称为称为码字码字。 其长度其长度 称为称为码字长度码字长度或或码长码长，全体码字，全体码字 的集合的集合C称称为为码码或或码书码书 。l编码器将信源符号集中的编码器将信源符号集中的信源符号信源符号 （或长为（或长为N的信源的信源符号序列符号序列 ）变成由）变成由码符号码符号组成的长为的与信源符号一组成的长为的与信源符号一一对应的输出序列。即一对应的输出序列。即 :12 ,qSs ss ixrxxx,.,21iWiliWisi12(1,2, )(1,2, )(,), iiiiiilijs iqW iqxxxxX 若要实现若要实现无失真编码，无失真编码，必须这种映射必须这种映射是一一对应

3、的、是一一对应的、可逆的。可逆的。53.1 基本概念 (1) 二元码二元码和和r元码元码 若码符号集若码符号集 ，编码所得码字为一些，编码所得码字为一些适合在二元信道中传输的二元序列，则称适合在二元信道中传输的二元序列，则称二元码二元码。二元码是数字通信与计算机系统中最常用的一种二元码是数字通信与计算机系统中最常用的一种码。若码符号集共有码。若码符号集共有 r 个元素，则所得之码称为个元素，则所得之码称为 r 元码元码。0,1X 63.1 基本概念 (2) 基本源编码基本源编码和和N次扩展源编码次扩展源编码 (3) 无失真编码无失真编码 和和有失真编码有失真编码 数学上称为非奇异码和奇异码，数

4、学上称为非奇异码和奇异码，若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。 (4)惟一可译码惟一可译码和和非惟一可译码非惟一可译码 若任意一串有限长的码符号序列只能被惟一地译成所若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为对应的信源符号序列，则此码称为惟一可译码惟一可译码（或称（或称单单义可译码义可译码）。否则就称为非惟一可译码或非单义可译码。）。否则就称为非惟一可译码或非单义可译码。 若要使某一码为惟一可译码，则对于任意给定的有限若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。长的码符号序列，只能被惟

5、一地分割成一个个的码字。73.1 基本概念 例如例如：对于二元码：对于二元码 ，当任意给定一，当任意给定一串码字序列，例如串码字序列，例如“10001101”，只可唯一地划，只可唯一地划分为分为1,00,01,1,01，因此是惟一可译码；而对另，因此是惟一可译码；而对另一个二元码一个二元码 ，当码字序列为，当码字序列为“01001”时，可划分为时，可划分为0,10,01或或01,0,01，所以，所以是非惟一可译的。是非惟一可译的。11,01,00C 20,10,01C 83.1 基本概念 (5) 定长码定长码和和变长码变长码 若一组码中所有码字的长度都相同若一组码中所有码字的长度都相同-（即（

6、即 ），则称为等长码。），则称为等长码。,1,ill iq 信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p (s2)0101s3p (s3)10001s4p (s4)111019符号符号 码码A码码B码码C码码D码码E码码Fa 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011d 10 11 11 111 0001 0111103.2 离散无失真信源编码定理1、数据压缩的途径、数据压缩的途径 途径一：使序列中的各个符号尽可能地互相途径一：使序列中的各个符号尽可能地互相独立，即解除相关性，独立，即解除相关性，去冗余；去冗

7、余； 途径二：使编码中各个符号出现的概率尽可途径二：使编码中各个符号出现的概率尽可能地相等，即能地相等，即概率均匀化概率均匀化。 2、数据压缩的理论极限、数据压缩的理论极限113.2 离散无失真信源编码定理1. 平均码长平均码长 设信源有设信源有N个单符号消息个单符号消息x1，x2，xN，变长码编码器输出的代码组长度对应为变长码编码器输出的代码组长度对应为l1, l2, , lN ，其出现概率分别为其出现概率分别为 P(s1) , P(s2), P(sN)，则该变长码的平均长度为则该变长码的平均长度为1()NiiiLP slCode/sign123.2 离散无失真信源编码定理2. 编码后的信息

8、传输率编码后的信息传输率（1）等长码的信息传输速率：对单符号离散信源，设其信源熵为）等长码的信息传输速率：对单符号离散信源，设其信源熵为H(X)，对其进行等长编码，每码字对其进行等长编码，每码字l个码元，故其信息传输速率为个码元，故其信息传输速率为 R=H(X)/l( )/RHLX（2）变长码的信息传输速率：对单符号离散信源，设其信源熵为）变长码的信息传输速率：对单符号离散信源，设其信源熵为H(X)，对其进行等长编码，每码字对其进行等长编码，每码字l个码元，故其信息传输速率为个码元，故其信息传输速率为bit/codebit/code133.2 离散无失真信源编码定理3. 编码效率编码效率 信源

9、编码器输出代码组的信息传输速率与信道容量信源编码器输出代码组的信息传输速率与信道容量之比，称为信源编码器的编码效率。即之比，称为信源编码器的编码效率。即( )loglogRRH xCrLr143.2 离散无失真信源编码定理例1： 设离散无记忆信源概率空间为 信源熵： H ( X ) = 1/4 log4 +3/4 log3/4 = 0. 811 bit / 信源符号 若用二元定长编码 (0,1) 来构造一个即时码： 平均码长： 二元码符号 / 信源符号 编码效率： 输出的信息传输率：11L 1( )0.811logH xLr1( )0.811H xRLLbit/code153.2 离散无失真信

10、源编码定理再对长度 L 为 2 的信源序列进行 变长编码，其即时码如表： 码字平均长度： 单个符号的平均码长 编码效率 输出的信息传输率： R2 0.961bit/ 二元码符号 L2L2/ 227/32LL163.2 离散无失真信源编码定理编码复杂一些，但信息传输率有了提高 定长编码： 要求编码效率达到 96 时，允许译码错误概率 10 5 173.2 离散无失真信源编码定理1819 定理中的公式改写成定理中的公式改写成l 不等式左边表示长为不等式左边表示长为L的码符号序列能载荷的最的码符号序列能载荷的最大信息量，大信息量，l右边代表长为右边代表长为N的信源序列平均携带的信息量。的信源序列平均

11、携带的信息量。 所以定长编码定理告诉我们：只要码字传输所以定长编码定理告诉我们：只要码字传输的信息量大于信源携带的信息量，总可实现几乎的信息量大于信源携带的信息量，总可实现几乎无失真编码。无失真编码。20例题结论：定长编码简单，但要达到一定的差错率不易实现，且编码效率低。21( )( )1loglogH SH SLrr 对离散无记忆信源，消息长度为N，符号熵为H(S),对信源进行r元变长编码，一定存在无失真的信源编码方法2 码字平均长度码字平均长度 不能小于极限值不能小于极限值 ，否则唯一可译码不，否则唯一可译码不存在。存在。 定理给出平均码长的上界，但并不是说大于上界不能构成唯定理给出平均码

12、长的上界，但并不是说大于上界不能构成唯一可译码，而是我们希望一可译码，而是我们希望 尽可能短。尽可能短。 定理给出紧致码的最短平均码长，并指出这个最短的平均码定理给出紧致码的最短平均码长，并指出这个最短的平均码长与信源熵是有关的。长与信源熵是有关的。LrSHlog)(L2223如何分离码字？1001110？要求：码是唯一可译要求：码是唯一可译243.2.3码字唯一可译条件延时码即时码可分离唯一可译码非唯一可译码非奇异码奇异码码)(25判断以下码字是否可分离？例例3.2.2263.2.3码字唯一可译条件即时码的一种简单构造方法是即时码的一种简单构造方法是树图法树图法。对于给定码字的全体集合对于给

13、定码字的全体集合C，可用，可用码树码树来描述它。来描述它。所谓所谓树树，既有根、枝，又有节点。，既有根、枝，又有节点。n图中最上端图中最上端A点为点为根根，从根出发，从根出发向下伸出树枝，树枝的数目等于向下伸出树枝，树枝的数目等于码符号的总数码符号的总数r。n树枝的尽头为树枝的尽头为节点节点，从节点出发，从节点出发再伸出树枝，每次每个节点伸出再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树。枝，依次下去构成一棵树。273.2.3码字唯一可译条件n在下图中，当某一个节点被安在下图中，当某一个节点被安排为码字后，就不再继续伸枝，排为码字后，就不再继续伸枝，此节点称为此节点称为终端节点终端节点（

14、用粗黑点（用粗黑点表示）。表示）。n其他节点称为其他节点称为中间节点中间节点，不安，不安排为码字（用空心圈表示），给排为码字（用空心圈表示），给每个节点所伸出的树枝分别从左每个节点所伸出的树枝分别从左向右标上码符号向右标上码符号0，1，r。283.2.3码字唯一可译条件任一即时码都可用任一即时码都可用树图法树图法来表示。来表示。当码字长度给定时，即时码不是唯一的。当码字长度给定时，即时码不是唯一的。在每个节点上都有在每个节点上都有r个分枝的树称为个分枝的树称为整树整树（满树满树），），否则称为否则称为非整树非整树（非满树非满树）。）。rllllr当当 元元 节的码树的所有树枝都被用上时，第节的

15、码树的所有树枝都被用上时，第 阶节阶节点共有点共有 个终端节点，正好对应于长度为个终端节点，正好对应于长度为 的等长码，的等长码，可见等长码也是即时码的一种。可见等长码也是即时码的一种。29即时码的树图结构树与编码的关系树根码的起点树枝码的进制数节点码字或其部分终结点码字节数码长满树等长码非满树变长码0120120120120123.2.3码字唯一可译条件30克拉夫特不等式lr元长度为li的异前置码存在的充要条件是11inlir3.2.3码字唯一可译条件313.2.3码字唯一可译条件 Kraft不等式不等式是惟一可译码存在的是惟一可译码存在的充要条件充要条件， 必要性表现在如果码是惟一可译码，

16、则必定满必要性表现在如果码是惟一可译码，则必定满足足Kraft不等式不等式;充分性表现在如果满足充分性表现在如果满足Kraft不等式，则这种码不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码。不等式的码一定是惟一可译码。 因此，克拉夫特不等式是惟一可译码因此，克拉夫特不等式是惟一可译码存在存在的充要的充要条件，而不是惟一可译码的充要条件。条件，而不是惟一可译码的充要条件。323.2.3码字唯一可译条件 例例：设二进制码树中：设二进制码树中X= ， ， ， ，对应，对应的的 ， ， ， ，由上述定理，可得，由

17、上述定理，可得因此不存在满足这种码长的唯一可译码。因此不存在满足这种码长的唯一可译码。18922222322141ili22l11l34l23l4a3a1a2a333.2.3码字唯一可译条件a1=1 0 1 0 1 0 1a2=01a3=001a4=000 1，01，001，000 惟一可译码；惟一可译码； 1，01，101，000 不是惟一可译码；不是惟一可译码； 均满足克劳夫特不等式均满足克劳夫特不等式122222332141iKi343.2.3码字唯一可译条件 注意注意：不满足克拉夫特不等式的码，一定不是唯一：不满足克拉夫特不等式的码，一定不是唯一可译码。码长满足克拉夫特不等式的码，也不

18、一可译码。码长满足克拉夫特不等式的码，也不一定是唯一可译码。定是唯一可译码。 克拉夫特不等式只是说明唯一可译码是否克拉夫特不等式只是说明唯一可译码是否存存在在，并不能作为一种码制是否是唯一可译码的判，并不能作为一种码制是否是唯一可译码的判断依据。断依据。353.3 香农编码香农编码niinnxpxpxpxpxxx121211)(,)(.)()(.设有离散无记忆信源362log()iip al1234香农编码方法的步骤香农编码方法的步骤按信源符号的概率从大到小的顺序排队按信源符号的概率从大到小的顺序排队)(.)()(21napapap100)()() 1)(, 0)(jiijajaapapiij

19、apap累加概率个码字的表示第用令计算各信源符号的计算各信源符号的自信息量自信息量。编码码长应该大于自信息量。编码码长应该大于自信息量。5累加概论二进制化，取给定码长，得到累加概论二进制化，取给定码长，得到编码码字编码码字。3738香农编码香农编码例： 有一单符号离散无记忆信源 39 香农码的平均码长香农码的平均码长 信源熵 编码效率 为提高编码效率，可把 x 4 x 5 换成前面的节 点，可减小平均码长。 不应先规定码长，而是由码树来规定码 字，可得更好的结果。 L2logLRrLN( )78%H xR书例书例3.3.105. 01 . 015. 02 . 025. 025. 0)(6543

20、21xxxxxxXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制香农码。试对该信源编二进制香农码。3.3 香农编码香农编码40123456()0.2502000.250.252010.20.531000.150.731010.10.85411010.050.95511110ajipxlxxxxxx编码过程编码过程10)()(jiijaxpxp（1）码字码字4161()2.7iiiLp x l2logLRrLN42. 2)(XH%63.89)(RxH3.3 香农编码香农编码423.4 3.4 费诺编码费诺编码对概率按r进行分组，使每组概率尽可能相等给每个分组分配一个码

21、元对每个分组重复2、3步，直到不可分为止1234按信源符号的概率从大到小的顺序排队12()().()np ap ap a不妨设43概率匹配概率匹配 443.4 3.4 费诺编码费诺编码L( )H xR453.4 3.4 费诺编码特点费诺编码特点1) 费诺编码在构造费诺编码在构造码树码树时，是从树根开始到终端节时，是从树根开始到终端节 点结束；点结束； 2) 由于赋码元时的任意性，因此编出的码字不唯一；由于赋码元时的任意性，因此编出的码字不唯一； 3) 费诺编码虽属于费诺编码虽属于概率匹配概率匹配范畴，但并未严格遵守范畴，但并未严格遵守 匹配规则，有时出现概率小的码长反而小。因此匹配规则，有时出

22、现概率小的码长反而小。因此 平均码长一般不会最小。平均码长一般不会最小。 费诺码比较适合于费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源，特的信源，特 别是对每次别是对每次分组概率都相等的信源分组概率都相等的信源进行编码时，可达进行编码时，可达 到理想的编码效率。到理想的编码效率。 46例： 对该信源进行二 进制费诺编码。 平均码长： 编码效率：1L =2.12L =2.005. 010. 015. 02 . 025. 025. 0)(654321aaaaaaXPX设有一单符号离散无记忆信源设有一单符号离散无记忆信源试对该信源编二进制费诺码。试对该信源编二进制费诺码。书例书例3

23、.4.1NoImage3.4 3.4 费诺编码费诺编码471a2a3a4a5a6a25. 025. 02 . 015. 01 . 005. 0001010011000110110111011111编码过程48)/(42325.2)(signbitXH2logLRrN%91.98)(RxH61()2.45(/)iiiLp a lbitsign 可以看出本例中费诺码有较高的编码效率。可以看出本例中费诺码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。费诺码比较适合于每次分组概率都很接近的信源。3.4 3.4 费诺编码费诺编码4900000111111a2a3a4a5a6a50将信源符

24、号按概率由大到小顺序排队给两个概率最小的符号各分配一个码位，将其概率相加后合并作为一个新的符号，与剩下的符号一起，再重新排队给缩减信源中概率最小的符号各分配一个码元重复步骤2、3直至概率和为121433.5 3.5 赫夫曼编码赫夫曼编码51从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 552例：试对该信源编二进制哈夫曼码。试对该信源编二进制哈夫曼码。 读取码字的时候，要从后向前读，此 时编出来的码字是可分离的即时码。 5353平均码长平均码长 信源熵信源熵 H(X) = H (0.2,0.19,0.18,0.17,0.15,0.1,0.01)=2.61 bit/ 符

25、号符号 编码效率编码效率 L( )H xR541) 哈夫曼编码在构造码树时，是从端点开始直到树 根结束； 2) 哈夫曼编码采用概率匹配方法来决定各码字长度， 概率大的符号对应于短码，概率小的符号对应与长 码，充分利用了短码，从而使平均码长最小； 3) 哈夫曼编码时，缩减信源的最后二个码字总是最 后一位不同，从而保证了哈夫曼码是即时码。 3.5 3.5 赫夫曼编码特点赫夫曼编码特点设有一单符号离散无记忆信源试对该信源编二进制哈夫曼码。书例书例3.5.105. 010. 015. 02 . 025. 025. 0)(654321aaaaaaXPX5515. 03 . 00.450.55000001

26、111105. 010. 015. 02 . 025. 025. 01a2a3a4a5a6a101101100100000001000000005a编码过程56()2.42325(/)H Xbit sym2.45L( )98.91%H xR573,2.5585312.7L若采用定长编码，码长则编码效率 可见，哈夫曼编码的效率提高了。58Huffman码的编码方法不是唯一的首先:每次对缩减信源两个最小的符号分配“0”和“1”码元试任意的;其次:若合并后的新符号的概率与其他符号的概率相等，这几个符号的次序可任意排列;一般将合并的概率放在上面，这样可获得较小的码方差。说明：说明：59例例 设有离散无

27、记忆信源设有离散无记忆信源1 . 01 . 02 . 02 . 04 . 0)(54321xxxxxXPX用两种不同的方法对其编二进制huffman码60方法一方法一方法二方法二61信源符号信源符号xi概率概率p(xi)码字码字Wi1码长码长Ki1码字码字Wi2码长码长Ki2x10.411002x20.2012102x30.20003112x40.1001040103x50.1001140113两种不同的编码方法得到的码字和码长的对比62平均码长和编码效率平均码长和编码效率63码字的码长方差比较码字的码长方差比较64可以看出第二种编码方法的码长方差要小许多,码长变化较小，比较接近平均码长。要求

28、：Huffman编码时应使合并的信源符号位于缩减信源序列尽可能高的位置上，码长变化较小，比较接近平均码长，易于实现。结论：结论：65663.5 3.5 赫夫曼编码赫夫曼编码m 进制哈夫曼编码 在编 m 进制哈夫曼码时，为了使短码得到充分利用， 使平均码长最短，必须使最后一步的缩减信源有 m 个 信源符号。 缩减次数 每次缩减所减少 的信源符号个数 信源符号数 n 应满足：不满足时：设q个概率为 0 的信源符号，使q+n 满足要求 第一次对最小概率符号分配码元时只取 (m-q) 个，分别 配以 0,1, m-q-1 ，把这些符号的概率相加作为一个新 符号的概率，与其它符号一起重新排列。以后每次取

29、 m 个符号，分别配以 0,1, m-1；如此下去，直至所有 概率相加得 1 为止，即得到各符号的 m 进制码字。 673.5 3.5 赫夫曼编码赫夫曼编码m 进制哈夫曼编码 例 试对该信源编三进制哈夫曼码。 m =3 ， n =8 无法满足 n = s ( m -1) + m s =3 ， q =1 q + n = s ( m -1) + m 第一次取 m - q =2 个符号进行编码 683.5 3.5 赫夫曼编码赫夫曼编码m 进制哈夫曼编码 693.5 3.5 赫夫曼编码赫夫曼编码m 进制哈夫曼编码 平均码长 编码效率 L( )H xR70简单讨论简单讨论 T：0.072 O：0.065

30、4 A：0.063 N：0.059 I：0.055 R：0.054 S：0.052 V：0.008 K：0.003 X：0.002 J、Q：0.001 Z：0.001英文各个字符的统计概率如下：71简单讨论简单讨论1、编码效率：、编码效率：Shannon码码：码长码长:3-11,平均码长平均码长: 4.602bit/sym,效率效率：0.895Fano码码：码长码长:3-11,平均码长平均码长: 4.168bit/sym,效率效率：0.989Huffman码码：码长码长:3-10,平均码长平均码长: 4.156bit/sym,效率效率：0.9922、编码思路：、编码思路：Shannon码码：自

31、信息：自信息Fano码码：等概划分：等概划分Huffuman码码：从概率最小的符号开始：从概率最小的符号开始三种编码的比较Huffman:不唯一，但对信源没有特殊要求，且编码效率较高，设备要求简单，综合性能优于另外两种。相同点：三种编码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使平均码长缩短，实现了信源压缩。不同点：shannon：有唯一的编码，但编码效率不是很高；Fano:编码方法不唯一，适合与分组概率相等或相近的信源；723.6 游程编码73 前面的几种编码方法主要时针对无记忆信源，对有前面的几种编码方法主要时针对无记忆信源，对有记忆信源，这些编码方法的效率并不高，特别是对二记忆信源，这些编码方法的效率并不高，特别是对二元相关信源，需要