下界值 第 4 章 - 无失真源编码.ppt 第 47 页

* 当平均码长达到极限值时，编码通道的信息传输速率为logr * 也可以证明，如果我们不准确地知道信源的概率分布，而用估计的概率分布来编码，平均码长会变长，但如果估计偏差不大，平​​均码长不会增加太多（定理4.9的内容）。 * 信源编码定理从理论上解释了编码效率接近1，即理想编码器的存在，其代价是在实际编码中需要取无限长的信源符号（L→∞）进行统一编码。 第四节 变长信源编码定理 平均码长决定了编码的信息传输速率：平均码长可以无限小吗？ 平均码长极限定理* * 平均码长下限定理的意义是采用正确的原则，合理匹配码字长度和源符号的概率分布，使得平均码长可以为减少了，但是平均码长的减少是有限的。 ，其下界为 H(S)/logr。 在保持实时码所必需的结构条件——克拉夫特不等式的情况下，平均码长永远不会小于其下界值。 当且仅当源符号si、li的概率分布p(si)=(1/r)li均为正整数时，即时码的平均码长才能达到下界值，此时的码这个时候就是更优的代码了。 。 *思考：如果平均码长小于下限会发生什么？ * 实际上，下界值利用换底公式进行变换，对数的底变成了编码符号的个数r： * 上界定理的结论：平均码长不超过其上界值[Hr(S)+1] 低于这个上界，可以形成即时码，但这并不意味着超过这个上界，就不能形成即时码，只是因为我们总是希望平均码长可以尽可能小。

根据不等式确定码字长度实际上是构造即时码的方法，称为香农码。 香农码虽然不是效率更高的，但是根据源符号的概率分布可以直接得到对应码字长度的准确数字，这给编码带来了一定的方便。 * 对平均代码长度极限定理的思考？ 如果一个码字对应于单个源符号来构造即时码，则平均码长的下限由给定源的熵值确定为H(S)/logr。 如果想进一步降低平均编码长度，提高通信的有效性，就需要尝试改变编码对象本身的信息特征。 如果源S发送的消息由N个符号组成，则一条消息可以被视为源S扩展了N次的符号。 编码时，一个完整的码字不再对应于单个源符号，而是对应于扩展源的符号。 平均代码长度可以减少吗？ 也就是说，是否可以通过扩展源来达到数据压缩的目的呢？ 为，编码器的码元符号集为A：，对信息源进行编码时，总能找到一种编码方法，形成唯一的可译码，使得信息源S中每个符号si所需的平均码长满足 则可得： 第四节变长信源编码定理* 如下： 是编码后每个信源符号所携带的平均信息量。 之一个定理可以表达如下： 如果存在唯一的可翻译变长码，如果 则不存在唯一的可翻译变长码。

定义： **对应于离散平稳记忆信息源，上述结论仍然成立，H(S) = H∞； M阶马尔可夫信息源：H(S)=Hm+1结论：当平均码长达到极限值时，编码后信道的信息传输速率为logr，即信道达到信道容量*无失真信源编码定理是香农信息论中一个非常重要的定理，也称为香农之一定理。 为了实现无失真的信源编码，信源的每个符号所需的平均符号数就是信源的熵值。 如果小于该值，则唯一可解码的不存在。 可见，熵是无失真信息的来源。 编码限制。 通过对扩展源进行编码，当N接近无穷大时，平均码长可以接近这个极限值。 （可以通过扩展信源来完成）而且因为需要无失真传输，所以无失真信源编码后，必须接入无噪声通道。 因此，无失真信源编码定理也可以称为无噪声信道编码定理。 。 无失真信源编码定理总结* 变长编码效率： 码残差程度： 在二进制无噪声无损信道中： 在二进制无噪声无损信道中信息传输速率： 编码效率和码残差程度用来衡量编码效果，介绍编码效率。 *示例：其熵为：H(S)=0.811。 我们设置 s1=0 和 s2=1。 此时，平均码长和编码效率为。 编码二次扩展源：实时码 s1s1 9/16 0 s1s2 3/16 10 s2s1 3/16 110 s2s2 1/16 111 可见，编码效率得到提升* Kraft不等式总结及独特的可解码性准则告诉我们我们正在寻找的代码满足独特的可译性。

