信息论编码作业

信息论编码一．信息论的认识1.消息是信息的载荷者。信息是抽象的，消息是具体的。要研究信息，还得从研究消息入手。2.由于信源发送什么消息预先是不可知的，只能用概率空间来描述信源3.单符号信源：输出是单个符号（代码）的消息离散信源连续信源4.平稳随机序列信源：信源输出的消息由一系列符号序列所组成，可用N维随机矢量X＝(X1,X2,…,XN)描述，且随机矢量X的各维概率分布都与时间起点无关----平稳！离散平稳信源连续平稳信源无记忆（独立）离散平稳信源有记忆信源m阶马尔可夫信源5.随机波形信源信息是信息论中最基本、最重要的概念，既抽象又复杂信息在日常生活中被认为是“消息”、“知识”、“情报”等“信息”不同于消息（在现代信息论形成之前，信息一直被看作是通信中消息的同义词，没有严格的数学含义），消息是表现形式，信息是实质；“信息”不同于情报，情报的含义比“信息”窄的多，一般只限于特殊的领域，是一类特殊的信息；信息不同于信号，信号是承载消息的物理量；信息不同于知识，知识是人们根据某种目的,从自然界收集得来的数据中整理、概括、提取得到的有价值的信息，是一种高层次的信息。6.互信息量I(xi;yj)：收到消息yj后获得关于xi的信息量信源编码器信道译码器噪声源信宿干扰消息信号信号＋干扰消息)()|(log)|(1log)(1log)/()();(ijijiijixpyxpyxpxpyxIxIyxI即：互信息量表示先验的不确定性减去尚存的不确定性，这就是收信者获得的信息量对于无干扰信道，I(xi;yj)=I(xi)；二．我们学到了1.离散信源熵和互信息定义具有概率为p（xi）的符号xi的自信息量为I(xi)=-logp（xi）信源输出的整体特征用平均自信息量，表示本身的特征用信源熵。2.信道与信道容量信道分类：根据用户数量可分为单用户信道和多用户信道根据信道输入端和输出端的关系可分为无反馈信道和反馈信道。根据信道参数与时间的关系可分为固定参数信道和时变参数信道。根据信道中所受噪声种类的不同，可分为随即差错信道和突发差错信道。根据输入输出的特点可分为离散信道、连续信道、半离散半连续信道、波形信道等。3.信源编码编码——————码树（1）r进制码树对应r进制编码（2）码序列为树根到每个终端结点的树枝的序号（3）n级终端节点对应一个码字最多有n个码字符号（4）q个终端节点对应q个不同码字一.编码器模型由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。下图为一个编码器模型:4.码树形状：倒立树概念：树枝：码树上的线段结点：树枝的两端点树根N级结点R进制码树终端节点5.编码（1）变长码若一组码中码字的码长各不相同（即码字长度不等），则称为变长码.如表中“编码1”为等长码，“编码2”为变长码。信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p(s2)0101s3p(s3)10001s4p(s4)11101（2）分组码若每个信源符号按照固定的码表映射成一个码字，则称为分组码。否则就是非分组码.如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。下面讨论分组码的一些直观属性。（3）非奇异码和奇异码若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列)，则称为非奇异码。反之，则为奇异码。如表中的“编码2”是奇异码，其他码是非奇异码。（4）惟一可译码若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（或称单义可译码）。否则就称为非惟一可译码或非单义可译码。若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。（5）综上所述，可将码作所示的分类：6.码树如下图–树根码字起点；树枝数码的进制数；–节点码字或码字的一部分；终端节点码字；–阶数码长；非整树变长码；–整树等长码。–变长码往往在码长的平均值不很大时，就可编出效率很高而且无失真的码，其平均码长受香农第一定理所限定，即：–若对信源离散无记忆信源S的N次扩展信源进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：7.编码分类：香浓编码（1）香农第一定理指出，可选择每个码字的长度满足关系式：或：（2）x表示不小于x的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。（3）香农码的编码步骤如下：【1】将个信源符号按概率递减的方式进行排列：【2】按香农不等式计算出每个信源符号的码长；【3】为了编成惟一可译码，计算第i个信源符号的累加概率【4】将累加概率用二进制数表示。【5】取对应二进制数的小数点后位构成该信源符号的二进制码字。rSHNLNrSHNlog)(1log)(信源符号对应的二进制数码字0.2000.0002.3430000.190.20.0011…2.4130010.180.390.0110…2.4830110.170.570.1001…2.5631000.150.740.1011…2.7431010.100.890.1110…3.34411100.010.990.1111110…6.6671111110费诺编码（1）费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现分布形式的条件下，才能达到最佳码的性能。（2）费诺码的编码步骤如下：【1】信源符号以概率递减的次序排列起来；【2】将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”；【3】将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号；【4】依次下去，直至每个小组只剩一个信源符号为止；【5】信源符号所对应的码字即为费诺码。（3）例:将下列消息按二元费诺码方法进行编码。解:其编码过程如下页：码的性能分析：此信源的熵(比特／符号)，而码的平均长度(二元码符号／符号)显然，该码是紧致码，编码效率：–该码之所以能达到最佳，是因为信源符号的概率分布正好满足式，否则，在一般情况下是无法达到编码效率等于“1”的。（4）费诺码具有如下的性质：①费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。②费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。③费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。•r元费诺码前面讨论的费诺码是二元费诺码，对r元费诺码，与二元费诺码编码方法相同，只是每次分组时应将符号分成概率分布接近的r个组。•1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码。•设信源，其对应的概率分布为，则对二元霍夫曼码而言，其编码步骤如下：•1）将q个信源符号按概率递减的方式排列起来；•2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源；•3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源S2；•4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示；•5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。•:对离散无记忆信源哈弗曼编码（1）进行霍夫曼编码。解:编码过程如表所示：【1】将信源符号按概率大小由大至小排序。【2】从概率最小的两个信源符号和开始编码，并按一定的规则赋予码符号，如下面的信源符号（小概率）为“1”，上面的信源符号（大概率）为“0”。若两支路概率相等，仍为下面的信源符号为“1”上面的信源符号为“0”。【3】将已编码两个信源符号概率合并，重新排队，编码。【4】重复步骤3）直至合并概率等于“1.0”为止。【5】从概率等于“1.0”端沿合并路线逆行至对应消息编码.（2）按霍夫曼码的编码方法，可知这种码有如下特征：①它是一种分组码：各个信源符号都被映射成一组固定次序的码符号；②它是一种惟一可解的码：任何码符号序列只能以一种方式译码；③它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接解码出来。（3）霍夫曼码的译码：对接收到的霍夫曼码序列可通过从左到右检查各个符号进行译码。三．总结1.信息通过信道传输到信宿的过程即为通信。要做到既不失真又快速地通信，需要解决两个问题：–在不失真或允许一定失真条件下，如何提高信息传输速度----这是本章要讨论的信源编码问题.–在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大----这是下章要讨论的信道编码问题.2.一般来说，抗干扰能与信息传输率二者相互矛盾。然而编码定理已从理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。3.信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。4.许多信号变换方法都可用于变换编码。需要注意的是数据的压缩并不是在变换步骤取得的，而是在量化变换系数时取得的，因为在实际编码时，对应于方差很小的分量，往往可以不传送，从而使数据得到压缩。对某一个给定的编码应用，如何选择变换取决于可容许的重建误差和计算要求。5.变换具有将信号能量集中于某些系数的能力，不同的变换信号能量集中的能力不同。对常用的变换而言，DCT比DFT和WHT有更强的信息集中能力。从理论上说，KL变换是所有变换中信息集中能力最优的变换，但KLT的变换矩阵与输入数据有关，所以不太实用。实际中用的变换其变换矩阵都与输入数据无关，在这些变换中，非正弦类变换（如WHT)实现起来相对简单，但正弦类变换(如DFT和DCT)更接近KLT的信息集中