信息论与编码第五章

1、第5章信源编码，5.1数据压缩概述5.2无损信源编码的基本原理5.3无损信源编码方法，主要内容，第二类，第三类，第四类，本类内容3360 5.1数据压缩概述5.2无损信源编码的基本概念5.2.1信源编码器5.2.2编码类型，有三个重要的问题需要解决的来源：1 2。信息源输出信息的计算，即信息源熵问题；3.如何更有效地表达源输出问题，即源压缩编码问题。信源编码的主要任务是减少冗余和提高编码效率。在第五章中，有两种基本的信源编码方法：一种是使序列中的每个符号尽可能独立，即消除相关性；第二是使编码中每个符号的概率尽可能相等，即使概率一致。具体来说，根据源输出符号序列的统计特性，找到了将源输出符号序列

2、转换为最短码字序列的方法。然而，在许多情况下，不需要在接收器处精确地再现源的输出，只要它满足某些重建质量要求，这不仅允许信息传输中的某些失真，这是有限失真源编码的问题。例如，在电话通信中，只要对话内容可以传递给对方，对声音质量就没有很高的要求。在实际通信中，信道经常会有干扰，因此完全准确地再现源输出几乎是不可能的。这允许接收信号具有一定程度的失真。这就是限制失真编码的问题，所以我们不会关注它。5.1数据压缩概述，数据压缩：用尽可能少的比特表示源信号(采样和量化的数字信号)，并且可以恢复它。压缩的任务是将源信号保持在可接受的状态，并使所需的位数最小化，从而降低存储、处理和传输成本。4.1数据压缩

3、概述信息论认为，如果信源编码的熵大于信源的实际熵，则信源中一定存在冗余，消除冗余不会减少信息量，而且数据仍然可以恢复原状；然而，如果熵减少，数据就不能完全恢复。然而，在允许的范围内会丢失一定的熵，并且数据可以被近似地恢复。4.1数据压缩概述，常用的压缩编码方法可分为两类：1。无损压缩编码方法，也称为冗余压缩方法或熵编码方法和无损编码；2.有损压缩编码，也称为熵压缩或失真限制编码。4.1数据压缩概述，无损压缩：它使用数据的统计冗余进行压缩，可以完全恢复原始数据，而不会造成任何失真。然而，压缩率受到数据统计冗余理论的限制，一般在2:1到533601之间。特殊应用(如指纹图像、医学图像等)中的图像数

4、据压缩。)通常采用这种压缩。由于压缩比的限制，仅靠无损压缩方法无法解决图像和数字视频存储和传输的所有问题。4.1数据压缩概述，常用的无损压缩方法有香农编码、霍夫曼编码、游程编码、LZW(莱姆佩尔-齐夫-韦尔奇)编码和算术编码。无损压缩的优点：100%保存，无信号丢失，转换方便。无损压缩不足：占用空间大，压缩率低，缺乏硬件支持。4.1数据压缩概述，有损数据压缩：压缩和解压缩的数据不同于原始数据，但一种非常接近的压缩方法，也称为破坏性压缩，意味着压缩二级信息数据，并牺牲一些质量来减少数据量和提高压缩率。例如，人类对图像或声波中的某些频率成分不敏感，使得某些信息在压缩过程中丢失；虽然原始数据不能完全

5、恢复，但是丢失部分对理解原始图像的影响减小了，但是获得了大得多的压缩比。4.1数据压缩概述有损压缩广泛用于语音、图像和视频的压缩在多媒体应用中，常见的压缩方法包括脉码调制、预测编码、变换编码、插值和外推、统计编码、矢量量化和子带编码。混合编码近年来被广泛使用。4.1数据压缩概述，有损压缩的优势：在某些情况下，文件大小可能比任何已知的无损方法小得多，同时满足系统的需求。有损压缩的不足：它会影响图像质量，特别是仔细观察，质量会下降得更明显。4.1数据压缩概述，5.2无损信源编码的基本概念5.2.1信源编码器，编码的本质：它是根据一定的数学规则对信源的原始符号进行变换，用码字代替原始的信源符号，使变

