《无失真信源编码》PPT课件

《《无失真信源编码》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章无失真信源编码本章需要掌握的内容：编码的目的离散无记忆信源的定长编码离散无记忆信源的变长编码定理变长编码的Huffman编码方法一.信源编码第一节信源编码和码的类型信源编码无失真信源编码限失真信源编码1.信源编码的概念编码：将携带信息的一种符号序列按照一定规则映射成另一种符号序列的变换。信源编码:根据信源的统计特性对信源发出的信息进行编码。3.编码器的数学模型信源编码器信源发出的消息符号集输出的码字集合C（代码组）信道的基本符号集合其中：Wi称为码字，如果码字由N个码元组成，则码长为N。称为码元,或码符号2.信源编码目的压缩信源剩余度，提高传输消息的有效性，

2、把消息变成适合信道传输的信号。2.二元码：3.定长码：8.非同价码：信道的基本符号集中码元个数为2√每个码元所占的传输时间不完全相同7.同价码：每个码元所占的传输时间相同√6.奇异码：码中码字至少有两个相同5.非奇异码：码中所有的码字都不相同√4.变长码：码中的码字长短不一码中所有码字的长度都相同二.码的类型1.分组码：将信源符号集中的每个信源组符号映射成一个固定的码字例5-1：设有二元信道的信源编码器，其概率空间编码后的结果：信源符号Si码1码2码3码4S100000S201011110S3100010000S4111111110定长码非奇异码非奇异码变长码变长

3、码奇异码9.N次扩展码（类似N次扩展信源）举例：10.唯一可译码：一个分组码若对任意有限的整数N,其N次扩展码均为非奇异码，则称为唯一可译码。或每个信源符号序列映射成一个固定的码字，并且代码组中每个码字只能唯一地被译成所对应的信源符号序列。11.即时码：无需考虑后续的码符号即可从码符号序列中译出码字，这样的唯一可译码称为即时码，又称非延时码。*唯一可译码要成为即时码的条件：其中任一码字都不是其他码字的前缀即时码可用树图构造：树根一阶节点二阶节点三阶节点(终端节点)A00011010111001000111110101100011010001(1)树图的最顶部的节点

4、称为树根，树枝的尽头称为节点(2)每个节点的分支数等于码元数，且各分支分别对应一个固定的码元，各分支伸出方向所对应的码元是统一的，如图向左伸出为0，向右伸出为1。(3)各码字分布在码树的终端节点(即不再分支的节点)。(4)节点一旦被分配码字，后边的枝便要去掉，否则成为非即时码。有一离散无记忆信源输出为N长符号序列，信道基本符号r个，信源输出符号个数为q，则存在唯一可译码的充要条件为：第二节离散无记忆信源的定长编码一.离散无记忆信源的唯一可译码存在条件结论:当码长为l的码元序列的个数不小于信源输出的N长序列的个数时,才存在唯一可译码.由表明:对于定长唯一可译码,每个

5、信源输出的符号序列经编码后的码字的码长至少为Nlogq/logr,如果小于Nlogq/logr,则唯一可译码不存在.表示平均每个信源符号至少用logq/logr个码元来表示例5-2：英文电报有32个符号(26个字母加上6个字符),请问对信源符号进行二进制编码，要想有唯一可译码，码长至少为多少？解：r=2,q=32,N=1，要想有唯一可译码，则二、定长编码定理进行长度为的定长编码，对用码元集设离散无记忆信源的熵为H(S)，其N次扩展对于只要满足(正定理)则当N足够大时，几乎可实现无失真信源编码，此时译码差错小于δ。反之，若则当N足够大时，译码错误概率趋于1(编码误差

6、任意大)（逆定理）信源为例5-3：仍以英文电报为例，当认为各符号是等概分布时的熵为，但是考虑相关性后英文信源的极限熵为那么对它们进行定长编码时，各自需要的码长是多少？哪种情况的信息传输率高？解：等概时所需的最少码符号5个，而考虑相关性时需要的最少码符号是2个。后一种的信息传输率高三.编码效率η当允许错误概率小于δ时，信源符号序列的长度N：为自信息的方差如果为最佳编码，则例5-4：设离散无记忆信源求信源序列的长度。对S采取等长二元编码，要求编码效率允许错误概率一.变长编码的概念概念：通过编码后的代码组中的每个码字的码长不尽相等。要实现无失真信源编码，变长码必须是唯一

7、可译码第三节离散无记忆信源的变长编码提问：信源符号数和码字长度之间应该满足什么条件才能构成唯一可译码呢？二.克拉夫特(Kraft)不等式和麦克米伦(McMillan)不等式设信源符号集为其分别对应码长为l1,l2,…lq，则即时码存在的充要条件是：对信源进行编码，相应的码字集为码符号集为1.Kraft不等式：2.McMillan不等式在满足kraft不等式的条件下，唯一可译码存在的充要条件是：设S0为原始码字的集合。再构造一系列集合S1,S2,…Sn。构造S1,S2,…Sn的方法：1、首先考察S0中所有的码字。若码字Wj是码字Wi的前缀，即Wi=WjA，则将后缀A

8、列为S1中