下载文档原格式
第5章无失真信源编码定理●通信的实质是信息的传输。
高效率、高质量地传送信息又是信息传输的基本问题。
●信源信息通过信道传送给信宿，需要解决两个问题：第一，在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率。
第二，在信道受干扰的情况下，如何增强信号的抗干扰能力，提高信息传输的可靠性同时又使得信息传输率最大。
●为了解决以上两个问题，引入了信源编码和信道编码。
●提高抗干扰能力（降低失真或错误概率）往往是增加剩余度以降低信息传输率为代价的；反之，要提高信息传输率往往通过压缩信源的剩余度来实现，常常又会使抗干扰能力减弱。
●上面两者是有矛盾的，然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。
●第5章着重讨论对离散信源进行无失真信源编码的要求、方法及理论极限，得出极为重要的极限定理——香农第一定理。
5.1编码器●编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。
●图5.1就是一个编码器，它的输入是信源符号集S={s 1,s 2,…,s q }。
同时存在另一符号集X={x 1,x 2, …,x r }，一般元素x j 是适合信道传输的，称为码符号（或称为码元）。
编码器是将信源符号集中的符号s i （或者长为N 的信源符号序列a i ）变换成由x j（j=1,2, …,r ）组成的长度为l i的一一对应序列。
●这种码符号序列W i 称为码字。
长度l i称为码字长度或简称码长。
所有这些码字的集合C 称为码。
●编码就是从信源符号到码符号的一种映射，若要实现无失真编码，必须这种映射是一一对应的、可逆的。
编码器S ：{s 1,s 2,…s q }X ：{x 1,x 2,…x r }C ：{w 1,w 2,…w q }（w i 是由l i 个x j （x j 属于X ））组成的序列，并于s i 一一对应一些码的定义●二元码：若码符号集为X={0,1}，所得码字都是一些二元序列，则称为二元码。
可变长无失真信源编码定理一、概述可变长无失真信源编码定理是信息论的核心概念之一，它是由美国数学家香农（Claude Shannon）于1948年首次提出。
该定理主要探讨了信源编码的极限性能，为无失真编码提供了理论基础。
可变长无失真信源编码定理不仅在理论上有重要意义，而且在数据压缩、网络传输和存储系统等领域有着广泛的应用价值。
二、定理内容可变长无失真信源编码定理的主要内容是：对于任意给定的离散无记忆信源，存在一种可变长编码方式，使得编码后的平均码长小于或等于信源的熵，从而实现无失真编码。
换句话说，如果信源的熵为H，那么存在一种编码方式，使得编码后的平均码长L满足L ≤ H。
三、证明过程证明可变长无失真信源编码定理的过程较为复杂，涉及到概率论和信息论的基本知识。
以下是证明过程的大致步骤：1.定义信源的熵：信源的熵是信源输出随机变量的不确定性度量，定义为所有可能符号的概率加权和。
如果信源有n个符号，每个符号出现的概率为p1, p2, ..., pn，则信源的熵H定义为H = - Σ (pi * log2(pi))，其中i=1,2,...,n。
2.构造一个可变长度编码表：根据信源的概率分布，构造一个可变长度编码表，使得出现概率较大的符号对应较短的码字，反之亦然。
假设码字长度按照字典序排列，第i个码字的长度为log2(1/pi)，其中i=1,2,...,n。
3.计算平均码长：根据可变长度编码表，计算所有可能符号的平均码长。
平均码长等于所有码字长度的概率加权和，即L = Σ(log2(1/pi) * pi)，其中i=1,2,...,n。
4.证明平均码长小于或等于信源熵：利用不等式性质和概率分布的性质，推导出平均码长L满足L ≤H。
关键在于利用概率分布的不均匀性，通过调整码字长度来最小化平均码长。
5.构造一个解码函数：为了实现无失真解码，需要构造一个解码函数，使得每个码字能够唯一地还原为原始符号。
解码函数可以采用查表法或类似算法实现。
无失真编码与保真度准则下的信源编码比较无失真编码和保真度编码是两种不同的信源编码方法。
无失真编码是一种编码方法，其中编码的输出与其输入完全相同，即没有信息损失。
保真度编码是一种编码方法，其中编码输出与输入之间具有某种度量，通常用于指定被编码信源的相关度量。
在无失真编码中，被编码的信源通常通过重复信源符号来实现。
例如，在串行传输系统中，数据被重复多次，以确保接收方能够正确地接收数据。
虽然这种方法可以确保完全输送原始信源，但它有几个限制。
首先，它需要更多的带宽，因为数据需要被重复发送多次。
其次，它并不适用于所有类型的数据，特别是当数据非常长或不规则时，这种方法会变得非常昂贵和低效。
与此不同的是，保真度编码的目标是在尽可能减少带宽和存储空间的情况下，最大限度地保留原始信源的信息。
通过使用保真度准则，可以将信源表示为某种度量形式。
这些度量通常包括信号功率、功率频谱分布、自相关函数和互相关函数等。
保真度编码通常使用一些高级编码技术，如哈夫曼编码、熵编码和维纳滤波器等。
这些编码方法都源于信息论和通信工程领域的数学理论。
通过这些编码技术，保真度编码可以提高信源的压缩效率，同时最大程度地保留信源的信息。
当比较无失真编码和保真度编码时，无失真编码通常比较简单，但需要更多的带宽和存储空间。
而保真度编码则需要更复杂的算法和技术，但可以在尽可能减少带宽和存储空间的情况下保留更多的原始信息。
综上所述，在处理信源编码问题时，需要综合考虑多个方面，包括数据类型、带宽和存储空间要求等。
无失真编码适用于对带宽和存储空间要求不是很高的应用，例如音频、图片和视频的传输。
保真度编码适用于对存储空间和带宽要求较高的应用，例如用于数字通信系统的压缩算法。
第3章无失真信源编码教学内容包括：信源编码概述、定长编码、变长编码常用的信源编码3．1信源编码概述讲课内容：1、信源编码及分类2、信源编码定义3、信源编码基础1、给出编码译码示意图2、编码：信源编码、信道编码。
信源 = 信息 + 冗余信源编码：针对信源的编码，能更加有效地传输、存储信息。
编码后尽可能减少所需信息的损失，提高编码后携带信息的效率。
3、信源编码的主要任务a、减少冗余b、提高编码效率4、信源编码的基本途径a、解除相关性b 、概率均匀化4、信源编码的两个基本定理a 、无失真编码定理（可逆编码的基础、只适用于离散信源）b 、限失真编码定理（连续信源） 5、信源编码的分类a 、冗余度压缩编码，可逆压缩，经编译码后可以无失真地恢复。
统计特性：Huffman 编码，算术编码Arithmetic Codingb 、熵压缩编码，不可逆压缩 压缩超过一定限度，必然带来失真 允许的失真越大，压缩的比例越大译码时能按一定的失真容许度恢复，保留尽可能多的信息本章讨论离散信源无失真编码，包括定长、变长无失真编码定理和编码方法，以及几种实用的无失真信源编码，如香农编码、费诺编码、哈夫曼编码等。
6、信源编码的定义首先给出信源编码的定义，信源编码就是从信源符号到码符号的一种映射f ，它把信源输出的符号u i 变换成码元序列w i 。
f ：u i ——>w i ，i =1，2，…，q译码是从码符号到信源符号的映射。
若要实现无失真编码，这种映射必须是一一对应的、可逆的。
给出马元、码字、马块、二元编码的概念结合P34例3.1.1给出编码的分类如下：给出平均码长的定义和公式。
结合P34例3.1.1进行二进制信源的简单编码，并计算平均码长。
3．2克拉夫特（Kraft）不等式讲课内容：1、变长码的码字分离技术2、即时码的引入和码树表示方法3、即时码与克拉夫特不等式1、变长码的码字分离技术a、同步信号b、可分离码字2、即时码和码树表示法即时码是一种实时的惟一可译码，这类码无需另加同步信息，就能在接收端被分离出来。
在信源编码和数据压缩中，这类编码无论在理论还是在实际中都有很大意义，对较简单的信源，可以很方便地用码树法直接且直观地构造出可以分离码（异前缀码）。
根据码树判定即时码：3、即时码与克拉夫特不等式但是当信源较复杂，直接画码树就比较复杂。
针对这一问题，在数学上给出一个与码树等效的，表达码字可分离的充要条件，即著名的克拉夫特不等式。
【定理3.1.1】对于码长分别为l1，l2，…，l n的m元码，若此码为即时码，则必定满足(3.1.4)反之，若码长满足不等式（3.1.4），则一定存在具有这样码长的即时码。
给出该定理的理论意义与证明过程【定理3.1.2】对于任意r进制惟一可译码，各码字的码长l i，i=1，2，…，n，必须满足Kraft不等式，反过来，若上式成立，就一定能构造一个r进制惟一可译码。
给出该定理的理论意义与证明过程3．3定长编码讲课内容：1、定长编码定理2、定长编码方法3、定长编码的编码效率与差错率1、定长编码定理a、引入离散无记忆信源进行编码的最小平均码长问题前面讨论编码时，都是对信源输出的单个符号进行编码，现在考虑更一般的情况，即对信源输出的符号序列进行编码。
假设离散无记忆信源为[U，P U]=[u i，P(u)|i=1，2，…，q]，现要对U发出的N长符号序列进行编码。
对信源U的N i长符号序列进行r进制编码，实质上就是对扩展信源U N的单个符号进行编码，既可定长编码，也可变长编码。
若用代表对U N编码所得的平均码长，则我们追求的是最小的码，这就引出了一个理论问题，平均码长可小到什么程度呢？对此问题，定长无失真编码定理和变长无失真编码定理都给予了明确的回答。
只要可用的码字数不少于U N的符号数，即就可做到惟一译码。
将上式整理一下得U的一个符号所需用去的码元数目/N以U的最大r进制熵为下界，再小就不能惟一可译了。
b、给出解决方法----定长编码定理【定理3.2.1(定长编码定理)】用r元符号表对离散无记忆信源U的N长符号序列进行定长编码，N长符号序列对应的码长为，若对于任意小ε>0，δ>0，只要满足(3.2.3) 就几乎能实现无失真编码，且随着N的增大，译码错误率小于δ。
反之，若(3.2.4)时，不可能实现无失真编码，且随着N的增大，译码错误概率近似等于1，几乎必定出错。
c、给出该定理的理论意义并分析定理的结论。
d、给出定长编码的效率给出公式分析：为使编码真正有效，必须增大信源序列的分组长度N，这就会使编、译码的延时增大，同时也会使编、译码器的复杂程度增加，因此，定长编码在冗余度压缩编码中的理论意义远大于其实用价值。
2、定长编码方法（P82例3.2.1）a、计算平均码长b、计算信源熵c、计算编码效率3、定长编码的失真与差错率当<H(U)的时候，还有部分符号没有对应的码字，这些符号一旦出现，被传输至接收端，就没有对应的码字译码，因而引起译码差错。
所以定长编码一般都存在译码差错，只是差错大小不同。
将信源空间分为两个互补的集合和，集中的元素（样本矢量）有与之对应的不同码字，而集中的元素没有对应的输出码字，因而会在译码时发生差错。
在这种编码方式下，差错概率P e即为集中元素发生的概率，此时要求，因而集中的样本都应是小概率事件。
当N增大时，虽然样本数也随着增多，但小概率事件的概率将更小，有望使更小。
根据切比雪夫不等式可推得，（）当ζ2(U)和ε2均为定值时，只要N足够大，就可以使P e小于任意一正数δ，即，也就是当信源序列长度N满足(3.2.12)时，就能达到差错率要求。
定长编码在引入失真的前提下，还需要取很长的信源序列进行编码，才能达到较高的编码效率。
既要不失真，又要很高的编码效率，只能采用变长编码。
结合【例 3.2.2】分析上述结论。
3．4变长编码讲课内容：变长编码定理（香农第一定理）变长编码方法变长编码的编码效率1、变长编码定理变长编码不要求所有码字长度相同，但希望平均码长最小，信源无失真变长编码定理给出了在无失真编码的前提下平均码长的界限。
【定理3.3.1（无失真变长编码定理）】用r元符号表对离散无记忆信源U的N长符号序列进行变长编码，记N长符号序列对应的平均码长为，那么，要做到无失真编码，平均码长必须满足另一方面，一定存在惟一可译码，其平均码长满足结合Kraft不等式和概率完备性质给出定理两个结论的证明过程。
2、变长编码方法目标：变长编码采用即时码，力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩。
对给定的信源，使平均码长达到最小的编码方法称为最佳编码，编出的码称为最佳码。
将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。
证明变长编码定理的过程中给出的构造方法即香农编码。
但香农编码不能使平均码长达到最小，因此不是最佳编码。
只有哈夫曼编码是真正意义上的最佳编码，对给定的信源，用哈夫曼编码方法编出的码，平均码长达到最小。
变长编码的基本思路：针对不同编码平均码长的计算方法。
平均码长定义为式中，是所对应的码字的长度。
结合【例3.3.1】给出构造方法并计算平均码长。
结合【例3.3.2】给出编码效率的计算方法，并对变长编码和定长编码的编码效率进行分析，将达到同样编码效率两种方法所需要付出的代价进行比较。
3．５香农编码a、原理：按照变长编码定理来决定码长，再用合适的方法构造码字，这就是香农编码。
b、编码步骤设有离散无记忆信源，。
二进制香农码的编码步骤如下：(1) 将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(x n)；(2) 按下式求i个信源符号对应的码长l i，并取整；–log P(u i) ≤l i ＜–log P(u i) + 1(3.4.1)(3) 按下式求i个信源符号的累加概率P i；(4) 将累加概率P i转换成二进制数；(5) 取P i二进制数小数点后l i个二进制数字作为第i个信源符号的码字。
结合【例3.4.1】给出具体编码方法。
并计算其平均码长和编码效率。
３．６费诺（Fano）编码a、原理：它是通过构造一个码树，编出的码是即时码，但不一定是最佳码。
b、编码步骤(1) 将信源符号按概率从大到小的顺序排列，不失一般性，令p(x1)≥p(x2)≥…≥p(x n) 。
(2) 按编码进制数将概率分组，使每组概率尽可能接近或相等。
如编二进制码就分成两组，编m进制码就分成m组。
(3) 给每组分配一位码元。
如编二进制码，则给两组信源符号分别赋码元“0”和“1”。
(4) 将每一分组再按同样原则划分，重复步骤2和3，直到每一小组只含一个信源符号为止。
(5) 由此即可构造一个码树，所有终端节点上的码字组成费诺码。
c、结合【例3.4.2】给出具体编码方法。
并计算其平均码长和编码效率。
d、总结费诺编码的基本特点：(1) 费诺编码在构造码树时，是从树根开始到终端节点结束，这与哈夫曼编码相反；(2) 由于赋码元时的任意性，因此费诺编码编出的码字不惟一；(3) 费诺编码虽属于概率匹配范畴，但并未严格遵守匹配规则，即不全是按“概率大码长小、概率小码长大”来决定码长，有时会出现概率小码长反而小的情况，如表3.4.2中符号u4对应的码字就是如此，因此平均码长一般不会最小。
３．７哈夫曼编码哈夫曼编码是一种效率比较高的变长无失真信源编码方法，它的平均码长最短，因此是最佳编码。
下面主要介绍二进制哈夫曼编码。
a、原理：构造一个码树。
b、编码步骤：(1) 将信源符号按概率从大到小的顺序排列，为方便起见，令p(x1)≥p(x2)≥…≥p(x n) 。
(2) 对概率最小的两个信源符号求其概率之和，同时给两个符号分别赋予码元“0”和“1”。
将“概率之和”当作一个新符号的概率，与剩下符号的概率一起，形成一个缩减信源，结果得到一个只包含（n－1）个信源符号的新信源，称为信源的第一次缩减信源，用S1表示。
(3) 将缩减信源S1的符号仍按概率从大到小的顺序排列，重复步骤2，得到只含（n－2）个符号的缩减信源S2。
(4) 重复上述步骤，直至缩减信源只剩下两个符号为止，此时所剩两个符号的概率之和必为1。
(5) 按上述步骤实际上构造了一个码树，从树根到端点经过的树枝即为码字。
c、结合【例3.4.4】给出具体编码方法。
并计算其平均码长和编码效率。
d、总结哈夫曼编码的基本特点：第一，哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。
第二，哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。