树图法 -----构造唯一的可解码平均码长极限定理和变长编码定理 -----更佳码的定义* 第5节 Ferno编码 Ferno编码也是一种常见的概率匹配编码方法。 编码步骤如下： 将源符号按照概率值进行排序，使得 p(x1)≥ p(x2)≥…≥ p(xn) 将排序后的源符号按照概率值进行分组，使得每组的概率尽可能接近或相等。 例如，编码二进制码时，分为两组，编码m进制码时，分为m组。 每组分配一个代码元素。 按照同样的原则划分每一组，重复步骤2和3，直到每一组中只剩下一个源符号。 *示例：假设有一个单符号离散源，该源对源编码二进制 Ferno 代码。 编码过程如下。 第六节 Ferno编码* 该源的熵为： 平均码长为： 编码效率为： 本例中，Ferno编码的编码效率较高。 Ferno 代码更适合每个分组的概率非常接近的源。 尤其是在对每次分组概率相等的信息源进行编码时，能够达到理想的编码效率。 第 6 节 Ferno * 问题中的码字也可以用码树来表示，如图所示。 第 6 节 Ferno 编码* * 通道可以传输的符号与源发送的消息（符号）不一致。 通道不能传输消息，自然也不能传输它所承载的信息。 * 提高抗干扰能力往往是以降低信息传输速率为代价的； 反之，提高信息传输速率可能会削弱抗干扰能力，有效性和可靠性是矛盾的方面。

然而，源自信息论基础理论的编码定理从理论上证明下界值，至少存在某种更优的编码或信息处理方法，能够在有效性和可靠性两个矛盾方面实现辩证统一。 * 无失真：要求准确再现信源的输出，确保信源的所有信息无损传输到新宿。 仅考虑有效性而不考虑可靠性，信道编解码器被视为无损和无噪声信道。 * 使用通道的输入符号集作为编码符号集，对信源符号进行一一对应的编码，使信源适合信道传输。 这是信源编码在通信系统中的基本功能。 如果要在信道中没有噪声干扰的情况下不失真地传输来自源的信息，则源编码的代码必须是唯一可解码的。 * 等长非奇异码必须是单义可解码的定长码：码字长度K固定，相应的编码定理称为定长源编码定理，是一种寻求最小K值的编码方法。 变长编码：K是一个可变值，相应的编码定理称为变长编码定理。 这里的最小K值是指最小的数学期望*一般情况下，源符号不是均匀分布的，并且彼此相关，所以源的极限熵会比更大熵logr小很多。 此时，定长编码中每个信号的源符号所需的平均二进制码符号数量大大减少，从而提高了编码效率； * 理解：编码后的新源的l：源扩展N次后每个源符号对应的编码符号数，N：源扩展的次数； l/N：扩展前源符号对应的平均码符号数； l/Nlogr：一个l/N长码符号序列可以承载的更大信息量，H(S)：扩展前信源的熵； 定长信源编码定理的含义：信源经过定长编码后，其所能携带的更大信息量大于信源携带的平均信息量（熵）。 一般来说，源符号不是等概率分布且相互关联的，因此源的极限熵会远小于更大熵 logr。 此时定长编码中每个源符号平均学习的二进制码符号数量大大减少，从而提高了编码效率； * 对于码3，接收到10时，无法判断码字是否终止。 它必须等待下一刻代码符号的到来才能做出决定。

