第三章-无失真信源编码

1、第三章第三章 无失真信源编码无失真信源编码语音、图像信源；限失真信源编码，文字、文件信源；无失真信源编码，分类适用于离散信源或数字信号适用于离散信源或数字信号适用于连续信源或模拟信号适用于连续信源或模拟信号信源编码的分类信源编码的分类?为什么要对信源进行编码为什么要对信源进行编码? 由于信源符号之间存在分布由于信源符号之间存在分布不均匀不均匀和和相关性相关性，使得信源存，使得信源存在冗余度。在冗余度。 （1）信源输出符号间的依赖关系使得信源熵减小，这就）信源输出符号间的依赖关系使得信源熵减小，这就是信源的相关性。相关程度越大，信源的实际熵越小，越趋是信源的相关性。相关程度越大，信源的实际熵越小

2、，越趋近于极限熵近于极限熵 ；反之，相关程度减小，信源实际熵增大。；反之，相关程度减小，信源实际熵增大。 （2）实际信源的符号分布概率不是均匀的，这使得实际的）实际信源的符号分布概率不是均匀的，这使得实际的信源熵总是小于最大熵信源熵总是小于最大熵 。 也就是说，实际发送的消息总是包含有无用的信息。信源也就是说，实际发送的消息总是包含有无用的信息。信源包含有冗余。包含有冗余。)(XH)()(max0XHXH信源编码的信源编码的主要任务主要任务就是减少冗余，提高编码效率。就是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统计特性，具体说，就是针对信源输出符号序列的统计特性，寻找一定的方

3、法把信源输出符号序列变换为最短的码字序列。寻找一定的方法把信源输出符号序列变换为最短的码字序列。 信源编码的基本途径信源编码的基本途径 是什么是什么? 信源编码的信源编码的基本途径基本途径有两个，有两个，一是一是使序列中的各个符使序列中的各个符号尽可能地互相独立，即解除相关性；号尽可能地互相独立，即解除相关性；二是二是使编码中使编码中各个符号出现的概率尽可能地相等，即概率均匀化。各个符号出现的概率尽可能地相等，即概率均匀化。 信源编码的机理：信源编码的机理：AEP是什么导致我们研究渐进等同分割性质？ 回想：最大离散熵原理 定理：等概分布时，离散熵最大化 但是：信源输出的一般不是等概分布的 问题

4、：如何将非等概输出的信源变成等概？渐进等同分割性质信源输出序列信源输出序列将序列进行分割信源编码的基础是什么信源编码的基础是什么? 信源编码的信源编码的基础基础是：两个编码定理，即无失真编码定理和限失真是：两个编码定理，即无失真编码定理和限失真编码定理。编码定理。1）无失真编码是可逆编码，即信源符号转换成代码后，可从代码）无失真编码是可逆编码，即信源符号转换成代码后，可从代码无失真的恢复原信源符号。只适用于离散信源。无失真的恢复原信源符号。只适用于离散信源。2）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无

5、限多个。此时只能根据率失真编码定理在因为后者的取值可有无限多个。此时只能根据率失真编码定理在失真受限制的情况下进行限失真编码失真受限制的情况下进行限失真编码 说明说明： 编码定理证明编码定理证明： （1）必存在一种编码方法，使代码的平均长度可任意必存在一种编码方法，使代码的平均长度可任意接近但不能低于极限熵接近但不能低于极限熵 （2）达到这目标的途径，就是使概率与码长匹配。达到这目标的途径，就是使概率与码长匹配。 3.1信源编码概述信源编码概述3.2消息的冗余度消息的冗余度3.3定长编码定理和定长编码方法定长编码定理和定长编码方法3.4 变长编码定理变长编码定理 3.5 变长编码方法变长编码方

6、法3.6游程编码游程编码编码器可以看作这样一个系统，它的输入端为原始信源编码器可以看作这样一个系统，它的输入端为原始信源U，其符号集，其符号集为为U:u1,u2,uq；而信道所能传输的码符号集为；而信道所能传输的码符号集为X:x1,x2,xr；编；编码器的功能是用符号集码器的功能是用符号集X中的元素，将原始信源的符号中的元素，将原始信源的符号ui变换为相应变换为相应的码字符号的码字符号Wi，(i=1,2,q)，所以编码器输出端的符号集为，所以编码器输出端的符号集为W:W1,W2,Wq。3.1 信源编码概述信源编码概述信源消息信源消息U=(u1,u2, uq)码符号集码符号集X=(x1,x2,

7、xr)将将 ui Wi （ w1,w2,wLi ） wix1,x2,xr这种一一对应变换称为信源编码。这种一一对应变换称为信源编码。3.1.1 信源编码：信源编码：Li为码字为码字Wi的码元个数，称为码字的码元个数，称为码字Wi的长度，简称码长。的长度，简称码长。将信源消息分成若干组，即将信源消息分成若干组，即符号序列符号序列ui，ui=(ui1,ui2,uil,uiL)序列中的每个符号取自于同一个符号集序列中的每个符号取自于同一个符号集A， uil(a1,a2,an)。而每个符号序列而每个符号序列ui依照固定的码表映射成一个码字依照固定的码表映射成一个码字Wi，这，这样的码称为分组码。只有分

8、组码有对应的码表。样的码称为分组码。只有分组码有对应的码表。分组码定义：分组码定义：如果每次只传送一个符号，即序列长度如果每次只传送一个符号，即序列长度L1要将这样要将这样 的符号进行传输，常采用二元信道，码符号集的符号进行传输，常采用二元信道，码符号集X为为0,1。若将信源在该信道上传输，需把信源符号变换成。若将信源在该信道上传输，需把信源符号变换成0，1符号组成的码字序列。符号组成的码字序列。ui=ui1(a1,a2,an)例：例：信源符号信源符号信源符号出信源符号出现概率现概率码表码表a1a2a3a4p(a1)p(a2)p(a3)p(a4) 00 01 10 11 0 01 001 11

9、1码码1码码23.1.2 码的类型码的类型 码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码（非延长码）即时码（非延长码）码符号集中符号数码符号集中符号数r2称为二元码，称为二元码，r3称为三元码称为三元码若分组码中的码长都相同则称为等长码，否则称为变长码若分组码中的码长都相同则称为等长码，否则称为变长码信源符号信源符号信源符号出信源符号出现概率现概率码表码表a1a2a3a4p(a1)p(a2)p(a3)p(a4) 00 01 10 11 0 01 001 111码码1码码2码码1是等长码，码是等长码，码2是变长码是

10、变长码奇异码和非奇异码奇异码和非奇异码若信源符号和码字是一一对应的，即所有码字都不相同，若信源符号和码字是一一对应的，即所有码字都不相同，则该码为非奇异码；反之为奇异码。则该码为非奇异码；反之为奇异码。信源符号信源符号符号出现概率符号出现概率 码码1码码2码码3码码4a1a2a3a41/21/41/81/8 0110011010000111010010001010010001码码1是奇异码，码是奇异码，码2，码，码3和码和码4是非奇异码，是非奇异码，码码4为即时码（非延长码）为即时码（非延长码）唯一可译码唯一可译码非奇异码中，任意有限长的码元序列，只能被唯一的译成所对非奇异码中，任意有限长的码

11、元序列，只能被唯一的译成所对应的信源符号序列，称为唯一可译码。应的信源符号序列，称为唯一可译码。例如：例如：U: u1,u2,u3; X:0,1; W: w1=0, w2=10, w3=11, 为唯一可译码。为唯一可译码。当接收码字序列为：当接收码字序列为：10011001111 时，可以唯一地译为：时，可以唯一地译为：w2,w1,w3,w1,w1,w3,w3;如果码字集合为：如果码字集合为：W:w1=0,w2=1,w3=01 则为非唯一可译码。则为非唯一可译码。当接收码字序列为：当接收码字序列为：00111101 时，可以译为：时，可以译为：w1,w1(w3)0011110100111101

12、w1,w1,w2,w2,w2,w2,w3w1,w3,w2,w2,w2,w3非即时码和即时码非即时码和即时码唯一可译码中，如果接收端收到一个完整的码字后，不能立唯一可译码中，如果接收端收到一个完整的码字后，不能立即译码，还需等下一个码字开始接收后才能判断是否可以译即译码，还需等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。码，这样的码叫做非即时码。例如：例如：W：1，10，100，111不是即时码，不是即时码， 1是是 10的前缀，的前缀， 10 为为100的前缀。的前缀。没有任何完整的码字是其他码字的前缀，可立即译码的叫没有任何完整的码字是其他码字的前缀，可立即译码的叫做即时

13、码（非延长码）。做即时码（非延长码）。即时码一定是唯一的，唯一可译码却不一定是即时码。即时码一定是唯一的，唯一可译码却不一定是即时码。例如：例如：W：0，01是唯一的，但不是即时码。是唯一的，但不是即时码。则是某一码组的前面向后面看：比如则是某一码组的前面向后面看：比如u1=0，被采用后，则从被采用后，则从0以后的任何延长出去组合，比如以后的任何延长出去组合，比如00、01、001等均不能再用。等均不能再用。 即时码及其树图构造法即时码及其树图构造法 码树码树码树码树：用码树表示码字的组成：用码树表示码字的组成码树构造要点：码树构造要点：1）最上（下）端为树根，从树根向下（上）延伸出树枝，）最

14、上（下）端为树根，从树根向下（上）延伸出树枝，树枝总数等于树枝总数等于r，树枝的尽头为节点。，树枝的尽头为节点。2）从每个节点再伸出）从每个节点再伸出r个树枝，当某节点被安排为码字个树枝，当某节点被安排为码字 后，就不再伸枝。后，就不再伸枝。3）每个节点伸出的树枝标上码符号，从根出发到终端节）每个节点伸出的树枝标上码符号，从根出发到终端节 点所走路径对应的码符号序列则为终端节点的码字。点所走路径对应的码符号序列则为终端节点的码字。r进制码树：有进制码树：有r个分支个分支树根树根一级节点：经过一个分支到达的节点，有一级节点：经过一个分支到达的节点，有r个个n级节点：级节点：rn个个码字：从树根到

15、节点的分枝标号序列码字：从树根到节点的分枝标号序列码树图码树图 二进制码树二进制码树（二元编码）（二元编码）012000001111122222三进制码树三进制码树（三元编码）（三元编码）A010000000000000111111111110114 唯一可译码存在的充要条件唯一可译码存在的充要条件：inKi11r其中其中n表示信源符号数，表示信源符号数，r表示进制数，表示进制数，Ki表示各码字长度。表示各码字长度。对含有对含有n个信源符号的信源用含有个信源符号的信源用含有r个码元的码符号集进行个码元的码符号集进行编码，各码字的长为编码，各码字的长为k1，k2.，其唯一可译码存在的充要，其唯一

16、可译码存在的充要条件是，满足条件是，满足克劳夫特（克劳夫特（Kraft）不等式）不等式例：设二进制码树中例：设二进制码树中U（a1,a2,a3,a4),K1=1,K2=2,K3=2,K4=3,请判断这是否存在唯一可译码？请判断这是否存在唯一可译码？i4K-1-2-2-3i192=2 +2 +2 +2 =18不存在这种不存在这种Ki的唯一可译码。的唯一可译码。010011a1a2a3a4如果传送如果传送000100，01000，1a3,a2a4,a1a1: 1a2: 01a3: 00a4: 000如果改成如果改成K1=1,K2=2,K3=3,K4=3,请判断这是否存在唯一可译码？请判断这是否存在

