《信息理论基础 第五章 无失真信源编码课件》由会员分享，可在线阅读，更多相关《信息理论基础 第五章 无失真信源编码课件（53页珍藏版）》请在金锄头文库上搜索。
1、第五章 无失真信源编码,本章需要掌握的内容：,编码的目的 离散无记忆信源的定长编码 离散无记忆信源的变长编码定理 变长编码的Huffman编码方法,一.信源编码,第一节 信源编码和码的类型,1.信源编码的概念,编码：将携带信息的一种符号序列按照一定规则映射成另一种符号序列的变换。,信源编码:根据信源的统计特性对信源发出的信息进行编码。,3.编码器的数学模型,其中：,称为码元,或码符号,2.信源编码目的,压缩信源剩余度，提高传输消息的有效性，把消息变成适合信道传输的信号。,Wi称为码字，如果码字由N个码元组成，则码长为N,2.二元码：,3.定长码：,8.非同价码：,信道的基本符号集中码元个数为2
2、 ,每个码元所占的传输时间不完全相同,7.同价码：,每个码元所占的传输时间相同,6.奇异码：,码中码字至少有两个相同,5.非奇异码：,码中所有的码字都不相同,4.变长码：,码中的码字长短不一,码中所有码字的长度都相同,二.码的类型,1.分组码：,将信源符号集中的每个信源组符号映射成一个固定的码字,例5-1：设有二元信道的信源编码器，其概率空间,编码后的结果：,信源符号Si 码1 码2 码3 码4 S1 00 0 0 0 S2 01 01 11 10 S3 10 001 00 00 S4 11 111 11 10,定长码 非奇异码,非奇异码变长码,变长码 奇异码,9.N次扩展码（类似N次扩展信源
3、）,举例：,10.唯一可译码：,每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。,11.即时码：,无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码，又称非延时码。,*唯一可译码要成为即时码的条件： 其中任一码字都不是其他码字的前缀,即时码可用树图构造：,(1)树图的最顶部的节点称为树根，树枝的尽头称为节点; (2)每个节点的分支数等于码元数，且各分支分别对应一个固定的码元，各分支伸出方向所对应的码元是统一的，如图向左伸出为0，向右伸出为1。 (3)各码字分布在码树的终端节点(即不再分支的节点)。 (4)节点一旦被分配码字
4、，后边的枝便去掉，否则为非即时码。,有一离散无记忆信源输出为N长符号序列，信道基本符号r个，信源输出符号个数为q，则存在唯一可译码的充要条件为：,第二节 离散无记忆信源的定长编码,一.离散无记忆信源的唯一可译码存在条件,结论:当码长为l的码元序列的个数不小于信源输出的N长序列的个数时,才存在唯一可译码.,每个信源输出的符号序列经编码后的码字的码长 至少为 ,如果小于 ,则唯一可译码不存在.,平均每个信源符号至少用 个码元来表示,例5-2： 英文电报有32个符号(26个字母加上6个字符),请问对信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？,解： r = 2, q = 32, N =
5、 1，要想有唯一可译码，则,二.定长编码定理,进行长度为 的定长编码，,对,用码元集,设离散无记忆信源,的熵为H(S)，其N次扩展,对于,只要满足,(正定理),则当N足够大时，几乎可实现无失真信源编码，此时译码差错小于。 反之，若,则当N足够大时，译码错误概率趋于1(编码误差任意大),（逆定理）,信源为,解：等概时所需的最少码符号5个，而考虑相关性时需要的最少码符号是1.4个。由此可见后一种的信息传输率高,三. 编码效率,当允许错误概率小于时，信源符号序列的长度N：,为自信息的方差,如果为最佳编码，则,一.变长编码的概念 概念：通过编码后的代码组中的每个码字的码长不尽相等。 要实现无失真信源编
6、码，变长码必须是唯一可译码,第三节 离散无记忆信源的变长编码,提问：信源符号数和码字长度之间应该满足什么条件才能构成唯一可译码呢和即时码？,要想即时译码，唯一可译码必须是即时码,二.克拉夫特不等式和麦克米伦不等式,1.Kraft不等式,2.McMillan不等式,在满足kraft不等式的条件下，唯一可译码存在的充要条件是：,设S0为原始码字的集合。再构造一系列集合S1,S2,Sn。 构造S1,S2, Sn的方法： 1、首先考察S0中所有的码字。若码字Wj是码字Wi的前缀，即Wi = WjA，则将后缀A列为S1中的元素，S1就是由所有具有这种性质的A构成的集合。 2、当n1，则将S0于Sn-1比
7、较，看是否S0中的码字是Sn-1的前缀，如果是，则取后缀为Sn中元素，且看Sn-1中码字是否为S0中码字的前缀，如果是，则取后缀为Sn中元素，如此构成集合Sn。,三.唯一可译码判断准则,准则：一种码为唯一可译码的充要条件是S1,S2,中没有一个含有S0中的码字。,1.平均码长,四.变长编码定理,表示编码时，平均每个信源符号需用的码元个数。,提问: 平均每个码元载荷的信息量(码率)与信道的信息传输率R有什么关系?,平均每个码元载荷的信息量 = 信道的信息传输率R,信源编码目的： 提高信道信息传输率R，充分利用信道,信道的信息传输率R,= 信道中平均每个符号所能传送的信息量,2.最佳码,对于某一信
8、源和某一码元集，若有一种唯一可译码，其平均长度 小于所有其他的唯一可译码，则称此码为最佳码(紧致码)。,请问:从提高无失真信源编码的有效性角度出发，当然希望平均码长越小越好，但是是否可以无限地小？有没有限度？,则总可以找到一种编码方法构成唯一可译码，使信源S中的每个信源符号所需的码字与平均长度满足,3.变长无失真信源编码定理(香农第一定理),其中， 为 中每个信源符号序列 编码所对应的码字的平均码长。,对离散信源进行适当变换，使变化后的码符号信源(作为信道的输入信源)尽可能等概分布，使每个码符号平均含的信息量最大，从而使信道的信息传输率R达到信道容量C，实现信源与信道的统计匹配。 香农第一定理
9、是香农信息论的主要定理之一： 若信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在信道上能够无差错地以最大信息率C传输信息。要使信息传输率R大于C而无差错地传输信息量是不可能的。,无失真信源编码的实质是：,4.编码效率和码的剩余度,码的剩余度 =1-,编码效率: 衡量各种码的优劣 码的剩余度: 衡量编码与最佳码的差距,第四节 变长编码的编码方法,一.莫尔斯(Morse)编码,二.香农编码 1.具体步骤: 将信源发出的q个消息符号按其概率的逆减次序排列,计算第i个消息的二进制码字的码长li,并取整,为了编成唯一可译码，首先计算第i个消息的累加概率,根据码长li, 对的结果取小数
10、点后li位数作为第i个消息的码字,将累加概率Pi变成二进制数,利用,例5-7： 消息序号Si 概率p(Si) logp(Si) 码长Li 累加概率pi 二进制码 S1 0.40 1.32 2 0 00 S2 0.30 1.74 2 0.40 01 S3 0.20 2.32 3 0.70 101 S4 0.10 3.32 4 0.90 1110,用0，1码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源S1,称为缩减信号源。,三.二元Huffman编码,1.编码步骤,将信源发出的q个信源按其概率依次从大到小排列,把缩减信源S1的符号按
11、概率从大到小排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0和1码元表示，这样形成q-2个符号的新信源S2。,依此类推，直至信源只剩两个符号为止，并分别用“0”和“1”表示。,从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即相应码字。,例5-8,信源符号Si 概率p(Si) 编码过程 码字Wi 码长li S1 S2 S3 S1 0.4 S2 0.2 S3 0.2 S4 0.1 S5 0.1,0.40.2,0.40.6,编码过程：,1 01 2 000 3 0010 4 0011 4,用树图检验是否为即时码,(1)每次对信号缩减时，赋予最后两个概率最小的符号 用
12、“0”和“1”是可任意的。 (2)对信源进行缩减时两个概率最小的符号合并后的概率与其他符号概率相同时，可任意排序。,经哈夫曼编码方法得到的码并非是唯一的,造成非唯一的原因：,例题5-8：,由此可见：,结论：当进行哈夫曼编码时，为了得到质量好的码，应使合并的信源符号位于缩减信源序列尽可能高的位置，这样可充分利用短码。,r元哈夫曼码可由二元哈夫曼码的编码方法推广得到。只是编码过程中构成缩减信源时，每次将r个概率最小的符号合并，并分别用0，1，r-1码元表示。 为了充分利用短码，使哈夫曼码的平均码长最短，必须是最后一个缩减信源有r个信源符号。因此，对于r元哈夫曼码，信源S的符号个数q必须满足,如果信
13、源S的符号个数q不满足上式，则增补一些概率为0的信源符号。,四.r元哈夫曼码,例5-9：有一离散无记忆信源,码元集X=(0,1,2)，对S进行3元哈夫曼编码。,解：,信源符号 概率 编码过程 码字Wi 码长li Si p(Si) S1 S2 Wi li S1 0.4 0.4 0.4 0 1 S2 0.3 0.3 0.3 2 1 S3 0.2 0.2 0.3 10 2 S4 0.05 0.05 12 2 S5 0.025 0.05 110 3 S6 0.025 111 3 S7 0 112 3,2,1,0,2,1,0,2,1,0,例5-10：某气象员报告气象状态，有四种可能的消息：晴、云、雨和雾
14、。若每个消息是等概率分布的，那么发送每个消息最少所需的二元脉冲数是多少？又若四个消息出现的概率分别为1/4、1/8、1/8和1/2，问在此情况下消息所需的二元脉冲数是多少？如何编码？,编码： 信源消息 编码过程 码字 码长 雾 1/2 1/2 1/2 0 1 晴 1/4 1/4 1/2 10 2 云 1/8 1/4 110 3 雨 1/8 111 3,平均码长：,例5-11：若有一信源： 每秒钟发出2.66个信源符号，将此信源的输出符号送入某一个二元信道中进行传输（假设信道是无噪无损的），而信道每秒钟只传递2个二元符号。试问信源不通过编码能否直接与信道连接？若通过适当编码能否在此信道中进行无失
15、真传输？若能连接，试说明如何编码并说明原因。,每秒发2.66个信源符号，所以信源输出的信息速率为： Rt=2.66*H(S)=1.924比特/秒 该信道是二元无噪无损信道，所以此信道的最大信息传输率（信道容量） C=1比特/符号 信道每秒只传送2个二元符号，所以信道的最大信息传输速率： Ct=2*C=2比特/秒 RtCt 根据无失真信源编码定理，因为RtCt，则总能对信源的输出进行适当的编码，使此信源能在这个信道中进行无失真传输。,（2）信源熵：H（S）=0.722比特/符号,解：（1）如果对信源不进行编码，直接将信源符号s1以“0”符号传送，s2以“1”符号传送，这时因为信源输出2.66（二元信源符号/秒），大于2（二元信道符号/秒），就会使信道输入端造成信源符号的堆积，信息不能按时发送过去，所以，不通过编码这个信源不能直接与信道连接。
