第三章无失真信源编码精选文档.ppt

《第三章无失真信源编码精选文档.ppt》由会员分享，可在线阅读，更多相关《第三章无失真信源编码精选文档.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章无失真信源编码本讲稿第一页，共五十九页 引言引言 编码的定义编码的定义定长编码定理定长编码定理变长编码定理变长编码定理变长编码方法变长编码方法本讲稿第二页，共五十九页引言引言什么是编码什么是编码香农信息论三大定理香农信息论三大定理编码的分类编码的分类编码的任务和途径编码的任务和途径编码器编码器本讲稿第三页，共五十九页什么是编码什么是编码信源编码和信道编码信源编码和信道编码 通信的实质是传输信息，要求传输具有高效率和质量：（1）在不失真和允许一定失真的条件下，用尽可能少的符号传送信源信息，以便提高信息传输率。（2）在信道受干扰的情况下，增加信号的抗干扰能力，以便提高信息传输的可靠性。解决以

2、上两个问题需要引入信源编码和信道编码。本讲稿第四页，共五十九页什么是编码什么是编码生活中编码实例生活中编码实例?学号、身份证号码、一卡通、汉语等编码。编码实质：编码实质：信息的表示。结论结论:信息无处不在，编码无处不在。本讲稿第五页，共五十九页香农信息论三大定理香农信息论三大定理第一极限定理第一极限定理:无失真信源编码定理。第二极限定理第二极限定理:信道编码定理(包括离 散和连续信道)。第三极限定理第三极限定理:限失真信源编码定理。本讲稿第六页，共五十九页编码的分类编码的分类编码：编码：信源编码、信道编码。信源编码：信源编码：无失真信源编码、限失真信源编码。无失真信源编码：无失真信源编码：适用

3、于离散信源或数字 信号。限失真信源编码：限失真信源编码：适用于连续信源或模拟信号，如语音、图像等信号的数字处理。本讲稿第七页，共五十九页信源编码目的与方法信源编码目的与方法信源编码：信源编码：将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。目的：目的：提高通信的有效性。方法：方法：减少信源冗余度。本讲稿第八页，共五十九页信源编码的基本途径信源编码的基本途径信源编码的基本途径信源编码的基本途径 解除相关性解除相关性：使序列中的各个符号尽可能地互相独立。概率均匀化：概率均匀化：使编码中各个符号出现的概率尽可能地相等。信源编码的基础信源编

4、码的基础信源编码的基础信源编码的基础：无失真信源编码定理和限失真信源编码定理。本讲稿第九页，共五十九页编码定理表明：编码定理表明：（1）必存在一种编码方法，使代码的平均长度可任意接近必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵。但不能低于符号熵。（2）达到这目标的途径，就是使概率与码长匹配。达到这目标的途径，就是使概率与码长匹配。本讲稿第十页，共五十九页编码器编码器不少原始信源的消息符号不适应信道的传输；原始信源消息符号的传输效率低；编码器输入端为原始信源u，其符号集为S:s1,s2,sq；si(i=1,2,q)；而信道所能传输的符号集为x:x1,x2,xr；编码器的功能：用

5、符号集x中的元素，将原始信源的符号si变换为相应的码字符号Wi，(i=1,2,q)，所以编码器输出端的符号集为C=W1,W2,Wq。本讲稿第十一页，共五十九页编码器的数学模型编码器的数学模型S=原始信源符号集；x=码元符号集；C=码字符号集；（码组）基本源编码基本源编码消息集合消息集合码字集合码字集合本讲稿第十二页，共五十九页一些基本概念一些基本概念二元码定长码变长码非奇异码奇异码同价码分组码唯一可译码即时码码的前缀码树本讲稿第十三页，共五十九页1.二元码二元码 若码符号集为X=0,1，所有码字都是二元符号序列，则称为二元码。2.定长码定长码 若一组码中所有码字的码长都相同，即li=l（i=1

6、,2,n）,则称为定长码。本讲稿第十四页，共五十九页3.变长码变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）11111本讲稿第十五页，共五十九页4.非奇异码非奇异码 若一组码中所有码字都不相同，即所有信源符号映射到不同的码符号序列，则称码为非奇异码。本讲稿第十六页，共五十九页5.奇异码奇异码若一组码中有相同的码字，则称码为奇异码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）00S2p（s2）1110S3p

7、（s3）0000S4p（s4）1110本讲稿第十七页，共五十九页6.同价码同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。7.分组码分组码 将信源符号集中的每个信源符号映射成一个固定的码字，这样的码称为分组码。本讲稿第十八页，共五十九页8.唯一可译码唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。注意：注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。变长码则不一定，主要是不能固定长度分组。唯一可译码还有判定准则，后面将介绍。本讲稿第十九页，共五十九页唯一可译码唯一可译码(续续)信源符号si