6、换后得到的编码符号接近等概率分布，从而提高信息的传输效率。4.2无损信源编码的基本概念，4.2无损信源编码的基本概念，信源编码：从信源符号到编码符号的映射。源编码器：定义：元素si，i=1，2q的s称为信号单元或消息(总共有q个源符号)。编码器的作用：将源符号集中的符号sj、I=1，2q(或长度为n的源符号序列)转换成由基本符号xj、j=1，2r组成的长度为Li的一对一对应输出符号序列，即C=W1、W2、si (I=1，2q)，wi 4.2无损信源编码的基本概念，如：二进制信道的基本符号集为0，1，源符号S转换成由0和1符号组成的码符号序列(符号)，即4.2无损信源编码的基本概念，例如，下表是

7、用于信源编码的码表，信源输出序列的长度为L=1，信源有4个符号，对应的概率空间为，4.2无损信源编码的基本概念。以代码1为例，信源输出的符号按照固定的规则进行变换，即信源编码器输出4个码字，分别为00、01和11，即码表将信源输出的每个符号映射成二进制码。4.2无损信源编码的基本概念，5.2.2编码类型，1。二进制(代)码：码符号集是X=0，1，并且获得的码字都是二进制序列，所以它们是二进制码。它是数字通信和计算机系统中最常用的代码。2。奇偶校验码(代)码：如果码集X3360 X 3360 X 1(X2 XR)中每个码符号X的传输时间相同，则获得的码C是相同的价格码。通常，二进制代码是相同的价

8、格代码。电报中常用的莫尔斯电码不是同一个价格码，它的码符号()和叉号()占用不同的传输时间。见表5-1，代码一。4.可变长码：中码字的长度不同。见表5-1代码2。非奇异码：一组码中的所有码字都是不同的。即xixj、wiwj、4.2.2代码、6的类型。奇异码：一组代码具有相同的码字，即xixj，但wi=wj。见表代码1单数，代码2非单数。4.2.2代码类型、7。唯一可解码的：如果任何有限长度的编码符号序列串只能唯一地翻译成相应的源符号序列，它被称为唯一可解码的。4.2.2代码类型、代码1:如果代码符号序列是不可唯一解码的0010 s1 s3、s 1 s 2 s1、s3 s1，代码2。0010可翻

9、译为，4.2.2代码类型、注：单一代码不可唯一解码；非奇异代码是唯一的和非唯一的。唯一可解码的代码可以分为非实时解码和实时代码。非实时解码接收机：在接收到一个完整的码字后，不能立即解码，但在下一个码字开始接收之前，不能判断是否可以编码。4.2.2代码类型、表中的代码3是非实时代码，代码4是实时代码。只要收到1，代码含义就完整了。、4.2.2代码类型、即时代码(非扩展代码或非扩展代码):其中没有一个是其他代码字的前缀部分。一些扩展代码是唯一可翻译的，而另一些则不是。例如，代码3是唯一可解码的。总而言之，代码的分类如下：(非延迟代码)，4.2.2代码类型，表5-2不同的代码字，1是单数代码，2是非

10、单数代码。代码3是唯一可解码的，代码2不是唯一可解码的，代码3是非实时代码。只要在代码4中接收到符号1，就意味着码字是完整的，并且可以立即解码。因此，代码4是立即代码，也称为非扩展代码，任何代码字都不是其他代码字的前缀部分。上一课的内容：第5章，源代码编码5.1数据压缩概述5.2无损源代码编码的基本原则5.2.1源代码编码器5.2.2代码类型，1。常用压缩编码方法2。有损压缩编码，也称为熵压缩或失真编码。代码分类，复习，本课的内容，5.2.3几个基本概念5.2.4等长编码定理5.2.5可变长编码定理5.3无失真信源编码方法，1。代码树：通常，代码树可以用来表示每个代码字的组成。如果代码字序列符

