第5章 信源编码part1v2

第5章信源编码信源编码信源编码的基础是信息论中的两个编码定理：无失真编码定理限失真编码定理无失真编码只适用于离散信源；对于连续信源，只能在失真受限制的情况下进行限失真编码。本章首先介绍信源编码的相关概念以及信源编码定理，然后描述编码方法。2024/3/202信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/203目的及基本思路相关术语信源编码的目的及基本思路信源编码的过程：目的：用尽可能少的码符号数(条件：码进制数相同),去传递同样多的信息量。信源符号信源符号序列信源符号集

类比：同样多货物，用尽可能少车次(载重量相同)去拉。码符号序列码符号集符合信道传输特性码符号4研究信源编码时的通信系统模型编码后的符号序列要符合信道传输特性(32个符号)010010100…5问题：如何编码才能保证信息的无失真传输？回答：信源符号序列要与码符号序列一一对应。问题：最大可能的信源符号序列数和码符号序列数？回答：信源符号序列数码符号序列数为简化起见，假设，则要求：，信源没有被压缩的可能性？问题：分析：(1)由于符号之间具有相关性，有些符号的组合不可能出现。例：英语信源不会出现。(2)有些符号的组合，出现概率非常微小。对这些符号的组合，可不进行编码。只能实现近乎无失真译码。6问题：假设信源符号间没有相关性，能否实现完全无失真压缩？分析：，表面上看没有压缩的余地。但这只是对定长编码而言。对于非定长编码，则有可能有：。实例：考虑无记忆信源的三次扩展信源编码：编码后平均码长：7总结：信源的冗余主要由两方面因素造成。(1)前后符号间的相关性。(2)不同符号的发生概率不同。*解决思路：使编码后的码符号序列不存在相关性，各符号出现概率相等。*比特平均每符号的实际载信量：比特一定有：降低了通信效率。平均每符号的最大载信量：指导思想：a.利用某种数学方法去除相关性。b.增加的长度，

越长,符号间相关性越强。(2)高概率对应短码，低概率对应长码。8去除相关性经常采用的数学方法：傅里叶变换，离散余弦变换，变换，小波变换等例：离散傅里叶变换时域表示法：个时域采样点，每个采样点的幅度频域表示法：个频域采样点，采样点的傅里叶系数相关独立正交变换，各频率分量彼此独立9信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2010目的及基本思路基本术语信源编码的一些基本术语码字长度码符号序列集合又称码书，码又称码字又称码元信源符号信源符号序列信源符号集码符号序列码符号集符合信道传输特性码符号信源符号序列集合11无失真编码：实现从信源符号序列集合到码符号序列集合间的一一映射。

元码：又称进制码，指码符号集合中符号的个数。等长码：又称定长码，指所有码字的长度相等。变长码：所有码字的长度可以不相等。分组码：将信源的输出符号序列，分组处理的编码。非分组码：当前码符号与信源已经输出的全部符号有关。本课程只研究分组码。12实例：码1是码2是奇异码非奇异码问题1：奇异码能否实现无失真传输？问题2：非奇异码是否一定能实现无失真传输？回答：不一定。例如：码2中的可翻译成或。回答：不能。？？13原因：非奇异码只是正确译码的必要条件，因为当码字排在一起时还有可能出现奇异性。奇异码与非奇异码：若分组码中所有码字不相同，称非奇异码，否则称为奇异码。问题：如何才能保证码为唯一可译码？分析：假设所编的码为。则所有可能的码符号序列应包括：一次扩展码：共个二次扩展码：共个

次扩展码：……共个14唯一可译码与非唯一可译码：对于任意有限长的码符号系列，若只能唯一的分割成一个个码字，则为唯一可译码；否则为非唯一可译码。例：一连串的码符号序列有两种解释

三次扩展码中的一个元素

