第四章-无失真信源编码

《第四章-无失真信源编码》由会员分享，可在线阅读，更多相关《第四章-无失真信源编码（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，

7、1，码字W=W1，W2，W3，W4,字长分别是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个码元构成的码字,

8、单义码存在定理,按照不等式可知，q=4，r=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,单义码存在定理,码字不满足克拉夫特不等式，则肯定不是唯一可译码。码字满足克拉夫特不等式，并不一定是唯一可译码，只是说存在这样的码长条件的唯一可译码。,等长编码,等长码：各个码字码长都相等的码,可以编码成 有效性： 更好 可靠性： 更好，提供纠错功能,对于等长码，如果是非奇异码，那么一定是唯一可

9、译码,等长编码,信源符号集有2个符号，可以用 编 码，码长为1； 信源符号有4个，码长为1就不行了，必须 用码长为2的等长码 设信源符号集中有符号q个；用二元码进行 编码，码长为 ，能够提供的最多码字为 个，因此要满足,等长码码长不能无限制缩短。,用 准则编解码过程非常简单， 但是编码效率非常低，有效性很差。主要 原因是没有考虑到信源符号间的相关性。,等长编码,如：英文电报由26个字母和6个标点符号组成，共32个信源符号。用2元等长码编码，传输一个字母或标点，用5个2元码符号，而5个2元码符号能够传输的最大信息量是5bit。实际统计，每个英文字符包含信息量1.4bit,等长编码,N次扩展码：扩

10、展前，一个信源符号编码成 一个码字。N次扩展码，就是把N个信源符号 组成的序列，变换成N个码字组成的序列,N次等长扩展码,如信源符号集 码字为 2次扩展后信源符号集 2次扩展码为,N次等长扩展码,进行N次扩展，共有 个信源符号， 需要 ， 平均到扩展前每一个信源符号， 这样看来并没有提高编码效率 考虑到相关性，不用对所有 个信源符号 进行编码，有些信源符号不可能出现，有些 出现的概率非常小。码长自然减少了,N次等长扩展码,对信源扩展的次数越多，利用信源的相关性就越充分，编出来的码长平均到每个信源符号上平均码长就越短，编码效率就越高 对信源做无限次扩展之后，能够将编码效率提高到一个极限的程度,等

11、长编码定理,一个平稳离散信源的信息熵为 ，若对 长为N的信源符号序列进行等长编码，N长符号 对应的码长为 ,设码符号集中有r个码符号。 对于任意的 ，只要满足 当N足够大时，可以实现几乎无失真的编码。 反之，则不可能实现无失真的编码,等长编码定理,编码效率：描述编码的优劣,编码后信息率,每个信源符号的信息熵,定义编码效率为,码的冗余度(编码后的新信源的冗余度）,等长编码,例：离散无记忆信源(DMS),用码元表X=0,1对U的单符号进行等长编码,必须用码长为3的等长码,要无失真的信息传输，必须满足,编码后信息率,每个信源符号的信息熵,定义编码效率为,码的冗余度(编码后的新信源的冗余度）,等长编码定理,等长信源编码的意义： 通过不断的扩展信源进行等长编码，可以不断提高编码效率，当扩展次数N很大的时候，能够达到最大的编码效率 编码后平均每个信源符号对应的码符号序列所能携带的最大的信息量，一定要大于等于信源本身的信息量,等长编码的缺陷