11、号是M进制的，那么M个符号的代码树可以用来构造代码字，5.2.3几个基本概念，4.2.3几个基本概念，图4-3(a)二进制代码树，图4-3(b)三进制代码树，其中A是根，分为两个分支，n=3个节点，其终端节点是23=8个符号代表源代码，而图A是全代码树，必须是实时代码，相反，任何实时代码都是由代码树表示的。实时代码的代码树可用于解码。4.2.3几个基本概念，例5.2-1二月天气的概率分布如下：雨天概率为1/8，雪天概率也为1/8，阴天概率为1/4，晴天概率为1/2。假设x1代表雨天，x2代表下雪天，x3代表阴天，x4代表晴天，则离散无记忆信源的概率空间为，4.2.3基本概念，表5-3两种信源编

12、码方案，4.2.3基本概念。使用两种信源编码方案编译的码字如下表所示。画出方案1和方案2的代码树，并试着比较方案1和方案2的哪个代码字更有效。表5-3两种信源编码方案，4.2.3几个基本概念，编码后每个信源符号所需的平均符号数(编码符号)。单位是“符号/源符号”。对单个源符号进行编码，假设源为，2，平均码长、4.2.3基本概念、4.2.3基本概念，并且对应于每个码字的码长为Ki(i1，2q)。此代码的平均代码长度为(符号/源符号)，即方案1的平均代码长度。单位为位/符号或位/代码符号。4.2.3一些基本概念，例4.2-1，信息源熵h (x)是1.75比特/符号，方案1编码后每个符号有效载荷的平

13、均信息量：方案2编码后每个符号有效载荷的平均信息量：(比特/符号)，(比特/符号)，因为每个二进制符号，4.2.3几个基本概念，4。编码效率编码效率：它表示实际信息量与编码后可以加载的最大信息量之比。假设符号是M进制的，也就是说，可以取M个可能的值，每个符号可以携带的最大信息是logm比特/符号。二进制编码效率，4.2.3，方案2编码后每个符号负载的平均信息量：(比特/符号)，(比特/符号)，方案1编码，从编码效率来看，方案1编码效率为0.875，方案2编码效率为1。因此，方案2比方案1更有效。5。克劳福德不等式利用码树的概念，我们可以推导出存在唯一可解码码的充要条件，即每个码字的长度Ki应符

14、合不等式，m是基符号的个数，n是源符号的个数，这称为卡夫不等式，以及4.2.3基本概念，这指出了实时码的码长必须满足的条件。麦克米伦证明了唯一可解码的也满足这个不等式；在代码长度选择的情况下，实时代码与唯一代码一致。Cloft不等式给出了在m进制码中，信源序列中的消息数n和码字的每个码长之间的关系。也就是说，如果三者满足上述公式，它们至少可以形成一个具有这种码长的实时码或唯一可解码码，否则，它们不能形成一个实时码或唯一可解码码。4.2.3几个基本概念，示例4.2-2假设没有唯一的可解码代码树满足此Ki。例如，码字是0、10、11、110。试着把码字的长度改为，这时，有一个唯一的可解码码，例如，

15、码字是0，10，110，111。4.2.3，0，10，110，11，码字是，但不是唯一可以解码的。为了实现上述代码，代码字1，111必须放在中间，从而产生非扩展代码0，10，110，111，4.2.3的几个基本概念。这是因为克罗夫特不等式不能作为判断一个代码是实时代码还是只能解码的基础。例如，如果在代码组中有两个具有相同长度的码字，则无论这两个码字是否相同，都可以建立不等式。然而，当两个码字相同时，它们不能是唯一可解码的。因此，唯一可解码代码必须满足卡夫不等式，相反，满足卡夫不等式的代码不一定是唯一可解码的。4.2.3一些基本概念、可用于编码该信源而不失真，即，码长为K=3个符号/符号、示例：信源有8种等概率符号，L=1，信源序列的熵达到最大，这由最大熵定理H确定。只有22.55=5.856个可能的码字，并且一些符号没有相应的码字，这将在它们到达接收端时引起解码错误。因此，固定长度编码通常有解码错误，l越大，错误越小。如果源的输出概率不相等，例如p(x)=0.4、0.18、0.1、0.1、0.07、0.06、0.05、0.04，那么比特/符号、4.2.4等长编码定理、如果信源是等长编码的，它必须满足要求，其中k1是码长，M是码符号集中的符