北邮通信原理课件-第七章II

1、1第七章 信源和信源编码2什么是信源？n信息的源泉，产生并且发出信息的somethingn产生消息n说话的人、赌徒的色子n信源的共同特征n统计特性：所产生的消息的统计特性n色子的点数的统计特性n信件的文字的统计特性3什么是信息？ n信源给出的sth，称消息消息。信源一般以符号的形式发出具体的消息。n信息信息用来描述消息的共同特征。n信源所发消息的统计特性的某一参量。它不是消息本身，又包含在消息之中。信息f(信源统计特性)4信源类型n离散信源：输出是离散符号。n连续信源：输出是连续信号。n单符号信源n序列信源单消息离散信源单消息连续信源离散符号序列信源离散符号序列信源5单消息信源的描述 iXx

2、10111,2,.,niiiiP xP xP xin ,iX P x 11.iniinXxxxP xP xP xP x010.50.5iXP x ,Xxa bp xp x6序列信源LlXXXX.1 tXitt iX t信源的输出是一个离散符号序列：信源的输出是一个模拟的消息，一个随机过程:连续符号序列信源连续符号序列信源:离散符号序列信源离散符号序列信源:7离散符号序列信源的统计特性1.lLXXXX1. .lLxxxx 12132111|.LLP xP xP xxP xx xP xxx11.LLLmnminaaaXP aP aP aP x1,lLmmmmaxxx信源：L维矢量样本序列无记忆=符

3、号间统计独立： 11. .LlLiiP xxxP x序列信源有记忆：符号之间有相关性8离散有记忆序列信源 n有记忆序列，n前后符号间不满足统计独立的条件。n需要用全部记忆区间内的统计特性描述。n一阶马氏链n序列中任一符号仅与前面一个符号有直接统计关联n一阶马氏信源：n信源的输出为一阶马氏链n推广：序列中K个符号组成消息状态，仅与前一个消息状态有直接的统计关联9n一个消息，包涵的信息量是大还是小？如何判断？n消息的不确定性：n发生概率小的消息：n发生概率大的消息：n结论：概率小的消息，包涵的信息量大信息的度量： 自信息I(x)10 iI P xiP x 0iP x iI P x 1iP x 0i

4、I P x符号出现的概率越小，包含的信息量越大。即的单调减函数是单调递减性：单调递减性：可加性：可加性：两个独立的消息所提供的信息量两个分别提供的信息量的和 1loglogiiiI P xP xP x ixX 对数形式对数形式 iIp xiXx时，包含的信息量：1212P xP xI P xI P x极限：极限：的信息量：三个公理化条件11两个单符号信源： 条件自信息量 & 联合自信息量1loglogiiiI P yP yP y 1|loglog|jijijiI P yxP yxP yx 1|loglog|ijijijI P xyP xyP xy 1loglogijijijI P x

5、yP x yP x y ,XY考虑两个信源：12信源的整体情况考虑信源：猜测信源的输出：X1最琢磨不定，X3最容易判定考虑单个符号：X3中的a1，出现的概率最小，其携带的信息量最大 1120.50.5iXaaP x 2120.30.7iXaaP x 3120.010.99iXaaP x13熵 对数的底2e10熵的单位bitnatdet熵的单位：信源输出的平均信息量C.E.Shannon将其定义为信源的信息熵，简称为熵。 11logloglogniiiiiiH XE I P xEEP xP xP xP x 单符号离散信源：14信息熵的性质 n对称性n非负性n连续性n扩展性n确定性n可加性 122

6、13(,)(,)nnH p ppH pp pp()0H X 15n自信息I(x)：一个消息包涵的信息量，不确定性程度的数学描述，统计量。n信息熵H(X)：信源的特性，信源的全部符号的不确定性程度的数学期望。信息的度量： 自信息I(x)和信息熵H(X)16联合熵1111.ijnmijnmx yx yx yXYP XYP x yP x yP x yXY：二维随机变量logijijI x yp x y ：联合自信息 1111lognmnmijijijijijijH XYp x yI x yp x yp x y ：联合自信息的数学期望 联合熵联合熵17条件熵logijijijH Y xp y xp y

