第四章-无失真信源编码

信息论基础李富年武汉科技大学信息传输系统等效信道信源编码器信道编码器信道解码器信源解码器信源消息信宿消息第二章:信息量第三章信道与信道容量第四章:无失真信源编码信息论基础李富年武汉科技大学第四章无失真信源编码信源编码的概念信源编码的模型等长编码变长编码香农－费诺－艾利斯编码霍夫曼编码费诺编码信息论基础李富年武汉科技大学信源编码的概念要把信源的信息高速度、高质量地通过信道传送给信宿，一般要通过信源编码和信道编码来完成。研究信源编码：只考虑有效性，不考虑可靠性信源信宿信源编码器信道解码器信道编码器信源解码器消息消息等效无噪声信道信道干扰源信号S噪声S＋N调制器解调器信息论基础李富年武汉科技大学信源编码的概念信源编码的作用例：信源发送符号为{是，否}信道中能够传输的符号为{0，1}符号变换：用信道能传输的符号来代表信源发出的消息，使信源适合于信道的传输。信息论基础李富年武汉科技大学信源编码的概念例：电报：1：母亲患癌症，情况危急，请速归。2：母病危速归例：信源发送符号为{是，否}方案1：{0，1}方案2：{000，111}有效传输(冗余度压缩)——减少信源的剩余度在不失真的条件下，用尽可能少的符号来传送信源信息，提高信息传送率。信息论基础李富年武汉科技大学信源编码的概念一般而言，编码就是用数字形式表示消息的过程。编码实质上是对要处理的源数据按一定的规则进行变换。这些数学方法和变换策略的目的都是力图用尽可能少的符号或位来表示较多、较长的符号及消息。具体来说，信源编码就是根据信源的统计特性，对信源发出的消息进行编码。信息论基础李富年武汉科技大学信源编码的概念对于离散信源，如果信源的统计特性已知，便可直接进行编码。对于连续信源，应根据采样定理将连续信号离散化。连续信号经过采样和量化就变成了离散信号。将离散信号按一定规律与一组代码相对应就是编码。信息论基础李富年武汉科技大学无失真信源编码的基本概念根据能否在解码后完全准确的恢复出原始消息(信息熵是否变换)，将信源编码分为无失真信源编码和率失真信源编码.否：率失真信源编码能：无失真信源编码号？能否完全恢复出原始信错有差错，没必要没有差编码，语音、图像，率失真编码：连续信源据，不能有差错编码，无失真编码：离散信源信息论基础李富年武汉科技大学信源编码模型设信源概率空间为1234:0.50.250.1250.125ssssS对此信源进行二进制编码。1234,,,sssss0,1B编码的过程就是建立之间元素的对应关系。和信息论基础李富年武汉科技大学编码的定义如果一种编码方案0011xs0122xs3310sx4411sx如果信源连续发送S1S2S3三个符号，则该信源编码的输出为000110信息论基础李富年武汉科技大学编码的定义001001010011011110假定这样的码经信道传输，在接收端收到以“0”“1”为符号的序列。如001001010011011110000110如果一种编码方案110sx2210sx33110sx44111sx将此序列进行译码，能唯一地恢复原来的消息序列。S1S1S1S3信息论基础李富年武汉科技大学信源编码模型信源空间为：)(......)()(......2121qqspspspsssS12{,,...}rXxxx编码符号表为，用的符号对消息进行编码。Xis信息论基础李富年武汉科技大学isX消息与由的符号组成的符号序列相对应，用公式表示为12.....iiiiiinsWxxx1,2,....ikixXkn信源编码模型叫做对应消息的码字。isiW称为码元。ikxiniW称为的字长。信息论基础李富年武汉科技大学无失真信源编码的基本概念无失真编码器12:,qSSSS信源符号集码字集合12:,qC码符号集12:,rXxxx12.....iiiiinWxxx信息论基础李富年武汉科技大学码的分类二元码：码符号集为，所有码字都是由0、1组成的二元符号序列。100,1,....1rr进制码元：码元符号集为，所有码字都是由0、1….r-1组成的r进制数字序列。信源符号码1码2S1000S2111S3102S4113信息论基础李富年武汉科技大学码的分类根据编码后码字的长度等长码变长码：码字集合中各码字的码长都相等：码字集合中各码字的码长不完全相等信源符号码1码2码3码4S1000001S21101110S310000100S41111111000信息论基础李富年武汉科技大学码的分类根据码字的情况ijijSSWW：所有码字都不相同，信源符号与码字之间唯一对应：码字集合中有相同的码字，即存在但非奇异码奇异码信源符号码1码2码3码4S1000001S20101110S310000100S41111111000信息论基础李富年武汉科技大学根据译码恢复出的序列的情况唯一可译码（UDC）任意有限长的码字序列，只能被唯一地分割成一个个的码字，且任一码字只与唯一一个信源符号对应，便称为唯一可译码。又称单义码。非唯一可译码码的分类信息论基础李富年武汉科技大学0101010例：10,11,0X码的分类例：0,01,10X要保证无失真编码，必须采用唯一可译码。01010101333SSSS1333SSSS2221SSSS信息论基础李富年武汉科技大学码的分类信源符号码1码2S10000S20101S31000S41111001110等长非奇异码一定是唯一可译码。信息论基础李富年武汉科技大学根据码字相互关联的情况非续长码任意一个码字都不是另一个码字的续长，称为非续长码。换句话说，不能在任意一个码字后边，添上一些码元构成一个新的码字。因此，当非续长码码字的最后一个码字出现时，译码器能立即判断一个码字已经结束，可以立即译码，又称即时码或立即码。码的分类续长码信息论基础李富年武汉科技大学码的分类信源符号码4码5S101S20101S3011001S41110001结论：非续长码一定是单义码，而单义码却不一定是非续长码。0011101011信息论基础李富年武汉科技大学码的分类非奇异码、唯一可译码、非续长码的关系非奇异码唯一可译码非续长码变长码非奇异码唯一可译码非续长码等长码信息论基础李富年武汉科技大学树图法•树图法：所有码字用码树描述出来。码树是一棵倒置的树，最上端是根节点，从根节点出发不断向下伸出树枝，分支与码符号一一对应。•一个节点继续分支，称为中间节点；一个节点不再继续分支，称为终端节点。•将信源符号对应的节点用实心圆表示，从根节点到这个节点经过的分支对应的码符号序列就是码字；没有与信源符号对应的节点用空心圆表示信息论基础李富年武汉科技大学对于码和用码树表示如下：0001001011100010010111110001000树图法信息论基础李富年武汉科技大学编码：用树图法构造非续长码，只要将信源符号全部对应于终端节点，而不是中间节点即可。这样就可以保证任何一个码字都不是其它码字的前缀解码：按照码符号的顺序，从根节点依次查询到终端节点，就得到对应的信源符号。再从根节点对剩下的码符号序列做相同的处理，直到处理完码符号序列中所有的码符号。非续长码-树图构造信息论基础李富年武汉科技大学例：给定编码符号表X={0，1}，码字W={W1，W2，W3，W4},字长分别是n1=1，n2=2，n3=n4=3，求非续长码。非续长码-树图构造信息论基础李富年武汉科技大学111000W1=1W2=01W3=001W4=000111000W1=0W2=10W3=110W4=111非续长码-树图构造①非续长码不是唯一的。②全部终端节点都代表码字，这种情况叫做用尽的非续长码。信息论基础李富年武汉科技大学单义码存在定理设信源S的符号集为，码符号集，又设码字为，其码长分别为。则存在单义码的必要条件是：满足Kraft不等式，即其中，q是码字的个数，r是编码符号表的码元个数，ni是字长。若上式成立，就一定能构造一个r进制的唯一可译码。},...,{:21qsssS12:{,,...}rXxxxq),...,2,1(,,qinrqi11qinir信息论基础李富年武汉科技大学例：给定编码符号表X={0，1}，码字W={W1，W2，W3，W4}={0，01，10，011},分别由1，2，2，3个码元构成的码字单义码存在定理按照不等式可知，q=4，r=2，n1=1，n2=2，n3=2，n4=3，代入Kraft不等式左边得189814141212411inqiniir信息论基础李富年武汉科技大学单义码存在定理如W改为为{0，10，110，111}，即n1=1，n2=2，n3=3，n4=31818141212411inqiniir如W改为为{0，01，110，011}，即n1=1，n2=2，n3=3，n4=31818141212411inqiniir信息论基础李富年武汉科技大学单义码存在定理码字不满足克拉夫特不等式，则肯定不是唯一可译码。码字满足克拉夫特不等式，并不一定是唯一可译码，只是说存在这样的码长条件的唯一可译码。信息论基础李富年武汉科技大学等长编码•等长码：各个码字码长都相等的码10否是11100010111000可以编码成有效性：更好可靠性：更好，提供纠错功能•对于等长码，如果是非奇异码，那么一定是唯一可译码信息论基础李富年武汉科技大学等长编码信源符号集有2个符号，可以用编码，码长为1；信源符号有4个，码长为1就不行了，必须用码长为2的等长码设信源符号集中有符号q个；用二元码进行编码，码长为，能够提供的最多码字为个，因此要满足1011100100ll2qlqllog2等长码码长不能无限制缩短。信息论基础李富年武汉科技大学用准则编解码过程非常简单，但是编码效率非常低，有效性很差。主要原因是没有考虑到信源符号间的相关性。qllog等长编码如：英文电报由26个字母和6个标点符号组成，共32个信源符号。用2元等长码编码，传输一个字母或标点，用5个2元码符号，而5个2元码符号能够传输的最大信息量是5bit。实际统计，每个英文字符包含信息量1.4bit信息论基础李富年武汉科技大学等长编码1231:0.4550.0010.544sssS1232:111333sssS000110131:0.4550.544ssS01信息论基础李富年武汉科技大学N次扩展码：扩展前，一个信源符号编码成一个码字。N次扩展码，就是把N个信源符号组成的序列，变换成N个码字组成的序列N次等长扩展码否是10否否否是是否是是11100100如信源符号集码字为2次扩展后信源符号集2次扩展码为信息论基础李富年武汉科技大学N次等长扩展码进行N次扩展，共有个信源符号，需要，平均到扩展前每一个信源符号，这样看来并没有提高编码效率考虑到相关性，不用对所有个信源符号进行编码，有些信源符号不可能出现，有些出现的概率非常小。码长自然减少了NqqNqLNNloglogqLlogNq信息论基础李富年武汉科技大学N次等长扩展码对信源扩展的次数越多，利用信源的相关性就越充分，编出来的码长平均到每个信源符号上平均码长就越短，编码效率就越高对信源做无限次扩展之后，能够将编码效率提高到一个极限的程度信息论基础李富年武汉科技大学等长编码定理一个平稳离散信源的信息熵为，若对长为N的信源符号序列进行等长编码，N长符号对应的码长为,设码符号集中有r个码符号。对于任意的，只要满足当N足够大时，可以实现几乎无失真的编码。反之，则不可能实现无失真的编码()HU0()logNlHUNrNl信息论基础李富年武汉科技大学等长编码定理编码效率：描述编码的优劣'logNlRrN编