二次扩展码中的一个元素15回答：唯一可译要求码的任意有限次扩展码应为非奇异码。（唯一可译性）*在唯一可译码中，有一类码，在译码时无需参考后续的码符号就能立即做出判断，译成对应的信源符号序列，称此类码为即时码；否则，称为非即时码。即时码与非即时码：实例：码1是码2是非即时码即时码第1位第2位第3位第4位10101011?16分析码2：即时码的条件因为如果没有一个码字是其它码字的前缀,则在接收到一个相当于一个完整码字的码符号序列后,便可立即译码,而无须考虑其后的码符号。2024/3/2017问题：如何判断码是否为即时码？（条件）回答：要求任何一个码字都不是其它码字的前缀。例：码1反例即时码的构造：最简单、最常用的方法是利用码树图法。根节点树枝一级节点二级节点三级节点编码过程及要点：对于元码，每个节点应延伸出个树枝。从第一级树枝开始，每个树枝分配一个码元。从根节点开始，到终节点结束的联枝，对应一个码字。终端节点终节点叶节点其后不再有树枝联枝(连在一起的树枝)18m＝2的二进制树图2024/3/2019问题：为什么上述编码过程，能保证编码为即时码？回答：关键是对到终节点结束的联枝编码字。从树根到每一个终端节点所走的路径均不相同，故一定满足对前缀的限制。整树与非整树考虑一个树有n阶节点整树：码树的各个分支都延伸到最后一级端点，此时，将共有mn个码字；非整树：码树中存在分支，没有延伸到最后一级端点，此时，将少于mn个码字。2024/3/202021从根节点开始，每级节点中所有的节点都向下延伸出m个节点，直到最后一级。满树：码的分类：同价码与非同价码：若码符号集中

的每个码符号

所占的传输时间都相同，称为同价码；否则，称为非同价码（如：电报中的莫尔斯码）。显然，对于同价码，定长码中每个码字的传输时间都相同，而变长码则可能不同。(本课程只研究同价码)非唯一可译码非奇异码分组码码非分组码奇异码唯一可译码即时码非即时码非同价码码同价码变长码码定长码22信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2023唯一可译定长码的存在条件定长信源编码定理唯一可译定长码的存在条件2024/3/2024对一个简单信源X进行定长编码，信源X存在唯一可译定长码的条件是：其中，n是信源X的符号个数，m是码符号数（码元个数），K是定长码的码长（码字长）。唯一可译要求:码的任意有限次扩展码应为非奇异码。定长码:每个码字长度相等，所以只要定长码是非奇异码，则必为唯一可译码。L次扩展信源的定长码对L次扩展信源XL进行定长编码，若要编得的定长码是唯一可译码，则必须满足：2024/3/2025唯一可译定长码的存在条件－举例英文电报信源有32个符号，26个英文字母加上6个标点符号，对此信源的每个符号进行二元编码。如何实现唯一可译码？2024/3/2026这就是说，每个英文电报符号至少要用5位二元符号进行编码才能得到唯一可译码。分析：信源符号数为n＝32，码元个数为m＝2，码字长度？定长信源编码定理－引入2024/3/2027满足上述条件的定长编码,可保证无失真的编码问题：平均码长很大，编码的效率很低。定长编码定理：讨论了编码的有关参数对译码差错的限制关系。信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2028唯一可译定长码的存在条件定长信源编码定理正定理：一个熵为的离散无记忆信源，若对长度为的信源符号序列进行等长编码，设码字是从个码符号集中选取的个码元组成。对于任意的和,只要满足：则当足够长

,必可使译码差错小于。逆定理：反之，当：，译码差错一定大于。当时，译码差错趋近于1。定长编码定理29所要求的译码差错概率信源符号信源符号序列信源符号集码符号序列（码字）码符号集符合信道传输特性码符号定长编码定理的物理意义30编码场景n：信源符号个数L:信源符号序列长m：码符号个数K:码符号序列长正定理：

长码符号序列的最大可能载荷信息量。折算后,平均每个信源符号的最大可能载信量。每个信源符号的实际载信量。若,说明不够。