7、 x iXx 11log|log|iiinmijjiijjijiH Y Xp xH Y xP x yP yxEP yxE I P yx 时， 的不确定性：Y定义：18联合熵和条件熵 1loglogniiiiiH YE I P yEP yP yP y 11|log|log|nmjijiijjiijH YXE I P yxEP yxP x yP yx 11|log|log|nmijijijijijH X YE I P xyEP xyP x yP xy 11,loglognmijijijijijH X YE I P x yEP x yP x yP x y 1,2,iXxin 1,2,jYyjm单符号

8、信源：19联合熵和条件熵的性质 ,|H X YH XH YXH YH X Y|H XH X Y |H YH YXShannon不等式等号成立的条件：X和Y独立12121312121,LLLH XXXH XH XXH XXXH XXXX熵函数的链规则 ,H XH YH X Y20证明： ,|H X YH XH YXH YH X Y 11111111111111,loglogloglogloglogloglognmijijijnmijijiijnmnmijiijjiijijnmnmijiijijiijijniiijijiijH X Yp x yp x yp x yp xp y xp x yp xp

9、 x yp y xp x yp xp xp y xp y xp xp xp xp y xp y x 11nminiiiH Xp xH Y xH XH Y X21信源的冗余度n信源输出的符号序列，符号之间有相关性n平稳特性实际信源平稳信源离散信源马尔科夫信源近似近似序列信源的特性：22121limlim,LLLLHXHH XXXLX极限熵12121312121,LLLH XH XXXH XH XXH XXXH XXXX121,LLHXH XXXL121lim,LLLHH XXXXL维符号序列的熵符号序列中，平均一个符号的熵极限熵有人证明L足够大时：23极限熵&最大熵20log 2H X

10、YH X1211112222121112201lim,lim,1lim,0,l g,omLLLLLmLmLLmH XXXXH XXXXH XHXH XXXLNHXX XXH XX XXH X单符号二进制信源：20logH X YH XN单符号N进制信源：序列信源，N进制，极限熵：02logHXN最大熵24信源 效率&相对剩余度HX序列实际传输的信息量，单个符号平均0HX能够传输的最大的信息量，单个符号0HXHX富余的，没有利用的部分0HXHX信源效率011HXRHX 信源相对剩余度25n英语字母英语字母26个个，加上一个，加上一个空格空格，共，共27个符号。个符号。n英语信源的最大熵英

11、语信源的最大熵( (等概率等概率) ) n H0=log227=4.76(比特比特/符号符号)例：英语等概率离散无记忆信源2627个个符号出现的概率统计结果。符号出现的概率统计结果。例：英语不等概-离散无记忆信源 27121log4.03(/)iiiHp ep e 比特 符号AI_NGAE_ITE_NNR_ASAEV_OTE_BAINTHA_HYROO_PORE_SETRYGAIETRWCO_EHDUARU_EUEU_C_FT_NSREM_DIY_EESE_F_O_SRIS_R_UNNASHOR27英语：字母之间的依赖性nTn出现H,R的可能性较大n出现J,K,M,N的可能性极小n不会出现Q,

12、F,X28n英语信源近似看做英语信源近似看做1阶，阶，2阶，阶，阶阶马尔可夫信源，马尔可夫信源，熵为熵为H2=3.32(比特比特/符号符号)H3=3.1(比特比特/符号符号)n英语信源近似成英语信源近似成2阶马尔可夫信源，某个输出：阶马尔可夫信源，某个输出：nIANKS_CAN_OU_ANG_RLER_THTTED_OF_TO_SHOR_OF_TO_HAVEMEM_A_I_MAND_AND_BUT_WHISS_ITABLY_THERVEREERn单词中间的依赖关系单词中间的依赖关系n考虑所有依赖关系，真实英语：考虑所有依赖关系，真实英语：H =1.4比特比特/符号符号把英语看成马尔可夫信源01

