信息论与编码自学报告

1、信息论与编码课程自学报告题 目:信息论与编码自学报告学 号:姓 名:任课教师:黄素娟联系方式:二零17年1月10日第一部分 阐述“第四章 信息率失真函数”主要容1.1失真函数与平均失真度平均失真度在离散情况下，信源X = a1,a2, - ar),其概率分布p(x)= p (a1), p (a2), , p (ar),信宿 Y= (b1, b2, bs)。若已知试验信道的传递 概率为p(bj/ai)Dt,则平均失真度为：D = »pabyja.b)=艺艺门("z)Q(乞XY凡满足保真度准则-平均失真度DDO的试验信通称D失真许可的试验信道。失真函数假如某一信源X,输出样值为

2、xi, xi a1,-an),经过有失真的信源编码 器，输出Y,样值为yj, yj b1,-bmo如果xi=yj,则认为没有失真；如 果xi yj,那么就产生了失真。失真的大小，用一个量来表示，即失真函数 d(xi, yj),以衡量用yj代替xi所引起的失真程度。一般失真函数定义为最常用的失真函数均方失真二"(兀,”)=(兀-儿尸绝对失真二班兀，匕)=|x. -yy|相对失真:：d(兀，儿)=忆-儿|4珀误码失真=0.jv, = vd(x . v ) = 8 (xv.)= <""丿”,宜它前三种失真函数适用于连续信源，后一种适用于离散信源。12信息率失真函数

3、的定义互信息取决于信源分布和信道转移概率分布。当p(xi) 定时，互信息I是关于 p(yj/xi)的U型凸函数，存在极小值。在上述允许信道PD中，可以寻找一种信 道pij,使给定的信源p(xi)经过此信道传输互信息I (X; Y)达到最小。该 最小的互信息就称为信息率失真函数R(D),即尺(巧=哽tu(x；y)单位：止/信源符号对于离散无记忆信源，R(D)函数可写成2=锂1f土血陀聲畔怦 M ./=!妙)p(ai), i =1, 2,，n是信源符号概率分布；p(bj/ai), i=1, 2,，n, j = 1, 2,，m 是转移概率分布； p(bj), j = 1, 2,，m是接收端收到符号概

4、率分布。信息率失真函数给出了爛压缩编码可能达到的最小爛率与失真的关系1.3信息率失真函数的性质1、R(D)函数的定艾域和值域R(D)的定艾域为°<久肿。讥ax九=2>(x)mind(x,y) =nunp(x)d(x,y) >允许失真度D的下限可以是零，这是不允许任何失真的情况。2、R(D)是关于平均失真度D的下凸函数设为任意两个平均失真，则有：+ (1 5 uR(DJ + (1 6/)7?(Z)2)3. R(D)是 区间上的连续和严格单调递减函数。离散信源的信息率失真函数2.1离散信源信息率失真函数的参量表达式(1)n m工 p(bj / q ) = 1( -1,料

5、)为工 pgp(bj / M(ab) = D(2) 円(3) 日円m= I(X;Y)-比工 p(b/aJ-sD (5)j=iD(s)=工工 p(q)p(b”d(q, b) expsd (q,勺)(4.3.16)R(s) = sD(s) + 22 P(a>)loS A (4.3.17)2. 2二元及等概率离散信源的信息率失真函数设二元信源；' J =(-V1 並 1其中p< -，所以1- p > -|_卩(七)IP1 - Pj22失真矩阵人切=°“ a > 0a 0.输入符号集X G 七=0,毛=1 输出符号集F e r, = 0, y2 = 1计算率失

6、真函数/?( 对于这种简单信源，可从0(5)解出S与。的显式表达式。£S = ln 冬x-f1_2A = p1-zU =生- i - pD小=a(1 a)P(%)=D_ & l- a5 / %=匕 _ 寻X。_ 寻)p（i 学） 。5/心=垃里：去包窖） E匕/=饭与）（/、（1 - #Xi - - i）"/e = a *xi 普）=刀3） 上式右边第一项是信沥鯛.第二项是因容忍一定失真而可能 压缩的信息率。D = 0,MO) = Hjp)R3J=0二元等概率离散信源的率失真函数当上述二元信源呈等概率分布时，上而式子分别退化为U = 2 卡入= 2(1 - )

7、63;a21_2入=2(1 - )=入1-121 DW 一 Q = £1 2D 21 a/ 並)=P(Yi / -v2)=/ 业)=/ -vx)=R(D) = In 2 - H(-) a3保真度准则下的信源编码定理定理4.1 (保真度准则下的信源编码定理，香农第三定理)设R(D)为一离散无记忆信源的信息率失真函数，并且有有限的失真测度D。 对于任意D,以及任意长的码长k, 一定存在一种信源编码C,其码字个数为使 编码后码的平均失真度。定理的含艾是：只要码长k足够长，总可以找到一种信源编码，使编码E的信息 传输率略大于(直至无限逼近)率失真函数R(D),而码的平均失真度不大于给定的允许

8、失真度，即：D < D由于R(D)为给定D前提下信源编码可能达到的传信率的下限，所以香农第 三定理说明了：达到此下限的最佳信源编码是存在的。第二部分信源编码或信道编码典型案例的实现方案信源编码典型案例的实现方案一霍夫曼编码的mat lab实现1. 编码原理霍夫曼(Huffman)编码算法是满足前缀条件的平均二进制码长最短的编- 源输出符号，而将较短的编码码字分配给较大概率的信源输出。算法是：在信源 符号集合中，首先将两个最小槪率的信源输出合并为新的输出，其概率是两个相 应输出符号概率之和。这一过程重复下去，直到只剩下一个合并输出为止，这个 最E的合并输出符号的概率为仁 这样就得到了一树图

9、，从树根开始，将编码符 号1和0分配在同一节点的任意两分支上，这一分配过程重复直到树叶。从树 根到树叶途经支路上的编码最E就构成了一组异前置码，就是霍夫曼编码输出。2.编码步骤(1) 、码树形成过程：将信源概率按照从小到大顺序排序并建立相应的位置索引。 然E按上述规则进行信源合并，再对信源进行排序并建立新的位置索引，直到合 并结束。在这一过程中每一次都把排序后的信源槪率存入矩阵G中，位置索引存 入矩阵Index中。这样，由排序之后的概率矩阵G以及索引矩阵Index就可以 恢复原概率矩阵P 了，从而保证了回溯过程能够进行下去。(2) 、码树回溯过程：在码树上分配编码码字并最终得到Huffman编

10、码。从索 引矩阵M的末行开始回溯。(1) 在Index的末行2元素位置填入0和1。(2) 根据该行索引1位置指示，将索引1位置的编码('1')填入上一行的第一、 第二元素位置，并在它们之后分别添加'0'和'1'。(3) 将索引不为'1'的位置的编码值C0')填入上一行的相应位置(第3列)。(4) 以Index的倒数第二行开始向上，重复步骤(1)(3),直到计算至Index 的首行为止。3. 程序代码%取得信源概率矩阵，并进行合法性判断c I ear;P=inputC请输入信源概率向量P二');N二length(P)

