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

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

2、真信源编码定理。第二极限定理: 信道编码定理(包括离 散和连续信道)。第三极限定理: 限失真信源编码定理。编码的分类编码：信源编码、信道编码。信源编码：无失真信源编码、限失真信源编码。无失真信源编码：适用于离散信源或数字 信号。限失真信源编码：适用于连续信源或模拟信号，如语音、图像等信号的数字处理。信源编码目的与方法 信源编码：将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号序列，且使该序列组成的新信源的冗余度尽可能地减少。 目的：提高通信的有效性。 方法：减少信源冗余度。信源编码的基本途径信源编码的基本途径 解除相关性：使序列中的各个符号尽可能地互相独立。 概率均匀化：使编码中各

3、个符号出现的概率尽可能地相等。 信源编码的基础 信源编码的基础：无失真信源编码定理和限失真信源编码定理。编码定理表明：（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。编码器的数学

4、模型S=原始信源符号集；x=码元符号集；C=码字符号集；（码组）基本源编码消息集合码字集合一些基本概念二元码定长码变长码非奇异码奇异码同价码分组码唯一可译码即时码码的前缀码树1.二元码 若码符号集为X=0,1，所有码字都是二元符号序列，则称为二元码。2.定长码 若一组码中所有码字的码长都相同，即li=l（i=1,2,n）,则称为定长码。3.变长码若一组码中所有码字的码长各不相同，即任意码字由不同长度li的码符号序列组成，则称为变长码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111114.非奇异码 若一组码中所

5、有码字都不相同，即所有信源符号映射到不同的码符号序列，则称码为非奇异码。5.奇异码若一组码中有相同的码字，则称码为奇异码。信源符号si信源符号出现概率p（si）码1码2S1p（s1）00S2p（s2）1110S3p（s3）0000S4p（s4）11106.同价码若码符号集中每个码符号所占的传输时间都相同，则所得的码为同价码。7.分组码 将信源符号集中的每个信源符号映射成一个固定的码字，这样的码称为分组码。8.唯一可译码 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则此码称为唯一可译码。也称单义可译码。注意：定长码是非奇异的就是唯一可译码，因为它能固定长度分组。 变长码

6、则不一定，主要是不能固定长度分组。 唯一可译码还有判定准则，后面将介绍。唯一可译码(续)信源符号si信源符号出现概率p（si）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）111119.即时码无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。信源符号si码1码2S111S21001S3100001S41000000110.码的前缀 定理:唯一可译码成为即时码的充要条件是其中任何一个码字都不是其他码字的前缀。11.码树 码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树

7、（r叉树，r进制树）。当然二元码对应的是二叉树或二元树。 树根、叶子节点、中间节点、深度、码长。 整树、非整树、全树。码树图唯一可译码定理设原始信源符号集为S:S1,S2,Sq，码元符号集为x:x1,x2,xr，码字集合为W:W1,W2,Wq，其码长分别为L1,L2,Lq；则唯一可译码存在的充要条件为码长组合满足Kraft不等式，即 式中，r是进制数，q是信源符号数，l为码字长度。 唯一可译码Kraft不等式：是唯一可译码的充要条件，也是即时码的充要条件；Kraft不等式指明了即时码的码长必须满足的条件；充要条件是对于码长组合而言，而不是对于码字本身而言，即满足Kraft不等式的码长组合一定能

8、构成至少一种唯一码，唯一码的码长组合一定满足Kraft不等式。否则无法构成唯一可译码。唯一可译码有些码字的码长组合虽满足Kraft不等式，但不是唯一码。Kraft 不等式不能用来判断W是否是唯一可译码，但不满足该不等式的W一定不是唯一可译码。唯一可译码判别准则：用来判断W是否是唯一可译码。无失真信源编码定理研究内容若信源输出符号序列的长度 ，即 变换成由KL个符号组成的码序列（码字)变换要求:(1)能够无失真或无差错地从Y恢复X，也就是能正确地进行反变换或译码 。(2)传送Y时所需要的信息率最小 。 由于Yk可取m种可能值，即平均每个符号输出的最大信息量为logm，KL长码字的最大信息量为KL