* 非扩展代码是唯一可以解码的代码类型，这意味着非扩展代码必定是唯一可疑的代码。 相反，事实并非如此。 唯一可解码的代码不一定是非扩展代码。 由于非扩展码是明确的并且可以立即解码，因此它们通常用于无失真源编码。 使用树形图方法可疑地构造非扩展代码。 * 在利用树形图构建实时代码的过程中，源符号数q、代码符号数r以及这q个码字的代码长度ni之间存在一些约束。 满树：在码数图中，当每个码字的级联分支数量相同时，为定长码。 此时的代码树称为完整树。 例如：码长为N的全树的终端节点数为mN，可以表示mN个码字。 * 源代码是否具有单义可译性与待编码的源符号数量、代码符号数量以及码字长度密切相关。 单义可解码性存在的充分必要条件是满足卡夫不等式。 由于定理的必要性，qrli 的任何唯一可解码结构都必须满足不等式。 从充分性来看，满足不等式的qrli至少可以构成具有rqli结构的实时码，因此任何唯一的可解码码都可以用具有相同结构的非扩展码来代替。 因为以后的重点会放在实时代码上。 * 给出要编码的源S。 * 码率R反映了实时编码在无噪声信道中传输信息的有效性。 R越大，每个代码符号携带的信息越多。 平均信息量越大，即有效性越高； 对于给定的信源S，由于统计特性已确定，其熵值H(S)，各信源符号 第4章 不失真信源编码* 第4章 无失真信源编码 之一节简介 第二节 码的分类 第三节 等长源编码定理第 4 节 变长源编码定理 第 5 节 Ferno 编码* 简介 通信的基本任务：高效可靠地传输信息。

为了将源发送的消息携带的信息通过信道高速、高质量地传输到接收者，存在三个问题：之一，源发送的符号可能不适合信道传输。 ?以信道能够传输的符号作为编码符号集，对信源发出的每个符号进行一对一的无失真编码。 （无失真信源编码）第二，信道能够尽可能快地传输信源发送的符号，即要求编码有效，用尽可能少的信道符号来表示信源发送的每一条消息。 第三，在受干扰和噪声的信道中传输时，码字应具有抗干扰功能，并具有一定的自动检错和纠错能力。 （噪声离散信道编码） * 信源编码：以提高通信效率为目的的编码。 这通常是通过压缩源的冗余来实现的。 所使用的一般方法是压缩每个源符号的平均位数或源的码率。 即用较小的码率传输相同的信息量，增加了单位时间内平均传输的信息量，从而提高了通信的有效性。 信道编码：以提高信息传输的可靠性为目的的编码。 这通常是通过增加源的冗余来实现的。 一般采用的方法是增加码率/带宽。 与源编码正好相反。 密码：是为了提高通信系统的安全性而设置的密码。 这通常是通过加密和解密来实现的。 之一节引言* 信源编码理论是信息论的一个重要分支，其理论基础是信源编码两大定理。 无失真源编码定理：是离散源/数字信号编码的基础； 失真受限源编码定理：是连续源/模拟信号编码的基础。

信源编码的分类：离散信源编码、连续信源编码和相关信源编码。 离散信源编码：独立信源编码，可实现无失真编码； 连续源编码：独立源编码，只能实现失真受限的源编码； 相关源编码：非独立源编码。 第1节介绍*第2节代码的分类编码器可以看成是这样一个系统。 其输入端为原始源S，其符号集为； 信道可以传输的符号集是。 编码器的功能是利用符号集中的元素即码字的码字长度，简称码长。 * 示例：用{u1, u2, u3, u4}表示信源的4条消息，编码符号集为{0,1}。 表3-1列出了几种不同的源编码。 表4-1 同一源的几种不同编码源。 每个消息概率代码 1 code 2 code 3 code 4 u1 q(u1) 00 00 0 1 u2 q(u2) 11 01 1 10 u3 q(u3) 10 10 00 100 u4 q(u4) 11 11 11 1000 * 1。二进制代码：代码符号集X={0,1}。 如果要通过二进制通道传输信息源，就必须将信息源编码成二进制码，这也是最常用的编码。