物理意义的解释：31意义：定长编码后，所能携带的最大信息量，一定要大于信源所携带的平均信息量(熵)32定长编码定理－提高效率分析：一般情况下，信源符号非等概率分布，且相互关联信源极限熵H∞(X)

Hmax(X)=logn。2024/3/2033进行定长编码可使每个信源符号平均所需的码符号长大大减少，从而提高效率唯一可译定长码的存在条件问题：平均码长很大，编码的效率很低。定长编码定理－提高效率2024/3/2034平均每个英文信源符号只需近似用1.4个二元符号来编码，这比由式(K/L)≥logn计算的需要5位二元符号减少了许多，从而提高了信息传输速率。例：英文电报的二元编码：已知信源极限熵H∞(X)≈1.4比特/符号由可以得出：即(K/L)>1.4；编码信息率2024/3/2035编码信息率：编码后平均每个信源符号能载荷的最大信息量。若对长为L的信源符号序列进行定长编码，每个序列对应的码字长度为K，则比特/信源符号编码效率：=编码后平均每个信源符号的最大可能载信量要求平均每个信源符号携带的实际信息量编码效率36编码后的实际码长最小可能码长=说明：编码效率是小于或等于1的数。对同一信源，平均码长越短，信息传输率就越高，编码效率也越接近1。编码效率可以用来衡量各种编码方法在有效性方面的优劣。对于等长编码观察正定理：的含义：当时，说明：折算后平均每个信源符号携带的最大可能信息量等于要求携带的实际信息量。此时编码效率为。越大，编码效率越低。编码效率分析37编码效率与扩展次数L的关系回答：定长编码定理中，只有在L足够大的时候，必可使译码差错小于

，编码效率才能趋近于1经计算，当允许错误概率小于时，信源序列长度L必满足2024/3/2038问题：什么时候编码效率趋近1？？例1

设有离散无记忆信源要求编码效率,译码错误概率,求需要的信源序列长度L

。(1)计算自信息量的数学期望和方差比特/信源符号比特2/信源符号2解：分析计算步骤定理的应用—例139或者利用方差的简便计算公式：(2)根据要求的编码效率计算比特/信源符号(3)代入公式，计算信源符号序列长度。定理的应用—例1（续）40定理的应用—例2例2设离散无记忆信源，采取等长二元编码时，要求编码效率，允许错误概率求得：H(X)=0.8112024/3/2041分

析在编码效率和译码差错概率都不十分苛刻的情况下，所需的符号长度也是非常惊人的。一般只有在信源接近等概率分布时，算出的符号序列长度才是实际可接受的。对定长编码定理应用范围的说明：虽然定长编码定理的推导过程中要求信源是无记忆信源，但所得结论可推广到有记忆信源。无记忆信源有记忆信源正定理逆定理多符号信源：马尔可夫信源：42信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2043变长编码的必要性及付出代价变长码唯一可译码的条件变长信源编码定理变长编码的必要性44定长编码在理论上可以达到很高的编码效率，但是从例子中可以看到，在编码效率、错误概率要求较高的情况下，扩展次数L（定长编码需要的符号数）需要非常大，这在实际工程中是无法实现的。1.变长编码的必要性当L有限时，高传输效率的等长码往往要引入一定的失真和错误，它不像变长码那样可以实现无失真编码。在实际过程中，普遍使用变长编码。变长编码付出的代价452.付出的代价(1)译码时需要同步。信源符号序列2…变长码通常需要专门的同步通道。(2)可能遇到译码延迟。延迟问题：可利用编成即时码解决。定长码（例：）信源符号序列1译码为不需要同步通道信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2046变长编码的必要性及付出代价变长码唯一可译码的条件变长信源编码定理变长码唯一可译码的条件47唯一可译码的条件:变长码必须是非奇异码，而且任意有限长L次扩展码也应该是非奇异码。为了能够即时译码，变长码必须是即时码问题1:如何判断一组由给定码字构成的码是否为即时码？回答:要求任何一个码字都不是其它码字的前缀。即时码的判定问题判断任何一个码字是不是其它码字的前缀的方法？将给定的一组码字转成码树图的形式：若所有码字均对应从根节点到终节点的联枝,则为即时码;若某个码字位于另一码字对应节点之后，则为非即时码。实例：判断以下码是否为即时码？即时码的判定48问题2:当未给定码字,