17、唯一可译码？i4K-1-2-3-3i12=2 +2 +2 +2 =1010011a1a2a3a4存在这种存在这种Ki的唯一可译码。的唯一可译码。a1: 1a2: 01a3: 000a4: 001注意：注意：克劳夫特（克劳夫特（Kraft）不等式只是用来说明唯一可译码是否）不等式只是用来说明唯一可译码是否存在，并不能作为判断哪些码是唯一可译码的依据存在，并不能作为判断哪些码是唯一可译码的依据如码字（如码字（0，10，010，111）满足克劳夫特不等式，但它不是）满足克劳夫特不等式，但它不是唯一可译码。其实只有前缀码才满足。唯一可译码。其实只有前缀码才满足。下面考虑求解前缀码的最小平均码长问题。该

18、问题等价于求解满足Kraft不等式的长度集合k1,kn，便得它的平均码长 ，不超过其他任何前缀码的期望长度这是一个标准的最优化问题最优码最优码Li iiLp k其约束条件为11inKir利用拉格朗日乘子法，将带约束的最小化问题转化为求iki iiiJp kr关于ki的微分等于0，可求得最优码长等于*logirikp 最优平均码长等于*logi iirirLp kppHX *rLHX由于码长为整数3.2 消息的冗余度消息的冗余度 信源熵信源熵 表示信源输出每一个符号所携带的信息表示信源输出每一个符号所携带的信息量。量。 对于一个具体信源，它所具有的总信息量是一定的对于一个具体信源，它所具有的总信