2、等长码：如果一组码中所有码字的长度都相同，则称为等长码。 3、变长码：如果一组代码中所有码字的长度不同，则称为变长码。 4、非奇异码：如果一组码中所有码字都不同，则称为非奇异码。 第二节 码的分类* 5. 奇异码：如果一组码具有相同的码字，则称为奇异码。 6. 代码的 N 倍扩展：如果代码，代码称为代码 B，则它是代码 C 的 N 倍扩展代码。 7. 唯一可解码：如果代码的任何有限长度的代码符号序列只能被唯一解码为相应的源符号序列，则该代码称为唯一可解码或单义可解码。 二段码的分类* 例：如果有四个源符号{s1,s2,s3,s4}，采用二进制编码，l=2，那么可以编译成s1=00,s2=01,s3=10 ，s4=11。 第三节 等长信源编码定理 如果信息源以不失真的等长编码，则必须满足 式中，l为码长，r为码符号集中的符号个数，q为信源个数符号。 如果我们要对N次扩展信息源进行编码，也必须满足。 两边取对数，可得： 表示每个源符号平均需要的编码符号数。 * 示例：英语电报32个符号的二进制编码。 根据上面的关系：我们已经知道英语的极限熵是1.4bit，远小于5bit。 也就是说，5个二进制码符号只携带1.4bit的信息。 事实上，5个二进制符号最多可以携带5位信息。

我们可以缩短平均码长，提高信息传输速率。 ---》香农的信源编码第3节等长信源编码定理* 定理4.3（等长信源编码定理） 具有熵H(S)的离散无记忆信源，如果将信息扩展N倍 信源执行等长r元编码，码长为l。 对于任何大于0的ε，只要N无穷大，就可以实现几乎无失真的编码。 反之，如果：则不可能实现无失真编码。 当 N 趋于无穷大时，译码错误率接近 1。 第三节 等长信源编码定理* 定理 4.3 的条件表达式可以写为： 左边表示一个编码符号所包含的更大信息量。 可以携带，而右边代表长度为 N 的序列携带的平均信息量。因此，只要码字传送的信息量大于源序列携带的信息量，失真-自由编码总是可以实现的。 定理4.3的条件表达式也可以写为： 令其称为编码信息率或编码率。 可见，只有当编码信息率大于信源的熵时，才能实现无失真编码。 第三节 等长信源编码定理* 更优编码效率为： 为了衡量编码效果，称为编码效率。 当方差和ε都给定，并且允许的错误概率小于δ时，源序列长度必须满足或： 第3节 等长源编码定理 只有当N足够大时，编码效率才接近1 * 举例：假设离散源：如果采用等长二进制编码，要求编码效率且允许错误率，则：即长度必须达到4130万以上。

第三节等长信源编码定理 由此可见，当误码率和效率要求不严格时，超过4000万个信源符号必须一起编码，技术实现难度很大。 * 第4节 变长源编码定理 不等长编码允许等长消息变换为不等长编码序列。 频繁出现的消息通常被编码为短代码，而不频繁出现的消息被编码为长代码。 这样可以最小化平均码长，从而提高通信效率，但代价是增加了编解码设备的复杂度。 例如，在由不等长码字组成的序列中，正确识别每个不同长度码字的起始点比等长码要复杂得多。 解码延迟/解码同步：收到不等长的码序列后，有时无法立即判断码字是否真正结束，从而无法立即解码。 它必须等到后续的符号被接收到之后才能被正确解码。 * 源符号出现概率 code 1 code 2 code 3 code 4 s1 s2 s3 s4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 1 10 100 1000 1 01 001 0001 第 4 节更改 长源编码定理代码1：显然不是唯一可以解码的。 。 代码2：它是一种非奇异代码，不是唯一可以解码的代码。 虽然这个码从单个码字的角度来看不是奇异的，但从有限长度码序列的角度来看它仍然是奇异的码。 代码3：虽然是唯一可以解码的，但直到接收到下一个“1”时才能确定码字的结束，解码存在延迟。