如何判断能否构造出一种即时码？Kraft（克拉夫特）不等式即时码的条件49描述了信源符号数和码字长度之间满足什么条件才能构成即时码。定理设信源符号集

，码符号集为

，对信源进行编码，相应的码字为

，其分别对应的码长为

，则即时码存在的充要条件是：说明：给定码字个数，码符号集中的符号个数,各码字的码元长度，满足Kraft（克拉夫特）不等式的构成一类码，这类码中一定至少有一个是即时码，但并不是该类码中的每个码都是即时码。即时码一定满足Kraft不等式，但反过来则不一定。实例：仅举一反例即可。有如下码字：由于是的前缀，为非即时码。但代入，得：，满足Kraft不等式。另外：Kraft不等式同样适用于唯一可译码的判别。50信源编码（主要内容）信源编码定理（定长、变长编码定理）信源编码的相关概念：定长编码定理变长编码定理（香农第一定理）香农第三定理信源编码方法离散信源编码连续信源编码相关信源编码变换编码2024/3/2051变长编码的必要性及付出代价变长码唯一可译码的条件变长信源编码定理对同一信源，用同一码符号集编成的即时码或唯一可译码可能有很多种。从高效传输信息的角度出发，当然是希望寻找平均码长最短的编码。平均码长：码符号/信源符号

紧致码的定义52因为是唯一可译码，信源符号xi和码字Wi是一一对应的紧致码:对于给定的信源和码符号集，若存在一个唯一可译码，其平均码长小于所有其它唯一可译码的平均码长，则称为紧致码。（最佳码）经信源编码后，平均每个码符号所携带的信息量。单位：比特/码符号如何计算？码符号/信源符号比特/信源符号信息传输率和信息传输速率53信息传输速率：单位时间传输的信息量。（设:传输一个码符号平均需要t秒）Rt越大，信息传输率就越高。信源熵H(X)是确定的，因此，提高信息传输率的方法是使平均码长最短。比特/秒信息传输率若单符号信源的熵为,码符号集中的符号个数为,则总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足：即：单符号信源的变长编码定理54问题：何时能取到最小的

（即上式左边取等号）回答：要求。实例：对二元码，要求所有消息的概率必须是只有在上述条件下，唯一可译码的平均码长才能达到下限值，而且可以保证所编得的码一定为紧致码。

必须为整数例

对编二元紧致码。解：算出各码字的码长，再利用码树图法进行构造。(1)计算各码字码长(2)利用码树图法构造验证上述码为紧致码：唯一可译码的码长下限：平均码长:55若次扩展信源的熵为,码符号集中的符号个数为，对信源进行编码，总可以找到一种无失真编码方法，构成唯一可译码，使其平均码长满足：单符号信源

次扩展信源无记忆信源次扩展信源的变长编码定理56是每个所对应的平均码长与单符号信源进行比较：趋于更短

特别地，当时：所得码一定是极致码。57离散无记忆信源X中每个信源符号xi所对应的平均码长变长无失真信源编码定理说明，只要编码后的码符号序列所能携带的信息量不小于信源本身的信息量,就可以实现唯一可译码。

单符号信源编码效率：编码后平均每个信源符号的最大可能载信量要求平均每个信源符号携带的实际信息量可用来估算，为达到效率，所需要的信源符号序列长度。扩展信源*【分母变大，结果变小】58例要求编码效率,对二元变长编码,求需要的信源序列长度。解：代入：比特/符号计算得：比较：定长编码问题：为什么变长编码可做到完全无失真编码？回答：因为变长编码可保证信源符号序列和码符号序列一一对应。59对变长编码定理应用范围的说明：60虽然变