第2章-信源编码技术

《第2章-信源编码技术》由会员分享，可在线阅读，更多相关《第2章-信源编码技术（86页珍藏版）》请在金锄头文库上搜索。

1、信源编码,原始的语音信号，如果不做任何处理，将含有很多的冗余信息，不利于在信道上进行传输。 为了提高传输效率，需要对该信号进行压缩，这一步骤称为信源编码。 与此类似，图像、视频等信号的压缩，都属于信源编码的范畴。 最主要的目的：提高通信的有效性。,信源编码原理：冗余的存在是由于原有信息之间存在着一定的关联，以及不同信息之间出现的概率分布不均匀所致。 例：语音的冗余，文字的不均匀性 通过编码处理，使得信息之间成为完全独立的符号，且出现概率相同，可以大大压缩原有信息的长度，而保持信息量不变。,2.1.4 信源的信息度量 1. 信息的基本概念 我们在前面讨论了信源的分类与统计描述,主要利用了信源的客

2、观概率分布(包括概率与概率密度)特性描述了信源。 为了进一步深入定量地研究信源,仅限于上述一般化的描述是不够的。 信源就其信息实质来说,具有不确定性,那么信息与不确定性是什么关系,而不确定性又如何利用客观概率来表达,这就是信源输出的消息(或符号)所包含信息的定量度量问题。 ,2. 信源的信息度量 信源输出的是消息,消息的内涵是信息,信息的最主要特征是具有不确定性。 如何度量信息的不确定性？信源的统计特性可以采用概率及概率密度来描述,那么度量信息的不确定性与信源的概率与概率密度是什么关系? 信源输出的信息量,信息论创始人Shannon将其定义为 H(X)=HP(x1), , P(xn) =EIP

3、(xi) =E-logP(xi) = P(xi) logP(xi),其中, “E”表示求概率统计平均值,即求数学期望值。 Shannon称H(X)为信源的信息熵,简称为熵。 从数学上看,熵是信源消息概率P(xi)的对数函数logP(xi)的统计平均值,故又称为P(xi)的泛函数,它是定量描述信源的一个重要物理量。 熵是Shannon于1948年首先给出的一个从概率统计角度来描述信源不确定性的一个客观物理量,是从信源整体角度上反映信源不确定性的度量。 ,4. 信源编码的理论基础 现在我们来讨论信源冗余度的概念,它是信源统计分析中一个非常重要的概念,是信源信息处理、 信源编码的理论依据。 由于实际

4、信源几乎都是有记忆的,这也就是说信源输出的消息序列的各个消息之间存在着记忆,即统计关联。 如果能首先定量地计算出这一统计关联引入的冗余度,就能充分地利用它。 下面讨论冗余度及其计算。 对于一个最简单二进制信源有下列基本不等式: 0H(X/Y)H(X)lb2=1 (2-32) 其中lb2为离散二进制信源消息等概率分布时的熵函数值（最大值、 极值）。 ,例2-3 关于英文文字信源冗余度的讨论。 根据英文中各个字母（含空格）出现的概率,可列出表2-2。,表2-2 英文字母出现概率统计表,由表2-2,首先求得独立等概率情况下的H0(X)值: H0(X)=lb27=4.76 b 再求独立不等概率情况下的

5、H1(X)值: H1(X)= P(xi) lbP(xi)=4.03b 还可进一步求得有一阶、 二阶记忆下的H2(X)和H3(X)为 H2(X) =3.32 b H3(X) =3.1 b,最后,利用统计推断方法求得H(X)的值。 一般而言,由于采用不同的逼近方法和所取样本上的差异, 所推算的结果也不同,这里我们采用Shannon求得的推算值： H(X) 1.4b 这样,利用公式(2-35)及(2-36)可分别求得=0.29, R=0.71。 这一结论说明英文字母信源从理论上看,有71%是多余的,即可以认为一本100页的英文书,理论上看仅有29页是有效的,其余71页从统计角度看完全是多余的。 也正

