第三章无失真信源编码优秀PPT.ppt

第三章无失真信源编码现在学习的是第1页，共59页 引言引言 编码的定义编码的定义定长编码定理定长编码定理变长编码定理变长编码定理变长编码方法变长编码方法现在学习的是第2页，共59页引言引言什么是编码什么是编码香农信息论三大定理香农信息论三大定理编码的分类编码的分类编码的任务和途径编码的任务和途径编码器编码器现在学习的是第3页，共59页什么是编码什么是编码信源编码和信道编码信源编码和信道编码 通信的实质是传输信息，要求传输具有高效率和质量：（1）在不失真和允许一定失真的条件下，用尽可能少的符号传送信源信息，以便提高信息传输率。（2）在信道受干扰的情况下，增加信号的抗干扰能力，以便提高信息传输的可靠性。解决以上两个问题需要引入信源编码和信道编码。现在学习的是第4页，共59页什么是编码什么是编码生活中编码实例生活中编码实例?学号、身份证号码、一卡通、汉语等编码。编码实质：编码实质：信息的表示。结论结论:信息无处不在，编码无处不在。现在学习的是第5页，共59页香农信息论三大定理香农信息论三大定理第一极限定理第一极限定理:无失真信源编码定理。第二极限定理第二极限定理:信道编码定理(包括离 散和连续信道)。第三极限定理第三极限定理:限失真信源编码定理。现在学习的是第6页，共59页编码的分类编码的分类编码：编码：信源编码、信道编码。信源编码：信源编码：无失真信源编码、限失真信源编码。无失真信源编码：无失真信源编码：适用于离散信源或数字 信号。限失真信源编码：限失真信源编码：适用于连续信源或模拟信号，如语音、图像等信号的数字处理。现在学习的是第7页，共59页信源编码目的与方法信源编码目的与方法信源编码：信源编码：将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。目的：目的：提高通信的有效性。方法：方法：减少信源冗余度。现在学习的是第8页，共59页信源编码的基本途径信源编码的基本途径信源编码的基本途径信源编码的基本途径 解除相关性解除相关性：使序列中的各个符号尽可能地互相独立。概率均匀化：概率均匀化：使编码中各个符号出现的概率尽可能地相等。信源编码的基础信源编码的基础信源编码的基础信源编码的基础：无失真信源编码定理和限失真信源编码定理。现在学习的是第9页，共59页编码定理表明：编码定理表明：（1）必存在一种编码方法，使代码的平均长度可任意接必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵。近但不能低于符号熵。（2）达到这目标的途径，就是使概率与码长匹配。达到这目标的途径，就是使概率与码长匹配。现在学习的是第10页，共59页编码器编码器不少原始信源的消息符号不适应信道的传输；原始信源消息符号的传输效率低；编码器输入端为原始信源u，其符号集为S:s1,s2,sq；si(i=1,2,q)；而信道所能传输的符号集为x:x1,x2,xr；编码器的功能：用符号集x中的元素，将原始信源的符号si变换为相应的码字符号Wi，(i=1,2,q)，所以编码器输出端的符号集为C=W1,W2,Wq。现在学习的是第11页，共59页编码器的数学模型编码器的数学模型S=原始信源符号集；x=码元符号集；C=码字符号集；（码组）基本源编码基本源编码消息集合消息集合码字集合码字集合现在学习的是第12页，共59页一些基本概念一些基本概念二元码定长码变长码非奇异码奇异码同价码分组码唯一可译码即时码码的前缀码树现在学习的是第13页，共59页1.二元码二元码 若码符号集为X=0,1，所有码字都是二元符号序列，则称为二元码。2.定长码定长码 若一组码中所有码字的码长都相同，即li=l（i=1,2,n）,则称为定长码。现在学习的是第14页，共59页3.变长码变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）11111现在学习的是第15页，共59页4.非奇异码非奇异码 若一组码中所有码字都不相同，即所有信源符号映射到不同的码符号序列，则称码为非奇异码。现在学习的是第16页，共59页5.奇异码奇异码若一组码中有相同的码字，则称码为奇异码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）00S2p（s2）1110S3p（s3）0000S4p（s4）1110现在学习的是第17页，共59页6.同价码同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。7.分组码分组码 将信源符号集中的每个信源符号映射成一个固定的码字，这样的码称为分组码。现在学习的是第18页，共59页8.唯一可译码唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。注意：注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。变长码则不一定，主要是不能固定长度分组。唯一可译码还有判定准则，后面将介绍。现在学习的是第19页，共59页唯一可译码唯一可译码(续续)信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）11111现在学习的是第20页，共59页9.即时码即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。信源符号si码1码2S111S21001S3100001S410000001现在学习的是第21页，共59页10.码的前缀码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。11.码树码树 码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树（r叉树，r进制树）。当然二元码对应的是二叉树或二元树。树根、叶子节点、中间节点、深度、码长。整树、非整树、全树。现在学习的是第22页，共59页码树图码树图现在学习的是第23页，共59页唯一可译码定理唯一可译码定理设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则唯一可译码存在的充要条件为码长组合满足Kraft不等式，即 式中，式中，r r是进制数，是进制数，q q是信源符号数，是信源符号数，l l为码字长度。为码字长度。现在学习的是第24页，共59页唯一可译码唯一可译码Kraft不等式：是唯一可译码的充要条件，也是即时码的充要条件；Kraft不等式指明了即时码的码长必须满足的条件；充要条件是对于码长组合而言，而不是对于码字本身而言，即满足Kraft不等式的码长组合一定能构成至少一种唯一码，唯一码的码长组合一定满足Kraft不等式。否则无法构成唯一可译码。现在学习的是第25页，共59页唯一可译码唯一可译码有些码字的码长组合虽满足Kraft不等式，但不是唯一码。Kraft 不等式不能用来判断W是否是唯一可译码，但不满足该不等式的W一定不是唯一可译码。唯一可译码判别准则：用来判断W是否是唯一可译码。现在学习的是第26页，共59页无失真信源编码定理研究内容无失真信源编码定理研究内容若信源输出符号序列的长度若信源输出符号序列的长度 ，即，即变换成由变换成由K KL L个符号组成的码序列（码字个符号组成的码序列（码字)变换要求变换要求:(1)(1)能够无失真或无差错地从能够无失真或无差错地从Y恢复恢复X，也就是能正确地进行反，也就是能正确地进行反变换或译码变换或译码。(2)(2)传送传送Y时所需要的信息率最小时所需要的信息率最小。现在学习的是第27页，共59页 由于由于Y Yk k可取可取m m种可能值，即平均每个符号输出的最大信种可能值，即平均每个符号输出的最大信息量为息量为logmlogm，K KL L长码字的最大信息量为长码字的最大信息量为K KL Llogmlogm。用该码字表。用该码字表示示L L长的信源序列长的信源序列,则送出一个信源符号所需要的信息率平均则送出一个信源符号所需要的信息率平均为为:其中其中 是是Y Y所能编成的码字的个数。所能编成的码字的个数。信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使 最小。最小。无失真信源编码定理研究内容无失真信源编码定理研究内容:(1)(1)最小信息率为多少时，才能得到无失真的译码？最小信息率为多少时，才能得到无失真的译码？(2)(2)若小于这个信息率是否还能无失真地译码？若小于这个信息率是否还能无失真地译码？现在学习的是第28页，共59页第二节第二节 定长编码定理定长编码定理定长信源编码定理定长信源编码定理由由L个符号组成的、平均符号熵为个符号组成的、平均符号熵为HL（X）的无记忆平稳信源）的无记忆平稳信源符号序列符号序列，可用，可用KL个符号个符号（每个符号有（每个符号有m种可能值）进行定长编码。对任种可能值）进行定长编码。对任意意，只要，只要(注注:把把L移过去观察移过去观察)则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几乎必定出足够大时，译码几乎必定出错。错。现在学习的是第29页，共59页说明说明（1）当编码器容许的输出信息率，也就是当每个信源）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是符号所必须输出的码长是时，只要时，只要，这种编码器一定可以做到几，这种编码器一定可以做到几乎乎无无失失真真，也也就就是是收收端端的的译译码码差差错错概概率率接接近近于于零零，条件是所取的符号数条件是所取的符号数L足够大。足够大。现在学习的是第30页，共59页(2)将定理的条件改写成将定理的条件改写成 其中：左边：其中：左边：KL长码字所能携带的最大信息量，长码字所能携带的最大信息量，右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是量，则可以使传输几乎无失真，当然条件是L足够大。足够大。反之，当反之，当 时，不可能构成无失真的编码，也就是不可时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。能做一种编码器，能使收端译码时差错概率趋于零。时，则为临界状态，可能无失真，也可能有失真。时，则为临界状态，可能无失真，也可能有失真。现在学习的是第31页，共59页第三节第三节 变长编码定理变长编码定理单个符号变长编码定理单个符号变长编码定理:若若一一离离散散无无记记忆忆信信源源的的符符号号熵熵为为H（X），每每个个信信源源符符号号用用m进进制制码码元元进进行行变变长长编编码码，一一定定存存在在一一种种无失真编码方法，其码字平均长度满足下列不等式无失真编码方法，其码字平均长度满足下列不等式 现在学习的是第32页，共59页离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理对于平均符号熵为对于平均符号熵为HL（X）的离散平稳无记忆）的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信信源，必存在一种无失真编码方法，使平均信息率息率满足不等式满足不等式 其中其中为任意小正数。为任意小正数。现在学习的是第33页，共59页证明证明:设用设用m进制码元作变长编码，序列长度为进制码元作变长编码，序列长度为L个信源符号，则由（个信源符号，则由（331）式可以得到平均码字长度）式可以得到平均码字长度满足下列不等式满足下列不等式 当当L足够大时，可使足够大时，可使，这就得到了这就得到了所需结论所需结论现在学习的是第34页，共59页说明说明:(1)用变长编码来达到相当高的编码效率，一般所要求用变长编码来达到相当高的编码效率，一般所要求的符号长度的符号长度L可以比定长编码小得多。可得编码效率的可以比定长编码小得多。可得编码效率的下界：下界：现在学习的是第35页，共59页(2)例例用二进制，用二进制，m2，log2m=l，H（X）2.55比特符号，若要求比特符号，若要求，则，则 现在学习的是第36页，共59页(3)码的冗余度为码的冗余度为 码的码的冗余度冗余度用来衡量各种编码方法与最佳码的差用来衡量各种编码方法与最佳码的差距距。现在学习的是第37页，共59页例例331设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为求求:编码效率编码效率?解解:根据信源熵计算公式有：根据信源熵计算公式有：比特/符号 现在学习的是第38页，共59页(1)定长编码定长编码若用二元定长编码（若用二元定长编码（0,1）来构造一个）来构造一个即时码：即时码：这时平均码长为这时平均码长为=1二元码符号二元码符号/信源符号信源符号编码效率为编码效率为(对于无记忆信源而言对于无记忆信源而言,有有HL(X)=H(X)输出的信息率为输出的信息率为R0.811比特二元码符号比特二元码符号现在学习的是第39页，共59页(2)变长编码变长编码假定信源序列的长度为假定信源序列的长度为L=2,其即时码如表其即时码如表3-3所示所示。序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10现在学习的是第40页，共59页这个码的码字平均长度这个码的码字平均长度单个符号的平均码长单个符号的平均码长编码效率编码效率输出的信息率为输出的信息率为R20961比特二元码符号比特二元码符号 现在学习的是第41页，共59页将信源序列的长度增加，将信源序列的长度增加，L3或或L=4，对这些，对这些信源序列信源序列X进行编码进行编码，并求出其编码效率为并求出其编码效率为 信息传输率分别为：信息传输率分别为：R30985比特二元码符号比特二元码符号R40991比特二元码符号比特二元码符号如果对这一信源采用定长二元码编码，要求编码效率达到如果对这一信源采用定长二元码编码，要求编码效率达到96时，允许译码错误概率时，允许译码错误概率。则根据（。则根据（326）式，）式，自信息的方差自信息的方差所需要的信源序列长度所需要的信源序列长度现在学习的是第42页，共59页变长码相关结论变长码相关结论应用变长码往往在N不很大时，就可编出效率很高且无失真的码；变长码必须是唯一可译码，才能实现无失真编码；变长码要满足唯一可译码必须是非奇异码,而且任意有限长N次扩展码也必须是非奇异的；为了能够即时进行译码，变长码还必须是即时码。现在学习的是第43页，共59页第四节第四节 变长码的编码方法变长码的编码方法(1)最佳码定义最佳码定义凡是能载荷一定的信息量，且码字的平均长度最短，可凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。分离的变长码的码字集合都可称为最佳码。(2)最佳编码思想最佳编码思想将概率大的信息符号编以短的码字，概率小的符号编以将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。长的码字，使得平均码字长度最短。(3)最佳码的编码主要方法最佳码的编码主要方法香农（香农（Shannon）、费诺（）、费诺（Fano）、哈夫曼（）、哈夫曼（Huffman）编码等。）编码等。现在学习的是第44页，共59页3.4.1香农编码方法香农编码方法香农第一定理香农第一定理编码方法如下：编码方法如下：(1)将信源消息符号按其出现的概率大小依次排列将信源消息符号按其出现的概率大小依次排列(2)确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki：现在学习的是第45页，共59页 (3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率(4)将累加概率将累加概率Pi变换成二进制数。变换成二进制数。(5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该消位即为该消息符号的二进制码字。息符号的二进制码字。现在学习的是第46页，共59页例例3-4-1设信源共设信源共7个符号消息，其概率和累加概率如表个符号消息，其概率和累加概率如表3-4-1所所示。以示。以i=4为例，为例，现在学习的是第47页，共59页累加概率累加概率P4=0.57，变换成二进制为，变换成二进制为0.1001，由于，由于3，所以第，所以第4个消息的编个消息的编码码字为码码字为100。其他消息的码字可用同样方。其他消息的码字可用同样方法求得，法求得，7个消息符号对应的码字依次为：个消息符号对应的码字依次为：000,001,011,100,101,1110,1111110现在学习的是第48页，共59页说明说明:(1)该信源共有该信源共有5个三位的码字，各码字之间至少有一个三位的码字，各码字之间至少有一位数字不相同，故是唯一可译码。同时可以看出，位数字不相同，故是唯一可译码。同时可以看出，这这7个码字都不是延长码，它们都属于即时码。这里个码字都不是延长码，它们都属于即时码。这里L=1，m=2.(2)信源符号的平均码长信源符号的平均码长码元码元/符号符号 现在学习的是第49页，共59页(3)平均信息传输率平均信息传输率 现在学习的是第50页，共59页3.4.2费诺编码方法费诺编码方法编码步骤：编码步骤：（1）将信源消息符号按其出现的概率大小依次排列：）将信源消息符号按其出现的概率大小依次排列：p(x1)p(x2)p(xn)。（2）将依次排列的信源符号按概率值分为两大组，使两个）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元组的概率之和近于相同，并对各组赋予一个二进制码元“0”和和“1”。现在学习的是第51页，共59页（3）将每一大组的信源符号进一步再分成两组，使划）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号一个二进制符号“0和和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。）如此重复，直至每个组只剩下一个信源符号为止。（5）信源符号所对应的码字即为费诺码。）信源符号所对应的码字即为费诺码。现在学习的是第52页，共59页如何求出费诺码如何求出费诺码编码过程参见编码过程参见P44，表，表3-4-2。费诺码的平均码长费诺码的平均码长信息传输速率信息传输速率 现在学习的是第53页，共59页3.4.3哈夫曼编码方法哈夫曼编码方法哈夫曼编码步骤：哈夫曼编码步骤：（1）将）将n个信源消息符号按其出现的概率大小依个信源消息符号按其出现的概率大小依次次排列，排列，p（x1）p（x2）p（xn）（2）取两个概率最小的字母分别配以）取两个概率最小的字母分别配以0和和1两码元，并两码元，并将这两个概率相加作为一个新字母的概率，与未分配将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。的二进符号的字母重新排队。现在学习的是第54页，共59页（3）对重排后的两个概率最小符号重复步骤（）对重排后的两个概率最小符号重复步骤（2）的过程。）的过程。（4）不断继续上述过程，直到最后两个符号配以）不断继续上述过程，直到最后两个符号配以0和和1为止。为止。（5）从最后一级开始，向前返回得到各个信源符号）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。所对应的码元序列，即相应的码字。现在学习的是第55页，共59页哈夫曼编码过程，见哈夫曼编码过程，见P44表表3-4-3所示所示说明说明:哈夫曼码的平均码长为哈夫曼码的平均码长为信息传输速率信息传输速率 现在学习的是第56页，共59页问题问题:为何哈夫曼编码方法得到的码并非是唯一的为何哈夫曼编码方法得到的码并非是唯一的?(1)每每次次对对信信源源缩缩减减时时，赋赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以以任任意意的的，所所以以可可以以得得到到不不同同的的哈哈夫夫曼曼码码，但不会影响码字的长度。但不会影响码字的长度。现在学习的是第57页，共59页(2)对对信信源源进进行行缩缩减减时时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同同时时，这这两两者者在在缩缩减减信信源源中中进进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码码。此此时时将将影影响响码码字字的的长长度度，一一般般将将合合并的概率放在上面，这样可获得较小的码方差。并的概率放在上面，这样可获得较小的码方差。现在学习的是第58页，共59页例例342 设有离散无记忆信源设有离散无记忆信源哈夫曼编码如下哈夫曼编码如下(见书见书P45):现在学习的是第59页，共59页