9、logm。用该码字表示L长的信源序列,则送出一个信源符号所需要的信息率平均为:其中 是Y所能编成的码字的个数。信息率最小，就是找到一种编码方式使 最小。无失真信源编码定理研究内容: (1)最小信息率为多少时，才能得到无失真的译码？(2)若小于这个信息率是否还能无失真地译码？第二节 定长编码定理定长信源编码定理 由L个符号组成的、平均符号熵为HL（X）的无记忆平稳信源符号序列 ，可用KL个符号 （每个符号有m种可能值）进行定长编码。对任意 ，只要(注:把L移过去观察) 则当L足够大时，必可使译码差错小于 ；反之，当 时，译码差错一定是有限值，而当L足够大时，译码几乎必定出错。 说明（1）当编码器

10、容许的输出信息率，也就是当每个信源符号所必须输出的码长是时，只要 ，这种编码器一定可以做到几乎无失真，也就是收端的译码差错概率接近于零，条件是所取的符号数L足够大。(2)将定理的条件改写成 其中：左边：KL长码字所能携带的最大信息量， 右边：L长信源序列携带的信息量。 上述定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是L足够大。 反之，当 时，不可能构成无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。 时，则为临界状态，可能无失真，也可能有失真。 第三节 变长编码定理单个符号变长编码定理: 若一离散无记忆信源的符号熵为H（X

11、），每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 离散平稳无记忆序列变长编码定理 对于平均符号熵为HL（X）的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式 其中 为任意小正数。证明:设用m进制码元作变长编码，序列长度为L个信源符号，则由（331）式可以得到平均码字长度 满足下列不等式 当L足够大时，可使 ，这就得到了 所需结论说明: (1) 用变长编码来达到相当高的编码效率，一般所要求的符号长度L可以比定长编码小得多。可得编码效率的下界： (2) 例 用二进制，m2，log2m=l，H（X）2.55比特符号，若要求 ，

12、则 (3) 码的冗余度为 码的冗余度用来衡量各种编码方法与最佳码的差距。例331设离散无记忆信源的概率空间为 求:编码效率?解:根据信源熵计算公式有： 比特/符号 (1)定长编码 若用二元定长编码（0,1）来构造一个 即时码：这时平均码长为 =1 二元码符号/信源符号编码效率为(对于无记忆信源而言,有HL(X)=H(X) ) 输出的信息率为 R0.811比特二元码符号 (2)变长编码 假定信源序列的长度为L=2,其即时码如表3-3所示。 序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10这个码的码字平均长度 单个符号的平

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

14、 变长码的编码方法(1)最佳码定义 凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。 (2)最佳编码思想 将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。 (3)最佳码的编码主要方法 香农（Shannon）、费诺（Fano）、哈夫曼（Huffman）编码等。 3.4.1 香农编码方法香农第一定理编码方法如下： (1)将信源消息符号按其出现的概率大小依次排列 (2) 确定满足下列不等式的整数码长Ki： (3)为了编成唯一可译码，计算第i个消息 的累加概率 (4)将累加概率Pi 变换成二进制数。 (5)取Pi二进数的小数点后Ki

15、位即为该消 息符号的二进制码字。 例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)该信源共有5个三位的码字，各码字之间至少有一位数字不相同，故是唯一可译码。同时可以看出，这7个码字都不是延长码，它们都属于即时码。这里L=1，m=2. (2)信源符号的平均码长 码元/符号 (3) 平均信息传输率 3.4.2 费诺编码方法编码

16、步骤：（1）将信源消息符号按其出现的概率大小依次排列：p(x1) p(x2) p(xn)。（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号“0和“1”。（4）如此重复，直至每个组只剩下一个信源符号为止。（5）信源符号所对应的码字即为费诺码。 如何求出费诺码 编码过程参见P44 ，表3-4-2。 费诺码的平均码长 信息传输速率 3.4.3 哈夫曼编码方法哈夫曼编码步骤：（1）将n个信源消息符号按其出现的概率大小依 次排列， p（x1）p（x2）p（xn）（2）取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。 （3）对重排后的两个概率最小符号重复步骤（2）的过程。（4）不断继续上述过程，直到最后两个符号配以0和1为止。（5）从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。 哈夫曼编码过程，见P44表3-4-3