信息论与编码课件第5章

1、信源编码信源编码 5.1 编码的定义5.2 无失真信源编码5.3 限失真信源编码5.4 常用信源编码方法简介23 信源编码： 无失真信源编码第一极限定理 限失真信源编码第三极限定理 信道编码 第二极限定理1）信源编码 在不失真或允许一定失真条件下,如何用尽可能少的符号来传送信源信息,以便2）信道编码 在信道受干扰的情况下如何增加信号的,同时又使得信息传输率最大，提高信息提高信息的准确率的准确率。4信源编码器码表信源信道2、信源编码: 定义：将信源输出符号,经信源编码器后变换成另外的压缩符号,然后将压缩后信息经信道传送给信宿 -作用：信源符号之间存在分布不均匀和相关性, 使得信 源存在冗余度,信

2、源编码的主要作用就是 减少冗余,提高编码效率。 -目地：针对信源输出符号序列的统计特性,寻找 一定的方法把信源输出符号序列变换为的 码字序列。XY5信源符号 信源符号出现概率 码 表（分组码） 码0码1码2码3码4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001-信源每个符号序列xi=x1 x2 xL按照固定的码表映射成一个码字yi叫做分组码，只有分组码才有对应的码表，非分组码没有码表。-若码集为0,1,所得码字为二元序列,称为二元码例,信源符号Xa1,a2,a3,a4,

