第五章信源编码.ppt

第五章信源编码,通信的实质：信息的传输。信息传输的基本问题：高速度、高质量地传送信息。这就需要解决两个问题：第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息；第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。,一、通信系统的优化模型：,信源编码目的：提高通信系统有效性，实现信源与通信系统间的统计匹配。,信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。,【例3.3】用u1，u2，u3，u4表示信源的四个消息，码符号集为0,1，表3-1列出了该信源的几种不同编码。表3-1同一信源的几种不同编码,码的分类,3.变长码若码字集合C中的所有码字cm(m=1,2,M)，其码长不都相同，称码C为变长码，表3-1中列出的码3、码4就是变长码。,2.等长码在一组码字集合C中的所有码字cm(m=1,2,M)，其码长都相同，则称这组码C为等长码，表3-1中列出的码1、码2就码长n=2等长码。,一般，可以将码简单的分成如下几类：1.二元码若码符号集为0，1，则码字就是二元序列，称为二元码,二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，表3-1列出的4种码都是二元码。,5.非奇异码从信源消息到码字的影射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例表3-1中的码2、码3和码4都是非奇异码。,4.奇异码对奇异码来说，从信源消息到码字的影射不是一一对应的。例表3-1中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。,例：,奇异码,奇异码：若一组码中有相同的码字，则称为奇异码。,非奇异码,01000010,01000010,非奇异码：若一组码中所有码字都不相同，则称为非奇异码。,6）唯一可译码：若码的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。,等长码,非奇异码,00011011,唯一可译,如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码。,7非即时码：,非奇异码,1101001000,10,0,1,不即时,任何一个码字是其它码字的延长或前缀,8.即时码对于变长码，又有如下定义,定义3.2对于码字c=c1c2cn,称c、=c1c2ci(i0，,则香农编码方法如下：,(1)将信源消息符号按其出现的概率大小依次排列：,(2)确定满足下列不等式的整数码长,(3)为了编成唯一可以码，计算第个消息的累加概率,(4)将累加概率变换成二进制数。,(5)取二进制数的小数点后位，即为该消息符号的二进制码字。,可以证明，这样得到的编码一定是唯一可译码，且码长比较短，接近于最佳编码。严格意义上来说不是最佳码。,例题：设信源共有7个符号组成，其概率如表所示，求其香农码。,解：,以为例，,累加概率，变成二进制数，为0.1001，,1码字长度计算,2将pi转换为二进制数的方法,码字为100,可以看出，编码所得的码字是即时码（唯一可译码）。,平均码长为：,编码效率为,香农编码的效率不高，实用意义不大，但对其它编码方法有很好的理论指导意义。,香农编码方法特点：由于bi总是进一取整，香农编码方法不一定是最佳的；由于第一个消息符号的累加概率总是为0，故它对应的码字总是0、00、000、00的式样；码字集合是唯一的，且为即时码；先有码长再有码字；对于一些信源，编码效率不高，冗余度稍大，因此其实用性受到较大限制。,评述,1)将信源符号以概率递减的次序排列起来，将排列好的信源符号分成两组，使每一组的概率之和相接近，并各赋予一个二元码符号“0”或者“1”；2)将每一组的信源符号再分成两组，使每一小组的符号概率之和也接近相等，并又分别赋予一个二元码符号。3)依此下去，直到每一个小组只剩下一个信源符号为止。这样，信源符号所对应的码符号序列则为编得的码字。,2.费诺编码方法,费诺编码也不是最佳编码方法，但有时可以得到最佳编码。,例题：信源符号及其概率仍如香农码中的例题所示。,设信源共有7个符号组成，其概率如表所示，,编码过程及编码结果如下表所示,可以求得，该费诺码的平均码长为,编码效率为,例题：离散无记忆信源及其符号概率分布如下表所示，求其费诺码。,求费诺码的过程,码的平均长度为，信源的熵为是最佳码。原因是概率分布满足一定的条件。,费诺编码特点：概率大，则分解的次数小；概率小,则分解的次数多。这符合最佳编码原则。码字集合是唯一的。分解完了，码字出来了，码长也有了。因此，费诺编码方法又称为子集分解法。费诺编码方法比较适合于每次分组概率都很接近的信源，特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,评述,3.哈夫曼（Huffman）编码方法一种最佳的逐个符号的编码方法。,一)编码步骤如下：,1952年哈夫曼提出了一种构造最佳码的方法。,(1)将q个信源符号按概率分布的大小，以递减次序排列起来，设,(2)用“0”和“1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的符号合并成一个符号，合并的符号概率为两个符号概率之和，从而得到只包含q-1个符号的新信源，称为缩减信源。,(4)依此继续下去，直至信源只剩下两个符号为止。将这最后两个信源符号分别用“0”和“1”表示。,(3)把缩减信源的符号仍旧按概率大小以递减次序排列，再将其概率最小的两个信源符号分别用“0”和“1”表示，并将其合并成一个符号，概率为两符号概率之和，这样又形成了q-2个符号的缩减信源。,(5)然后从最后一级缩减信源开始，向前返回，就得出各信源符号所对应的码符号序列，即对应的码字。,例1：,二）总结编码规则：,1)将信源消息U按概率大小排序（由大至小）。2)从最小两个概率开始编码，并赋予一定规则，如下支路小概率为“1”，上支路大概率为“0”。3)将已编码两支路概率合并，重新排队，编码。4)重复步骤3）直至合并概率归一时为止。5)从概率归一端沿树图路线逆行至对应消息编码。,编码效率为,例2：下表是一个哈夫曼编码的整个过程。,其平均码长为,例3：如下表是又一个哈夫曼编码的过程。,四、注意事项：,原因：1）因为每次对缩减信源中两个概率最小的符号编码的时候，“0”和“1”的安排是任意的。,2）当两个符号的概率相同的时候，排列的次序也是随意的，所以可能导致不同的编码结果，但最后的平均码长一定是一样的。,2、在这种情况下，怎么样来判断一个码的好坏呢？,引进码字长度偏离平均长度的方差，即,方差越小，说明各个码的长度都比较接近平均长度，这样编码器和解码器就可以比较简单，这样的码就认为是好码。,3、结论：在哈夫曼编码的过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽可能处于最高的位置，这样可使合并的元素重复编码次数减少，使短码得到充分利用。,1、哈夫曼编码得到的码不是唯一的:,码符/信符,4、编码不惟一的例子（码字1的编码过程）,码符/信符,（码字2的编码过程）,从表中编码过程可以看出，哈夫曼编码方法得到的码一定是即时码。因为这种编码方法不会使任一码字的前缀为码字。这一点在用码树形式来表示的时候，看得更清楚。下图是用码树形式进行哈夫曼编码的过程，由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀。,另外，由于哈夫曼编码总是把概率大的符号安排在离根节点近的终端节点，所以其码长比较小,因此得到的编码整体平均码长就比较小。,四、结论,(1)哈夫曼编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，且短码得到充分利用。(2)每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同。(3)每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的哈夫曼编码一定是最佳码。缺点：缺乏严格的构造性，无法用确定的数学加以概括,哈夫曼编码具有以下三个特点：,五、r元Huffman码：,例1：,信源符号个数q需满足,信源缩减次数,例2：,增补信源,应用,1、JPEG标准,2、MPEG-4标准,六、下面讨论哈夫曼编码应用中的一些问题：,哈夫曼编码是一种无失真信源最佳编码，但是在实际信道中是有失真的。噪声的引入必然要破坏变长码结构，对于变长码（不加同步），错误不但影响受干扰位，还要进一步扩散。,1)误差扩散：,目前对扩散还没有很有效的方法，工程上克服方法：限制哈夫曼码仅能应用于优质信道（=10-6）以限制扩散的可能性；,由于绝大多数信源是不等概率的，由它编成的码长度与速率是可变的。然而实际信道则要求其输入端速率是固定的。所以信源与信道之间还存在一个速率匹配问题。,2)速率匹配问题：,在工程上解决这一问题的方法是在两者之间加一个类似与水库的缓存器，它变速入，恒速出，以解决两者速率的匹配。,变长码本身就是与信源统计特性相匹配的无失真信源编码，因此信源统计特性的变化对变长码影响很大，它主要体现在下面两点：与信源消息种类多少的关系：一般变长码更适合于大的消息集，而不适合于小且概率分布相差很大的集合。小消息集合只有在很特殊情况下才能实现统计匹配。变长码是在信源概率特性已知情况下，实现统计匹配的。如果信源统计特性不完全知道甚至完全不知道时，如何实现编码，这是属于通用编码所要研究的问题。,3)与信源统计特性相匹配的问题,5、游程编码,游程：在二元序列中，只有“0”和“1”两个码元，我们把连续出现的“0”叫做“0”游程，连续出现的“1”叫做“1”游程。,二元序列0001100111100010-3224311（多元序列）,游程长度：连续出现“0”或者“1”码元的个数叫做游程长度,一个二元序列可以转换