11、;for componenth : 1: Ni f(P(component)<0)error ('信源概率不能小于O');endendif (sum(P)-1)>0. 0001)error ('信源概率之和必须为1');end%建立各概率符号的位置索引矩阵Index,利于编码后从树根进行回溯，从而得出 对应的编码Q二 PIndex二zeros (NT, N);%初始化 I ndexfor i=1:N-1Q, L=sort (Q);I ndex (i, :) = L (1: N-i+1), zeros (1, i1);G(i, :)=Q;Q=Q(1)+

12、Q(2),Q(3：N),1； %将Q中概率最小的两个元素合并，元素不足的地 方补1end%根据以上建立的Index矩阵，进行回溯，获取信源编码for i=1:N-1Char(i, :)=blanks(N*N) ;%初始化一个由空格符组成的字符矩阵N*N,用于 存放编码end%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的 对应关系向其第一行进行编码Char(N-1,N) = ,0, ;%G中的NT行即最后一行第一个元素赋为0,存到Char中NT 行的N列位置Char(N-1,2*N) = ,1,;%G中的NT行即最后一行第二个元素赋为1,存到Char中 N-1行的2*

13、N列位置%以下从G的倒数第二行开始向前编码for i=2:N-1Char (N-i,1:N-1)=Char(N-i +1,N*(f ind(Index(N-i +1, :)=1)-(N-2):N*(find(lndex(N-i+1, :)=1);%将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置Char(N-i,N) = ,O, ; %然后在当前行的第一个编码位置末尾填入'O'Char (N-i, N+1:2*N-1) =Char (N-i, 1:N-1) ; %将6 后一行中索引为 1 的编码码 字填入到当前行的第二个编码位置Char(N-i,2*N) =

14、,1,;%然总在当前行的第二个编码位置末尾填入1'for j=1:i-1%循环作用：将Index E 行中索引不为1处的编码按照左右顺序填入当前行的 第3个位置开始的地方，最E计算到Index的首行为止Char (N-i, (j+1)*N+1: (j+2)*N)二 Char (N-i+1, N* (find (Index (N-i+1, :)=j+1)-1 )+1:N*find(lndex(N-i+1, :)=j+1);endend%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一 行索引将编码对应到相应概率的信源符号上。for i=1:NResult (i, 1: N)二 Char (1, N*(f ind (Index (1, :) = i