3、L=1，即每个符号序列长度为1，即为单符号序列，对应不同码字(分组码）如表-等长码：码中所有码字的长度都相同 码0，码1，码2-变长码：码中的码字长短不一 码3，码4-非奇异码：信源符号与码字是一一对应的，码0-奇异码：反之不是一一对应，码1 任意有限长的码元序列,只能被唯一地分割成一个个的码字。 例1：0,10,11是一种唯一可译码。 任意一串有限长码序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都会产生一些非定义的码字。 例2：10,0,0,01,00是一种非唯一可译码。 任意一串有限长码序列,如10000100可被分割成10,0,0,01,00 。也

4、可被分割成10,0,00,10,0 。 奇异码不是唯一可译码8l 非即时码： (延长码) 如果接收端收到一个完整的码字后不能立即译码,还需等下一个码字开始接收后才能判断是否可以译码例：码3是非即时码l 即时码： (非延长码) (异前缀码) 在译码译码时无需参考后续的码符号就能立即作出判断,译成对应的信源符号。 任意一个码字都不是其它码字的前缀部分例：码4是即时码 在延长码中,有的码是唯一可译的,取决于码的总体结构码非分组码 分组码奇异码 非奇异码 非唯一可译码 唯一可译码非即时码 即时码 (非延长码) 106、码树 表示各码字的构成 A0100000000000001111111011111二

5、进制码树2000001111122222三进制码树树根码字的起点 分成r个树枝码的进制数终端节点码字1101中间节点码字的一部分节数码长码4111100010100100017、码字和码数的对应关系 如果有n个信源符号,那么在码树上就要选择n个终端节点,用相应的r元基本符号表示这些码字。（码0）码001001111100100-任一即时码（码4）都可用树图法来表示。该码树从根到终端节点所经路径上每一个中间节点都不为码字,因此满足异前缀条件。11010001001000 码3（非即时码）对应的树如下图: 该码树从根到终端节点所经路径上每一个中间节点皆为码字,因此不满足异前缀条件。 虽然码3不是即

6、时码,但它是唯一可译码。 13 满树： 每个节点上都有r个分枝的树等长码例：二进制码树例：二进制码树 非满树： 每个节点上都不一定有同样的r个分枝的树-变长码例：三进制码树例：三进制码树 用树的概念可导出唯一可译码存在的充分和必要条件,即各码字的长度Ki应符合Kraft不等式m是进制数（分的叉）n是信源符号数（终端节点个数）K为各个码字的长度（树的节数）11niKim 例：设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得： 这样的码字不存在唯一可译码 0001101011011中间节点 如果将各码字长度改成K1=1,K

7、2=2,K3=3,K4=3,则18922222322141iKi122222332141iKi这样的码字就存在唯一可译码 11115 Kraft不等式只是用来说明唯一可译码是否存在,并不能作为唯一可译码的判断依据。即：唯一可译码满足Kraft不等式，但是满足Kraft不等式的不一定是唯一可译码 如码字0，10，010，111虽然满足Kraft不等式,但它不是唯一可译码。1617信源编码器码表信源信道 信源编码器输入的消息序列: 序列长度：序列长度：X=(X1 X2Xl XL), 每个消息取值范围： Xla1,an, 输入的消息总共有nL种可能的组合 输出的码字为: 序列长度：序列长度：Y=(Y

8、1 Y2 Yk YKL ) , 每个码字的取值范围： Ykb1,bm 输出的码字总共有mKL种可能的组合。XYL长序列KL长码字182、实现的信源编码,要求: 能够无失真或无差错地从码字Y恢复信息X,也就是能正确地进行反变换或译码 ; -传送Y时所需要的信息率最小 _logLKKmL即就是找到一种编码方式使得即就是找到一种编码方式使得传送Y时信息率信息率（即码字长度满足的条件）：（即码字长度满足的条件）：最小最小logloglogLLmYKmYKmL为中 每 个 码 字 的 信 息 量为 所 有 码 字的 信 息 量为 平 均 传 送 一 个 信 息 所 需 要 的 信 息 量1、在定长编码中

9、,每个码字长度相等kL=K是定值。无失真要求： -信源符号和码字一一对应的；正变换一一对应 -码字和信源符号也是一一对应的； 逆变换也一 一对应2、无失真的定长码码字长度满足的必要条件： -我们的目的是寻找最小K值。 编码器输入X=(X1 X2Xl XL), Xla1,an, 输入的消息总共有nL种可能的组合 输出的码字Y=(Y1 Y2 Yk YK ) , Ykb1,bm 输出的码字总共有mK种可能的组合。 -若对信源进行定长无失真编码,必须满足(一对多）: nLmK 3、无失真的定长码码字长度满足的必要条件和等价条件：mnLKmnKLloglog或 此时才可能存在定长非奇异码（即无失真的定长

10、码）。 例如英文电报有27个符号,n=27,L=1,m=2(二元编码)527logloglog222mnLK每个英文电报符号至少要用5位二元符号编码，才存在定长奇异码，即27个信息符号需要32个码字4、定长编码定理： 由L个符号组成的、每个符号的熵为HL(X)的无记忆平稳信源符号序列X1XlXL,可用 K个符号Y1YkYK(每个符号有m种可能值)进行定长编码。对任意0,0,只要 则当L足够大时,必可使译码差错小于; 反之,当 时,译码差错一定是有限值,而当L足够大时,译码几乎必定出错 log(X)LKKmHLlog(X)2LKKmHL22当编码器容许的输出信息率,也就是当每个信源符号所必须输出

11、的长度是 时,只要 ,即平均每个码字携带的信息量大于信源符号熵，这种编码器一定可以做到几乎无失真,也就是收端的译码差错概率接近于零,条件是所取的符号数L足够大。_logLKKmL)(_XHKL23将定理的条件改写成其中：左边：KL长码字所能携带的最大信息， 右边：L长信源序列携带的信息量。即所有码字携带的信息量大于信源熵log ( )( )LLKmLHXH X24 上述定理表明:平均每个码字携带的信息量大于信源符号平均每个码字携带的信息量大于信源符号熵熵 ；或者所有码字所能携带的信息；或者所有码字所能携带的信息量大于信源熵量大于信源熵 ,则可以使传输几则可以使传输几乎无失真乎无失真,当然条件是

12、当然条件是L足够大。足够大。反之反之,当当 时时,不可能构成无失真的编码不可能构成无失真的编码,也就是不可能做一种编码器也就是不可能做一种编码器,能使收端译码时能使收端译码时差错概率趋于零。差错概率趋于零。 时时,则为则为临界状态临界状态,可能无失真可能无失真,也可能也可能有失真。有失真。)(_XHKL)(_XHKL_( )LK H Xlog( )LLKm LH X5、编码效率： -为了衡量编码效果(),0LHXK 上式为信源的平均符号熵和采用平均符号码字码长为 的比率，即编码的效率。0,)()(XHXHLLK-最佳编码效果6、定长无失真编码序列长度L： 对定长编码,若要实现几乎无失真编码,则

13、信源序列长度必须满足:22)( XL )()()(22XHxIEXi信源序列的自信息方差差错率 例5-2设离散无记忆信源概率空间04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321aaaaaaaaPX 信源熵： 方差：符号/55. 2)(log)()(bitxpxpXHiii 若取差错率106,编码效率为90%,则L应满足22281282. 7)()(log)(bitXHppXiii76222108 . 91028. 082. 7)(XL 在差错率和编码效率要求并不十分苛刻的条件下,就需要L=108个信源符号进行联合编码,这显然是很难实现的。1、变长

14、编码 在变长编码中码长码长KL是变化的。 我们可根据信源各个符号的统计特性,如概率大的符号用短码,概率小的用较长的码,这样在大量信源符号编成码后平均每个信源符号所需的信息量（输出符号数）就可以降低,从而提高编码效率292、单个符号变长编码定理： 若一离散无记忆信源的符号熵为H(X),每个信源符号用m进制码元进行变长编码,一定存在一种无失真编码方法,其平均码长 满足下列不等式:()()1 loglogLH XH XKmm30LK3、离散平稳无记忆序列变长编码定理 对于平均符号熵为HL(X)的离散平稳无记忆信源,必存在一种无失真编码方法,使平均符号信息率 满足不等式 X)()(LLHKXHK其中其

15、中为任意小正数为任意小正数4、编码效率的下界：( P92公式推导) LmXHXHKXHLLLlog)()()(32总结：总结：用变长编码来达到相当高的编码效率,一般所要求的符号长度L可以比定长编码小得多。 由LmXHXHKXHLLLlog)()()( 若对例5-2用变长码实现, 要求90%,用二进制,m2,log2m=l。得L= 4L155. 255. 29 . 033 例5-3设离散无记忆信源概率空间414321aaPX 信源熵：符号/811. 0)(log)()(bitxpxpXHiii 若用二元定长编码(0,1)来构造一个即时码: a1 0, a2 1 平均码长=平均每个符号码长为：11KK 编码效率为811. 0)(KXHL 输出的信息效率为二元码符号/811. 0bitR 34 再对长度为L =2的信源序列进行变长编码,其即时码如表 平均码长为29331271233(1616161616K 相当于K) 编码效率为961. 0)(2KXHL 输出的信息效率二元码符号/961. 02bitR a