19、息量是一定的 信息熵越大（每个信源符号所承载的信息量越大）信息熵越大（每个信源符号所承载的信息量越大） 输出全部信源信息所需传送的符号就越少输出全部信源信息所需传送的符号就越少 通信效率越高通信效率越高 这是我们研究信息熵的目的这是我们研究信息熵的目的 离散无记忆信源：离散无记忆信源： 信源符号间彼此无依赖、等概率分布，信源熵最大信源符号间彼此无依赖、等概率分布，信源熵最大（最大熵定理最大熵定理） H Hmaxmax ，携带信息的效率最高。，携带信息的效率最高。离散有记忆信源：离散有记忆信源： 信源输出符号间彼此依赖、相关，信源熵减小（条信源输出符号间彼此依赖、相关，信源熵减小（条件熵无条件熵

20、），输出符号间相关长度越长，信源件熵无条件熵），输出符号间相关长度越长，信源熵越小。熵越小。 所有有记忆信源、非等概率离散无记忆信源熵所有有记忆信源、非等概率离散无记忆信源熵 H Hmaxmax 121lim()lim(/)bit/LLLLLHHH XX XXX符号对平稳信源对平稳信源理论上需要传输的最小信息率理论上需要传输的最小信息率有有其中其中: 是具有是具有N种取值可能的单消息信源的最大信息熵种取值可能的单消息信源的最大信息熵(等概时等概时) (符号所含的信息熵依次递减符号所含的信息熵依次递减,平均符号信息熵自平均符号信息熵自然越来越小然越来越小) 编码时如果有以下假设编码时如果有以下假

21、设:消息序列的各符号统计独立消息序列的各符号统计独立;各取值各取值等概出现，则实际是没有对信源仔细的研究等概出现，则实际是没有对信源仔细的研究,没有利用其统计特没有利用其统计特性性,认为其平均符号信息熵为认为其平均符号信息熵为 ,这必然会产生大量的冗余这必然会产生大量的冗余,这正是进行压缩编码的前提。这正是进行压缩编码的前提。 H是考虑全部信源统计特性后的最小信息熵，是信道传送理是考虑全部信源统计特性后的最小信息熵，是信道传送理论上的最佳值，只要在信道传送论上的最佳值，只要在信道传送H，在接收端利用信源统计，在接收端利用信源统计关联的记忆特性，可恢复出全部信息关联的记忆特性，可恢复出全部信息2