8、信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）11111本讲稿第二十页，共五十九页9.即时码即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。信源符号si码1码2S111S21001S3100001S410000001本讲稿第二十一页，共五十九页10.码的前缀码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。11.码树码树 码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树（r叉树，r进制树）。当然二

9、元码对应的是二叉树或二元树。树根、叶子节点、中间节点、深度、码长。整树、非整树、全树。本讲稿第二十二页，共五十九页码树图码树图本讲稿第二十三页，共五十九页唯一可译码定理唯一可译码定理设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则唯一可译码存在的充要条件为码长组合满足Kraft不等式，即 式中，式中，r r是进制数，是进制数，q q是信源符号数，是信源符号数，l l为码字长度。为码字长度。本讲稿第二十四页，共五十九页唯一可译码唯一可译码Kraft不等式：是唯一可译码的充要条件，也是即时码的充要条件；Kra

10、ft不等式指明了即时码的码长必须满足的条件；充要条件是对于码长组合而言，而不是对于码字本身而言，即满足Kraft不等式的码长组合一定能构成至少一种唯一码，唯一码的码长组合一定满足Kraft不等式。否则无法构成唯一可译码。本讲稿第二十五页，共五十九页唯一可译码唯一可译码有些码字的码长组合虽满足Kraft不等式，但不是唯一码。Kraft 不等式不能用来判断W是否是唯一可译码，但不满足该不等式的W一定不是唯一可译码。唯一可译码判别准则：用来判断W是否是唯一可译码。本讲稿第二十六页，共五十九页无失真信源编码定理研究内容无失真信源编码定理研究内容若信源输出符号序列的长度若信源输出符号序列的长度 ，即，即

11、变换成由变换成由K KL L个符号组成的码序列（码字个符号组成的码序列（码字)变换要求变换要求:(1)(1)能够无失真或无差错地从能够无失真或无差错地从Y恢复恢复X，也就是能正确地进行反变换，也就是能正确地进行反变换或译码或译码。(2)(2)传送传送Y时所需要的信息率最小时所需要的信息率最小。本讲稿第二十七页，共五十九页 由于由于Y Yk k可取可取m m种可能值，即平均每个符号输出的最大信种可能值，即平均每个符号输出的最大信息量为息量为logmlogm，K KL L长码字的最大信息量为长码字的最大信息量为K KL Llogmlogm。用该码字表。用该码字表示示L L长的信源序列长的信源序列,

12、则送出一个信源符号所需要的信息率则送出一个信源符号所需要的信息率平均为平均为:其中其中 是是Y Y所能编成的码字的个数。所能编成的码字的个数。信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使 最小。最小。无失真信源编码定理研究内容无失真信源编码定理研究内容:(1)(1)最小信息率为多少时，才能得到无失真的译码？最小信息率为多少时，才能得到无失真的译码？(2)(2)若小于这个信息率是否还能无失真地译码？若小于这个信息率是否还能无失真地译码？本讲稿第二十八页，共五十九页第二节第二节 定长编码定理定长编码定理定长信源编码定理定长信源编码定理由由L个符号组成的、平均符号熵为个符号组

13、成的、平均符号熵为HL（X）的无记忆平稳信源符）的无记忆平稳信源符号序列号序列，可用，可用KL个符号个符号（每个符号有（每个符号有m种可能值）进行定长编种可能值）进行定长编码。对任意码。对任意，只要，只要(注注:把把L移过去观察移过去观察)则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几乎必足够大时，译码几乎必定出错。定出错。本讲稿第二十九页，共五十九页说明说明（1）当编码器容许的输出信息率，也就是当每个信源符）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是号

14、所必须输出的码长是时，只要时，只要，这种编码器一定可以做到几，这种编码器一定可以做到几乎乎无无失失真真，也也就就是是收收端端的的译译码码差差错错概概率率接接近近于于零零，条件是所取的符号数条件是所取的符号数L足够大。足够大。本讲稿第三十页，共五十九页(2)将定理的条件改写成将定理的条件改写成 其中：左边：其中：左边：KL长码字所能携带的最大信息量，长码字所能携带的最大信息量，右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。上述定理表明，只要码字所能携带的信息量大于信源序列输出上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是的信息量

15、，则可以使传输几乎无失真，当然条件是L足够大。足够大。反之，当反之，当 时，不可能构成无失真的编码，也就是不时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。可能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有时，则为临界状态，可能无失真，也可能有失真。失真。本讲稿第三十一页，共五十九页第三节第三节 变长编码定理变长编码定理单个符号变长编码定理单个符号变长编码定理:若若一一离离散散无无记记忆忆信信源源的的符符号号熵熵为为H（X），每每个个信信源源符符号号用用m进进制制码码元元进进行行变变长长编编码码，一一定定存存在在一一种种无