编码4：唯一可解码且无解码延迟。 码字中的符号“1”起到逗号的作用，故称为逗号码。 * 定义：如果一个码组中的任意一个码字不是另一个码字的扩展，或者没有发现一个码字是另一个码字的前缀，或者说任何一个码字后面都跟着多个码元。 如果最后一个不是码组中的另一个码字，则称为即时码或非扩展码。 又叫前缀条件码/不同前缀码/不同前缀码/逗号码、所有码、非奇异码、唯一可解码即时码、第四节、变长源编码定理* 图解码的分类结构图如下从上面的结构图可以看出代码分类结构图。 码分为两类：奇异码和非奇异码。 我们只讨论非奇异码。 非奇异码分为两类：唯一可解码和非唯一可解码。 我们只讨论唯一可解码的。 * 2.实时代码的树形图构造方法 我们可以以树形图的形式构造实时代码，如代码 0 1 0 0 1 1 1 1 01 001 0001 代码 4 1 0 1 1 的树形图0 0 0 0 10 110 1110 code 3 的树形图。 Root - 码字的起点。 分支数 - 代码符号数。 节点 - 分支的结束顺序 - 代码长度的端点 - 代码字的完整树 - 等长代码的非完整树 - 可变长度。 代码节4 变长源编码定理 从树根到各阶节点的路径分支上的代码符号被视为一阶节点各自的代码符号序列* 例如，代码C包含4个码字，码字 *** 为{1,01,000,001}，由试验代码树表示。

解决方案：代码树采用二叉代码树，如图。 (000)001 (001)01(01)R1 (1) 图像代码的二进制码树表示* 3. Kraft 不等式定理 4.4 对于任何具有代码符号 的实时代码，对应的代码长度为 ，则必须满足：反之，如果码长满足上式，那么一定存在这样的立即码。 可以证明，为了实现唯一的可解码性，也必须满足上述不等式。 定理4.6 如果存在唯一可解码的码长，则必定存在相同长度的实时码。 第四节 变长源编码定理* 唯一可解码准则* 唯一可解码准则——例如，假设源消息集{x1,x2,x3,x4,x5,x6,x7}，它们分别编码为{a,c, ad,abb, bad,deb,bbcde}，可构造如下表所示的编码符号集序列： S0 S1 S2 S3 S4 S5 S6 S7 ad eb de b ad d eb c bb cde bcde ad abb bad deb bbcde 时n>7，sn 为空集。 根据定义，它不是唯一可解码的* 假设信源编码后的码字为：，码长为： 则该码的平均码长为： 平均每个符号所携带的信息量即为信息传输速率编码后：如果存在唯一可解码的码，其平均码长小于其他唯一可解码的长度，则该码称为紧凑码或更优码。 ，无失真源编码的基本问题是找到紧致码。

