第四章 无失真信源编码.ppt

4.3 变长码及变长信源编码定理 定理4.3.5(无失真信源编码定理--香农第一定理)设离散无记忆信源 其信源熵为H(S)，该信源的N次扩展信源为： 对扩展信源进行编码，总可构造唯一可译码，使信源S中的每个符号所需要的平均码长满足： 4.3 变长码及变长信源编码定理 证明：将扩展信源视为一个新的离散无记忆信源，按照定理4.3.4可以得出 或者 当 或者 当N充分大时，每个信源符号所对应的平均码长等于r进制的信源熵 或者2进制信源熵 ,若达不到这个码长，则唯一可译码不存在。 4.3 变长码及变长信源编码定理 推论：对于一般离散信源或者马尔可夫信源则有 表示编码后平均每个信源符号能载荷的信息量。 则 若是对N次扩展信源编码，平均码长 编码后信道的信息传输率 编码后的极限信息传输率为R=logr，对于无噪无扰信道，其信道容量C=logr，即R≤C。 无失真信源编码定理也称无噪信道编码定理，可表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息；反之则不可能无差错传输。 4.3 变长码及变长信源编码定理 若对有记忆普通信源 4.3 变长码及变长信源编码定理 为了衡量各种编码距极限压缩(码长越短越好)值的情况，定义变长编码的编码效率 一般有记忆信源 对于无记忆信源 无记忆信源二元编码 为了衡量各种编码与最佳码的差距，定义编码的剩余度 4.3 变长码及变长信源编码定理 [例4-7] 已知信源模型 1)对单信源符号进行二元编码，即s1→0，s2→0，求平均码长和编码效率； 2)编码成2次扩展码，信源序列与码序列的映射 关系为s1s1→0,s1s2→10,s2s1→110,s2s2→111，求平均码长和编码效率。 解： 4.3 变长码及变长信源编码定理 与例4-1、4-2相比，可以看出，为得到同样编码效率所用的N比定长码小得多，因此容易达到高的编码效率，是变长码的显著优点。 信息传输率 用同样可得对3、4次扩展信源编码。其编码效率。 4.4 常见无失真信源编码方法 4.4 常见无失真信源编码方法 信源编码主要分为无失真和限失真信源编码，其目的都是为了用较少的码率来传送同样多的信息，增加单位时间传送的信息量，提高有效性。 无失真信源编码主要适用于离散信源或数字信号，例如文本、表格及工程图纸等信源；限失真信源编码主要适用于波形信源或波形信号(模拟信号)，如语音、电视图象、彩色静止图象等信号。 无失真信源编码常被称熵编码(entropy coding)，常见的无失真信源编码方法有：香农编码、霍夫曼编码、费诺编码、游程编码及算术编码等。 4.4 常见无失真信源编码方法 4.4.1 香农编码(不是最佳编码方法) 最佳编码：凡能载荷一定信息量，平均码长最短，可分离的(接收端能分开)变长码的码集。 关键：码长最短 大概率→短码 小概率→长码 香农编码编码步骤为: 1 信源符号按概率排序：p(s1)≥p(s2)≥…≥p(sn) 2 确定码长lj(整数)：-log2p(sj)≤lj＜1-log2p(sj) 3 计算第j个码字(之前)的累加概率pa(sj) 4 将pa(sj)变为二进制数，并取其小数点后lj位作为si的编码。 4.4 常见无失真信源编码方法 [例4-8] 对下表信源符号s1,s2,…s7进行编码，并计算平均码长及编码效率。 0.000 0.0011… 0.0110… 0.1001… 0.1011… 0.1110… 0.1111110… 累加概率对应的二进制 000 001 011 100 101 1110 1111110 3 3 3 3 3 4 7 2.34 2.41 2.48 2.56 2.74 3.34 6.66 0 0.20 0.39 0.57 0.74 0.89 0.99 0.20 0.19 0.18 0.17 0.15 0.10 0.01 S1 S2 S3 S4 S5 S6 S7 二进制代码 代码长度li -logp(si) 累加概率pa(sj) 消息概率p(si) 消息符号si 4.4 常见无失真信源编码方法 4.4.2 费诺编码 费诺编码属于概率匹配编码，但也不是最佳编码，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。步骤： 1）将信源符号以概率递减的次序排列； 2）将信源符号按概率划分成两大组，使每组的概率和接近相等, 并赋值“0”和“1”； 3）将每一大组信源符号再分成两组，使划分后每组的概率和接近相等, 分别赋值“0”和“1”； 4）依次下去，直至各小组只剩一个信源符号；; 5）按分组次序由前向后将赋值排序，即得码字。 4.