第三章-无失真信源编码课件.ppt

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

2、和信道编码。什么是编码什么是编码 生活中编码实例生活中编码实例?学号、身份证号码、一卡通、汉语等编码。 编码实质：编码实质：信息的表示。 结论结论: 信息无处不在 ，编码无处不在。香农信息论三大定理香农信息论三大定理第一极限定理第一极限定理: 无失真信源编码定理。第二极限定理第二极限定理: 信道编码定理(包括离 散和连续信道)。第三极限定理第三极限定理: 限失真信源编码定理。编码的分类编码的分类 编码：编码：信源编码、信道编码。 信源编码：信源编码：无失真信源编码、限失真信源编码。 无失真信源编码：无失真信源编码：适用于离散信源或数字 信号。 限失真信源编码：限失真信源编码：适用于连续信源或模

3、拟信号，如语音、图像等信号的数字处理。信源编码目的与方法信源编码目的与方法 信源编码：信源编码：将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。 目的：目的：提高通信的有效性。 方法：方法：减少信源冗余度。信源编码的基本途径信源编码的基本途径 信源编码的基本途径信源编码的基本途径 解除相关性解除相关性：使序列中的各个符号尽可能地互相独立。 概率均匀化：概率均匀化：使编码中各个符号出现的概率尽可能地相等。 信源编码的基础信源编码的基础 信源编码的基础信源编码的基础：无失真信源编码定理和限失真信源编码定理。编码定理表明：编码定理表明：（

4、1）必存在一种编码方法，使代码的平均长度可任必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵。意接近但不能低于符号熵。（2）达到这目标的途径，就是使概率与码长匹配。达到这目标的途径，就是使概率与码长匹配。 编码器编码器不少原始信源的消息符号不适应信道的传输； 原始信源消息符号的传输效率低； 编码器输入端为原始信源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。编码器的数学模型

