信息论与编码_PPT_第5章信源编码.

《信息论与编码_PPT_第5章信源编码.》由会员分享，可在线阅读，更多相关《信息论与编码_PPT_第5章信源编码.（85页珍藏版）》请在金锄头文库上搜索。

1、信息论基础 第5章 信源编码 编码分为信源编码和信道编码，其中信源编 码又分为无失真和限失真。 一般称 u无失真信源编码定理为第一极限定理； u信道编码定理（包括离散和连续信道）称为第 二极限定理； u限失真信源编码定理称为第三极限定理。 1 信息论基础 第5章 信源编码 由于信源符号之间存在分布不均匀和相关性， 使得信源存在冗余度，信源编码的主要任务就是 减少冗余，提高编码效率。 2 信息论基础 第5章 信源编码 信源编码的基本途径有两个： n使序列中的各个符号尽可能地互相独立，即解 除相关性； n使编码中各个符号出现的概率尽可能地相等， 即概率均匀化。 3 信息论基础 第5章 信源编码 信

2、源编码的基础是信息论中的两个编码定理： n无失真编码定理 n限失真编码定理 无失真编码只适用于离散信源 对于连续信源，只能在失真受限制的情况下进行限失 真编码 4 信息论基础 5.1 编码的定义 信源编码器信道 码表 图5-1 信源编码器示意图 5 信息论基础 5.1 编码的定义 信源编码是指信源输出符号经信源编码器编码 后转换成另外的压缩符号 无失真信源编码：可精确无失真地复制信源输 出地消息 6 信息论基础 5.1 编码的定义 将信源消息分成若干组，即符号序列xi， xi(xi1xi2xilxiL)， xilA=a1，a2，ai，an 每个符号序列xi依照固定码表映射成一个码字yi， yi

3、(yi1yi2yilyiL)， yilB=b1，b2，bi，bm 这样的码称为分组码，有时也叫块码。只有分组码才有对 应的码表，而非分组码中则不存在码表。 7 信息论基础 5.1 编码的定义 如图5-1所示，如果信源输出符号序列长度L1，信源 符号集A(a1，a2，an) 信源概率空间为 若将信源X通过二元信道传输，就必须把信源符 号ai变换成由0，1符号组成的码符号序列，这个 过程就是信源编码 8 信息论基础 5.1 编码的定义 不同的码符号序列，如表5-1所示。 表5-1 变长码与定长码 信 源 符 号 ai 信源 符号 出现 概率 p(ai) 码表 码 1 码 2 a1p(a1) 0 0

4、 0 a2p(a2) 0 1 0 1 a3p(a3) 1 0 0 0 1 a4p(a4) 1 1 1 1 1 9 信息论基础 5.1 编码的定义 码 奇异码 非分组码 分组码 非奇异码 非唯一可译码 非即时码 即时码(非延长码) 唯一可译码 10 信息论基础 5.1 编码的定义 表5-2 码的不同属性 信源符号ai符号出现概率 p(ai) 码1码2码3码4 a11/20011 a21/411101001 a31/80000100001 a41/8110110000001 11 信息论基础 5.1 编码的定义 通常可用码树来表示各码字的构成 0 1 0 1 0 1 0 1 0 1 0 1 0 1

5、 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 二进制码树 12 信息论基础 5.1 编码的定义 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 三进制码树 13 信息论基础 5.1 编码的定义 唯一可译码存在的充分和必要条件 各码字的长度Ki 应符合克劳夫特不等式： 14 信息论基础 5.1 编码的定义 例：设二进制码树中X (a1， a2 ， a3 ， a4 )， K11，K22，K32，K43，应用上述判断 定理： 因此不存在满足这种Ki的唯一可译码。 15 信息论基础 5.1 编码的定义 a1=1 0 1 0 1 0 1 a2=01 a3=01

6、1a4=000 1，01，001，000 惟一可译码； 1，01，101，000 不是惟一可译码； 均满足克劳夫特不等式 16 信息论基础 5.2 无失真信源编码 信源输出 X(X1X2XlXL)， Xla1，a2，ai，an 编码为 Y(Y1Y2Yk YkL)， Ykb1，b2，bj，bm。 要求能够无失真或无差错地译码，同时传送Y 时所需要的信息率最小 17 信息论基础 5.2 无失真信源编码 无失真的信源编码定理 n定长编码定理 n变长编码定理 18 信息论基础 5.2 无失真信源编码 由L个符号组成的、每个符号的熵为HL(X)的无记忆 平稳信源符号序列X1X2XlXL，可用KL个符号Y

7、1， Y2，Yk，（每个符号有m种可能值）进行定 长编码。对任意0，0，只要 则当L足够大时，必可使译码差错小于； 反之，当 时，译码差错一 定是有限值，而L足够大时，译码几乎必定出错 19 信息论基础 5.2 无失真信源编码 定长编码定理说明， 码字所能携带的信息量大于信源序列输出 的信息量，则可以使传输几乎无失真，当 然条件是L足够大。 20 信息论基础 5.2 无失真信源编码 反之，当 时，不可能构成无失真的编 码，也就是不可能做一种编码器，能使收端译码 时差错概率趋于零。 时，则为临界状态，可能无失真，也 可能有失真。 21 信息论基础 5.2 无失真信源编码 式中 为自信息方差 为一