22、1020()()()()logHXHXHXHXN0()HX0()HX信源的冗余度信源的冗余度E E 1 1减去相对熵。减去相对熵。 相对熵相对熵 信源的实际信息熵与具有同样符信源的实际信息熵与具有同样符号集的最大熵的比值。号集的最大熵的比值。 max0()()=()()H XHXHXHXmax0()()111()()HXH XEHXHX 冗余度信源最大可能熵与实际熵的差定义为内熵：信源最大可能熵与实际熵的差定义为内熵：内熵内熵max()()HXH X或或0()()HXHX英语的熵率英语的熵率 英语是稳恒的各态历经信源吗？u这个很难无法回答，但是我们仍可以从统计角度上对英语语言进行分析u假定源消

23、息含有26个字母和1个空格，忽略标点符号和大小写字母出现的概率是不同的，E最大（13%），Q和Z最小（大约0.1%）u两个字母的组合也是非等概的，TH出现最频繁（3.7%）u由此，我们可以构建高阶的概率转移模型，但是实际上这是不可行的。英语的熵率英语的熵率0().()HXHX冗余度冗余度0.7，说明压缩编码的必要。，说明压缩编码的必要。几种语言的熵率几种语言的熵率u 信源符号间依赖关系越大，信源冗余度越大，信源符号间依赖关系越大，信源冗余度越大， 信息论研究目信息论研究目的提高信息传输的的提高信息传输的有效性、可靠性、保密性有效性、可靠性、保密性。u 从提高信源输出有效性的观点出发，希望从提高

24、信源输出有效性的观点出发，希望减少或去掉冗余度减少或去掉冗余度。u冗余度大的信源冗余度大的信源具有较强的抗干扰能力具有较强的抗干扰能力，当干扰使信息在传，当干扰使信息在传输过程中出现错误时，可从它的上下关联中纠正错误，因此输过程中出现错误时，可从它的上下关联中纠正错误，因此从提高信息传输可靠性观点出发，总是希望从提高信息传输可靠性观点出发，总是希望增加信源冗余度增加信源冗余度。u信源编码信源编码就是通过减少或消除信源冗余度来提高通信的传输就是通过减少或消除信源冗余度来提高通信的传输效率，效率，即提高通信的有效性即提高通信的有效性。 信道编码信道编码则是通过增加信源的则是通过增加信源的冗余度来提

25、高通信的抗干扰能力，冗余度来提高通信的抗干扰能力，即提高通信的可靠性即提高通信的可靠性。 总结总结3.3 无失真信源编码无失真信源编码离散、无失真、无记忆信源编码的一般模型：离散、无失真、无记忆信源编码的一般模型： LKLKnrnr失真：有效：编码的原则编码的原则Ui有n种取值Ck有r种取值互相矛盾！互相矛盾！KLrn无失真：无失真：则有：则有：loglogKnLr若消息种类数若消息种类数=码的种类数，即码的种类数，即n=r，则必有，则必有LK ，不满足有效性，不满足有效性如如K=L，则，则r 也不满足有效性。也不满足有效性。所以要想同时满足无失真和有效性，必须从信源统计特性想办法。所以要想同

26、时满足无失真和有效性，必须从信源统计特性想办法。loglogKnLr式子左边表示码长与消息长度之比，而右边表示等概率条件下式子左边表示码长与消息长度之比，而右边表示等概率条件下（不考虑统计特性）的消息熵（不考虑统计特性）的消息熵 与码字熵与码字熵 之比。之比。nUHlog)( )logHr代入上式：代入上式：()logKLr 即使即使n=r，只要满足，只要满足log( )rH U就有可能实现就有可能实现LK 即有可能同时满足即有可能同时满足无失真和有效两个无失真和有效两个目标。目标。 可以采用码长不变的等长码来实现，也可以更加灵活的采用可以采用码长不变的等长码来实现，也可以更加灵活的采用码长变

27、化的变长码来实现。码长变化的变长码来实现。()logKLr K平均码长平均码长信源编码的机理：信源编码的机理：AEP是什么导致我们研究渐进等同分割性质？ 回想：最大离散熵原理 定理：等概分布时，离散熵最大化 但是：信源输出的一般不是等概分布的 问题：如何将非等概输出的信源变成等概？渐进等同分割性质信源输出序列信源输出序列将序列进行分割古典概率理论中大数定律的回顾古典概率理论中大数定律的回顾渐进等同分割性质的评述u渐进等同分割性质：Asymptotic Equipartition Propertyu差不多所有的事件都是等概出现的：Almost all events are almost equa

28、lly surprisingu可以简单地由大数定理推出u对于数据压缩的贡献：等同分割等概率最大离散熵定长编码定理揭示了一种定长编码的方法渐进等同分割性质定理：如果X1,X2，是独立同分布的离散随机变量,分布服从p(x)，则等价表述：设离散无记忆稳恒信源输出的一个特定序列X=x1x2xn。则任给 和 ，可以找到一个整数N0，使当 有0nN典型序列典型序列典型序列集合典型序列集合典型序列的性质物理解释定长编码定理问题的提出： 设X1,X2,Xn.是服从分布p(x)的离散无记忆信源的输出序列 我们的目标是寻找尽量短的编码方案，来描述这一随机序列直观的分析： p(x)一般不是均匀分布，因此，针对每一个