第 4 节 变长源编码定理* 平均代码长度与有效性之间的关系。 给出要编码的源S。 源S的每个源符号si包含的平均信息量等于源S的熵H(S)，其值保持不变。 每个码符号携带的平均信息量，即码W的信息传输速率，取决于平均码长。 因此，平均码长是即时码有效性的衡量标准。 编码时不仅要考虑满足Kraft不等式，还要考虑码长与信源空间的合理组合，充分挖掘信源统计特性的潜力，使平均码长尽可能小。 *例如：源空间为编码符号集{0,1}，码字长度为l1=1,l2=2,l3=3,l4=3。 1.求唯一可译码的可能性，因为满足Kraft的不等式，因此它必须能够形成至少一个即时码：例如，W(1):{w1=0; w2=10； w3=110； w4=111； }W(2):{w1=1; w2=01； w3=000； w4=001； }W(3):{w1=0; w2=11； w3=100； w4=101； 这三个实时码的四个码字与源符号集一致。 符号可以有不同的组合，编译出的代码满足独特的可解码性条件，并且都是无失真的源代码。 因此，即时码的形式并不唯一。

*不同组合得到的平均码长不同，因此效率也不同。 例如，若概率较高的符号对应码长较小的码字，则W(1)：{s1->w1=0； s2->w2=10； s3->w3=110； s4->w4=111 } 如果平均码长使得高概率的符号对应长码长的码字，则W(1)：{s1->w1=111； s2->w2=110； s3->w3=10； s4-> w4=0 } 说明：为了提高编码效率，即时码的平均码长必须尽可能小，并且概率高的源符号必须尽可能分配给短码; 尝试将源符号分配为长编码 2.考虑编码的有效性，找到更佳编码* * 通道可以传输的符号与源发送的消息（符号）不一致。 通道无法传输消息，自然也无法传输所承载的信息。 * 提高抗干扰能力往往是以降低信息传输速率为代价的； 反之，提高信息传输速率可能会削弱抗干扰能力，有效性和可靠性是矛盾的方面。 然而，源自信息论基础理论的编码定理从理论上证明，至少存在某种更优的编码或信息处理方法，能够在有效性和可靠性两个矛盾方面实现辩证统一。 * 无失真：要求准确再现信源的输出，确保信源的所有信息无损传输到新宿。 仅考虑有效性而不考虑可靠性，信道编解码器被视为无损和无噪声信道。

* 使用通道的输入符号集作为编码符号集，对信源符号进行一一对应的编码，使信源适合信道传输。 这是信源编码在通信系统中的基本功能。 如果要在信道中没有噪声干扰的情况下不失真地传输来自源的信息，则源编码的代码必须是唯一可解码的。 * 等长非奇异码必须是单义可解码的定长码：码字长度K固定，相应的编码定理称为定长源编码定理，是一种寻求最小K值的编码方法。 变长编码：K是一个可变值，相应的编码定理称为变长编码定理。 这里的最小K值是指最小的数学期望*一般情况下，源符号不是均匀分布的，并且彼此相关，所以源的极限熵会比更大熵logr小很多。 此时，定长编码中每个信号的源符号所需的平均二进制码符号数量大大减少，从而提高了编码效率； * 理解：编码后的新源的l：源扩展N次后每个源符号对应的编码符号数，N：源扩展的次数； L/N：在扩展前对应于源符号的代码符号的平均数量； l/nlogr：l/n长代码符号序列可以携带的更大信息，h（s）：在扩展源熵之前； 固定长度源编码定理的含义：在固定长度编码后，它可以携带的更大信息量大于源携带的平均信息（熵）。 通常，源符号不符合分布和相互关联，因此源的极限熵将比更大熵logr小得多。 目前，在固定长度编码中为每个源符号学到的二进制代码符号的平均数量大大降低，从而提高了编码效率。 *对于代码3，在接收10时，不能判断是否终止代码单词。 它必须在做出决定之前等待代码符号的到达。

*非扩展代码是唯一可以解码的代码类型，这意味着非扩展代码必须是唯一可疑的代码。 相反，这不是事实。 唯一的可解码代码不一定是非扩展代码。 由于非扩展的代码是明确的，并且可以立即解码，因此它们通常用于无失真源编码。 使用树图方法可疑地构造非扩展代码。 *在使用树图构建实时代码的过程中，源符号Q的数量，代码符号r的数量和这些Q代码字的代码长度NI之间存在一些约束。 完整树：在代码编号图中，当每个代码字的串联分支的数量相同时，它是固定长度代码。 此时代码树称为完整树。 例如：具有代码长度n的完整树的终端节点的数量是MN，它可以代表MN代码字。 *源代码是否具有单次转换性与要编码的源符号的数量，代码符号的数量和代码字的长度密切相关。 单局解释性的存在的必要条件是满足Kraft的不平等现象。 由于定理的必要性，QRLI的任何独特的可解码结构都必须满足不平等。 从充分性来看，满足不平等的QRLI至少可以构成与RQLI结构的直接代码，因此任何具有相同结构的非扩展代码都可以代表任何唯一的可解码代码。 由于稍后我们将重点介绍实时代码，因此给出了要编码的源。 *代码速率R反映了实时代码在无噪声通道中传输信息的有效性。 r越大，每个代码符号携带的信息越多。 平均信息量越大，即有效性越高； 对于给定的源s，由于已经确定了统计特征，因此其熵值h（s），每个源符号 *当平均代码长度达到限制值时，编码后的通道的信息传输速率是logr *还可以证明，如果我们不知道源的概率分布，并且我们使用估计的概率分布来编码，则平均代码长度将延长，但是如果估计的偏差（如果不大），则平均代码长度不会增加太多（定理4.9的内容）。 *理论上的源编码定理解释说，编码效率接近1，即理想编码器的存在，以无限长的源符号（L→∞）的成本用于实际编码中的统一编码。