5、编码器的数学模型 S=原始信源符号集； x=码元符号集； C=码字符号集；（码组）,21rxxxX 基本源编码基本源编码消息集合消息集合码字集合码字集合)(21iliiiixxxW,21qiSSSSSiw,21qiWWWCW 一些基本概念一些基本概念 二元码 定长码 变长码 非奇异码 奇异码 同价码 分组码 唯一可译码 即时码 码的前缀 码树1.二元码二元码 若码符号集为X=0,1，所有码字都是二元符号序列，则称为二元码。2.定长码定长码 若一组码中所有码字的码长都相同，即li=l（i=1,2,n）,则称为定长码。3.变长码变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符

6、号序列组成，则称为变长码。信源符号si信源符号出现概率p（si） 码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111114.非奇异码非奇异码 若一组码中所有码字都不相同，即所有信源符号映射到不同的码符号序列，则称码为非奇异码。5.奇异码奇异码若一组码中有相同的码字，则称码为奇异码。信源符号si信源符号出现概率p（si） 码1码2S1p（s1）00S2p（s2）1110S3p（s3）0000S4p（s4）11106.同价码同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。7.分组码分组码 将信源符号集中的每个信源符号映射成一个固定的

7、码字，这样的码称为分组码。8.唯一可译码唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。注意：注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。 变长码则不一定，主要是不能固定长度分组。 唯一可译码还有判定准则，后面将介绍。唯一可译码唯一可译码(续续)信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111119.即时码即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。信

8、源符号si码1码2S111S21001S3100001S41000000110.码的前缀码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。11.码树码树 码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树（r叉树，r进制树）。当然二元码对应的是二叉树或二元树。 树根、叶子节点、中间节点、深度、码长。 整树、非整树、全树。码树图码树图唯一可译码定理唯一可译码定理 设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则唯一可译码存在的充要条件为码长组合满足

9、Kraft不等式，即 式中，式中，r r是进制数，是进制数，q q是信源符号数，是信源符号数，l l为码字长为码字长度。度。 11qilir唯一可译码唯一可译码 Kraft不等式：是唯一可译码的充要条件，也是即时码的充要条件； Kraft不等式指明了即时码的码长必须满足的条件； 充要条件是对于码长组合而言，而不是对于码字本身而言，即满足Kraft不等式的码长组合一定能构成至少一种唯一码，唯一码的码长组合一定满足Kraft不等式。否则无法构成唯一可译码。唯一可译码唯一可译码 有些码字的码长组合虽满足Kraft不等式，但不是唯一码。 Kraft 不等式不能用来判断W是否是唯一可译码，但不满足该不等

10、式的W一定不是唯一可译码。 唯一可译码判别准则：用来判断W是否是唯一可译码。无失真信源编码定理研究内容无失真信源编码定理研究内容若信源输出符号序列的长度若信源输出符号序列的长度 ，即，即 1L)(21LlXXXXXnilaaaaX,21变换成由变换成由K KL L个符号组成的码序列（码字个符号组成的码序列（码字) )(21LKkYYYYY变换要求变换要求: :(1)(1)能够无失真或无差错地从能够无失真或无差错地从Y恢复恢复X，也就是能正确地，也就是能正确地进行反变换或译码进行反变换或译码 。(2)(2)传送传送Y时所需要的信息率最小时所需要的信息率最小 。mjkbbbbY,21 由于由于Y

11、Yk k可取可取m m种可能值，即平均每个符号输出的种可能值，即平均每个符号输出的最大信息量为最大信息量为logmlogm，K KL L长码字的最大信息量为长码字的最大信息量为K KL Llogmlogm。用该码字表示。用该码字表示L L长的信源序列长的信源序列, ,则送出一个则送出一个信源符号所需要的信息率平均为信源符号所需要的信息率平均为: :MLmLKKLlog1log_LKmM _K其中其中 是是Y Y所能编成的码字的个数。所能编成的码字的个数。信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使 最小。最小。无失真信源编码定理研究内容无失真信源编码定理研究内容: :

12、(1)(1)最小信息率为多少时，才能得到无失真的译码？最小信息率为多少时，才能得到无失真的译码？(2)(2)若小于这个信息率是否还能无失真地译码？若小于这个信息率是否还能无失真地译码？_K第二节第二节 定长编码定理定长编码定理 定长信源编码定理定长信源编码定理 由由L个符号组成的、平均符号熵为个符号组成的、平均符号熵为HL（X）的无记忆平）的无记忆平稳信源符号序列稳信源符号序列 ，可用，可用KL个符号个符号 （每个符号有（每个符号有m种可能值）进行定长种可能值）进行定长编码。对任意编码。对任意 ，只要，只要(注注:把把L移过去观察移过去观察) 则当则当L足够大时，必可使译码差错小于足够大时，必

13、可使译码差错小于 ；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几足够大时，译码几乎必定出错。乎必定出错。 LlXXXX21LKkYYYY,210, 0)(logXHmLKLL2)(logXHmLKLL说明说明（1）当编码器容许的输出信息率，也就是当每个）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是信源符号所必须输出的码长是时，只要时，只要 ，这种编码器一定可以做到几，这种编码器一定可以做到几乎无失真，也就是收端的译码差错概率接近于零，乎无失真，也就是收端的译码差错概率接近于零，条件是所取的符号数条件是所取的符号数L足够大

14、。足够大。MLmLKKLlog1log_)(_XHKL(2)将定理的条件改写成将定理的条件改写成 其中：左边：其中：左边：KL长码字所能携带的最大信息量，长码字所能携带的最大信息量， 右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。 上述定理表明，只要码字所能携带的信息量大于信源序列上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。足够大。 反之，当反之，当 时，不可能构成无失真的编码，也时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋就是不可能

15、做一种编码器，能使收端译码时差错概率趋于零。于零。 时，则为临界状态，可能无失真，也可能时，则为临界状态，可能无失真，也可能有失真。有失真。 )()(logXHXLHmKLL)(_XHKL)(_XHKL第三节第三节 变长编码定理变长编码定理单个符号变长编码定理单个符号变长编码定理: 若一离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H（X），），每个信源符号用每个信源符号用m进制码元进行变长编码，一进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长定存在一种无失真编码方法，其码字平均长度满足下列不等式度满足下列不等式 1)-3-(3 1log)(log)(mXHKmXH离散平

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

17、Llog)(log)(当当L足够大时，可使足够大时，可使 ，这就得到了这就得到了 所需结论所需结论Lmlog 说明说明: (1) 用变长编码来达到相当高的编码效率，一般用变长编码来达到相当高的编码效率，一般所要求的符号长度所要求的符号长度L可以比定长编码小得多。可可以比定长编码小得多。可得编码效率的下界：得编码效率的下界： LmXHXHKXHLLLlog)()()(2) 例例 用二进制，用二进制，m2，log2m=l，H（X）2.55比特符号，若要求比特符号，若要求 ，则，则 428. 0/ 1, 9 . 0/ 155. 255. 2LL%90(3) 码的冗余度为码的冗余度为KXHL)(11

18、码的码的冗余度冗余度用来衡量各种编码方法与最佳码的用来衡量各种编码方法与最佳码的差距差距。例例331 设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为 4/14/321xxPX求求:编码效率编码效率?解解:根据信源熵计算公式有：根据信源熵计算公式有： 比特/符号 81. 043log4341log41)(22XH(1)定长编码定长编码 若用二元定长编码（若用二元定长编码（0,1）来构造一个）来构造一个 即时码：即时码：这时平均码长为这时平均码长为 =1 二元码符号二元码符号/信源符号信源符号编码效率为编码效率为(对于无记忆信源而言对于无记忆信源而言,有有HL(X)=H(X) ) 输出的

19、信息率为输出的信息率为 R0.811比特二元码符号比特二元码符号 1,021xx12log81. 02log81. 022KK811.0)(KXH(2)变长编码变长编码 假定信源序列的长度为假定信源序列的长度为L=2,其即时码如表其即时码如表3-3所示所示。 序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10 这个码的码字平均长度这个码的码字平均长度 单个符号的平均码长单个符号的平均码长 编码效率编码效率 输出的信息率为输出的信息率为 R20961 比特二元码符号比特二元码符号 信源序列二元码符号/16273161316

20、3216311692K信源序列二元码符号/322722KK961. 027811. 0322将信源序列的长度增加，将信源序列的长度增加，L3或或L=4，对这些，对这些信源序列信源序列X进行编码进行编码，并求出其编码效率为并求出其编码效率为 信息传输率分别为：信息传输率分别为： R30985比特二元码符号比特二元码符号 R40991比特二元码符号比特二元码符号 如果对这一信源采用定长二元码编码，要求编码效率达到如果对这一信源采用定长二元码编码，要求编码效率达到96时，允许译码错误概率时，允许译码错误概率 。则根据（。则根据（326）式，自信息的方差式，自信息的方差 所需要的信源序列长度所需要的信

21、源序列长度 991.0985.043212224715. 0)()(log)(iiiXHppX510752221013. 41004. 0)96. 0()811. 0(4715. 0L变长码相关结论变长码相关结论 应用变长码往往在N不很大时，就可编出效率很高且无失真的码； 变长码必须是唯一可译码，才能实现无失真编码； 变长码要满足唯一可译码必须是非奇异码,而且任意有限长N次扩展码也必须是非奇异的； 为了能够即时进行译码，变长码还必须是即时码。第四节第四节 变长码的编码方法变长码的编码方法(1)最佳码定义最佳码定义 凡是能载荷一定的信息量，且码字的平均长度最短，凡是能载荷一定的信息量，且码字的平

22、均长度最短，可分离的变长码的码字集合都可称为最佳码。可分离的变长码的码字集合都可称为最佳码。 (2)最佳编码思想最佳编码思想 将概率大的信息符号编以短的码字，概率小的符号编将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。以长的码字，使得平均码字长度最短。 (3)最佳码的编码主要方法最佳码的编码主要方法 香农（香农（Shannon）、费诺（）、费诺（Fano）、哈夫曼）、哈夫曼（Huffman）编码等。）编码等。 3.4.1 香农编码方法香农编码方法香农第一定理香农第一定理编码方法如下：编码方法如下： (1)将信源消息符号按其出现的概率大小依次排列将信源消息符号按

23、其出现的概率大小依次排列 (2) 确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki：)()()(21nxpxpxp1)(log)(log22iiixpKxp (3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息 的累加概率的累加概率 (4)将累加概率将累加概率Pi 变换成二进制数。变换成二进制数。 (5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该消位即为该消 息符号的二进制码字。息符号的二进制码字。 11)(ikkixpP例例3-4-1 设信源共设信源共7个符号消息，其概率和累加概率如表个符号消息，其概率和累加概率如表3-4-1所示。以所示。以i=4为

24、例，为例， 3,56. 356. 2117. 0log17. 0log44242KKK 累加概率累加概率P4=0.57，变换成二进制为，变换成二进制为0.1001，由于，由于3，所以第，所以第4个消息的编个消息的编码码字为码码字为100。其他消息的码字可用同样方。其他消息的码字可用同样方法求得，法求得，7个消息符号对应的码字依次为：个消息符号对应的码字依次为： 000,001,011,100,101,1110,1111110说明说明: (1)该信源共有该信源共有5个三位的码字，各码字之间至少有个三位的码字，各码字之间至少有一位数字不相同，故是唯一可译码。同时可以看一位数字不相同，故是唯一可译码

25、。同时可以看出，这出，这7个码字都不是延长码，它们都属于即时个码字都不是延长码，它们都属于即时码。这里码。这里L=1，m=2. (2)信源符号的平均码长信源符号的平均码长 码元码元/符号符号 14. 3)(71iiiKxpK(3) 平均信息传输率平均信息传输率 码元比特/ 831. 014. 361. 2)(KXHR3.4.2 费诺编码方法费诺编码方法编码步骤：编码步骤：（1）将信源消息符号按其出现的概率大小依次排）将信源消息符号按其出现的概率大小依次排列：列：p(x1) p(x2) p(xn)。（2）将依次排列的信源符号按概率值分为两大组，）将依次排列的信源符号按概率值分为两大组，使两个组的

26、概率之和近于相同，并对各组赋予一使两个组的概率之和近于相同，并对各组赋予一个二进制码元个二进制码元“0”和和“1”。（3）将每一大组的信源符号进一步再分成两组，使）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号个组一个二进制符号“0和和“1”。（4）如此重复，直至每个组只剩下一个信源符号为）如此重复，直至每个组只剩下一个信源符号为止。止。（5）信源符号所对应的码字即为费诺码。）信源符号所对应的码字即为费诺码。 如何求出费诺码如何求出费诺码 编码过程参见编码过程参见P44 ，表，表3-4-2。 费

27、诺码的平均码长费诺码的平均码长 信息传输速率信息传输速率 符号码元/ 74. 2)(71iiiKxpK码元比特/ 953. 074. 261. 2)(KXHR3.4.3 哈夫曼编码方法哈夫曼编码方法哈夫曼编码步骤：哈夫曼编码步骤：（1）将）将n个信源消息符号按其出现的概率大小依个信源消息符号按其出现的概率大小依 次排列，次排列， p（x1）p（x2）p（xn）（2）取两个概率最小的字母分别配以）取两个概率最小的字母分别配以0和和1两码元，两码元，并将这两个概率相加作为一个新字母的概率，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。与未分配的二进符号的字母重新排队。

28、（3）对重排后的两个概率最小符号重复步骤（）对重排后的两个概率最小符号重复步骤（2）的过程。的过程。（4）不断继续上述过程，直到最后两个符号配以）不断继续上述过程，直到最后两个符号配以0和和1为止。为止。（5）从最后一级开始，向前返回得到各个信源符）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。号所对应的码元序列，即相应的码字。 哈夫曼编码过程，见哈夫曼编码过程，见P44表表3-4-3所示所示 说明说明:哈夫曼码的平均码长为哈夫曼码的平均码长为 信息传输速率信息传输速率 符号码元/ 72. 2)(71iiiKxpK码元比特/ 9596. 072. 261. 2)(KX

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