信息论主要内容精.ppt

《信息论主要内容精.ppt》由会员分享，可在线阅读，更多相关《信息论主要内容精.ppt（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论主要内容第1页，本讲稿共45页信号信号信息、消息、信号三者之间的关系信息、消息、信号三者之间的关系消息消息信息信息（信号是消息的载体，信息含藏在消息之中，有信号有消息不一信号是消息的载体，信息含藏在消息之中，有信号有消息不一定有信息定有信息）第2页，本讲稿共45页香农信息论的主要内容香农信息论的主要内容 第3页，本讲稿共45页信源分类和描述信源分类和描述第4页，本讲稿共45页信息的定义和特性信息的定义和特性n信息量信息量表示其表示其不确定性不确定性程度的大小，事件概程度的大小，事件概率越小，信息量越大率越小，信息量越大比特(bit）、奈特(nat）、铁特(Tet）、哈特(Hart）信息量

2、具有非负性和可加性信息量具有非负性和可加性联合自信息量等于：联合自信息量等于：第5页，本讲稿共45页离散信源信息熵和联合熵的定义离散信源信息熵和联合熵的定义nH(X)表示统计平均的信息量表示统计平均的信息量(不确定性的量不确定性的量)，表示平，表示平均每个符号均每个符号(样本事件样本事件)所提供的信息量所提供的信息量=H(X)信息熵也具有非负性和可加性信息熵也具有非负性和可加性联合熵等于联合熵等于第6页，本讲稿共45页(1)非负性非负性(对于离散信源，连续信源不同)(3)极值性极值性(熵函数存在一个最大值，等概分布条件)(2)可加性可加性(多信息源的熵，熵值增加)离散熵重要性质和参数定义信息速

3、率：定义信息速率：Rt=H(X)/t bit/s定义信息含量效率：定义信息含量效率：=H(X)/HMAX(X)定义信源冗余度：定义信源冗余度：=1-第7页，本讲稿共45页离散二元信源的信息熵离散二元信源的信息熵第8页，本讲稿共45页平均互信息量和条件信息量的定义平均互信息量和条件信息量的定义从从Y Y中获取的关于中获取的关于X X的信息量，即的信息量，即X X不确定性的减少量。不确定性的减少量。条件熵条件熵平均的条件概率事件的自信息量平均的条件概率事件的自信息量=第9页，本讲稿共45页条件熵，互信息量的关系nI(X;Y)表示表示从变量从变量Y中所获得的中所获得的关于变量关于变量X的信息量的信息

4、量，是关于，是关于消息消息X 的的不确定性的减少量不确定性的减少量若若X=Y；则则I(X;Y)=H(X)。从从Y中获得了中获得了X的的全部信息全部信息。若若X,Y相互独立；相互独立；I(X;Y)=0。从从Y中得不到中得不到X的信息。的信息。nH(X|Y)表示表示变量变量Y已知的条件下已知的条件下变量变量X的平均信息量，的平均信息量，是关是关于消息于消息X 的的不确定性的量不确定性的量。若若X=Y；H(X|Y)=0。变量变量Y完全确定完全确定了变量了变量X的样值。的样值。若若X,Y相互独立；相互独立；H(X|Y)=H(X)。X的信息量与的信息量与Y无关。无关。第10页，本讲稿共45页I(X;Y)

5、与各个信息熵的关系与各个信息熵的关系H(XY)H(X)H(Y)H(Y|X)H(X|Y)第11页，本讲稿共45页(1)非负性非负性(2)互易性互易性(对称性对称性)平均互信息量平均互信息量 I(X;Y)的性质的性质不具有非负性(3)凸函数性凸函数性当当 p(y|x)给定时，给定时，I(X;Y)是是 p(x)的上凸函数。的上凸函数。研究信道容量的理论基础研究信道容量的理论基础当当 p(x)给定时，给定时，I(X;Y)是是 p(y|x)的下凸函数。的下凸函数。研究信源的信息率失真函数的理论基础研究信源的信息率失真函数的理论基础第12页，本讲稿共45页相对熵（微分熵）相对熵（微分熵）对相对熵的说明对相

6、对熵的说明n n非绝对值，而为相对值。定义形式相统一。非绝对值，而为相对值。定义形式相统一。n nHc(X)的取值：的取值：可能不存在可能不存在，可能为负值可能为负值。连续信源的相对熵第13页，本讲稿共45页微分熵性质n可加性：可加性：HC(XY)=HC(X)+HC(Y|X)=HC(Y)+HC(X|Y)n幅值（峰值）受限时的最大微分熵：幅值（峰值）受限时的最大微分熵：随机变量服从均匀分布时获得最大微分熵n功率（方差）受限时的最大微分熵：功率（方差）受限时的最大微分熵：随机变量服从高斯分布时获得最大微分熵（P=2+2）第14页，本讲稿共45页(随机)信源的分类方法n从消息变量取值的连续性分：离散

7、信源和连续信源n从连续信源输出时间上的连续性分：连续信源和波形信源n从离散信源的消息序列的长度来分：单符号信源和序列（扩展）信源n从离散信源序列之间的有无相关性分：无记忆信源(DMS)和有记忆信源n从离散有记忆信源序列的相关程度分：平稳信源、M阶Markov信源、第15页，本讲稿共45页马尔可夫信源：马尔可夫信源：n马马尔可夫尔可夫链定义链定义：1)马氏链的当前状态只与前一个状态有关，马氏链的当前状态只与前一个状态有关，2)马马氏链是时间离散状态离散的随机过程氏链是时间离散状态离散的随机过程n马尔可夫信源定义马尔可夫信源定义：1）信源状态由当前输出符号和前一时刻信）信源状态由当前输出符号和前一

8、时刻信源状态唯一确定，源状态唯一确定，2）某一时刻信源符号的输出只与当前的信源）某一时刻信源符号的输出只与当前的信源状态有关，与以前的状态无关状态有关，与以前的状态无关nm阶马氏源阶马氏源：是指其输出某一符号的概率：是指其输出某一符号的概率只与此前的只与此前的m个符个符号有关号有关。n马氏源与马氏链的关系马氏源与马氏链的关系：马氏源一般可用马氏链来描述。：马氏源一般可用马氏链来描述。若是若是一阶马尔可夫信源，一个符号对应一个状态，若是一阶马尔可夫信源，一个符号对应一个状态，若是m阶马尔阶马尔可夫信源，可夫信源，m个符号对应一个状态个符号对应一个状态。第16页，本讲稿共45页齐次马氏链齐次马氏链

9、(时齐马氏链时齐马氏链时齐马氏链时齐马氏链)：状态状态状态状态转移概率与时间点无关：转移概率与时间点无关：Pij(m,n)=Pij(K)齐次马氏链的表示方法齐次马氏链的表示方法转移概率矩阵转移概率矩阵转移概率矩阵转移概率矩阵状态转移图状态转移图状态转移图状态转移图由状态由状态由状态由状态 j j 转移到状态转移到状态转移到状态转移到状态 2 2 的概率；的概率；的概率；的概率；非负非负非负非负=1=1网格图网格图网格图网格图状态转移图与矩阵有一一对应关系每时刻的网格节点与马氏链的状态一一对应第17页，本讲稿共45页 定义:若对任意整数m,n,马氏链的状态分布满足 则称 为平稳分布或稳态分布，J

10、为状态数平稳平稳齐次齐次马氏链马氏链：为平稳状态分布为平稳状态分布行矢量，行矢量，k为转移步数为转移步数平稳齐次平稳齐次马氏链的分布马氏链的分布状态的概率分布与时间点无关状态的概率分布与时间点无关第18页，本讲稿共45页离散信道离散信道(数字信道数字信道数字信道数字信道)：输入输出空间为离散。：输入输出空间为离散。连续信道连续信道：状态集合连续，时间集合离散。：状态集合连续，时间集合离散。模拟信道模拟信道(波形信道波形信道波形信道波形信道)：输入输出空间为连续。：输入输出空间为连续。有记忆信道有记忆信道：输出：输出 Y不仅与当前的输入不仅与当前的输入 X 有关，有关，而与前面的输入有关。而与前

11、面的输入有关。无记忆信道无记忆信道：输出：输出 Y 仅与当前的输入仅与当前的输入 X 有关，有关，而且与前面的输入无关。而且与前面的输入无关。信道的数学模型和分类信道的数学模型和分类第19页，本讲稿共45页离散无记忆信道的信道容量离散无记忆信道的信道容量定理定理2 2：对于离散对称和准对称信道，达到信道容对于离散对称和准对称信道，达到信道容量的输入分布为等概分布。量的输入分布为等概分布。计算：计算：“离散对称离散对称”和和“准对称信道准对称信道”“无损信道无损信道”和和“确定信道确定信道”“独立并联信道独立并联信道独立并联信道独立并联信道”和和“和信道和信道和信道和信道”。第20页，本讲稿共4

12、5页对称信道对称信道：信道转移矩阵：信道转移矩阵P中所有的行都是同一中所有的行都是同一组元素的不同排列，所有的列也是同一组元组元素的不同排列，所有的列也是同一组元素的不同排列。素的不同排列。准对称信道准对称信道：设：设 B 为信道转移矩阵为信道转移矩阵P的列集合，的列集合，如果将如果将B划分成划分成m个子集，而用每一个子集构个子集，而用每一个子集构成的矩阵所对应的信道都是对称信道成的矩阵所对应的信道都是对称信道第21页，本讲稿共45页nH(X|Y)称为信道的称为信道的“疑义度疑义度”或或“损失熵损失熵”它表示信息在信道传输过程中的损失，又表示根据输出变量它表示信息在信道传输过程中的损失，又表示

13、根据输出变量Y Y不能确定输入变量不能确定输入变量X X的样的样值，有疑义。值，有疑义。nH(Y|X)称为信道的称为信道的“散布度散布度”或或“噪声熵噪声熵”从信道的输出从信道的输出Y Y信息中减去噪声干扰值就得到关于输入的信息，即信息中减去噪声干扰值就得到关于输入的信息，即H H(Y Y|X X)类类似于噪声；它表示根据似于噪声；它表示根据X X不能确定不能确定Y Y的程度，称为散布度。的程度，称为散布度。信道信道H(X|Y)和和H(Y|X)的物理意义的物理意义第22页，本讲稿共45页费诺（Fano）不等式n离散无记忆信道信道疑义度离散无记忆信道信道疑义度H(X|Y)与差错率与差错率Pe满足

14、如下不满足如下不等式：等式：H(X|Y)H(Pe,1-Pe)+Pelog(n-1)，n是输入符号个数是输入符号个数n应用应用1：信道编码逆定理：证当：信道编码逆定理：证当RC时，则不可能找到一种时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小到任意小n应用应用2：求信息率失真函数：求信息率失真函数：R(D)R(D)=minI(X,Y)=minH(X)-H(X|Y)R(D)=H(X)-H(Pe,1-Pe)-Pelog(n-1)第23页，本讲稿共45页无损信道和确定信道n损失熵为损失熵为“0”，称为，称为无损信道无

15、损信道n噪声熵为噪声熵为“0”，称为，称为确定信道确定信道n损失熵和噪声熵都为损失熵和噪声熵都为“0”，无损确定信道无损确定信道第24页，本讲稿共45页 独立并联信道独立并联信道独立并联信道独立并联信道特点：特点：特点：特点：1.1.1.1.积信道积信道积信道积信道:同时多输入，多输出同时多输入，多输出同时多输入，多输出同时多输入，多输出。2.2.2.2.容量：容量：容量：容量：独立并联信道独立并联信道第25页，本讲稿共45页 和信道和信道和信道和信道特点：特点：特点：特点：随机输入随机输入随机输入随机输入N N 个信道中的一个，合成一个信道个信道中的一个，合成一个信道个信道中的一个，合成一个

16、信道个信道中的一个，合成一个信道。容量：容量：容量：容量：分信道的使用概率：分信道的使用概率：分信道的使用概率：分信道的使用概率：和信道和信道第26页，本讲稿共45页结论：结论：结论：结论：（1 1 1 1）带宽一定时，信道的）带宽一定时，信道的）带宽一定时，信道的）带宽一定时，信道的最大传输率最大传输率最大传输率最大传输率 C C C C是信噪比的函数。是信噪比的函数。是信噪比的函数。是信噪比的函数。此时提高最大信息传输率的方法是提高信噪比。此时提高最大信息传输率的方法是提高信噪比。此时提高最大信息传输率的方法是提高信噪比。此时提高最大信息传输率的方法是提高信噪比。（2 2 2 2）信噪比确

17、定时，信道容量与带宽成正比。）信噪比确定时，信道容量与带宽成正比。）信噪比确定时，信道容量与带宽成正比。）信噪比确定时，信道容量与带宽成正比。此时提高最大信息传输率的方法是提高带宽。此时提高最大信息传输率的方法是提高带宽。此时提高最大信息传输率的方法是提高带宽。此时提高最大信息传输率的方法是提高带宽。（3 3 3 3）对于有确定信道容量）对于有确定信道容量）对于有确定信道容量）对于有确定信道容量C C C C的信道，可以用的信道，可以用的信道，可以用的信道，可以用带宽带宽带宽带宽 B B B B与与与与信噪比信噪比信噪比信噪比 S/NS/NS/NS/N 的的的的不同组合来传输信息。不同组合来传

18、输信息。不同组合来传输信息。不同组合来传输信息。如减少带宽，则必须发送较大功率的信号。如增大带宽，如减少带宽，则必须发送较大功率的信号。如增大带宽，如减少带宽，则必须发送较大功率的信号。如增大带宽，如减少带宽，则必须发送较大功率的信号。如增大带宽，则同样的信道容量能够用较小功率的信号传输，即宽带则同样的信道容量能够用较小功率的信号传输，即宽带则同样的信道容量能够用较小功率的信号传输，即宽带则同样的信道容量能够用较小功率的信号传输，即宽带系统具有良好的抗干扰性。系统具有良好的抗干扰性。系统具有良好的抗干扰性。系统具有良好的抗干扰性。香农公式意义香农公式意义第27页，本讲稿共45页唯一可译码、即时

19、码、异前缀码和非续长码唯一可译码、即时码、异前缀码和非续长码唯一可译码、即时码、异前缀码和非续长码唯一可译码、即时码、异前缀码和非续长码n n唯一可译码唯一可译码唯一可译码唯一可译码：一个码的任意一串有限长的码符号序列：一个码的任意一串有限长的码符号序列：一个码的任意一串有限长的码符号序列：一个码的任意一串有限长的码符号序列 只能被唯一只能被唯一只能被唯一只能被唯一地译成所对应的信源符号序列。地译成所对应的信源符号序列。地译成所对应的信源符号序列。地译成所对应的信源符号序列。n n即时码即时码即时码即时码：唯一可译码，译码时无需参考后续的码符号就能立即作：唯一可译码，译码时无需参考后续的码符号

20、就能立即作：唯一可译码，译码时无需参考后续的码符号就能立即作：唯一可译码，译码时无需参考后续的码符号就能立即作出译码判断。出译码判断。出译码判断。出译码判断。n n异前缀码异前缀码异前缀码异前缀码：码前缀不是任意其他码字（即非续长码）。可以在无：码前缀不是任意其他码字（即非续长码）。可以在无：码前缀不是任意其他码字（即非续长码）。可以在无：码前缀不是任意其他码字（即非续长码）。可以在无延时的情况下解码。延时的情况下解码。延时的情况下解码。延时的情况下解码。存在唯一可译码的充要条件为存在唯一可译码的充要条件为存在唯一可译码的充要条件为存在唯一可译码的充要条件为(克拉夫特克拉夫特克拉夫特克拉夫特K

21、raftKraft不等式不等式)第28页，本讲稿共45页N N N N次扩展信源次扩展信源次扩展信源次扩展信源S S N N=a a1 1,a a2 2,a aqNqN，共有，共有，共有，共有q qN N个符号序列。个符号序列。个符号序列。个符号序列。设码符号集为设码符号集为设码符号集为设码符号集为X X=x x1 1,x x2 2,x xr r，长度为，长度为，长度为，长度为l l 的码符号序列的码符号序列的码符号序列的码符号序列W=WW=W1 1,WW2 2,WWqNqN，WWi i=(=(x xi i1 1 x xi i2 2 x xil il),),x xi i1 1,x xi i2

22、2,x xil ilX X。若要求编得的等长码是唯一可译码则必须满足若要求编得的等长码是唯一可译码则必须满足若要求编得的等长码是唯一可译码则必须满足若要求编得的等长码是唯一可译码则必须满足（理解钥（理解钥（理解钥（理解钥匙：码字的组合数不小于信源符号总数）匙：码字的组合数不小于信源符号总数）匙：码字的组合数不小于信源符号总数）匙：码字的组合数不小于信源符号总数）q q N N r r l l 或或或或 单符号单符号单符号单符号 平均码长满足：平均码长满足：平均码长满足：平均码长满足：等长编码及其无失真编码条件等长编码及其无失真编码条件第29页，本讲稿共45页定理定理定理定理3 3（单符号信源的

23、变长编码定理单符号信源的变长编码定理单符号信源的变长编码定理单符号信源的变长编码定理）若若若若有有有有一一一一离离离离散散散散无无无无记记记记忆忆忆忆信信信信源源源源S S 具具具具有有有有熵熵熵熵H H（S S），并并并并有有有有r r个个个个码码码码符符符符号号号号的的的的符符符符号号号号集集集集X X=x x1 1,x x2 2,x xr r，则则则则总总总总可可可可以以以以找找找找到到到到一一一一种种种种无无无无失失失失真真真真编编编编码码码码方方方方法法法法，构成唯一可译码，使其平均码长满足构成唯一可译码，使其平均码长满足构成唯一可译码，使其平均码长满足构成唯一可译码，使其平均码长满

24、足定理定理定理定理4 4 4 4 （变（变（变（变长长长长无失真信源无失真信源无失真信源无失真信源编码编码编码编码定理定理定理定理香香香香农农农农第一第一第一第一编码编码编码编码定理定理定理定理）离离离离散散散散无无无无记记记记忆忆忆忆信信信信源源源源S S的的的的N N次次次次扩扩扩扩展展展展信信信信源源源源S SN N=a a1 1,a a2 2,a aqNqN ，共共共共有有有有q qN N个个个个符符符符号号号号序序序序列列列列，具具具具有有有有熵熵熵熵H H（S SN N），并并并并有有有有r r个个个个码码码码符符符符号号号号的的的的符符符符号号号号集集集集X X=x x1 1,x

25、 x2 2,x xr r。若若若若对对对对信信信信源源源源S SN N（即即即即信信信信源源源源输输输输出出出出的的的的是是是是N N长长长长的的的的符符符符号号号号序序序序列列列列）进进进进行行行行编编编编码码码码，总总总总可可可可以以以以找找找找到到到到一一一一种种种种编编编编码码码码方方方方法法法法，构构构构成成成成唯唯唯唯一一一一可可可可译译译译码码码码，使使使使信信信信源源源源S S中中中中每个信源符号所需的码字平均长度满足每个信源符号所需的码字平均长度满足每个信源符号所需的码字平均长度满足每个信源符号所需的码字平均长度满足第30页，本讲稿共45页霍夫曼码的编码方法霍夫曼码的编码方法

26、二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：二进制霍夫曼码的的编码方法，它的编码步骤如下：（1 1 1 1）将）将）将）将q q q q个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设个信源符号按概率值的大小以递减次序排列起来，设 p p p p1 1 1 1 p p p p2 2 2 2p p p pq q q q（2 2 2 2）用用用用0 0 0 0和和和和1 1 1 1码码码码符符符符号号号号分分分分别别

27、别别代代代代表表表表概概概概率率率率最最最最小小小小的的的的两两两两个个个个信信信信源源源源符符符符号号号号，并并并并将将将将这这这这两两两两个个个个概概概概率率率率最最最最小小小小的的的的信信信信源源源源符符符符号号号号合合合合并并并并一一一一个个个个符符符符号号号号，从从从从而而而而得得得得到到到到包包包包含含含含q q q q1 1 1 1个个个个符符符符号号号号的的的的新新新新信信信信源源源源-缩减信源缩减信源缩减信源缩减信源SS。（3 3 3 3）把把把把缩缩缩缩减减减减信信信信源源源源S S S S 的的的的符符符符号号号号仍仍仍仍按按按按概概概概率率率率值值值值大大大大小小小小以

28、以以以递递递递减减减减次次次次序序序序排排排排列列列列，再再再再将将将将其其其其最最最最后后后后二二二二个个个个概概概概率率率率最最最最小小小小的的的的符符符符号号号号合合合合并并并并成成成成一一一一个个个个符符符符号号号号，并并并并分分分分别别别别用用用用0 0 0 0和和和和1 1 1 1码码码码符号表示，这样又得到符号表示，这样又得到符号表示，这样又得到符号表示，这样又得到q q q q2 2 2 2个符号的新缩减信源个符号的新缩减信源个符号的新缩减信源个符号的新缩减信源S S S S。（4 4 4 4）依依依依次次次次继继继继续续续续下下下下去去去去，直直直直至至至至信信信信源源源源最

29、最最最后后后后只只只只剩剩剩剩两两两两个个个个符符符符号号号号为为为为止止止止。将将将将这这这这最最最最后后后后两两两两个个个个信信信信源源源源符符符符号号号号分分分分别别别别用用用用0 0 0 0和和和和1 1 1 1码码码码符符符符号号号号表表表表示示示示。然然然然后后后后从从从从最最最最后后后后一一一一级级级级缩缩缩缩减减减减信信信信源源源源开开开开始始始始，向向向向前前前前返返返返回回回回，就就就就得得得得出出出出各各各各信信信信源源源源符符符符号号号号所所所所对对对对应应应应的的的的码码码码符符符符号号号号序序序序列列列列，即即即即得到对应的码字得到对应的码字得到对应的码字得到对应的

30、码字。第31页，本讲稿共45页费诺（费诺（FanoFano）码）码的编码方法的编码方法（1 1 1 1）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来 p p p p1 1 1 1 p p p p2 2 2 2p p p pq q q q（2 2 2 2）将将将将排排排排列列列列好好好好的的的的信信信信源源源源符符符符号号号号划划划划分分分分成成成成两两两两大大大大组组组组，使使使使每每每每组组组组的的的的概概概概率率率率和近似相同，并各赋于一个二进码符号和近似相同，并各赋于一个二进码符号和近似相同，并各赋

31、于一个二进码符号和近似相同，并各赋于一个二进码符号“0 0 0 0”和和和和“1 1 1 1”。（3 3 3 3）将将将将每每每每一一一一大大大大组组组组的的的的信信信信源源源源符符符符号号号号再再再再分分分分成成成成两两两两级级级级，使使使使同同同同一一一一组组组组的的的的两两两两个个个个小小小小组组组组的的的的概概概概率率率率和和和和近近近近似似似似相相相相同同同同，并并并并又又又又各各各各赋赋赋赋于于于于一一一一个个个个二二二二进进进进码码码码符符符符号号号号“0 0 0 0”和和和和“1 1 1 1”。（4 4 4 4）如如如如此此此此下下下下去去去去，直直直直至至至至每每每每组组组组

32、只只只只剩剩剩剩下下下下一一一一个个个个信信信信源源源源符符符符号号号号为为为为止止止止。这样，信源符号所对应的码符号序列就为编得的码字。这样，信源符号所对应的码符号序列就为编得的码字。这样，信源符号所对应的码符号序列就为编得的码字。这样，信源符号所对应的码符号序列就为编得的码字。第32页，本讲稿共45页香农编码香农编码（1 1 1 1）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来）将信源符号以概率递减次序排列起来 p p p p1 1 1 1p p p p2 2 2 2p p p pq q q q（2 2 2 2）对对对对第第第第1 1

33、 1 1个个个个符符符符号号号号编编编编码码码码，取取取取log1/Plog1/Plog1/Plog1/P1 1 1 1的的的的整整整整数数数数(不不不不小小小小于于于于该该该该值值值值)为为为为码码码码长长长长，取取取取累累累累积积积积概概概概率率率率P1P1P1P1，=0=0=0=0。将将将将P1P1P1P1转转转转换换换换为为为为二二二二进进进进制制制制数数数数的的的的小小小小数数数数位位位位作作作作为为为为码码码码字字字字（以以以以2 2 2 2乘乘乘乘小小小小数位取整，再乘得第二位，至数位取整，再乘得第二位，至数位取整，再乘得第二位，至数位取整，再乘得第二位，至L L L L位）。位

34、）。位）。位）。（3 3 3 3）取取取取log1/P2log1/P2log1/P2log1/P2的的的的整整整整数数数数为为为为码码码码长长长长，P1P1P1P1，加加加加第第第第1 1 1 1个个个个符符符符号号号号的的的的概概概概率率率率P1P1P1P1所所所所得得得得的的的的累积概率累积概率累积概率累积概率P2P2P2P2，作为对第作为对第作为对第作为对第2 2 2 2个字的编码依据。个字的编码依据。个字的编码依据。个字的编码依据。（4 4 4 4）取取取取log1/Pilog1/Pilog1/Pilog1/Pi的的的的整整整整数数数数为为为为码码码码长长长长，P Pi-1i-1，再再

35、再再加加加加第第第第i-1i-1i-1i-1个个个个符符符符号号号号的的的的概概概概率率率率P P P Pi-1i-1i-1i-1 所得的累积概率所得的累积概率PiPiPiPi，作为对第作为对第作为对第作为对第i i i i个字的编码依据，重复第一步。个字的编码依据，重复第一步。个字的编码依据，重复第一步。个字的编码依据，重复第一步。（5 5 5 5）如如如如此此此此下下下下去去去去，直直直直至至至至最最最最后后后后一一一一个个个个信信信信源源源源符符符符号号号号为为为为止止止止。这这这这样样样样，信信信信源源源源符符符符号号号号所对应的码符号序列就为编得的码字。所对应的码符号序列就为编得的码

36、字。所对应的码符号序列就为编得的码字。所对应的码符号序列就为编得的码字。第33页，本讲稿共45页几种实用的信源编码n游程编码游程编码用于文件传真（霍夫曼编码）用于文件传真（霍夫曼编码）n算术编码算术编码针对小集合信源（香农编码）针对小集合信源（香农编码）n基于字典的编码基于字典的编码针对无法确知信源的统计针对无法确知信源的统计特性的自适应编码（特性的自适应编码（LZ和和LZW编码）编码）第34页，本讲稿共45页典型的译码准则：典型的译码准则：n最佳译码准则可以使平均译码概率达到最小值。当译码准则最佳译码准则可以使平均译码概率达到最小值。当译码准则数量很大时，选择译码准则的运算量大，不简单。数量

37、很大时，选择译码准则的运算量大，不简单。n“最大后验概率准则最大后验概率准则”已知后验概率分布时已知后验概率分布时n“最大联合概率准则最大联合概率准则”已知联合概率分布时已知联合概率分布时n“最大转移概率准则最大转移概率准则”已知转移概率分布时，也叫已知转移概率分布时，也叫“最大最大似然准则似然准则”n最小汉明距离准则最小汉明距离准则等价于似然准则等价于似然准则用于卷积译码用于卷积译码n最小欧氏距离准则最小欧氏距离准则用于用于TCM译码译码第35页，本讲稿共45页有噪声信道编码定理（香农第二编码定理）有噪声信道编码定理（香农第二编码定理）n如一个离散有噪声信道有如一个离散有噪声信道有n n个输

38、入符号，个输入符号，m m个输出符号，信道容量个输出符号，信道容量为为C C。n当当信道的熵速率信道的熵速率RCRC时，只要码长足够长，总可以找到一种编码方时，只要码长足够长，总可以找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小，法及译码准则，使信道输出端的平均错误译码概率达到任意小，pe=。n当当R RC C时，则不可能找到一种编码方法及译码准则，使信道时，则不可能找到一种编码方法及译码准则，使信道输出端的平均错误译码概率达到任意小。输出端的平均错误译码概率达到任意小。信源编码定理的讨论信源编码定理的讨论第36页，本讲稿共45页n汉明码和最小汉明距离n循环码和CRC码n

39、BCH码和RS码n卷积码及其Viterbi译码译码nTCM映射和译码方法映射和译码方法几种实用的信道编码概念第37页，本讲稿共45页失真（度）函数的定义失真（度）函数的定义失真度（失真函数）定义失真度（失真函数）定义失真矩阵失真矩阵d（失真度的矩阵表示失真度的矩阵表示）d(ui,vj)0（即非负性）（即非负性）i=1，2，n,j=1，2，m 平均失真度定义平均失真度定义第38页，本讲稿共45页信息率失真函数信息率失真函数R（D）的定义的定义率失真函数定义（率失真函数定义（D D 为允许信道）为允许信道）信信源源信信道道信源编码器信源编码器（试验信道试验信道）p p(v v|u u)无噪无噪信道

40、信道第39页，本讲稿共45页R(D)的性质：连续、单调下降、下凸的性质：连续、单调下降、下凸连续信源实际熵无穷大而信道容量有限，故不可能无失真压缩。图连续信源实际熵无穷大而信道容量有限，故不可能无失真压缩。图b b为一般情形为一般情形第40页，本讲稿共45页R（D）的定义域）的定义域（Dmin,Dmax）率失真函数率失真函数R(D)的性质的性质nDMIN是给定失真矩阵是给定失真矩阵d和输入变量概率分布和输入变量概率分布p(u)条件条件下的最小平均失真度。某些情况下下的最小平均失真度。某些情况下DMIN=0。等于。等于失真失真度矩阵每行最小值所构成的列矩阵与输入分布的乘积。度矩阵每行最小值所构成

41、的列矩阵与输入分布的乘积。nDMAX是是I(U,V)0时的最大平均失真度。时的最大平均失真度。也是也是I(U,V)=0时的最小平均失真度时的最小平均失真度，不指，不指D随随p(v/u)变化的变化的最大值。等于最大值。等于失真矩阵与输入分布相乘后所构成的行失真矩阵与输入分布相乘后所构成的行矩阵元素的最小值矩阵元素的最小值第41页，本讲稿共45页上图含义：（已知输入概率分布和失真度矩阵的条件下）1）若给定接收端允许的平均失真度允许的平均失真度D D，则知道实验信道输出的最最小信息量小信息量I I（minI(U,V)=R(D)，I在曲线之上和在H(X)之下）。2）若已知从接收端得到的信息量得到的信息

42、量I I，则知道信道可能产生的最最小平均失真度小平均失真度D D（D(R)=minD(py|x)，如I=0的最小D值为Dmax）。第42页，本讲稿共45页限失真信源编码定理限失真信源编码定理(香农第三定理香农第三定理)设离散无记忆信源的率失真函数为设离散无记忆信源的率失真函数为R（D），如果信源编码后平均），如果信源编码后平均每个信源符号的每个信源符号的信息传输率信息传输率R R（D），），则一定存在一种信源编码则一定存在一种信源编码 C，使编码后的平均失真度使编码后的平均失真度d满足：满足：限失真信源编码定理限失真信源编码定理 设离散无记忆信源的率失真函数为设离散无记忆信源的率失真函数为R（

43、D），如果信源编码后平，如果信源编码后平均每个信源符号的信息传输率均每个信源符号的信息传输率R R（D），则无论采用什么编译），则无论采用什么编译码方式，一定有平均失真度码方式，一定有平均失真度d成立：成立：限失真信源编码限失真信源编码逆逆定理定理第43页，本讲稿共45页限失真信源信道编码定理限失真信源信道编码定理q设离散无记忆信源的信息率失真函数为设离散无记忆信源的信息率失真函数为R(D)，离散，离散无记忆信道的容量为无记忆信道的容量为C。l若满足若满足CR(D)CR(D)，则存在一种编码，使信源序列通过信，则存在一种编码，使信源序列通过信道传输后的平均失真道传输后的平均失真DD（D=RD=

44、R-1-1(C)(C)）l若若CR(D)CDD（D=RD=R-1-1(C)(C)）q信道容量信道容量C给定，若信源熵给定，若信源熵H(X)C，那么直接传输即，那么直接传输即有差错，或者先进行有失真压缩使得有差错，或者先进行有失真压缩使得H(X)C，再进行，再进行无失真传输。无失真传输。第44页，本讲稿共45页例例9.16：二元信源的符号概率为：二元信源的符号概率为1/4和和3/4，每秒发出，每秒发出1.5符号，通过一符号，通过一个二元对称信道传输，信道每秒使用个二元对称信道传输，信道每秒使用2次；求信源符号通过信道传输后次；求信源符号通过信道传输后的最小平均失真。设失真测度为汉明失真。的最小平

45、均失真。设失真测度为汉明失真。解：利用信源信道编码定理：有失真时解：利用信源信道编码定理：有失真时DR-1(C)n二元对称信道的容量为：二元对称信道的容量为：C=2(1-H(pe)bit/s，pe=1/4时时C=0.38bit/s。n汉明失真测度时汉明失真测度时,信源率失真函数为：信源率失真函数为：R(D)=1.5(H(1/4)-H(D)bit/s。其中：其中：D=DMAX=1/4时，时，R(D)=0bit/s。D=DMIN=0时，时，R(D)=0.285bit/sn所以所以DR-1(C)=R-1(2-2H(pe)其中其中pe0.29时，最小时，最小D=0。当。当pe=0.5，最小，最小D=1/4。第45页，本讲稿共45页