6、是由于理论上存在着这一多余成分,引导了实际工作者对英文信源进行压缩编码的研究。 英文信源的分析也带动了各国对自己国家语言文字信源的分析,现将类似结果列于表2-3。,表2-3 不同文字信源冗余度估算,例2-4 关于语音信源冗余度的一个粗略估计。 语音信源的编码大致可以分为波形编码、 参量编码与混合编码三大类。 这里,仅分析冗余度最大的参量编码,即声码器的最大潜力。 以英语为例,其音素大约有2728个,若按人们通常讲话的速率,每秒钟大约平均发送10个音素,这时英语语音信源给出的信息率为 上限： I1=lb (256) 10=80 b/s 下限： I2=lb (128) 10=70 b/s,若按PC

7、M常规数字化编码传送语音,其标准速率为64 kb/s,因此可求得 1= =0.001 25 2= =0.0011 R1=1-1=1-0.001 25=0.998 75 R2=1-2=1-0.0011=0.9989 可见,语音参量编码潜力巨大。 定义理论上最大压缩倍如下： K1= =800 (倍) K2= =914 (倍),2.2 无失真信源编码,2.2.1 基本原理 我们在前面讨论了无失真信源的信息度量： 信源熵H（X）。 在本节将进一步分析讨论实现通信系统优化的无失真信源编码定理。 为了分析简化,这里仅讨论最简单情况组合下的信源无失真编码定理： 离散、 无记忆、 平稳、 遍历、 二（多）进制

8、等（变）长编码条件下的信源编码定理。 下面,我们将从直观概念出发,直接推导出这类简化信源编码。 首先研究等长码,参见图2-2,其中, x为输入,它共有L位（长度）,每一位有n种取值可能; s为输出,它共有K位（长度）,每一位有m种取值可能。 ,图2-2 信源编码原理图,倘若不考虑信源的统计特性,为了实现无失真并有效的编码,应分别满足： 无失真要求：nLmK （即每个信源组合必须有对应的编码） (2-37) 有效性要求： nL mK （即编码组合总数要小于信源组合总数） (2-38) 从式(2-37)可推出 (2-39) 显然,上述两个条件是相互矛盾的。 如何解决这一对矛盾呢？惟一的方法是引入信

9、源的统计特性。 这时,就无需对信源输出的全部nL种信息组合一一编码,而仅对其中少数大概率典型组合进行编码。 ,下面,先分析公式(2-39)的含义,并在引入信源统计特性以后对它作适当的修改。 公式(2-39)的右端,其分子部分表示等概率信源的熵,而分母部分则表示等概率码元的熵。 当引入信源统计特性以后,信源不再满足等概率,这时分子可修改为不等概率实际信源熵H(X),则有 (2-40) 再将上式稍作变化,即可求得典型Shannon第一等长编码定理形式,当 时,有效的无失真信源编译码存在,可构造； (2-41),反之,当 (2-42) 时,有效的无失真信源编译码不存在,不可构造。 再讨论变长码,这时

10、仅需将公式(2-40)修改为 (2-43) 式中将等长码的码长K改成相对应变长码的平均码长 ,平均码长 由下式计算： (2-44),再将公式(2-43)稍加修改即可求得典型的Shannon第一变长编码定理形式: 对于二进制（m=2）,则有 当对数取2为底时,有,(2-45),(2-46),(2-47),式中, K/L表示平均每个码元的长度。 可见它要求平均每个码元的长度应与信源熵相匹配,因此又称为熵编码。 实现无失真信源编码的基本方法有两大类型： 一类为改造信源方式,即将实际不理想的不等概率信源变换成理想的具有最大熵值的等概率信源,再采用等长编码进行匹配； 另一类为适应信源方式,即对实际的不等

