第五章信源编码

一、通信系统的优化模型：n信源信源编码加密信道编码信源译码信道译码信道解密信宿密钥源噪声密钥源ULVLULSmCmXnYnC’mS’mVLK1K2信源编码目的：提高通信系统有效性，实现信源与通信系统间的统计匹配。语音、图像信源；—限失真信源编码，文字、文件信源；—无失真信源编码，分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例3.3】用{u1，u2，u3，u4}表示信源的四个消息，码符号集为{0,1}，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码信源消息各消息概率码1码2码3码4u1q(u1)000001u2q(u2)1101110u3q(u3)101000100u4q(u4)1111111000码的分类3.变长码若码字集合C中的所有码字cm(m=1,2,…,M)，其码长不都相同，称码C为变长码，表3-1中列出的码3、码4就是变长码。2.等长码在一组码字集合C中的所有码字cm(m=1,2,…,M)，其码长都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。一般，可以将码简单的分成如下几类：1.二元码若码符号集为{0，1}，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表3-1列出的4种码都是二元码。5.非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表3-1中的码2、码3和码4都是非奇异码。4.奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。例：1101104321ssss1s3s2s4s奇异码奇异码：若一组码中有相同的码字，则称为奇异码。01001004321ssss非奇异码0100001014321sssss010000102334ssss非奇异码：若一组码中所有码字都不相同，则称为非奇异码。6）唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。111001004321ssss等长码非奇异码000110114321ssss唯一可译如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。7非即时码：10001001014321ssss非奇异码110100100010?2s01不即时任何一个码字是其它码字的延长或前缀8.即时码对于变长码，又有如下定义定义3.2对于码字c=c1c2…cn,称c、=c1c2…ci(in)为码字c的字头（前缀）。定义3.3若码中任一码字都不是另一码字的字头，称该码为异字头码（无前缀码）。如果收到一个完整的码字以后，就可以立即译码，则叫做即时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。8即时码00010010114321ssss非奇异码1010010001任何一个码字不是其它码字的延长或前缀即时码012s即时即时码可用树图法来构造。图3-3用树图法编码树根编码深度u1：1u2：01u3：001u4：000110u1u2u3u411100【例】用树图法表示表3-2中的码3，如图3-3所示（D=2）。树----既有根、枝，又有节点,(如图所示)DABC000E11111010010001图5.2•二、码树：1、即时码的构造方法------树图法。A、B、C、D、E-----皆为节点，E-------终端节点。A、B、C、D----为中间节点中间节点不安排码字，而只在终端节点安排码字，每个终端节点所对应的码字----由根节点出发到终端节点走过的路径上所对应的符号组成},,,{21q对给定码字的全体集合来说，可以用码树来描述。最上端A-----根节点如图中的终端节点E，走过的路径为ABCDE，所对应的码符号分别为0、0、0、1，则E对应的码字为0001。•即时码：它可引用很直观的“码树”概念来说明：将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码§5.1.4信源编码常用的编码方法：香农码、费诺码、哈夫曼编码。使出现概率大的信源符号编码后码长尽量短一些。-------编码方法的出发点。最佳码定义：能载荷一定的信息量；且码字平均长度最短；可分离的变长码的码字集合。1.香农编码方法香农编码是采用信源符号的累计概率分布函数来分配码字。},,,{21qxxxX设信源符号集，并设所有的P(x)0，则香农编码方法如下：(1)将信源消息符号按其出现的概率大小依次排列：)()()(21nxpxpxp(2)确定满足下列不等式的整数码长iK1)(log)(log22iiixpKxp(3)为了编成唯一可以码，计算第个消息的累加概率i11)(ikkixpP(4)将累加概率变换成二进制数。iP(5)取二进制数的小数点后位，即为该消息符号的二进制码字。iPiK可以证明，这样得到的编码一定是唯一可译码，且码长比较短，接近于最佳编码。严格意义上来说不是最佳码。0.010.100.150.170.180.190.20符号概率信源消息符号1x2x3x4x5x6x7xix)(ixp例题：设信源共有7个符号组成，其概率如表所示，求其香农码。解：ix1x2x3x4x5x6x7xiPiK111111076.660.990.01111043.340.890.1010132.740.740.1510032.560.570.1701132.480.390.1800132.410.20.1900032.3400.20码字码字长度累加概率符号概率)(ixp)(log2ixp以为例，4i356.356.2117.0log17.0log44242KKK，因此即累加概率，变成二进制数，为0.1001…，57.0iP1〉码字长度计算2〉将pi转换为二进制数的方法码字为100可以看出，编码所得的码字是即时码（唯一可译码）。平均码长为：符号码元/14.3)(71iiiKxpK编码效率为831.014.361.2)(KXH香农编码的效率不高，实用意义不大，但对其它编码方法有很好的理论指导意义。香农编码方法特点：由于bi总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为0，故它对应的码字总是0、00、000、0…0的式样；码字集合是唯一的，且为即时码；先有码长再有码字；对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。评述•1)将信源符号以概率递减的次序排列起来，将排列好的信源符号分成两组，使每一组的概率之和相接近，并各赋予一个二元码符号“0”或者“1”；•2)将每一组的信源符号再分成两组，使每一小组的符号概率之和也接近相等，并又分别赋予一个二元码符号。•3)依此下去，直到每一个小组只剩下一个信源符号为止。•这样，信源符号所对应的码符号序列则为编得的码字。2.费诺编码方法费诺编码也不是最佳编码方法，但有时可以得到最佳编码。例题：信源符号及其概率仍如香农码中的例题所示。设信源共有7个符号组成，其概率如表所示，0.010.100.150.170.180.190.20符号概率信源消息符号1x2x3x4x5x6x7xix)(ixp编码过程及编码结果如下表所示消息符号符号概率第一次分组第二次分组第三次分组第四次分组二元码字码长x10.2000002x20.19100103x30.1810113x40.1710102x50.15101103x60.101011104x70.01111114可以求得，该费诺码的平均码长为符号码元/74.2)(71iiiKxpK编码效率为953.074.261.2)(KXH例题：离散无记忆信源及其符号概率分布如下表所示，求其费诺码。信源符号符号概率第一次分组第二次分组第三次分组第四次分组码字码长x11/400002X21/41012X31/81001003X41/811013X51/1610011004X61/16111014X71/161011104x81/16111114求费诺码的过程符号码元/75.2K符号/75.2)(bitXH码的平均长度为，信源的熵为是最佳码。原因是概率分布满足一定的条件。费诺编码特点：概率大，则分解的次数小；概率小,则分解的次数多。这符合最佳编码原则。码字集合是唯一的。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。费诺编码方法比较适合于每次分组概率都很接近的信源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。评述3.哈夫曼（Huffman）编码方法－－一种最佳的逐个符号的编码方法。一)编码步骤如下：)()()(21qxpxpxp1952年哈夫曼提出了一种构造最佳码的方法。(1)将q个信源符号按概率分布的大小，以递减次序排列起来，设(2)用“0”和“1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。(4)依此继续下去，直至信源只剩下两个符号为止。将这最后两个信源符号分别用“0”和“1”表示。(3)把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了q-2个符号的缩减信源。(5)然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。1.0:1.0:2.0:2.0:4.0:54321sssss014.02.02.02.0014.04.02.0016.04.00111w012w0003w00104w00115w1.01.02.02.04.0:][54321sssssPX例1：二）总结编码规则：•1)将信源消息U按概率大小排序（由大至小）。•2)从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。•3)将已编码两支路概率合并，重新排队，编码。•4)重复步骤3）直至合并概率归一时为止。•5)从概率归一端沿树图路线逆行至对应消息编码。编码效率为符号码元/72.2)(71iiiKxpK9596.072.261.2)(KXH例2：下表是一个哈夫曼编码的整个过程。信源符号符号概率编码过程码字码长0.201020.191120.1800030.1700130.1501030.10011040.01011141x2x3x4x5x6x7x0010.200.190.180.170.150.110.260.200.190.180.1701010.260.350.200.19010.350.260.39010.390.611其平均码长为例3：如下表是又一个哈夫曼编码的过程。信源符号符号概率编码2过程码字1码字2X10.4100X20.20110X30.200011X40.10010010X50.10011011000.40.20.20.210.40.40.2010.60.4011四、注意事项：原因：1）因为每次对缩减信源中两个概率最小的符号编码的时候，“0”和“1”的安排是任意的。2）当两个符号的概率相同的时候，排列的次序也是随意的，所以可能导致不同的编码结果，但最后的平均码长一定是一样的。2、在这种情况下，怎么样来判断一个码的好坏呢？2KiK引进码字长度偏离平均长度的方差，即qiiiiKKxpKKE1222))((])[(方差越小，说明各个码的