29、字母的定长码不合算 AEP告诉我们，若分割的段足够长，各段分布呈现等概趋势直观的解决： 利用典型序列集合的性质来进行编码典型序列示例：偏畸硬币抛掷典型序列示例：偏畸硬币抛掷对离散，无记忆、平稳信源对离散，无记忆、平稳信源U的的L长符号序列，进行长符号序列，进行r元符号元符号的定长编码，的定长编码，L长符号序列对应的码长为长符号序列对应的码长为K，若对任意，若对任意0,0，只要满足：，只要满足： 则当则当L足够大时，可使译码差错小于足够大时，可使译码差错小于，反之，当反之，当 时，就不可能做到无失真编码，当时，就不可能做到无失真编码，当L足够大时，可使译码差足够大时，可使译码差错趋于错趋于1。

30、2( ) logKH ULr2()2logKH ULr3.3.1定长编码定理定长编码定理2(/)log( ) KLrH U2log( ) KrLH U左边是左边是K长码字所能携带的最大信息量，右边是长为长码字所能携带的最大信息量，右边是长为L的信源序列的信源序列所携带的信息量。所携带的信息量。只要码字所携带的信息量大于信源序列输出的信息量，则可以使只要码字所携带的信息量大于信源序列输出的信息量，则可以使传输传输几乎无失真几乎无失真，条件是，条件是L足够大。足够大。说明：说明：2(/)log r( ) KLH U2(/)log( ) KLH Ur没有一种编码器实现无失真译码没有一种编码器实现无失

31、真译码临界，可能失真也可能无失真临界，可能失真也可能无失真几个概念：几个概念：1个信源符号所携带的码元平均信息个信源符号所携带的码元平均信息2logKrL比特比特/符号符号2logKrK个码元的信息量个码元的信息量比特比特/K个码元个码元码字平均长度码字平均长度码元码元/序列序列()iiKPKKKL码元码元/符号符号每个符号的平均码长每个符号的平均码长L=1,LKK 等长编码的时候，等长编码的时候，KK2( )logcH UKr编码效率编码效率( )H URK若信源的熵若信源的熵H(U)给定，编码后每个信源符号平均用给定，编码后每个信源符号平均用 个码元个码元来变换，那么平均每个码元携带的来变

32、换，那么平均每个码元携带的 信息量可以定义为编码后的信息量可以定义为编码后的 信息传输率信息传输率K比特比特/码元码元例例1：设有一简单：设有一简单DMS信源：信源：123456723456611111112222222uuuuuuuUp用码元表用码元表X0,1对对U的单个符号进行编码的单个符号进行编码(L=1)，即对，即对U的单个符号进行的单个符号进行2进制编码。进制编码。解：用解：用X的两个码元对的两个码元对U的的7个符号进行编码，单个符号进行编码，单个对应的定长码长：个对应的定长码长：loglog72.8/loglog2LKqKLr码元 符号信源信源U的熵为：的熵为：取取l=3，码长为，

33、码长为3的二进制码字有的二进制码字有8个，取其中任意个，取其中任意7个码个码字分别赋给字分别赋给7个信源符号即可，如：个信源符号即可，如：1234567: 001 010 011 100 101 110 111UuuuuuuuW7163( )( )log( )/32iiiH UP uP ubit 符3/63()3265.625%3 log2logLcKKH UKr码元 符号平均码长和编码效率为：平均码长和编码效率为：显然编码效率不高，可对显然编码效率不高，可对U的的符号序列符号序列进行编码，同时引入进行编码，同时引入一定的失真，由于定长编码定理限定了定长编码码长的最小一定的失真，由于定长编码定

34、理限定了定长编码码长的最小值，因此值，因此最佳的定长编码效率最佳的定长编码效率：( )( )( )( )loglogcLH UH UH UH UKrKrL下面分析一下等长编码的编码过程：下面分析一下等长编码的编码过程：例如，某信源有例如，某信源有8种符号，每种符号的输出概率分别为种符号，每种符号的输出概率分别为0.4, 0.18, 0.1, 0.1, 0.07, 0.06, 0.05, 0.04, L=1，用二元定长码进行，用二元定长码进行编码。编码。1()2.55/H Ubit符号分析：分析：如果用如果用来编码，则只能编来编码，则只能编种符号，种符号，还有部分符号没有对应的码字。还有部分符号