8、正数。当 和 均为定值时，只要L足 够大，Pe可以小于任一正数。即， 22 信息论基础 5.2 无失真信源编码 当信源序列长度L满足 时， 能达到差错率要求 23 信息论基础 5.2 无失真信源编码 在连续信源的情况下，由于信源的信息量趋于 无限，显然不能用离散符号序列Y来完成无失真 编码，而只能进行限失真编码。 24 信息论基础 5.2 无失真信源编码 定义 为编码效率，即信源的平均符号熵为H(X)，采 用平均符号码长为 来编码，所得的效率。 编码效率总是小于1，且最佳编码效率为 25 信息论基础 5.2 无失真信源编码 编码定理从理论上阐明了编码效率接近1的理想 编码器的存在性，它使输出符

9、号的信息率与信源 熵之比接近于1，即 L取无限长 26 信息论基础 5.2 无失真信源编码 例设离散无记忆信源概率空间为 比特/符号 27 信息论基础 5.2 无失真信源编码 对信源符号采用定长二元编码，要求编码效率 为 90，若取L1，则可算出 2.55 90%=2.8比特/符号 Pe0.04 太大 28 信息论基础 5.2 无失真信源编码 若要求译码错误概率 29 信息论基础 5.2 无失真信源编码 变长编码定理 在变长编码中，码长K是变化的 根据信源各个符号的统计特性，如概率大的符 号用短码，概率小的用较长的码，使得编码后平 均码长降低，从而提高编码效率。（统计匹配） 30 信息论基础

10、5.2 无失真信源编码 单个符号变长编码定理：若离散无记忆信源的 符号熵为H(X)，每个信源符号用m进制码元进行 变长编码，一定存在一种无失真编码方法，其码 字平均长度满足下列不等式 31 信息论基础 5.2 无失真信源编码 离散平稳无记忆序列变长编码定理：对于平均 符号熵为HL(X)的离散平稳无记忆信源，必存在 一种无失真编码方法，使平均信息率满足不等式 其中为任意小正数。 32 信息论基础 5.2 无失真信源编码 编码效率总是小于1，可以用它来衡量各种编码 方法的优劣。 为了衡量各种编码方法与最佳码的差距，定义 码的剩余度为 33 信息论基础 5.2 无失真信源编码 例设离散无记忆信源的概

11、率空间为 34 信息论基础 5.2 无失真信源编码 若用二元定长编码(0，1)来构造一个即 时码： 。 平均码长 1二元码符号/信源符号 35 信息论基础 5.2 无失真信源编码 编码效率为 输出的信息效率为 R0.811比特/二元码符号 36 信息论基础 5.2 无失真信源编码 长度为2的信源序列进行变长编码（编码方法 后面介绍），其即时码如下表 aip(ai)即时码 a1a19/160 a1a23/1610 a2a13/16110 a2a21/16111 37 信息论基础 5.2 无失真信源编码 二元码符号/信源序列 二元码符号/信源符号 38 信息论基础 5.2 无失真信源编码 编码效率

12、 信息效率 R20.961比特/二元码符号 39 信息论基础 5.2 无失真信源编码 L3 R30.985比特/二元码符号 L4 R40.991比特/二元码符号 40 信息论基础 5.2 无失真信源编码 定长二元码编码，要求编码效率达到96时 ，允许译码错误概率 41 信息论基础 5.2 无失真信源编码 能获得最佳码的编码方法主要有： n香农（Shannon） n费诺（Fano） n哈夫曼（Huffman）等 42 信息论基础 5.2 无失真信源编码 香农（Shannon）编码 n将信源消息符号按其出现的概率大小依次排 列 n确定满足下列不等式的整数码长Ki。 43 信息论基础 5.2 无失真

13、信源编码 n为了编成唯一可译码，计算第i个消息的累加概 率 n将累加概率Pi变换成二进制数。 n取Pi二进数的小数点后Ki位即为该消息符号的 二进制码字。 44 信息论基础 5.2 无失真信源编码 例 设信源共7个符号消息，其概率和累加概率 如下表所示。 45 信息论基础 5.2 无失真信源编码 信源消息符 号ai 符号概 率 (ai) 累加概 率Pi -log p(ai)码字长 度Ki 码字 a10.2002.323000 a20.190.22.393001 a30.180.392.473011 a40.170.572.563100 a50.150.742.743101 a60.100.89

14、3.3241110 a70.010.996.6471111110 46 信息论基础 5.2 无失真信源编码 码元/符号 比特/码元 47 信息论基础 5.2 无失真信源编码 费诺编码方法 费诺编码属于概率匹配编码 (1)将信源消息符号按其出现的概率大小依次 排列： 。 (2)将依次排列的信源符号按概率值分为两大 组，使两个组的概率之和近于相同，并对各 组赋予一个二进制码元“0”和“1”。 48 信息论基础 5.2 无失真信源编码 (3)将每一大组的信源符号进一步再分成两组 ，使划分后的两个组的概率之和近于相同， 并又赋予两个组一个二进制符号“0”和“1”。 (4)如此重复，直至每个组只剩下一个

15、信源符 号为止。 (5)信源符号所对应的码字即为费诺码。 49 信息论基础 5.2 无失真信源编码 例 对以下信源进行费诺编码。 消息符 号ai 各个消 息概率 p(ai) 第一次 分组 第二次 分组 第三次 分组 第四次 分组 二元 码字 码长 Ki a10.200 0 002 a20.191 0 0103 a30.18 1 0113 a40.171 0 102 a50.151 0 1103 a60.101011104 a70.01111114 50 信息论基础 5.2 无失真信源编码 码元/符号 bit/符号 51 信息论基础 5.2 无失真信源编码 哈夫曼编码方法 (1)将信源消息符号按其出现的概率大小依次排 列， (2)取两个概率最小的字母分别配以0和1两个码 元，并将这两个概率相加作为一个新字母的概率 ，与未分配的二进符号的字母重新排队。 52 信息论基础 5.2 无失真信源编码 (3)对重排后的两个概率最