13、.41110.714.76HXRHX 29 结论n英语文章，英语文章，71%是由语言结构定好的，只有是由语言结构定好的，只有29%是写文是写文字的人可以自由选择的。字的人可以自由选择的。100页的书，大约只传输页的书，大约只传输29页页就可以了，其余就可以了，其余71页可以压缩掉。页可以压缩掉。信息的冗余度表示信信息的冗余度表示信源可压缩的程度源可压缩的程度。n从提高传输效率的观点出发，总是希望从提高传输效率的观点出发，总是希望减少减少或或去掉去掉冗余冗余度。度。n冗余度大的消息抗干扰能力强。能通过前后字之间的关冗余度大的消息抗干扰能力强。能通过前后字之间的关联纠正错误。联纠正错误。30通信过

14、程中接收机获得的信息量n熵：信源本身统计特性的一个参数。 n接收到的信息量：n信宿对于信源不确定性的减少。 n无干扰，信宿得到的信息量等于信源给出的信息量，即信源的熵。n若信道有干扰，信宿得到的信息量不等于信源给出的信息量。31互信息I(X;Y);I X Y信道YX;|I X YH XH X Y：发送X，通过信道，接收到Y。接收者获得的信息量X的不确定程度收到Y后，X的不确定程度不确定程度的减少，信宿获得的信息量32互信息I(X;Y)的性质;I X Y,H X YH X H Y/H X Y/H YX ;|,I X YH XH X YH YH Y XH XH YH X Y;0I X Y ;I X

15、 YH X ;I X YH Y对称性：非负性：33信源编码n信源编码：用离散序列表示信源n编码序列速率小n无失真/可以容忍的失真-恢复信源的输出符号n两种编码：n无失真n限失真34一些相关的定义n二元码：码符号集为二元码：码符号集为X=0,1，所得码字，所得码字都是一些二元序列。都是一些二元序列。n定长码定长码/等长码：一组码中所有码字的码长等长码：一组码中所有码字的码长都相同，即都相同，即ki=K(i=1,2,n)。n变长码：一组码字中所有码字的码长各不变长码：一组码字中所有码字的码长各不相同，即任意码字由不同长度的码符号序相同，即任意码字由不同长度的码符号序列组成。列组成。35奇异码/非奇

16、异码信源符号奇异码非奇异码A00B1110C0000D1101非奇异码：码字不相同36唯一可译码/即时码信源符号唯一可译/非即时 唯一可译/即时A11B1001C100001D10000001唯一可译码：任意有限长码元序列，唯一分割成码字序列。即时码：无需考虑后续符号，即可译出码字。37信源编码模型信源编码1,.,LXxx1,.,KSss如果信源独立等概：符号x有n种取值符号s有m种取值无失真：KLmn有效性： 尽可能小Km独立等概信源，不能够进行压缩编码等号成立独立等概信源的编码38不等概信源的情况n不等概信源，小概率出现的信源序列，不进行编码。n出现失真n编码压缩可以实现n大概率出现的序列

17、，进行编码n近似无失真编码，视为无失真编码。非典型序列典型序列39典型序列&非典型序列n信源输出：长度为L的离散无记忆序列，每个符号有n个可能取值。n当L足够大时，其中一些序列的集合以趋于1的概率出现，并且这个序列的集合的每个序列具有相同的出现概率，约n称这些序列为典型序列，构成典型序列集合n信源输出序列可以分成两个互补集合： 即： 典型序列集合&非典型序列集合。()2LH X40典型序列&非典型序列 22xL 22ixE I xH XeP可以证明：只要L足够大足够大，为给定任意小的正数小于任意正数则只对典型序列编码只对典型序列编码，忽略非典型序列，引入的译码差错率eP

18、视为：无失真41等长编码定理信源编码1,.,LXxx1,.,KSss符号x有n种取值符号s有m种取值独立等概信源，无失真：KLmnloglogKnLm信源的熵一般情况下，无失真：logH XKLmlogKmH XL42等长编码定理2logKRmLRH X编码器输出的信息率编码器近似无失真的必要条件43变长编码定理logH XKLmlogKmH XLlogKH XmH XL与熵匹配 2logH xLH xRKm信源输出序列的信息量编码输出序列的最大信息量2logKRmL编码器输出的信息率：编码效率： 221loglogH xH xKmLLmL足够大时，可以做到几乎无失真编码44等长编码 1234

