信息论复习.ppt

课程内容• 信息论的基本问题—信息的度量• 无失真信源编码定理—香农第一定理• 信道编码定理—香农第二定理• 限失真信源编码定理—香农第三定理• 信源编码引 论第一章主要内容：• 1、信息论的奠基人香农及其重要著作；• 2、信息、消息、信号的区别和联系• 3、通信系统的模型各主要功能模块（包括信源、信道 、信宿、信源编译码器、信道编译码器）及其作用• 信息论的奠基人：香农• 信息时代的里程碑：1948年 香农《通信的数学理论》(A mathematical theory of communication)第一次提出了信息量的 概念，并应用数理统计的方法来研究通信系统，创立 了信息论 • 三大定理 – 无失真信源编码定理（第一极限定理） – 信道编码定理（第二极限定理） – 限失真信源编定理（第三极限定理）（一） 信息论的形成与发展（二）信息、消息和信号的区别与联系• 信息–是事物运动状态或存在方式• 消息–是指包含有信息的语言、文字和图像等 • 信号–是消息的物理体现 信号是信息的载荷子或载体，是物理性的• 同一信息，可以采用不同的信号形式 (比如文字、语 言、图象等）来载荷；• 同一信号形式，比如 “0”与 “1”可以表达不同形 式的信息，比如无与有、断与通、低与高 (电平) 等 。

• 在通信系统中，实际传输的是信号，但本质内容的是 信息信息包含在信号之中，信号是信息的载体通 信的结果是消除或部分消除不确定性，从而获得信息 三）数字通信系统模型信道信源信源编码加密信道编码干扰源信宿信源解码解密信道解码加密 密钥解密 密钥u ux xy yk kz zv vz z' 'y y' 'x x' '信源、信宿和信道 • 信源：向通信系统提供消息u的人和机器发送消息的 源• 信宿：信息归宿之意，亦即收信者或用户，是信息传送 的终点或目的地• 信道：传输信息的物理媒介 信源编码器与译码器 • 信源编码器–符号转换； –压缩信源的冗余度,提高通信系统传输效率； –包括无失真信源编码、限失真信源编码• 信源译码器–把信道译码器输出的代码组变换成信宿所需要的消息 形式，它的作用相当于信源编码器的逆过程信道编码器与译码器• 信道编码–提高信息传送的可靠性–在信源编码器输出的代码组上有目的地增加一些监 督码元,使之具有检错或纠错的能力• 信道译码器–具有检错或纠错的功能,它能将落在其检错或纠错 范围内的错传码元检出或纠正,以提高传输消息的 可靠性 信息量和熵第二章• 定义•单位–常用的对数底是2,信息量的单位为比特(bit)；–若取自然对数e,则信息量的单位为奈特(nat)；–若以10为对数底,则信息量的单位为笛特(det)(一)（非平均）互信息量I(xi ; yj)表示接收到某消息yj后获得的关于事件xi的信息量。

• 性质 （1）对称性：I(xi; yj)=I(yj; xi)（2）当rij=qiwj时I(xi; yj)=0当两个事件相互独立时，互信息量为0）3）当rij>qiwj时I(xi; yj)>0，当rij0，若存在L0、ξ()、D()，使当 码长L>L0时，PeH(U)，则R是可达的；若R

c.给每一组分配一位码元d.将每一分组再按同样原则划分，重复步骤b和c，直 至概率不再可分为止最佳不等长编码是平均码长最小的不 等长编码nHuffman编码n算术编码nLZ编码三、最佳不等长编码哈夫曼编码a.将信源符号按概率从大到小的顺序排列b.给两个概率最小的信源符号p(xn-1)和p(xn)各分配一 个码位0和1，将这两个符号合并成一个新符号，其概 率之和作为新符号的概率，得到(n－1)个符号c.将缩减信源符号按概率排列，重复步骤a,b直至缩减信源只剩两个符号为止d.从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字算术编码• 算术编码是计算序列的累计分布，用累计分布值表示序 列，所以称为算术编码 • 以二元信源输出序列的编码为例01110P(0) P(1)F(0 )F(1)P(00)P(01)F(01 )P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)u对应区间的宽度等于符号序列的概率算术编码• 递推公式编码 • P(u=bbbbbbaa)=0.7560.252= • F(a)=0, F(b)=0.25序号uiP(ui)=HF(ui)=Gn(ui)S 01001b3/41/4 =0+1*1/410.12b9/167/16 = 1/4 + 3/4 *1/410.13b27/6437/64 = 7/16 + 9/16 * 1/420.11 4b81/256175/256 = 37/64 + 27/64 *1/420.115b243/1024781/1024=…30.1116b729/40963367/4096=…30.111 7a729/163843367/4096=…50.110118a729/655363367/4096=…70.110101 0H=HP(ul+1),G=G+HF(al+1)适用于离散信源1. 失真函数d( xi, yj )适 用 于 连 续 信 源2. 几种常用失真函数与主观 特性最 匹配3. 信息率失真函数R(D)的性质(1) R(D)的值域和定义域值域：由I(X;Y)取值范围可得 ：0  R(D) H(X)D Dmax0DminH(X)R(D)0一般的，Dmin =0，对应无失真的情况且R(D)max = R(Dmin) =H(X)当D取大过某个值时，R(D)都=0，定义Dmax为所有满足 R(D)=0的D的最小值• (2) R(D)是D的连续、下凸函数(3) R(D)在定义域上是严格单调递减函数4 限失真信源编码定理（香农第三定理） R(D)——在允许失真 的条件下，每个信源 符号能够被压缩的最低值。

限失真信源编码定理（香农第三定理）简单阐述 ：——信息率，即编码后平均每个信源符号能传 输的最大信息量限失真信源编码定理说明限失真最佳编码是存在的， 但并没有提供具体构造最佳码的思路迄今尚无可实 现编码方法接近R(D)这个界。