35、没有对应的码字。856. 5255. 2bit55. 2)(1UHK信源一旦出现这些符号，就只能用其他码字代替编码，因而信源一旦出现这些符号，就只能用其他码字代替编码，因而引起差错。差错发生的可能性取决于这些符号出现的概率。引起差错。差错发生的可能性取决于这些符号出现的概率。当当L足够大时，有些符号发生的概率变得很小，使得差错概率足够大时，有些符号发生的概率变得很小，使得差错概率达到足够小。达到足够小。当采用定长编码时，如果允许一定的差错，则无需对全部组合当采用定长编码时，如果允许一定的差错，则无需对全部组合的的nL种信息一一编码，而仅需对其中少数大概率事件集合中的种信息一一编码，而仅需对其中

36、少数大概率事件集合中的元素进行编码即可。元素进行编码即可。 任何一个离散随机序列信源，可以分成大概率事件集合任何一个离散随机序列信源，可以分成大概率事件集合A 与小概与小概率事件集合率事件集合 ,即即 ，集，集A 中的元素有对应的输出码中的元素有对应的输出码字，而字，而 中的元素没有对应的码字，因而会在译码时发生差错。中的元素没有对应的码字，因而会在译码时发生差错。ALnAAA如果允许一定的差错如果允许一定的差错，则，则 编码时只需要对属于集合编码时只需要对属于集合 A 中的中的 个样本赋以不同的码字，即输出码字的总个数个样本赋以不同的码字，即输出码字的总个数 大于大于 r在这种编码方式下，差

37、错概率在这种编码方式下，差错概率 即为集合即为集合 中元素发中元素发生的概率，此时要求生的概率，此时要求A)(Ap()pA 可以证明，差错率满足如下关系可以证明，差错率满足如下关系当当2 和和均为定值时，只要均为定值时，只要L足够大，差错概率可以小于任一正足够大，差错概率可以小于任一正数数，即当信源序列长度即当信源序列长度L满足下式时，能达到差错要求满足下式时，能达到差错要求。 22UL 22UL22222221( )( )( )()( )() log()( )eqiiiiUPLUUEI uH UP uP uH U其中为信源自信息量的方差：在给定在给定和和后，用下式规定了后，用下式规定了L的大

38、小。的大小。1Ap这些在这些在A中的元素分别用不同码字来代表，就完成了编码过程。中的元素分别用不同码字来代表，就完成了编码过程。计算所有可能的信源序列样本矢量的概率，按概率大小排列，计算所有可能的信源序列样本矢量的概率，按概率大小排列，选用概率较大的作为选用概率较大的作为A中的元素，直到中的元素，直到定长编码过程：定长编码过程：22UL 2222( )( )( )( )(1)cccUH ULH UH U例：设有一简单离散信源：例：设有一简单离散信源：L=1,n=4123411112488uuuuUp对其进行近似于无失真的等长编码，若要求其编码效率对其进行近似于无失真的等长编码，若要求其编码效率

39、为为95%，差错率低于，差错率低于10- -6，试求符号联合编码长度，试求符号联合编码长度L=？ 解：解： , 2=0.6875 bit2由编码效率：由编码效率：即：即： 41( )log1.75iiiH Uppbit %95)()(UHUH092.095.095.075.175.1可见可见,需要需要100万个信源符号联合编码万个信源符号联合编码,才能达到上述要求才能达到上述要求,这显然这显然是不现实的是不现实的.定长编码既要实现几乎无失真，并且也要有较高的编码效率是定长编码既要实现几乎无失真，并且也要有较高的编码效率是不能同时满足的，必须考虑变长编码。不能同时满足的，必须考虑变长编码。再由再

40、由:2262262 0.68750.813 10(0.092)10eePLLP3.3.2 变长编码定理变长编码定理根据信源各符号的统计特性，对概率大的符号用短码，对概率根据信源各符号的统计特性，对概率大的符号用短码，对概率小的用较长的码进行信源编码。小的用较长的码进行信源编码。【无失真变长编码定理无失真变长编码定理】用用r r 元符号表对元符号表对DMSDMS信源信源U U 的的L L长符号序列进行变长编码，要做到无失真编码，长符号序列进行变长编码，要做到无失真编码，平均码长必须满足：平均码长必须满足：LrKHUL另一方面，一定存在唯一可译码，其平均码长满足：另一方面，一定存在唯一可译码，其平

41、均码长满足：1LrKHULL证明证明: ()log0LLHUKr（1）先证明平均码长的下界，只须证明）先证明平均码长的下界，只须证明 信源U发出的任一L长符号序列都是其L次扩展信源UL的一个符号，L次扩展信源UL概率空间： UL, P=aj, P(aj) | j=1,2,.,qL 信源无记忆，所以Hr(UL)=LHr(U)。1111111()log()log()log()1()lnln2()1()(1)(ln1)ln2()()ln21 10()ln2LLLjLjLLjqqLLjjjjjjKqjjjKqjjjqqKjjjH UKrP aP aKrP arP aP arP azzP arP aKr

42、aft不等式和概率完备性质（2）根据信源的自信息量来选取与之对应的码长：）根据信源的自信息量来选取与之对应的码长：11loglog1,1,2,.,()()LrjrjjKjqP aP a即码长取大于等于自信息量的最小整数。即码长取大于等于自信息量的最小整数。11111log,1,2,.,()()() 1K1log1,1,2,.,()1()()(log1)( ) 1()1( )jLLjLLLrjjKjqqKjj=jLjrjqqLjjjrrj=j=jLrKjqP arP arP araftKjqP aKP aKP aLH UP aKH ULL根据可得所以，实际就是不等式，这样选取码长保证了唯一可译码

43、存在性。根据可得即（1）信源无失真变长编码定理又称信源无失真变长编码定理又称香农第一定理香农第一定理。（2） 是信息论的重要定理，给出了信源有效编码的是信息论的重要定理，给出了信源有效编码的界限。界限。如果信源单个符号对应的平均码长如果信源单个符号对应的平均码长 小于信源的熵小于信源的熵Hr(U)，编码就会失真；如果满足编码就会失真；如果满足 就一定能找到无失真编码。就一定能找到无失真编码。/LKKL/( ) 1/LrKKLH UL说明说明: (1) 用变长编码来达到相当高的编码效率，一用变长编码来达到相当高的编码效率，一般所要求的符号长度般所要求的符号长度L可以比定长编码小得多。可以比定长编

44、码小得多。可得编码效率的下界：可得编码效率的下界： 2()()log()cH XH XrKH XL(2) 例例 用二进制，用二进制，r2，log2r=l，H（X）2.55比比特符号，若要求特符号，若要求 ，则，则 %90c428. 0/ 1, 9 . 0/ 155. 255. 2LL(3) 码的剩余度码的剩余度 为为iiLKXPK)()11LHXK 码的剩余度码的剩余度 用来衡量各种编码方法与最佳码的差距用来衡量各种编码方法与最佳码的差距. （4）编码后码字的平均码长：（对长度为编码后码字的平均码长：（对长度为L的符号序列编码）的符号序列编码）LKKL单个符号的平均码长单个符号的平均码长符号序