11、概率信源采用与之相匹配的变长编码方法, 包括最佳变长哈夫曼（Haffman）编码、算术编码以及适合于有记忆信源的游程编码等。 ,2.2.2 哈夫曼（Huffman）编码 哈夫曼编码是一种统计压缩的可变长编码,它将预编码的字符用另一套不定长的编码来表示,基本原理是： 按照概率统计结果,出现概率高的字符用较短的编码来表示,出现概率低的字符用较长的编码来表示。 编码压缩性能是由压缩率（compression ratio）来衡量的,它等于每个采样值压缩前的平均比特数与压缩后的平均比特数之比。 由于编码的压缩性能与编码技术无关,而与字符集的大小有关,因此,通常可以将字符集转化成一种扩展的字符集,这样采用

12、相同的编码技术就可以获得更好的压缩性能。,哈夫曼编码过程可用于任意两个字符集。 下面分析一个任意输入字符集到一个二进制输出字符集的转换过程。 哈夫曼编码过程类似于树形生成过程。 首先列出输入字符集及其概率（或相对频率）,以降序排列,这些列表项相应于树枝末端,每个分支都标注了等于该分支概率的分支权值。 现在开始生成包含这些分支的树： 将最低概率的两个分支合并（在分支节点处）,形成一个新分支,并标注上两个概率的相加值； 每次合并后,将新的分支和剩下的分支重新排序（若需要）,以保证减少的列表概率的递降性,将这种排列方法称为冒泡法。 在每次合并后的重排中,新的分支在列表中不断上升至不能上升为止。,因此

13、,如果形成一个权值为0.2的分支,在冒泡过程中发现其他两个分支的权值也是0.2,那么,新的分支将被冒泡到权值为0.2的分支组的顶端,而不是简单地加入。 冒泡到同权值组的顶端可以生成码长方差小的编码,以降低缓冲溢出的可能性。 为了讨论方便、 描述准确,我们定义n元素m字符集为： 字符集中共有n个元素,每个元素都包含m个字符,即每个元素包含的字符数目相同。,例2-5 6元素单字符集的哈夫曼编码。 设6元素单字符集中每个元素的出现概率如表2-4所示。,表2-4 6元素单字符集哈夫曼编码的详细参数,图2-3 6元素单字符集的哈夫曼编码树,将哈夫曼编码过程应用于表2-4所示的输入字符集。按照哈夫曼编码规

14、则,生成哈夫曼编码树,如图2-3所示。然后在哈夫曼编码树的每个分支节点标上二进制数“0”或“1”,以区分两个分支。 这种标记可以是任意的,但为了保持一致,将每个节点的上向分支标为“1”,下向分支标为“0”。 标记好之后,沿着树径从树基（最右）到每个分支（最左）的路径包含了到达该分支的二进制序列,该二进制序列就是分支对应字符的哈夫曼编码,哈夫曼编码的详细参数如表2-4所示。,可计算出字符集的平均码长是2.4b。这好像意味着我们必须找到一个传输非整数比特的方法。实际上这个结果表明,当要传输100个输入码元时,通信信道中平均需要传输240 b。比较一下,若采用等长码来表示6元素单字符集,则码长K为3

15、b。而输入字符集的熵（平均信息量）为2.32b。 因此,哈夫曼编码提供了1.25（3.0/2.4）的压缩率,该字符集编码效率达到了96.67（2.32/2.40）。 为了说明代码扩展的应用,我们再举一个例子。,例2-6 3元素单字符集的哈夫曼编码（元素的概率分布不均匀）。 该字符集的哈夫曼编码树见图2-4,其详细参数见表2-5(i=1, 2, 3)。,表2-5 3元素单字符集哈夫曼编码的详细参数,图2-4 3元素单字符集的哈夫曼编码树,该哈夫曼编码的平均码长是1.27 b； 采用等长码则码长为2b。 这里,哈夫曼编码提供的压缩率是1.57（2/1.27）,比6元素单字符集的1.25大。 但是,应用式(2-21)计算字符集的熵（平均信息量）为0.9443b,该字符集编码效率为74.35（0.9443/1.27）,却比6元素单字符集的96.67小。这是因为6元素单字符集的信息熵（2.32b）与平均码长（2.4 b）的匹配比3元素单字符集的信息熵（0.9443 b）与平均码长（1.27 b）的匹配要好。,