16、无失失真真编编码码方方法法，其其码码字字平平均均长长度度满满足足下下列不等式列不等式 本讲稿第三十二页，共五十九页离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理对于平均符号熵为对于平均符号熵为HL（X）的离散平稳无记忆）的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息信源，必存在一种无失真编码方法，使平均信息率率满足不等式满足不等式 其中其中为任意小正数。为任意小正数。本讲稿第三十三页，共五十九页证明证明:设用设用m进制码元作变长编码，序列长度为进制码元作变长编码，序列长度为L个信源符号，则由（个信源符号，则由（331）式可以得到平均码字长度）式可以得到平均码字长度满足

17、下列不等式满足下列不等式 当当L足够大时，可使足够大时，可使，这就得到了这就得到了所需结论所需结论本讲稿第三十四页，共五十九页说明说明:(1)用变长编码来达到相当高的编码效率，一般所用变长编码来达到相当高的编码效率，一般所要求的符号长度要求的符号长度L可以比定长编码小得多。可得编码可以比定长编码小得多。可得编码效率的下界：效率的下界：本讲稿第三十五页，共五十九页(2)例例用二进制，用二进制，m2，log2m=l，H（X）2.55比特符号，若要求比特符号，若要求，则，则 本讲稿第三十六页，共五十九页(3)码的冗余度为码的冗余度为 码的码的冗余度冗余度用来衡量各种编码方法与最佳码的差用来衡量各种编

