普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著1第5章 信源编码 编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真。一般称u无失真信源编码定理为第一极限定理；u信道编码定理（包括离散和连续信道）称为第二极限定理；u限失真信源编码定理称为第三极限定理。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著2第5章 信源编码由于信源符号之间存在分布不均匀和相关 性，使得信源存在冗余度，信源编码的主 要任务就是减少冗余，提高编码效率。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著3第5章 信源编码信源编码的基本途径有两个：n使序列中的各个符号尽可能地互相独立 ，即解除相关性；n使编码中各个符号出现的概率尽可能地 相等，即概率均匀化。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著4第5章 信源编码信源编码的基础是信息论中的两个编码定理：n无失真编码定理n限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进 行限失真编码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著5第5章 信源编码本章讨论离散信源编码，首先从无失真编码定理出发，重点讨论以香农码、费诺码和霍夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著65.1 编码的定义信源编码器信道码表图5-1 信源编码器示意图普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著75.1 编码的定义信源编码是指信源输出符号经信源编码器编码后转换成另外的压缩符号无失真信源编码：可精确无失真地复制信源输出地消息普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著85.1 编码的定义将信源消息分成若干组，即符号序列xi，xi(xi1xi2xilxiL)，xilA=a1，a2，ai，an 每个符号序列xi依照固定码表映射成一个码字yi，yi(yi1yi2yilyiL)，yilB=b1，b2，bi，bm这样的码称为分组码，有时也叫块码。只有分组码才有对 应的码表，而非分组码中则不存在码表。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著95.1 编码的定义如图5-1所示，如果信源输出符号序列长度L1， 信源符号集A(a1，a2，an)信源概率空间为 若将信源X通过二元信道传输，就必须把信源符号ai变换成由0，1符号组成的码符号序列，这个过程就是信源编码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著105.1 编码的定义码可分为两类：一、固定长度的码，码中所有码字的长度 都相同，如表5-1中的码1就是定长码二、可变长度码，码中的码字长短不一， 如表中码2就是变长码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著115.1 编码的定义不同的码符号序列，如表5-1所示。 表5-1 变长码与定长码信源 符号ai信源符号出 现概率p(ai)码表码1码2a1p(a1)000a2p(a2)0101a3p(a3)10001a4p(a4)11111普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著125.1 编码的定义（1）奇异码和非奇异码 若信源符号和码字是一一对应的，则该码为非奇异码。反之为奇异码。如表5-2中的码1是奇异码，码2是非奇异码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著135.1 编码的定义表5-2 码的不同属性信源符号 ai符号出现现概率 p(ai)码码1码码2码码3码码4a11/20011a21/411101001a31/80000100001a41/8110110000001普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著145.1 编码的定义（2）唯一可译码 任意有限长的码元序列，只能被唯一地分割成一个个的码字，便称为唯一可译码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著155.1 编码的定义唯一可译码中又分为非即时码和即时码：如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著165.1 编码的定义即时码：只要收到符号就表示该码字已完 整，可以立即译码。 即时码又称为非延长码，任意一个码字都 不是其它码字的前缀部分，有时叫做异前 缀码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著175.1 编码的定义码奇异码非分组码分组码非奇异码非唯一可译码 非即时码即时码(非延长码)唯一可译码普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著185.1 编码的定义通常可用码树来表示各码字的构成 0 10 1 0 10 1 0 1 0 1 0 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1二进制码树普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著195.1 编码的定义0 1 20 1 2 0 1 2 0 1 20 1 20 1 2三进制码树普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著205.1 编码的定义唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式： 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著215.1 编码的定义例：设二进制码树中X (a1， a2 ， a3 ， a4 )，K11，K22，K32，K43，应用 上述判断定理： 因此不存在满足这种Ki的唯一可译码。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著225.1 编码的定义a1=10 10 10 1a2=01a3=011a4=0001，01，001，000 惟一可译码； 1，01，101，000不是惟一可译码；均满足克劳夫特不等式普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著235.1 编码的定义克劳夫特不等式只是用来说明唯一可译码是否存在，并不能作为唯一可译码的判据。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著245.2 无失真信源编码信源输出 X(X1X2XlXL)， Xla1，a2，ai，an编码为 Y(Y1Y2Yk YkL)， Ykb1，b2，bj，bm。要求能够无失真或无差错地译码，同时传 送Y时所需要的信息率最小 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著255.2 无失真信源编码Yk平均每个符号的最大信息量为log mKL长码字的最大信息量为KLlog m则传送一个信源符号需要的信息率平均为普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著265.2 无失真信源编码所谓信息率最小，就是找到一种编码方 式使 最小。无失真信源编码定理研究的内容:最小信息率为多少时，才能得到无失真 的译码？若小于这个信息率是否还能无 失真地译码 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著275.2 无失真信源编码无失真的信源编码定理n定长编码定理n变长编码定理 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著285.2 无失真信源编码n定长编码定理 K是定值 且惟一可译码普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著295.2 无失真信源编码由L个符号组成的、每个符号的熵为HL(X)的无记 忆平稳信源符号序列X1X2XlXL，可用KL个符 号Y1，Y2，Yk，（每个符号有m种可能 值）进行定长编码。对任意0，0，只要则当L足够大时，必可使译码差错小于； 反之，当 时，译码差错一定是有限值，而L足够大时，译码几乎必定出错 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著305.2 无失真信源编码定长编码定理说明，码字所能携带的信息量大于信源序列输出 的信息量，则可以使传输几乎无失真，当 然条件是L足够大。 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著315.2 无失真信源编码反之，当 时，不可能构成无失 真的编码，也就是不可能做一种编码器， 能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真 ，也可能有失真。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著325.2 无失真信源编码式中 为自信息方差 为一正数。当 和 均为定值时，只要 L足够大，Pe可以小于任一正数。即， 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著335.2 无失真信源编码当信源序列长度L满足 时，能达到差错率要求 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著345.2 无失真信源编码在连续信源的情况下，由于信源的信息量 趋于无限，显然不能用离散符号序列Y来完成无失真编码，而只能进行限失真编码。普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著355.2 无失真信源编码定义为编码效率，即信源的平均符号熵为H(X) ，采用平均符号码长为 来编码，所得的 效率。 编码效率总是小于1，且最佳编码效率为 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著365.2 无失真信源编码编码定理从理论上阐明了编码效率接近1 的理想编码器的存在性，它使输出符号的 信息率与信源熵之比接近于1，即L取无限长普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著375.2 无失真信源编码例设离散无记忆信源概率空间为比特/符号 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著385.2 无失真信源编码对信源符号采用定长二元编码，要求编码 效率为 90，若取L1，则可算出2.55 90%=2.8比特/符号Pe0.04 太大普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著395.2 无失真信源编码若要求译码错误概率 普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著405.2 无失真信源编码变长编码定理 在变长编码中，码长K是变化的根据信源各个符号的统计特性，如概率大 的符号用短码，概率小的用较长的码，使 得编码后平均码长降低，从而提高