无失真数据压缩理论.docVIP

第二章 无失真数据压缩理论 数据压缩就是把输入数据流转变成另一种较小数据流的过程。任何都存在冗余，冗余大小与中每个符号的出现概率和符号间的相关性有关。数据压缩技术基于不同的理念，适合不同的数据类型，产生不同的效果，但是原理是相同的，即通过去除源文件中原始数据的冗余成份。 信源与信源熵 2.1 信源熵 在讨论数据压缩的时候，需要涉及现代科学的一个重要分支——信息论。信息论中有关熵的概念对数据压缩有着重要的指导意义。它一方面给出了数据压缩的理论极限，另一方面又指明了数据压缩的技术途径。设信源用一个随机变量X描述，它取值于有限字母表，则信源熵 (2-1) 其中表示离散随机变量的概率质量函数。信源熵从平均意义上表示信源的总体数字特征，信源输出符号后平均每个信源符号所提供的信息量对信源进行无失真编码时。如果随机变量为等概率分布时，信源熵达到最大，即 (2-2) 对信源进行，通常取。从物理意义上讲，通常传输或存储一个二元字符(0”或1”)，其所含信息量总低于1比特。只有当字符0”或1”等概率出现时，每一个信源符号才含有1比特信息量。此最大值和熵之间的差值，就是信源的冗余度。 在香农信息论中，信源常用随机变量序列描述。一个离散信源的输出可用随机变量序列表示 (2-3) 随机变量序列的联合熵 (2-4) 对联合熵取平均，再令，得熵率 (2-5) 熵率表示信源输出的符号序列中平均每个符号所携带的信息量，也表示对信源无失真编码时所需的最少比特数。 2. 离散平稳信源 离散平稳无记忆信源输出的符号序列是平稳随机序列，并且是统计独立的。根据统计独立的多维随机变量的联合熵与信息熵之间的关系，可以推出 (2-6) 所以离散平稳信源的熵率 (2-7) 离散无记忆信源的冗余度隐含在信源符号的非等概率分布之中。只要信源不等概率分布，就存在着数据压缩的可能性。 离散平稳有记忆信源输出的符号序列是平稳随机序列，并且序列之间存在着统计依赖关系。例如，两个随机变量的联合熵 (2-8) 上式表明，联合信息熵不大于各分量信息熵之和，仅当统计独立时等号成立，此时联合熵达到最大值。而一般情况下。这二者之差就反映了此联合信源所含有的冗余度，两信源之间的相关性越大，冗余度就越大。 对于离散平稳有记忆信源随着序列长度N的增加，也就是随着统计约束条件不断增加，平均符号熵随之减小。当时， (2-9) 离散无记忆信源的冗余度隐含在信源间的相关性之中。只要考虑序列本身的相关性，此平稳信源的熵一般就要降低。而间隔无限远也可能有相关性，所以当N增大也即考虑更多的元素相互依赖关系时，熵值进一步降低，所得到的熵就越接近于实际信源所含的熵。 冗余对于一个离散平稳信源，其输出的每个符号实际所携带的平均信息量用熵率表示。由于信源符号间的依赖关系，使信源的减小。如果信源输出符号间彼此不存在依赖关系，且为等概率分布时，信源的等于最大熵。信源的冗余度R (2-10) 如果把信源的实际熵看作有用信息，而把看作无用信息量，则信源的冗余度实际上就是信源在发出消息时无用信息量所占的比例。例如，英文26个英文字母加空格共27个符号，假设完全等概率，则得英文的最大熵为 (2-11) 实际上，英文中字母组合构成单词，单词组合构成句子，句子组合构成段落和文章。通过大量的统计得到26个字母和空格的出现概率，见表1。由常识可知，仅仅按照表中的出现频率随机构成的一串字母序列通常不能构成英文单词，这是因为实际应用的英文单词，其构成还有许多语法和修辞方面的制约，这种制约在数学关系上的反映就是其性。 表1 英文26个英文字母和空格的出现概率 序号 字母 出现概率 序号 字母 出现概率 1 空格 0.2000 15 U 0.0225 2 E 0.1050 16 M 0.0210 3 T 0.0720 17 P 0.0175 4 O 0.0654 18 Y 0.0120 5 A 0.0630 19 W 0.0120 6 N 0.0590 20 G 0.0110 7 I 0.0550 21 B 0.0105 8 R 0.0540 22 V 0.0080 9 S 0.0502 23 K 0.0030 10 H 0.0470 24 X 0.0020 11 D 0.0350 25 J 0.0010 12 L 0.0290 26 Q 0.0010 13 C 0.0230 27 Z 0.0010 14 F 0.0225 如果认为英文字母是离散无记忆的，根据表1，可以计算这27个符号的实际熵为 (2-12) 若考虑前后两个字母之间存在着相关