信息论与编码技术

《信息论与编码技术》由会员分享，可在线阅读，更多相关《信息论与编码技术（22页珍藏版）》请在装配图网上搜索。

1、前两个是别人的，后两个是自己的，学术交流，抛砖引玉。信息论与编码实验报告样板 实验室名称：S1-306实验一 二维随机变量信息熵的计算 教学实验报告实验目的掌握二变量多种信息量的计算方法。实验要求1熟悉二变量多种信息量的计算方法，设计实验的数据结构和算法；2编写计算二维随机变量信息量的书面程序代码。 实验内容离散二维随机变换熵的计算说明：1)2)利用random函数和归一化方法构造一个二维离散随机变量(X, Y)；分别计算X与Y的熵、联合熵、条件熵：H (X)、H (Y)、H (X,Y) H (XIY)、I(XIY)；3)对测试通过的程序进行规范和优化；4)编写本次实验的实验报告。实验步骤实验

2、过程中涉及的各种熵的主要公式(或定义式)：1、离散信源熵(平均不确定度/平均信息量/平均自信息量)H (X)=工 p(x )I(x )= 一工 p(x )log p(x )i i i i2、在给定某个yj条件下，xii的条件自信息量为I(xyj), X集合的条件熵H (X/yj)为H(X / y )=工 p(x / y )I(x / y )ji j i ji在给定Y条件下，X集合的条件熵H(X/Y)为：p(y )p(x / y )I(x / y ) j i j i j i , jH(X/Y)二工 p (y )H (X / y ) = Ejjp (xy ) I (x / y )i ji ji ,