45、列的平均码长符号序列的平均码长P（Xi): 符号序列的概率符号序列的概率例：例：设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为 4/14/321xxPX解解:其信源熵为其信源熵为 81. 034log434log41)(22XH比特比特/符号符号 求求:定长编码和变长编码的编码效率定长编码和变长编码的编码效率?(1)定长编码定长编码 若用二元定长编码（若用二元定长编码（0，1）来构造一个）来构造一个 即时码：即时码：这时平均码长为这时平均码长为 =1 码元码元/符号符号编码效率为编码效率为(对于无记忆信源而言对于无记忆信源而言,有有HL(X)=H(X) ) 输出的信息率为输出的信息率

46、为 1, 021xxK2()100%81.1%log2HXKLKK 2log81. 02L=1,().H XRK比特比特/码元码元(2)变长编码变长编码 假定信源序列的长度为假定信源序列的长度为L=1,也用二元编码，其即时码如下表也用二元编码，其即时码如下表所示。所示。 符号符号概率即时码 x13/4 0 x2 101/4这个码的码字平均长度这个码的码字平均长度 单个符号的平均码长单个符号的平均码长 编码效率编码效率 输出的信息率为输出的信息率为 R106488 比特码元比特码元 12.K 0.811100%4.88%1.25.KK 码元/符号码元/符号假定信源序列的长度为假定信源序列的长度为

47、L=2,也用二元编码，其即时码如下表所也用二元编码，其即时码如下表所示。示。 序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 10这个码的码字平均长度这个码的码字平均长度 单个符号的平均码长单个符号的平均码长 编码效率编码效率 输出的信息率为输出的信息率为 R20961 比特码元符号比特码元符号 信源序列二元码符号/162731613163216311692K%1 .96%10027811. 0322符号码元符号/322722KK将信源序列的长度增加，将信源序列的长度增加，L3或或L=4，对这些信源序列，对这些信源序列X进

48、行编进行编码码，并求出其编码效率为并求出其编码效率为 %1.99%5.9843信息传输率分别为：信息传输率分别为： R30985比特码元符号比特码元符号 R40991比特码元符号比特码元符号如果对这一信源采用定长二元码编码，要求编码效率达到如果对这一信源采用定长二元码编码，要求编码效率达到96时，时，允许译码错误概率允许译码错误概率 。则自信息的方差。则自信息的方差 所需要的信源序列长度所需要的信源序列长度 510212224715. 0)()(log)(iiiXHppX752221013. 41004. 0)96. 0()811. 0(4715. 0L(1)最佳码定义是什么最佳码定义是什么?

49、 凡是能载荷一定的信息量，且码字的平均长度最短，可分凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。离的变长码的码字集合都可称为最佳码。 (2)最佳编码思想是什么最佳编码思想是什么? 将概率大的信息符号编以短的码字，概率小的符号编以长将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。的码字，使得平均码字长度最短。 (3)最佳码的编码主要方法有哪些最佳码的编码主要方法有哪些? 香农（香农（ Shannon-Fano-Elias 码）、费诺（码）、费诺（Fano）、霍夫曼）、霍夫曼（Huffman）编码等。）编码等。 3.5 变长

50、编码方法变长编码方法1. Huffman1. Huffman编码编码（一）二进制的（一）二进制的HuffmanHuffman编码编码 把信源发出的把信源发出的n n个消息按其概率递减次序排列个消息按其概率递减次序排列 把概率最小的两个消息分别编成把概率最小的两个消息分别编成“1”1”和和“0”0”码元码元( (即把概率较大的消息即把概率较大的消息编为编为“1”1”，概率较小的消息编为，概率较小的消息编为“0”0”；或反之也可；或反之也可),),并对这两个消息求并对这两个消息求概率之和概率之和 把上述的概率和作为一个新消息的概率，再与原来的其他消息按概率递减把上述的概率和作为一个新消息的概率，再

51、与原来的其他消息按概率递减的次序排列的次序排列 重复上述编码步骤与，直到概率和是重复上述编码步骤与，直到概率和是1 1为止为止 从最终的编码步骤，在各个消息编码方向线的逆行程顺序地取下所编出的从最终的编码步骤，在各个消息编码方向线的逆行程顺序地取下所编出的码元，构成相对的代码组码元，构成相对的代码组思想：贪婪算法思想：贪婪算法例：例：0.170.010.200.190.100.150.180.110000001111110.260.350.390.611.01101000010010011011113422433 由上可得代码组的平均长度为：由上可得代码组的平均长度为： 所以，信息传输速率所以

52、，信息传输速率R R为：为： 编码效率编码效率为：为：710.2 20.19 20.18 3 0.17 3 0.15 3 0.1 40.01 42.72iiP 码元码元/符号符号16. 2)(log)()(712iiixPxPXHbit/bit/符号符号()2.160.962.72H XR bit/bit/码元码元%96例：已知信源例：已知信源X X的概率空间，的概率空间， 用用HuffmanHuffman编码方法找出各消息的代码组，并计算编码效率编码方法找出各消息的代码组，并计算编码效率 解解1 1：X X，P( )P( )X1， X2， X3， X4， X50.40.4， 0.10.1，

53、0.20.2， 0.20.2， 0.10.10.10.20.20.10.4x1x3x4x2x5010111001.0101110110000322320.20.40.6 由题意可得：由题意可得：122. 21 . 0log1 . 022 . 0log2 . 024 . 0log4 . 0)(log)()(22251 iiixPxPXHbit/bit/符号符号510.4 20.2 2 20.1 3 22.2iiiP 码元码元/符号符号()2.1220.96452.2H XR bit/bit/码元码元%45.96 解解2 2：0.10.20.20.10.4x1x3x4x2x5010001111.0

54、11010101100111412430.20.40.20.6510.4 1 0.2 20.2 3 0.1 2 42.2iiiP 码元码元/符号符号二、二、m 进制进制HuffmanHuffman编码编码1. 编码步骤编码步骤同二进制，但需注意两点同二进制，但需注意两点 (1) 每次取最小的每次取最小的m个概率个概率,分别赋以分别赋以0,1,m-1； (2) 为使平均码长最短，当对应的码树为非全树时，为使平均码长最短，当对应的码树为非全树时， 第一次采用小于第一次采用小于m个概率个概率，此后每次均用，此后每次均用m个概率个概率2. 非全树时的编码非全树时的编码 (1) 全树全树 码树中码树中,

55、每个中间节点的每个中间节点的后续枝数必为后续枝数必为m (2) 非全树非全树码树中码树中,有些中间节点的后续枝数不足有些中间节点的后续枝数不足m三进制三进制满树满树（等长码）（等长码）三进制全树三进制全树（少一根即（少一根即为非全树）为非全树）(3) m进制的全树的终端节点数进制的全树的终端节点数(即时码个数即时码个数) m + k(m-1), k = 0,1,2,. (每从一个节点分出每从一个节点分出m枝枝, 就增加就增加m-1个终端个终端)(4) 当当 n m+k(m-1)时时, 令令 s = m+k(m-1)-n, s(a吗?这种形式。则Huffman编码无法解决这种问题。而上述的Fan

56、o编码算法正好是一个“分片”算法。2.费诺编码费诺编码(Fano)1)将信源消息符号按其出现的概率大小依次排列为将信源消息符号按其出现的概率大小依次排列为12.nppp2)将依次排列的信源符号按概率值分为两组，使划分后的两个组的概将依次排列的信源符号按概率值分为两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制码元率之和近似相同，并对各组赋予一个二进制码元0和和13)将每一大组的信源符号再分成两组，使划分后的两个组的概率之将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并对各组赋予一个二进制符号和近似相同，并对各组赋予一个二进制符号0和和1。4)如此重复，直至

