《第四章 无失真信源编码ppt课件.ppt》由会员分享，可在线阅读，更多相关《第四章 无失真信源编码ppt课件.ppt（96页珍藏版）》请在三一办公上搜索。
1、信息传输系统,第二章:信息量,第三章信道与信道容量,第四章:无失真信源编码,第四章 无失真信源编码,信源编码的概念 信源编码的模型等长编码变长编码香农费诺艾利斯编码霍夫曼编码费诺编码,信源编码的概念,要把信源的信息高速度、高质量地通过信道传送给信宿，一般要通过信源编码和信道编码来完成。 研究信源编码：只考虑有效性，不考虑可靠性,信源编码的概念,信源编码的作用,例： 信源发送符号为 是，否 信道中能够传输的符号为0，1,符号变换：用信道能传输的符号来代表信源发出的消息，使信源适合于信道的传输。,信源编码的概念,例：电报： 1：母亲患癌症，情况危急，请速归。 2：母病危速归,例： 信源发送符号为
2、是，否,方案1： 0，1 方案2： 000，111,有效传输(冗余度压缩)减少信源的剩余度 在不失真的条件下，用尽可能少的符号来传送信源信息，提高信息传送率。,信源编码的概念,一般而言，编码就是用数字形式表示消息的过程。编码实质上是对要处理的源数据按一定的规则进行变换。这些数学方法和变换策略的目的都是力图用尽可能少的符号或位来表示较多、较长的符号及消息。,具体来说，信源编码就是根据信源的统计特性，对信源发出的消息进行编码。,信源编码的概念,对于离散信源，如果信源的统计特性已知，便可直接进行编码。,对于连续信源，应根据采样定理将连续信号离散化。连续信号经过采样和量化就变成了离散信号。将离散信号按
3、一定规律与一组代码相对应就是编码 。,无失真信源编码的基本概念,根据能否在解码后完全准确的恢复出原始消息(信息熵是否变换)，将信源编码分为无失真信源编码和率失真信源编码.,信源编码模型,设信源概率空间为,对此信源进行二进制编码。,编码的定义,如果一种编码方案,如果信源连续发送S1S2S3三个符号，则该信源编码的输出为,000110,编码的定义,假定这样的码经信道传输，在接收端收到以“0”“1”为符号的序列。如,000110,如果一种编码方案,将此序列进行译码，能唯一地恢复原来的消息序列。,S1S1S1S3,信源编码模型,信源空间为：,编码符号表为,，用,的符号对消息 进行编码。,消息 与由 的
4、符号组成的符号序列相对应，用公式表示为,信源编码模型,叫做对应消息 的码字。,称为码元。,称为 的字长。,无失真信源编码的基本概念,码的分类,二元码：码符号集为 ，所有码字都是由0、1组成的二元符号序列。,r进制码元：码元符号集为 ， 所有码字都是由0、1.r-1组成的r进制数字序列。,码的分类,根据编码后码字的长度,码的分类,根据码字的情况,根据译码恢复出的序列的情况唯一可译码（UDC） 任意有限长的码字序列，只能被唯一地分割成一个个的码字，且任一码字只与唯一一个信源符号对应，便称为唯一可译码。又称单义码。 非唯一可译码,码的分类,例：,码的分类,例：,要保证无失真编码，必须采用唯一可译码。
5、,码的分类,001110,等长非奇异码一定是唯一可译码。,根据码字相互关联的情况非续长码 任意一个码字都不是另一个码字的续长，称为非续长码。换句话说，不能在任意一个码字后边，添上一些码元构成一个新的码字。 因此，当非续长码码字的最后一个码字出现时，译码器能立即判断一个码字已经结束，可以立即译码，又称即时码或立即码。,码的分类,续长码,码的分类,结论： 非续长码一定是单义码，而单义码却不一定是非续长码。,0011101011,码的分类,非奇异码、唯一可译码、非续长码的关系,树图法,树图法：所有码字用码树描述出来。码树是一棵倒置的树，最上端是根节点，从根节点出发不断向下伸出树枝，分支与码符号一一对
6、应。一个节点继续分支，称为中间节点；一个节点不再继续分支，称为终端节点。 将信源符号对应的节点用实心圆表示，从根节点到这个节点经过的分支对应的码符号序列就是码字；没有与信源符号对应的节点用空心圆表示,对于码 和用码树表示如下：,树图法,编码：用树图法构造非续长码，只要将信源符号全部对应于终端节点，而不是中间节点即可。这样就可以保证任何一个码字都不是其它码字的前缀 解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码符号序列中所有的码符号。,非续长码 -树图构造,例：给定编码符号表X=0，1，码字W=W1，W2，W3，W
7、4,字长分别是n1=1，n2=2 ，n3=n4=3，求非续长码。,非续长码 -树图构造,非续长码 -树图构造,非续长码不是唯一的。全部终端节点都代表码字，这种情况叫做用尽的非续长码。,单义码存在定理,设信源S的符号集为 ，码符号集 ，又设码字为 ，其码长分别为 。则存在单义码的必要条件是： 满足Kraft不等式，即 其中，q是码字的个数，r是编码符号表的码元个数，ni 是字长。若上式成立，就一定能构造一个r进制的唯一可译码。,例：给定编码符号表X=0，1，码字W=W1，W2，W3，W4 = 0，01，10，011,分别由1，2，2，3个码元构成的码字,单义码存在定理,按照不等式可知，q=4，r
8、=2，n1=1，n2=2 ，n3=2 ，n4=3 ，代入Kraft不等式左边得,单义码存在定理,如W改为为0，10，110，111， 即n1=1，n2=2 ，n3=3 ，n4=3,如W改为为0，01，110，011， 即n1=1，n2=2 ，n3=3 ，n4=3,单义码存在定理,码字不满足克拉夫特不等式，则肯定不是唯一可译码。码字满足克拉夫特不等式，并不一定是唯一可译码，只是说存在这样的码长条件的唯一可译码。,等长编码,等长码：各个码字码长都相等的码,可以编码成 有效性： 更好 可靠性： 更好，提供纠错功能,对于等长码，如果是非奇异码，那么一定是唯一可译码,等长编码,信源符号集有2个符号，可以
9、用 编码，码长为1； 信源符号有4个，码长为1就不行了，必须用码长为2的等长码 设信源符号集中有符号q个；用二元码进行编码，码长为 ，能够提供的最多码字为 个，因此要满足,等长码码长不能无限制缩短。,用 准则编解码过程非常简单，但是编码效率非常低，有效性很差。主要原因是没有考虑到信源符号间的相关性。,等长编码,如：英文电报由26个字母和6个标点符号组成，共32个信源符号。用2元等长码编码，传输一个字母或标点，用5个2元码符号，而5个2元码符号能够传输的最大信息量是5bit。实际统计，每个英文字符包含信息量1.4bit,等长编码,N次扩展码：扩展前，一个信源符号编码成一个码字。N次扩展码，就是把
10、N个信源符号组成的序列，变换成N个码字组成的序列,N次等长扩展码,如信源符号集 码字为2次扩展后信源符号集2次扩展码为,N次等长扩展码,进行N次扩展，共有 个信源符号， 需要 ， 平均到扩展前每一个信源符号， 这样看来并没有提高编码效率 考虑到相关性，不用对所有 个信源符号进行编码，有些信源符号不可能出现，有些出现的概率非常小。码长自然减少了,N次等长扩展码,对信源扩展的次数越多，利用信源的相关性就越充分，编出来的码长平均到每个信源符号上平均码长就越短，编码效率就越高 对信源做无限次扩展之后，能够将编码效率提高到一个极限的程度,等长编码定理,一个平稳离散信源的信息熵为 ，若对长为N的信源符号序
11、列进行等长编码，N长符号对应的码长为 ,设码符号集中有r个码符号。 对于任意的 ，只要满足 当N足够大时，可以实现几乎无失真的编码。反之，则不可能实现无失真的编码,等长编码定理,编码效率：描述编码的优劣,编码后信息率,每个信源符号的信息熵,定义编码效率为,码的冗余度(编码后的新信源的冗余度）,等长编码,例：离散无记忆信源(DMS),用码元表X=0,1对U的单符号进行等长编码,必须用码长为3的等长码,要无失真的信息传输，必须满足,编码后信息率,每个信源符号的信息熵,定义编码效率为,码的冗余度(编码后的新信源的冗余度）,等长编码定理,等长信源编码的意义：通过不断的扩展信源进行等长编码，可以不断提高
12、编码效率，当扩展次数N很大的时候，能够达到最大的编码效率 编码后平均每个信源符号对应的码符号序列所能携带的最大的信息量，一定要大于等于信源本身的信息量,等长编码的缺陷,会产生一定的误差：因为把一些小概率的组合去掉，没有进行编码扩展维数太大：要达到比较高的编码效率，扩展信源的维数需要很大,例：信源的概率分布 ，要达到0.96的编码效率，错误率控制在 以内，信源需要扩展4130万次，扩展后信源符号数为 个,变长编码-平均码长,对于变长编码，不要求每个码字的码长都很,但却要求整个码字集合的平均码长较小,变长编码-平均码长,显然，要是平均码长短，除了要缩短每一个码字的码长外，还要合理的分配长短码，使概
13、率较大的信源符号使用较短的码，概率较小的信源符号使用较长的码对于某一信源，若有一个唯一可译码，其平均码长小于其它任何唯一可译码的平均码长，则称此码为紧致码，或最佳码,变长信源编码定理（香农第一定理),平稳信源信息熵为 ，对长为N的信源符号序列进行编码，编码后的平均码长为 ，码符号有r个，那么要做到无失真编码，平均码长必须满足,另一方面，一定存在唯一可译码，其平均码长满足：,即：,变长编码-变长信源编码定理,香农第一定理给出了无失真信源编码的平均码长所能达到的极限值，但是并不是所有的信源编码方法都能够达到这个极限值。为了衡量各种编码到达极限状况的程度，定义了编码效率：,相应的码的冗余度为：,变长
14、编码-变长信源编码定理,【例】信源用0、1构成即时码,等长编码,变长编码-变长信源编码定理,对信源进行二次扩展,并变成编码,变长编码-变长信源编码定理,香农第一定理的意义：通过不断的扩展信源进行变长编码，可以不断提高编码效率，当扩展次数N很大的时候，能够达到最大的编码效率 编码后平均每个信源符号对应的码符号序列所能携带的最大的信息量，一定要大于等于信源本身的信息量,经典编码方法,霍夫曼（Huffman）编码香农（Shannon）编码费诺（Fano）编码,霍夫曼（Huffman）编码,霍夫曼编码是1952年由霍夫曼提出的一种编码方法。这种编码方法的主导思想是根据源数据符号发生的概率进行编码。在源
15、数据中出现概率越高的符号，相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据。理论表明，在数据压缩中，霍夫曼编码方法是接近压缩比上限的一种较好的编码方法。,霍夫曼（Huffman）编码,霍夫曼编码及其变种，在压缩编码领域中应用的非常广泛。数字图像 JPEG运动图像 MPEG2、H.261、H.263 通信编码 Modem ADSL,(1)将n个信源U的各个符号ui按概率分布p（ui）以递减次序排列起来。,霍夫曼（Huffman）编码,编码方法,(2)将两个概率最小的信源符号合并成一个新符号，新符号的值为两个信源符号值的和，从而得到只包含n1个符号的新信源，称为
16、U信源的缩减信源U1。,(3)把缩减信源U1的符号仍按概率以递减次序排列，然后将其中两个概率最小的符号合并成一个符号，这样又形成了n2个符号的缩减信源U2。,霍夫曼（Huffman）编码, (4)依次继续下去，直至信源最后只剩下个符号为止。,(5)将每次合并的两个信源符号分别用0和1码符号表示。 , (6)从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即得各信源符号对应的码字。,霍夫曼（Huffman）编码,霍夫曼编码例1,编成2元霍夫曼码，求编码效率,霍夫曼编码例1,霍夫曼编码例1,霍夫曼编码例1,霍夫曼编码例1,例：离散无记忆信源:,对应的霍夫曼编码如图所示：,霍夫
17、曼编码-课堂作业,霍夫曼编码-课堂作业,霍夫曼编码,对于同一个信源，霍夫曼编码的方式有很多种：左分支编0、右分支编1；左分支编1、右分支编0；左右分支混编编出来的平均码长都一样,霍夫曼编码,合并后的新信源符号与其它信源符号概率相同时，合并后的符号插入到什么位置，编出来的码也是不一样的：例1中是将新信源符号插入到最前面例2将新信源符号插入到最后面,霍夫曼编码例2,编成2元霍夫曼码，求编码效率,霍夫曼编码例2,霍夫曼编码例2,霍夫曼编码例2,霍夫曼编码例2,霍夫曼编码,两种编码方式的编码效率相等。第一种方法只有两种码长：2、3；第二种方法有4种码长14第一种方法方差比较小，更接近于等长码，更简单，
18、更容易实现,霍夫曼编码,扩展到r元霍夫曼编码，只要每次取r个最小概率的信源符号即可编成3元霍夫曼码，求编码效率,霍夫曼编码例3,霍夫曼编码例3,霍夫曼编码例3,霍夫曼编码解码,霍夫曼编码的所有码字都在码树的终端节点上，所以霍夫曼码是即时码。 因此霍夫曼码的解码可以使用即时码的解码方法。从码树的根节点开始，按码符号对应的分支逐步向下，直到找到一个终端节点。再从根节点开始对剩下的码符号序列做相同的处理，直到处理完所有的码符号。,霍夫曼编码解码,解码100101100011,霍夫曼编码解码,优点就是编码效率很好，是最佳编码缺点是容错性能非常差，只要有1位出现了错误，将可能导致后面的解码全部错误或翻译
19、不出来,费诺编码,霍夫曼编码在构造码树的时候，是从下层节点开始，逐级向上直到根节点的；而费诺编码正好相反，是由根节点出发，直到终端节点。费诺编码的思想就是使编码后的码集尽可能的等概率分布。费诺码不是最佳编码方法，但是有时候也能编出最佳码 。,费诺编码,将信源符号按概率大小递减排列，按照概率之和分为大致相等的r组（2组），分别编以0、1r-1（0、1），再分别对r个（2个）组做相同的处理，直到每个组只有一个信源符号为止。,例：求2元费诺码及编码效率,费诺编码,费诺编码,课堂练习,离散无记忆信源 对源信源进行二维扩展后，采用费诺编码法，求编码效率；,课堂练习,课堂练习,香农编码,香农编码法多余度较
20、大，实用性不大，但在理论上的意义很大。编码方法如下：,将信源消息出现的概率的大小依次排列,2.从最初0个，1个，2个依次相加，并分别设为 ，即,香农编码,4.确定满足下列不等式的整数,3.用二进制数表示,5.令 的二进表示形式的小数点后面 位为 。则这个 为对应于第j个消息的码符号。,香农编码,小数：基数乘法（1）将给定的十进制纯小数乘以基数2，其积的整数部分便是等值二进制纯小数的最高位（2）将上一步中乘积的小数部分再除以基数2，所得乘积的整数部分便是次高位。（3）重复步骤2，直到乘积的小数部分为0，或者达到要求的精确度为止。 各次乘积的整数部分便是二进制纯小数的各位，最后一次乘积的整数部分是最低位。,香农编码,香农编码,【例】离散无记忆信源概率分布为 ： 求对应的香农编码,香农编码,香农编码,香农编码,信源编码模型,
