《14九信息论.ppt》由会员分享，可在线阅读，更多相关《14九信息论.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三部分第三部分 信息论信息论第三部分第三部分 信息论信息论信信号号理理论论已已被被证证明明是是有有价价值值的的分分析析工工具具，但但它它不不能能把把握握信息传输的根本过程。信息传输的根本过程。ShannonShannon在在19481948年年的的博博士士论论文文中中提提出出了了全全新新的的理理论论“通通信信的的数数学学理理论论”（信信息息论论），他他将将数数学学与与工工程程紧密的结合在一起。紧密的结合在一起。通通行行过过程程的的中中心心任任务务：给给定定一一个个消消息息源源，其其输输出出不不由由我我们们选选择择，应应该该如如何何表表达达消消息息才才能能使使它它可可靠靠地地通通过过一一个具有
2、内在物理限制地通行信道？个具有内在物理限制地通行信道？12/19/20222第三部分第三部分 信息论信息论信息论的三个基本内容：信息论的三个基本内容：信信息息的的度度量量；信信息息的的信信道道容容量量；为为利利用用信信道道容容量量传传输输信信息所需要的编码。息所需要的编码。相应的基本结论为：相应的基本结论为：如如果果一一个个信信息息源源所所发发出出的的信信息息速速率率不不超超过过信信道道容容量量，则则尽尽管管有有噪噪声声存存在在，我我们们总总可可以以找找到到一一种种编编码码方方法法，使全部信息以任意小的差错频度传过信道。使全部信息以任意小的差错频度传过信道。编码过程有两类：信源编码和信道编码。
3、编码过程有两类：信源编码和信道编码。信源编码信源编码降低信息速率；降低信息速率；信道编码信道编码等效无噪信道。等效无噪信道。12/19/20223第十三章第十三章 信息熵与信源编码信息熵与信源编码13.1 13.1 信息的度量与信息熵信息的度量与信息熵1.1.信息量信息量信息的度量与消息产生的概率有关。信息的度量与消息产生的概率有关。已知任意消息已知任意消息 ，“被选中的概率被选中的概率”则与则与 相关联的信息量定义为：相关联的信息量定义为：通常取通常取 为为2 2，此时，此时 的单位为的单位为bitbit（比特）。比特）。也也就就是是说说，消消息息的的可可能能性性越越小小，它它所所载载有有的
4、的信信息息量量越越大大。即即信信息息的的度度量量必必定定与与消消息息的的不不确确定定性性程程度度有有关关：不不确确定定性性越越高高，信信息息量量越越大大；不不确确定定性性越越低低，信信息息量量越小。越小。12/19/20224第十三章第十三章 信息熵与信源编码信息熵与信源编码信息量信息量 的性质：的性质：1 1）2 2）3 3）2.2.信息熵信息熵给定一个离散无记忆信源，其连续符号之间统计独立。给定一个离散无记忆信源，其连续符号之间统计独立。它它所所发发出出的的符符号号序序列列是是由由 个个不不同同符符号号中中选选出出的的。不不妨妨设设其其为为随随机机变变量量 ，每每个个符符号号以以概概率率
5、出出现现，并并载载有有信信息息量量 ；则则信信源源所所产产生生的的任任意意符符号号所携带的信息量也是一个离散随机变量，其期望为所携带的信息量也是一个离散随机变量，其期望为12/19/20225第十三章第十三章 信息熵与信源编码信息熵与信源编码此此即即为为该该信信源源的的信信息息熵熵，也也就就是是信信源源所所产产生生的的任任意意符符号号的平均信息量。的平均信息量。一一个个给给定定信信源源的的信信息息熵熵 取取决决于于符符号号概概率率 和和字字符符集集的大小的大小 ，有下列结论：，有下列结论：其中下界对应于无确定性的情况，即其中下界对应于无确定性的情况，即 ；上界对应于最不确定的或选择完全自由的情
6、况，即上界对应于最不确定的或选择完全自由的情况，即12/19/20226第十三章第十三章 信息熵与信源编码信息熵与信源编码证明：证明：易证；来证明易证；来证明 。设有设有 ，且，且则有则有因为不等式因为不等式 ，其中等号当且仅当，其中等号当且仅当 时成立。时成立。则有则有所以所以此时取此时取 ，则有，则有12/19/20227第十三章第十三章 信息熵与信源编码信息熵与信源编码所以有所以有即即其中等号当且仅当其中等号当且仅当 时成立。时成立。13.2 13.2 信源编码（熵编码）信源编码（熵编码）设设信信源源可可以以产产生生 种种不不同同符符号号，其其出出现现概率分别为概率分别为 。对对一一固固
7、定定信信源源，各各符符号号可可有有很很多多种种不不同同的的编编码码形形式式，可可以具有固定码长，也可以为非固定码长。以具有固定码长，也可以为非固定码长。12/19/20228第十三章第十三章 信息熵与信源编码信息熵与信源编码例如例如为为了了保保证证信信息息的的不不丢丢失失（或或编编码码的的可可逆逆性性），编编码码必必须须是唯一可解的。如果设是唯一可解的。如果设 分别是分别是所所对对应应的的二二进进制制码码长长，则则此此编编码码方方式式唯唯一一可可解解的的充充要要条条件是件是 克拉夫特不等式克拉夫特不等式下面证明相应结论。下面证明相应结论。12/19/20229第十三章第十三章 信息熵与信源编码
8、信息熵与信源编码证明：不妨设证明：不妨设则有则有 ，则需要证明，则需要证明在此在此,只给出最简单的情形只给出最简单的情形n=2n=2时时(其它类似其它类似),),有有要要使使得得编编码码唯唯一一,则则具具有有 码码长长的的码码字字中中前前 个个码码元元组组成的码字与具有成的码字与具有 码长的码字必须不一样码长的码字必须不一样.此此时时,具具有有 码码长长的的码码字字有有 个个,而而具具有有 码码长长的的码码字字中前中前 个码元状态至少有个码元状态至少有 种种,因此有因此有12/19/202210第十三章第十三章 信息熵与信源编码信息熵与信源编码即即对于任意给定编码方式对于任意给定编码方式(唯一
9、唯一),),可以定义平均码长可以定义平均码长按照按照ShannonShannon的信源编码定理的信源编码定理,有有证明证明:取取 ,其中其中 ;所以所以 .则按照前面的结论有则按照前面的结论有12/19/202211第十三章第十三章 信息熵与信源编码信息熵与信源编码即即又又 ,所以所以 .因因此此,熵熵给给出出了了在在给给定定符符号号下下系系统统所所能能获获得得的的压压缩缩率率下下限限,熵成为评价编码系统好坏的非常方便的指标熵成为评价编码系统好坏的非常方便的指标.问问题题:给给定定一一信信源源,如如何何选选择择编编码码方方式式,才才能能使使得得平平均均码码长尽可能地接近该信源的熵长尽可能地接近
10、该信源的熵?12/19/202212第十三章第十三章 信息熵与信源编码信息熵与信源编码熵编码熵编码基基本本原原则则：经经常常发发生生的的赋赋予予较较短短的的码码字字，不不经经常常发发生生的的赋予较长的码字赋予较长的码字对一组符号进行编码有很多方法，如对一组符号进行编码有很多方法，如信息量信息量编码编码编码编码晴晴阴阴雨雨雪雪平均码长平均码长.熵：熵：最佳编码方式：符号的码长与其信息量有关最佳编码方式：符号的码长与其信息量有关12/19/202213第十三章第十三章 信息熵与信源编码信息熵与信源编码）huffmanhuffman编码编码a.a.将各将各符号按概率排队；符号按概率排队；b.b.将最
11、小的两个合并；将最小的两个合并；c.c.重复上面的过程，直到只有一个节点重复上面的过程，直到只有一个节点12/19/202214第十三章第十三章 信息熵与信源编码信息熵与信源编码熵：熵：平均码长：平均码长：编码效率：编码效率：12/19/202215第十三章第十三章 信息熵与信源编码信息熵与信源编码）算术编码）算术编码已已知知符符号号及及其其出出现现概概率率，按按其其概概率率将将每每个个符符号号对对应应于于,之间的某个间隔：之间的某个间隔：符号符号概率间隔概率间隔a 0.2 0,0.2a 0.2 0,0.2）e e 0.3 0.2,0.5 0.3 0.2,0.5）i i 0.1 0.5,0.6 0.1 0.5,0.6）o o 0.2 0.6,0.8 0.2 0.6,0.8）u u 0.1 0.8,0.9 0.1 0.8,0.9）l l 0.1 0.9,1 0.1 0.9,1）编码时，若已知编码序列编码时，若已知编码序列eaioeolaeaioeola12/19/202216第十三章第十三章 信息熵与信源编码信息熵与信源编码 12/19/202217第十三章第十三章 信息熵与信源编码信息熵与信源编码 需要存储：需要存储：.2341208.2341208以及码长以及码长解码：解码：12/19/202218第十三章第十三章 信息熵与信源编码信息熵与信源编码 12/19/202219