3、 jY集合的条件熵H(Y/X)定义为:相应地，在给定X (即各个Xi)的条件下，H(Y/X)二工(xy )I(y /x )二工p(xy )log p(y /x)i jj ii jj i3、联合熵是联合符号集合XY上的每个元素对xiyj的自信息量的概率加权统计平均值, 表示X和Y同时发生的不确定度。)二-工 p(i,jx y )log p( x y )i j i jH(X Y)二工p(xy )I(xyi j i j i,j实验体会通过本次实验，掌握了离散信源熵、条件熵、联合熵的概念和它们与信源统计分布或条件分 布、联合分布之间的关系，并能进行计算。进一步加深了对各种信息熵的物理意义的理解。附：计

4、算信源熵、联合熵和条件熵的程序代码清单：（可写入实验报告也可不写入）#include#include#include#include #include using namespace std; void main()int k,n,t=0;double a44,b=0,c=0; srand(unsigned)time(NULL);for(k=0;k4;k+)for(n=0;n4;n+)akn=rand()%100;t+=akn;cout从0到100间随机取得行列的random函数：endl;for(k=0;k4;k+)for(n=0;n4;n+)coutsetw(5)akn;coutendl;

5、cout函数归一化：endl;for(k=0;k4;k+)for(n=0;n4;n+)coutsetw(12)akn/t;coutH(Y)计算：setw(20)H(X)计算：endl;int e=1;for(k=0;k4;k+)double i=0,g=0;for(n=0;n4;n+)i+=(akn/t);g+=(ank/t);coutP(Yk+1)：isetw(8)P(Xe)：gendl; +e;b-=(i*log(i)/log(2.0);c-=(g*log(g)/log(2.0);coutH(Y)=-刀p(Y)log p(Y)=bendl;coutH(X)=-刀p(X)log p(X)=c

6、endl;cout联合熵H (X,Y)计算:endl;b=0;int r,u,h=0;for(k=0;k4;k+)for(n=0;n4;n+)if(akn!=0)b-=(akn/t)*log(akn/t)/log(2.0);elser=k,u=n;h=1;break;if(h=0)coutH(X,Y)=-EEp(X,Y)log p(X,Y)=bendl;else coutP(r+l，u+l)为零，中断，无值endl;cout条件熵H (X|Y)计算:endl;b=0,h=0;for(k=0;k4;k+)double i=0; for(n=0;n4;n+)i+=(akn/t);for(n=0;n

7、4;n+)if(akn!=0)b-=(akn/t)*log(akn/t)/i)/log(2.0);else h=1;break;if (h=0)coutH(X|Y)=-刀刀P(X,Y)log(P(X,Y)/P(Y)=bend l; else coutP(r+l，u+l)为零，中断，无值endl;coutI (X|Y)计算：endl; if(h=0)coutI(X|Y)=H(X)-H(X|Y)=c-bendl;else coutP(r+l，u+l)为零，中断，无值endl;实验二简单信源编码方法实现 教学实验报告实验目的掌握 Huffman 编码方法。实验要求1. 熟悉离散信源的编码方法，重点是

8、Huffman编码方法，设计Huffman编码的数据结构和算法；2. 编写Huffman编码的书面程序代码。实验内容离散信源的 Huffman 编、译码方法说明：(1) 利用random函数构造一个一维离散随机变量分布P (X)；(2) 构造离散随机变量的概率压缩表；(3) 根据概率压缩表构造Huffman编码表，并实现Huffman编码；( 4)完成 Huffman 译码；(4) 编写本次实验的实验报告。实验体会通过本次实验，掌握了离散信源最佳不等长编码的概念，掌握了哈夫曼编码的基本方法和过程及平均码长和编码效率的计算。哈夫曼编码的计算例子： 给定离散信源概率分布如下:U _uuuuuuu=

9、1234567_ p(u)_0.20 0.19 0.18 0.17 0.15 0.10 0.01H(U)二0.21og 0.2 - 0.191og 0.19 - 0.181og 0.18 - 0.17 log 0.17-0.151og 0.15-0.101og0.10-0.011og0.01 二2.61平均码长:K = p( u )K 二 0.2 x 2 + 0.19 x 2 + 0.18 x 3 + 0.17 x 3 + 0.15 x 3 + 0.10 x 4 + 0.01 x 4 二 2.72i ii=1编码效率H (U)耳=K对本信源进行了哈夫曼编码，可以得到如下的一种可能编码:事讯辺E

10、：0WMjoim #includecstdio #includeiomanip #include #includecassert #include #includeiostream using namespace std; double *a; string *c;struct elemdouble a3;class stackint size;int top;elem *list;public:stack(const int sz=0)size=sz;top=0;list=new elemsz;stack()delete list;void clear()top=0;void push(co

11、nst elem& item)assert(topsize);listtop+=item;elem pop()assert(!isEmpty();return list-top;elem topValue() constassert(!isEmpty();return listtop-1;bool isEmpty() constreturn top=0;void aa(int n)double w=0;a=new doublen;srand(unsigned)time(NULL);cout随机生成归一化一维离散变量：endl;for(int i=0;i=i;j-)if(ajaj+1)p=aj+

12、1;aj+1=aj;aj=p;coutP(X):;for(int i=0;in;i+)cout.precision(3); coutaisetw(8);void huffman(double *a,string *c,int n)elem mp;stack s(n);double *b;b=new doublen;for(int i=0;in;i+)bi=ai; double *d;d=new doublen;for(int i=0;in;i+)di=i; double *e;e=new doublen;for(int i=0;i=2;m-) bm-2+=bm-1;mp.a2=dm-2;mp.

13、a3=dm-1;s.push(mp); double mp,mp1;for(int i=0;i=i;j-) if(bjbj+1)mp=bj+1; mp1=dj+1; bj+1=bj; dj+1=dj; bj=mp;dj=mp1; coutleftsetw(6)nP(X):;for(int i=0;im-1;i+) cout.precision(3); coutsetw(8)bi; while(!s.isEmpty()mp=s.pop(); for(int i=0;in;i+) if(mp.a2=ei)t=ci;for(int i=0;in;c=new stringn;aa(n);huffman

14、(a,c,n);coutendl;coutsetw(6)各项 Huffman 编码为：endl;for(int i=0;in;i+)cout.precision(3);coutsetw(8)ai;cout.precision(0);coutsetw(n+4)ci;coutendl;项目三：算术编码1. 实验内容对信源概率进行算术编码。2.数据结构与算法分析累积概率的递推公式为：G(& r) = G(&) + p(&)P(r)。3.实验数据与实验结果13本实验采用二元序列为：11111100 p()= 4，p蔦。实验结果:图3算术编码实验结果4程序代码清单:myLength用于计算码长，myPr

15、obability用于计算p( )p(r)的累积概率，myYouC用于计算 二元序列的G(&)并累加，myYouChengR用于输出编码结果。(1) YCAgain.h#ifndef YCAGAIN_H_INCLUDED#define YCAGAIN_H_INCLUDEDextern int myLength(double p);extern double myProbability(double *a,double p,int n);extern double myYouC(double *a,double p,int n);extern void myYouChengR(double p,

16、 int n);#endif / YCAGAIN_H_INCLUDED/.cpp#include #include int myLength(double p)int length; double result;if(p 0) length += 1;return length;double myProbability(double *a,double p,int n)int i; double sum =1; for(i=0; in; i+) if(*(a+i)=1) sum *=p; /puts(1t); if(*(a+i)=0) sum *=(1-p); /puts(0t);return

17、 sum;double myYouC(double *a, double p, int n)double sum=0; / all sum double myAn;int i;int j;for(i=0; i0)for(j=0; j=1)printf(1);p = p-1;elseprintf(0);i+;while(in);(2) main#include #include YCAgain.h #define N 8int main()double aN = 1,1,1,1,1,1,0,0; double p= 0.75;double myP;double myL;double myYCP;

18、 myP = myProbability(a,p,N); printf(P: %lfn,myP); myL = myLength(myP); printf(L: %lfn,myL); myYCP = myYouC(a, p, N); printf(YCP: %lfn,myYCP); printf(Code: ); myYouChengR(myYCP, myL);项目四：香农编码1. 实验内容香农编码2. 数据结构与算法分析(1) 将q个信源符号按概率递减的方式进行排列：P P . P12q(2) 按上式计算出每个信源符号的码长1。i3)为了编成唯一可译码，计算第 i 个信源符号的累加概率ik=

19、14)将累加概率G用二进制表示。i取G对应二进制的小数点后1位构成该信源符号的二进制码字。ii3. 实验数据与实验结果(1) 信源概率是随机产生的。(2) 实验结果如图：图2香农编码实验结果4程序代码清单:myRand产生信源随机概率，myLength计算码长，myQuickSort对信源概率排序，主函 数调用。(1). myRand/ .h#ifndef MYRAND_H_INCLUDED#define MYRAND_H_INCLUDEDextern void myRand(double*, int);#endif / MYRAND_H_INCLUDED.cpp#include #inclu

20、de vstdlib.hvoid myRand(double *p, int n)int i=0;double sum =0;srand(time(NULL);for(i=0; in; i+)*(p+i) = rand() % 100 + 1;sum += *(p+i);for(i=0; in; i+)*(p+i) /= sum;(2)myLength/.h#ifndef MYLENGTH_H_INCLUDED #define MYLENGTH_H_INCLUDEDextern int myLength(double);#endif / MYLENGTH_H_INCLUDED /.cpp#in

21、clude int myLength(double p)int length;double result; if(p 0)length += 1; return length;(3) myQuickSort /.h#ifndef MYQUICKSORT_H_INCLUDED #define MYQUICKSORT_H_INCLUDEDextern void myQuickSort(double *, int, int);#endif / MYQUICKSORT_H_INCLUDED /.cppint mySortBase(double *p, int left, int right)doubl

22、e m_flag;double tmp;m_flag = *(p + left);while(left *(p+right) )right-;if(m_flag *(p+right) );tmp = *(p+right);*(p+right) = *(p+left);*(p+left) = tmp;while( m_flag pleft)left+;if(m_flag pleft)tmp = *(p+right);*(p+right) = *(p+left);*(p+left) = tmp;*(p+left) = m_flag;return left;void myQuickSort(doub

23、le *p, int left, int right)int mid;if(leftright)mid = mySortBase(p,left,right); myQuickSort(p,left,mid-1);myQuickSort(p,mid+1,right);4) main#include #include myQuickSort.h#include myRand.h#include myLength.h #define N 7 int main()double pN = 0.20, 0.19, 0.18, 0.17, 0.15, 0.10, 0.01; double qN;int i,

24、j;int k;/编码 长度double b_c; / 二 进制 数/ 生成 随机数 puts(Rand:n);myRand(p, N);for(i=0; iN; i+)printf(%4.2lft, pi);puts(n);/ 排序 puts(Sort:n);myQuickSort(p, 0, N-1); for(i=0; iN; i+)printf(%4.2lft, pi);puts(n);/累加 概率 puts(Q:);q0 = 0;for(i=1; iN; i+)qi = qi-1 + pi-1;for(i=0; iN; i+)printf(%4.2lft, qi);puts(n);/输出 编码 for(i=0; iN; i+)printf(P%d: %4.2lft, i+1, pi); printf(Q%d: %4.2lft, i+1, qi); k = myLength(pi);b_c = 2*qi;for(j=0; j= 1)putchar(1);b_c -= 1;elseputchar(0);b_c *= 2;puts(n);return 0;