57、每个组只剩下一个信源符号为止。如此重复，直至每个组只剩下一个信源符号为止。5)信源符号所对应的码字即为费诺码（按顺序）。信源符号所对应的码字即为费诺码（按顺序）。 X X P(X ) P(X )X1, X2, X3, X4, X5, X6, X7, 0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01例：对下列信源进行费诺编码例：对下列信源进行费诺编码xiP(xi)第一次分组第二次分组第三次分组第四次分组二元码字码长KiX10.20 0 0 00 2X20.19 1 0 010 3X30.18 1 011 3X40.17 1 0 10 2X50.15 1 0 110

58、 3X60.10 1 0 1110 4X70.01 1 1111 4 费诺码的平均码长费诺码的平均码长 信息传输速率信息传输速率 编码效率：编码效率： = 95.3% 码元比特/ 953. 074. 261. 2)(KXHR符号码元 / 74. 2)(71iiiKxpK 3.香农编码香农编码 把信源发出的把信源发出的N N个消息按其概率递减的次序排列，得个消息按其概率递减的次序排列，得 根据式根据式 计算第计算第i i个消息的二进制个消息的二进制代码组的长度代码组的长度K Ki( (取正整数取正整数) ) 为了编出单义可译码组，首先计算出第为了编出单义可译码组，首先计算出第i i个消息的累加概率个消息的累加概率 ( (即不包括即不包括 P Pi 本身的前本身的前(i-1)(i-1)个累加概率个累加概率) )，再把，再把 P Pi 变换成二进变换成二进制小数，去除小数点，取小数点后的制小数，去除小数点，取小数点后的 K Ki 位数作为第