信息论第5章 无失真信源编码.pptVIP

第5章 无失真信源编码; ; 信源输出的符号序列,需要变换成适合信道传输的符号序列,一般称为码序列.对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码.完成编码功能的器件称为编码器.接收短有一个译码器完成相反的功能. ;编码：信息的组织方式 编码的实质：对信源的原始符号按一定的数学规则进行变换。 编码的目的： 提高信息传输的有效性（信源编码）； 提高信息传输的可靠性。（信源或信道编码） ;几个术语： 信源符号：信源输入S={s1,s2,…,sq} 码符号 (码元)：X={x1,x2,…,xr} 码字Wi： 由xj (j=1,2,…,r)组成的长度为 li 的序列，Wi与si一一对应。 码字长度 (码长)： Wi的长度li 码 (码书)：码字Wi的集合C={W1,W2,…,Wq} 编码器：将信源符号si变换成Wi的设备;信源编码 信源编码：把信源符号si映射为码字Wi的过程。 无失真编码：映射是一一对应、可逆的。 无失真信源编码：尽可能精确的再现信源的输出 信源编码基本思想：尽可能缩短出现概率大的信源符号的码 ;;8;9;10;11;定长码和变长码;奇异码和非奇异码;N次扩展码;15;16;说明:;5.2 分组码定义：;奇异性;20;唯一可译性;即时性;23;一个码，若其中所有码字均处于终端节点，即端点上，则该码为非续长码。;25;不超过;;28; 该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011　 ;各节点（包括树根）长出的树枝树等于r;31;5.3定长码;若令N＝1，则有;34;35;定理5.3.1;其中前一部分被视为正定理，后一部分被视为逆定理。;38;39;编码效率;41;42;5.4变长码;5.4.1 码的分类和主要编码方法;45;46;47;48;5.4.2 Kraft不等式;注意：仅仅是存在！;51;52;定理5.4.3 若存在一个码长为l1，l2，…，lq的惟一可译码，则一定存在具有相同码长的即时码。 若存在一个码长为l1，l2，…，lq的惟一可译码 满足Kraft不等式（定理5.4.2） 存在具有相同码长的即时码（定理5. 4.1） 任何一个惟一可译码均可用一个即时码来代替，而不改变任一码字的长度。 即时码可用树图法来构造。因此要构造惟一可译码，只需讨论构造即时码。;5.4.3 唯一可译码的判别准则;例：如下图中情况发生，其中Ai，Bi都是码字(Ai,Bi ?C)。 B1一定是A1的前缀，而A1的尾随后缀一定是另一码字B2的前缀，B2的尾随后缀又是其他码字的前缀。最后，码符号序列的尾部一定是一个码字。;判别准则：;57;唯一可译码的判别方法;5.4.4变长编码定理;平均码长;61;对于某一信源和某一码符号集来说，若有一个惟一可译码，其平均长度小于所有其他惟一可译码的平均长度，则该码称为紧致码，或称最佳码 无失真信源编码的基本问题?找出紧致码。;63;64;65;定理4.8（香农信息论的主要定理之一）的结论： 要做到无失真的信源编码，编码每个信源符号平均所需最少的r元码元数为信源的熵Hr(S) 。即Hr(S) 是无失真信源压缩的极限值。 若编码的平均码长小于信源的熵值Hr(S) ，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。 通过对扩展信源进行变长编码，当N ∞时，平均码长 Hr(S) 。;香农第一定理的物理意义 无失真信源编码的实质：对离散信源进行变换 变换后信源符号(信道的输入信源)尽可能为等概率分布 新信源符号平均所含的信息量达到最大à 使信道的信息传输率R达到信道容量C，实现信源与信道理想的统计匹配。 无失真信源编码定理通常又称为无噪信道编码定理。表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息，但要使信道的信息传输率R大于C而无差错地传输信息则是不可能的。;为了衡量各种编码是否达到极限情况;69;70;71;72;73;74;5.4.5 变长码的编码方法;76;77;78;79;80;81;82;83;84;85;86;87;88;89;90;91;92;93