18、码方法与最佳码的差距距。本讲稿第三十七页，共五十九页例例331设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为求求:编码效率编码效率?解解:根据信源熵计算公式有：根据信源熵计算公式有：比特/符号 本讲稿第三十八页，共五十九页(1)定长编码定长编码若用二元定长编码（若用二元定长编码（0,1）来构造一个）来构造一个即时码：即时码：这时平均码长为这时平均码长为=1二元码符号二元码符号/信源符号信源符号编码效率为编码效率为(对于无记忆信源而言对于无记忆信源而言,有有HL(X)=H(X)输出的信息率为输出的信息率为R0.811比特二元码符号比特二元码符号本讲稿第三十九页，共五十九页(2)变长编码

19、变长编码假定信源序列的长度为假定信源序列的长度为L=2,其即时码如表其即时码如表3-3所示所示。序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10本讲稿第四十页，共五十九页这个码的码字平均长度这个码的码字平均长度单个符号的平均码长单个符号的平均码长编码效率编码效率输出的信息率为输出的信息率为R20961比特二元码符号比特二元码符号 本讲稿第四十一页，共五十九页将信源序列的长度增加，将信源序列的长度增加，L3或或L=4，对这些，对这些信源序列信源序列X进行编码进行编码，并求出其编码效率为并求出其编码效率为 信息传输率分别为

20、：信息传输率分别为：R30985比特二元码符号比特二元码符号R40991比特二元码符号比特二元码符号如果对这一信源采用定长二元码编码，要求编码效率达到如果对这一信源采用定长二元码编码，要求编码效率达到96时，时，允许译码错误概率允许译码错误概率。则根据（。则根据（326）式，自信息的方）式，自信息的方差差所需要的信源序列长度所需要的信源序列长度本讲稿第四十二页，共五十九页变长码相关结论变长码相关结论应用变长码往往在N不很大时，就可编出效率很高且无失真的码；变长码必须是唯一可译码，才能实现无失真编码；变长码要满足唯一可译码必须是非奇异码,而且任意有限长N次扩展码也必须是非奇异的；为了能够即时进行

21、译码，变长码还必须是即时码。本讲稿第四十三页，共五十九页第四节第四节 变长码的编码方法变长码的编码方法(1)最佳码定义最佳码定义凡是能载荷一定的信息量，且码字的平均长度最短，可分离凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。的变长码的码字集合都可称为最佳码。(2)最佳编码思想最佳编码思想将概率大的信息符号编以短的码字，概率小的符号编以长的码字，将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。使得平均码字长度最短。(3)最佳码的编码主要方法最佳码的编码主要方法香农（香农（Shannon）、费诺（）、费诺（Fano）、哈夫曼

22、（）、哈夫曼（Huffman）编）编码等。码等。本讲稿第四十四页，共五十九页3.4.1香农编码方法香农编码方法香农第一定理香农第一定理编码方法如下：编码方法如下：(1)将信源消息符号按其出现的概率大小依次排列将信源消息符号按其出现的概率大小依次排列(2)确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki：本讲稿第四十五页，共五十九页 (3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率(4)将累加概率将累加概率Pi变换成二进制数。变换成二进制数。(5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该消位即为该消息符号的二进制码字。息符号的二

23、进制码字。本讲稿第四十六页，共五十九页例例3-4-1设信源共设信源共7个符号消息，其概率和累加概率如表个符号消息，其概率和累加概率如表3-4-1所示。以所示。以i=4为例，为例，本讲稿第四十七页，共五十九页累加概率累加概率P4=0.57，变换成二进制为，变换成二进制为0.1001，由于，由于3，所以第，所以第4个消息的编个消息的编码码字为码码字为100。其他消息的码字可用同样方。其他消息的码字可用同样方法求得，法求得，7个消息符号对应的码字依次为：个消息符号对应的码字依次为：000,001,011,100,101,1110,1111110本讲稿第四十八页，共五十九页说明说明:(1)该信源共有该

24、信源共有5个三位的码字，各码字之间至少有一位个三位的码字，各码字之间至少有一位数字不相同，故是唯一可译码。同时可以看出，这数字不相同，故是唯一可译码。同时可以看出，这7个个码字都不是延长码，它们都属于即时码。这里码字都不是延长码，它们都属于即时码。这里L=1，m=2.(2)信源符号的平均码长信源符号的平均码长码元码元/符号符号 本讲稿第四十九页，共五十九页(3)平均信息传输率平均信息传输率 本讲稿第五十页，共五十九页3.4.2费诺编码方法费诺编码方法编码步骤：编码步骤：（1）将信源消息符号按其出现的概率大小依次排列：）将信源消息符号按其出现的概率大小依次排列：p(x1)p(x2)p(xn)。（

25、2）将依次排列的信源符号按概率值分为两大组，使两个）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元组的概率之和近于相同，并对各组赋予一个二进制码元“0”和和“1”。本讲稿第五十一页，共五十九页（3）将每一大组的信源符号进一步再分成两组，使划分后）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进的两个组的概率之和近于相同，并又赋予两个组一个二进制符号制符号“0和和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。）如此重复，直至每个组只剩下一个信源符号为止。（5）信源符号所对应的码字即为费诺码

26、。）信源符号所对应的码字即为费诺码。本讲稿第五十二页，共五十九页如何求出费诺码如何求出费诺码编码过程参见编码过程参见P44，表，表3-4-2。费诺码的平均码长费诺码的平均码长信息传输速率信息传输速率 本讲稿第五十三页，共五十九页3.4.3哈夫曼编码方法哈夫曼编码方法哈夫曼编码步骤：哈夫曼编码步骤：（1）将）将n个信源消息符号按其出现的概率大小依个信源消息符号按其出现的概率大小依次排列，次排列，p（x1）p（x2）p（xn）（2）取两个概率最小的字母分别配以）取两个概率最小的字母分别配以0和和1两码元，两码元，并将这两个概率相加作为一个新字母的概率，与并将这两个概率相加作为一个新字母的概率，与未

27、分配的二进符号的字母重新排队。未分配的二进符号的字母重新排队。本讲稿第五十四页，共五十九页（3）对重排后的两个概率最小符号重复步骤（）对重排后的两个概率最小符号重复步骤（2）的过程。）的过程。（4）不断继续上述过程，直到最后两个符号配以）不断继续上述过程，直到最后两个符号配以0和和1为止。为止。（5）从最后一级开始，向前返回得到各个信源符号所）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。对应的码元序列，即相应的码字。本讲稿第五十五页，共五十九页哈夫曼编码过程，见哈夫曼编码过程，见P44表表3-4-3所示所示说明说明:哈夫曼码的平均码长为哈夫曼码的平均码长为信息传输速

28、率信息传输速率 本讲稿第五十六页，共五十九页问题问题:为何哈夫曼编码方法得到的码并非是唯一的为何哈夫曼编码方法得到的码并非是唯一的?(1)每每次次对对信信源源缩缩减减时时，赋赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以以任任意意的的，所所以以可可以以得得到到不不同同的的哈哈夫夫曼曼码码，但但不会影响码字的长度。不会影响码字的长度。本讲稿第五十七页，共五十九页(2)对对信信源源进进行行缩缩减减时时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同同时时，这这两两者者在在缩缩减减信信源源中中进进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码码。此此时时将将影影响响码码字字的的长长度度，一一般般将将合合并并的的概概率率放在上面，这样可获得较小的码方差。放在上面，这样可获得较小的码方差。本讲稿第五十八页，共五十九页例例342 设有离散无记忆信源设有离散无记忆信源哈夫曼编码如下哈夫曼编码如下(见书见书P45):本讲稿第五十九页，共五十九页