19、11112488ixxxxXP x等长编码 00 01 10 11，求信源熵以及编码效率？ 41log1.75/iiiH XP xP xbit symbol 解：解： 21.750.875log2H xLH xRKm45变长编码 123411112488ixxxxXP x变长编码 0 10 110 111 41log1.75/iiiH XP xP xbit symbol 解：解： 21.751log1.75H xLH xRKm 411.75iiiKP xK46树图、非延长特性、异前置特性n树图n非延长特性n异前置特性n码字同步问题47码树图 m元元/m进制树图进制树图n树根：树根：最顶部画一个

20、起始点。最顶部画一个起始点。n树枝：树枝：从根部引出从根部引出m条线段，每条线段都称为树枝。条线段，每条线段都称为树枝。n一级节点：一级节点：自根部起，通过一条树枝到达的节点。一级节点自根部起，通过一条树枝到达的节点。一级节点最多有最多有m个。个。nn级节点：级节点：通过通过n条树枝达到的节点。最多有条树枝达到的节点。最多有mn。n终节点终节点/终端节点：终端节点：下面不再有树枝的节点。下面不再有树枝的节点。n中间节点：中间节点：除了树根和终节点以外的节点。除了树根和终节点以外的节点。n联枝：联枝：串联的树枝。串联的树枝。n满树：满树：在码数图中，在码数图中，当每一个码字的串联枝数都相同时，就

21、是当每一个码字的串联枝数都相同时，就是定长码。此时的码树称为满树。定长码。此时的码树称为满树。 例如：码长为例如：码长为N的满树的终节点个数为的满树的终节点个数为mN，即可表示，即可表示mN个码字。个码字。48n非满树：非满树：有些树枝未用时的码树。有些树枝未用时的码树。 非满树构造的就是变长码。非满树构造的就是变长码。 如果每一个码字都被安排在终节点上，这种码就是异前置码。如果每一个码字都被安排在终节点上，这种码就是异前置码。49树图的特征与编码的对应关系树图的特征与编码的对应关系n树根树根 码字的起点码字的起点n树枝数树枝数 码的进制数码的进制数n节点节点 码字或码字的一部分码字或码字的一

22、部分n终节点终节点/终端节点终端节点 码字（异前置码）码字（异前置码）n节数节数 码长码长n满树满树 等长码等长码n非满树非满树 变长码变长码码树：50非延长特性&异前置特性000111全部码字：0，10，110，111例：01100100011110000111000111码字节点前面的路径里面，没有其他的码字节点非码字节点可以延长树枝；码字节点不能延长树枝异前置特性非延长特性树表示码字码字节点非码字节点树枝/路径树枝/码元关系51Kraft不等式n克拉夫特不等式：克拉夫特不等式：nm元长度为元长度为ki，i=1,2,n的异前置码存在的充要条的异前置码存在的充要条件是件是11niki

23、m52唯一可译码的判断方法n首先观察是否是非奇异码。若是奇异码，首先观察是否是非奇异码。若是奇异码，肯定不是唯一可译码；肯定不是唯一可译码；n其次，计算是否满足其次，计算是否满足Kraft不等式。若不不等式。若不满足一定不是唯一可译码；满足一定不是唯一可译码；n然后将码画成一棵树图，观察是否满足然后将码画成一棵树图，观察是否满足异前置码的树图的构造，若满足则是唯异前置码的树图的构造，若满足则是唯一可译码。一可译码。53Huffman编码n变长编码n概率大短码长 概率小大码长n异前置码 12345670.200.190.180.170.150.100.01iXxxxxxxxP x例：54限失真信源编码n无失真编码不是必须的n语音 图像n无失真编码有时不可实现n连续信号，熵无穷大/无失真编码定理，码长无穷大n限失真编码：n允许一定失真程度，码长小。55失真测度1212rrxxxXp xp xp xP1212ssyyyYp yp yp yP信源：收端：失真度or失真函数：,0,1,2, ;1,2,ijd x yirjs111112122212,ssrrrsd x yd x yd x yd xyd xyd xyDd xyd