信息论与编码第三章 无失真信源编码信息论与编码 引言 编码的定义 定长编码定理 变长编码定理 变长编码方法信息论与编码引言 什么是编码 香农信息论三大定理 编码的分类 编码的任务和途径 编码器信息论与编码什么是编码 信源编码和信道编码通信的实质是传输信息，要求传输具有高效率 和质量：（1）在不失真和允许一定失真的条件下，用尽 可能少的符号传送信源信息，以便提高信息传 输率。（2）在信道受干扰的情况下，增加信号的抗干 扰能力，以便提高信息传输的可靠性。解决以上两个问题需要引入信源编码和信道编 码。信息论与编码什么是编码 生活中编码实例? 学号、身份证号码、一卡通、汉语等编码。 编码实质：信息的表示。 结论: 信息无处不在 ，编码无处不在。信息论与编码香农信息论三大定理第一极限定理: 无失真信源编码定理。第二极限定理: 信道编码定理(包括离散和连续信道)。第三极限定理: 限失真信源编码定理。信息论与编码编码的分类 编码：信源编码、信道编码。 信源编码：无失真信源编码、限失真信源 编码。 无失真信源编码：适用于离散信源或数字 信号。 限失真信源编码：适用于连续信源或模拟 信号，如语音、图像等信号的数字处理。信息论与编码信源编码目的与方法信源编码：将信源输出的消息符号进行有 效变换，使其成为适合信道传输的符号序 列，且使该序列组成的新信源的冗余度尽 可能地减少。目的：提高通信的有效性。方法：减少信源冗余度。信息论与编码信源编码的基本途径 信源编码的基本途径解除相关性：使序列中的各个符号尽可能 地互相独立。概率均匀化：使编码中各个符号出现的概 率尽可能地相等。 信源编码的基础信源编码的基础：无失真信源编码定理和 限失真信源编码定理。信息论与编码编码定理表明：（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。信息论与编码编码器的数学模型 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）11111信息论与编码4.非奇异码若一组码中所有码字都不相同，即所有信 源符号映射到不同的码符号序列，则称码 为非奇异码。信息论与编码5.奇异码 若一组码中有相同的码字，则称码为奇异码 。信源符号si信源符号出现概率p（si） 码1码2 S1p（s1）00S2p（s2）1110S3p（s3）0000S4p（s4）1110信息论与编码6.同价码 若码符号集中每个码符号所占的传输时间 都相同，则所得的码为同价码。 7.分组码将信源符号集中的每个信源符号映射成一 个固定的码字，这样的码称为分组码。信息论与编码8.唯一可译码若码的任意一串有限长的码符号序列只能被 唯一的译成所对应的信源符号序列，则此 码称为唯一可译码。也称单义可译码。 注意：定长码是非奇异的就是唯一可译码， 因为它能固定长度分组。变长码则不一定，主要是不能固定长度分 组。唯一可译码还有判定准则，后面将介绍。信息论与编码唯一可译码(续)信源符号si信源符号出现概率p（si ）码1码2S1p（s1）000S2p（s2）0101S3p（s3）10001S4p（s4）11111信息论与编码9.即时码 无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯 一可译码称为即时码或瞬时码或逗点码或非延长码或异前缀码。信源符号si码1码2S111S21001S3100001S410000001信息论与编码10.码的前缀定理:唯一可译码成为即时码的充要条件是其中任何 一个码字都不是其他码字的前缀。11.码树码字的构造可用树的形式来表示，称为 码的树图构造法。r元码通常对应于r元树 （r叉树，r进制树）。当然二元码对应的 是二叉树或二元树。树根、叶子节点、中间节点、深度、码长 。整树、非整树、全树。信息论与编码码树图信息论与编码唯一可译码定理 设原始信源符号集为S:S1,S2,Sq，码元符 号集为x:x1,x2,xr，码字集合为 W:W1,W2,Wq，其码长分别为L1,L2,Lq ；则唯一可译码存在的充要条件为码长组合满 足Kraft不等式，即式中，r是进制数，q是信源符号数，l为码字 长度。 信息论与编码唯一可译码 Kraft不等式：是唯一可译码的充要条件， 也是即时码的充要条件； Kraft不等式指明了即时码的码长必须满足 的条件； 充要条件是对于码长组合而言，而不是对 于码字本身而言，即满足Kraft不等式的码 长组合一定能构成至少一种唯一码，唯一 码的码长组合一定满足Kraft不等式。否则 无法构成唯一可译码。信息论与编码唯一可译码 有些码字的码长组合虽满足Kraft不等式， 但不是唯一码。 Kraft 不等式不能用来判断W是否是唯一 可译码，但不满足该不等式的W一定不是 唯一可译码。 唯一可译码判别准则：用来判断W是否是 唯一可译码。信息论与编码无失真信源编码定理研究内容若信源输出符号序列的长度 ，即 变换成由KL个符号组成的码序列（码字)变换要求: (1)能够无失真或无差错地从Y恢复X，也就是能正确地进 行反变换或译码 。 (2)传送Y时所需要的信息率最小 。信息论与编码由于Yk可取m种可能值，即平均每个符号输出的 最大信息量为logm，KL长码字的最大信息量为 KLlogm。用该码字表示L长的信源序列,则送出一个 信源符号所需要的信息率平均为:其中 是Y所能编成的码字的个数。 信息率最小，就是找到一种编码方式使 最小。 无失真信源编码定理研究内容: (1)最小信息率为多少时，才能得到无失真的译码？ (2)若小于这个信息率是否还能无失真地译码？信息论与编码第二节 定长编码定理 定长信源编码定理由L个符号组成的、平均符号熵为HL（X）的无记忆平 稳信源符号序列 ，可用KL个符号（每个符号有m种可能值）进行定 长编码。对任意 ，只要(注:把L移过去 观察)则当L足够大时，必可使译码差错小于 ；反之，当时，译码差错一定是有限值，而当L足够大时，译码 几乎必定出错。 信息论与编码说明（1）当编码器容许的输出信息率，也就是当每 个信源符号所必须输出的码长是时，只要 ，这种编码器一定可以做到 几 乎无失真，也就是收端的译码差错概率接近于零 ，条件是所取的符号数L足够大。信息论与编码(2)将定理的条件改写成其中：左边：KL长码字所能携带的最大信息量，右边：L长信源序列携带的信息量。上述定理表明，只要码字所能携带的信息量大于信源序 列输出的信息量，则可以使传输几乎无失真，当然条件 是L足够大。反之，当 时，不可能构成无失真的编码， 也就是不可能做一种编码器，能使收端译码时差错概率 趋于零。时，则为临界状态，可能无失真，也可 能有失真。 信息论与编码第三节 变长编码定理单个符号变长编码定理:若一离散无记忆信源的符号熵为H（X），每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式信息论与编码离散平稳无记忆序列变长编码定理对于平均符号熵为HL（X）的离散平稳无记忆信源，必存在一种无失真编码方法，使平均信息率 满足不等式 其中 为任意小正数。信息论与编码证明: 设用m进制码元作变长编码，序列长度为L个信源符号，则 由（331）式可以得到平均码字长度 满足下列不等式 当L足够大时，可使 ， 这就得到了 所需结论信息论与编码 说明:(1) 用变长编码来达到相当高的编码效率，一 般所要求的符号长度L可以比定长编码小得多 。可得编码效率的下界： 信息论与编码(2) 例用二进制，m2，log2m=l，H（X） 2.55比特符号，若要求 ， 则 信息论与编码(3) 码的冗余度为码的冗余度用来衡量各种编码方法与最佳码的 差距。信息论与编码例331 设离散无记忆信源的概率空间为 求:编码效率? 解:根据信源熵计算公式有： 比特/符号 信息论与编码(1)定长编码若用二元定长编码（0,1）来构造一个 即时码： 这时平均码长为 =1 二元码符号/信源符号 编码效率为(对于无记忆信源而言,有HL(X)=H(X) ) 输出的信息率为 R0.811比特二元码符号 信息论与编码(2)变长编码假定信源序列的长度为L=2,其即时码如表3-3所示 。 序列序列概率即时码x1x1 9/16 0x1x2x2x1x2x2 1/163/163/1611111010信息论与编码 这个码的码字平均长度 单个符号的平均码长 编码效率 输出的信息率为 R20961 比特二元码符号 信息论与编码将信源序列的长度增加，L3或L=4，对这 些信源序列X进行编码，并求出其编码效率为 信息传输率分别为： R30985比特二元码符号 R40991比特二元码符号 如果对这一信源采用定长二元码编码，要求编码效率达 到96时，允许译码错误概率 。则根据（32 6）式，自信息的方差 所需要的信源序列长度 信息论与编码变长码相关结论 应用变长码往往在N不很大时，就可编出效 率很高且无失真的码； 变长码必须是唯一可译码，才能实现无失真 编码； 变长码要满足唯一可译码必须是非奇异码,而 且任意有限长N次扩展码也必须是非奇异的 ； 为了能够即时进行译码，变长码还必须是即 时码。信息论与编码第四节 变长码的编码方法(1)最佳码定义凡是能载荷一定的信息量，且码字的平均长度最短 ，可分离的变长码的码字集合都可称为最佳码。(2)最佳编码思想将概率大的信息符号编以短的码字，概率小的符号 编以长的码字，使得平均码字长度最短。(3)最佳码的编码主要方法香农（Shannon）、费诺（Fano）、哈夫曼（ Huffman）编码等。 信息论与编码3.4.1 香农编码方法香农第一定理编码方法如下： (1)将信源消息符号按其出现的概率大小依次排列(2) 确定满足下列不等式的整数码长Ki：信息论与编码(3)为了编成唯一可译码，计算第i个消息的累加