信息论与编码实验报告(DOC)

1、 实验一 绘制二进熵函数曲线（2个学时）一、实验目的：掌握Excel的数据填充、公式运算和图表制作掌握Matlab绘图函数掌握、理解熵函数表达式及其性质二、实验要求：提前预习实验，认真阅读实验原理以及相应的参考书。在实验报告中给出二进制熵函数曲线图三、实验原理：Excel的图表功能信源熵的概念及性质单位为 比特/符号 或 比特/符号序列。当某一符号xi的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X中只含有一个符号x时，必有p(x)=1，此时信源熵H（X）为零。四、实验内容：用Excel和Matlab软件制作

2、二进熵函数曲线。根据曲线说明信源熵的物理意义。Excel具体步骤如下：1、启动Excel应用程序。2、准备一组数据p。在Excel的一个工作表的A列（或其它列）输入一组p，取步长为0.01，从0至100产生101个p（利用Excel填充功能）。3、取定对数底c，在B列计算H(x) ,注意对p=0与p=1两处，在B列对应位置直接输入0。Excel中提供了三种对数函数LN(x),LOG10(x)和LOG(x,c)，其中LN(x)是求自然对数，LOG10(x)是求以10为底的对数，LOG(x,c)表示求对数。选用c=2,则应用函数LOG(x,2)。在单元格B2中输入公式：=-A2*LOG(A2,2)

3、-(1-A2)*LOG(1-A2,2)双击B2的填充柄，即可完成H(p)的计算。4、使用Excel的图表向导，图表类型选“XY散点图”，子图表类型选“无数据点平滑散点图”，数据区域用计算出的H(p)数据所在列范围，即$B$1:$B$101。在“系列”中输入X值(即p值)范围，即$A$1:$A$101。在X轴输入标题概率，在Y轴输入标题信源熵。（二）用matlab软件绘制二源信源熵函数曲线p = 0.0001:0.0001:0.9999;h = -p.*log2(p)-(1-p).*log2(1-p);plot(p,h)五、实验结果二元信源熵函数信源熵为信息的不确定度，概率的大小反映了信息量的大

4、小，如果二元信源的输出符号是确定的，即p=1,则该信源不提供任何信息，当二元信源符号0和1以等概率发生时，信源熵达到极大值，等于1bit信息量。实验二：验证二元离散对称信道的互信息的性质（4学时）（课后做）一、实验目的1掌握离散对称信道互信息的计算及性质特点。2练习应用matlab软件进行互信息的函数曲线的绘制，并从曲线上理解其物理意义。二、参看定理4.2.1及4.2.2三、实验内容1验证固定信道，I(X;Y)是信源分布的上凸函数；2验证固定信源，I(X;Y)是信道传递概率的下凸函数；3 I(X;Y)的三维分布绘制（自行学习三维图形的绘制函数）四、实验结果（1）I(X;Y)是信源分布的上凸函数

5、（2）I(X;Y)是信道传递概率的下凸函数（3）I(X;Y)的三维分布绘制 五、源代码（1）验证固定信道，I(X;Y)是信源分布的上凸函数symsw;x=w,1-w;p=0.90.1;0.10.9;pxy=x(1,1)*p(1,:);x(1,2)*p(2,:);py=x*p(:,1),x*p(:,2);px_y=pxy(:,1)/py(1,1),pxy(:,2)/py(1,2);Ix_y=sum(sum(pxy.*log2(p./py;py);ezplot(w,Ix_y,0,1,0,1);xlabel(变量w);ylabel(平均互信息量I);title(平均互信息量与w的关系);gridon

6、 （2）验证固定信源，I(X;Y)是信道传递概率的下凸函数m=10.50;figureholdon%设置为叠加绘图模式fori=1:5w=m(i);p=0:0.01:1;I=(w.*(1-p)+(1-w).*p).*log2(1./(w.*(1-p)+(1-w).*p)+(w.*p+(1-w).*(1-p).*log2(1./(w.*p+(1-w).*(1-p)-(p.*log2(1./p)+(1-p).*(log2(1./(1-p);plot(p,I,b);title(曲线图);xlabel(信道转移概率p);ylabel(平均互信息量I);end （3）I(X;Y)的三维分布绘制p,q=m

7、eshgrid(0.000001:0.01:1,0.000001:0.01:1);Hnoise=-p.*log2(p)-(1-p).*log2(1-p);%噪声熵x=(1-p).*q+p.*(1-q);I=-x.*log2(x)-(1-x).*log2(1-x)-Hnoise;mesh(p,q,I) 实验三：离散信道容量（1学时）一、实验目的掌握离散信道容量的计算。理解离散信道容量的物理意义。练习应用matlab软件进行函数曲线的绘制，并从曲线上理解其物理意义。二、实验原理二元对称信道BSC（Binary Symmetric Channel）二进制离散信道模型有一个允许输入值的集合X=0，1和

8、可能输出值的集合Y=0，1，以及一组表示输入和输出关系的条件概率（转移概率）组成。如果信道噪声和其他干扰导致传输的二进序列发生统计独立的差错，且条件概率对称，即这种对称的二进制输入、二进制输出信道称做二元对称信道（或二进制对称信道，简称BSC信道），如下图所示：信道容量公式：三、实验内容BSC信道是DMC信道对称信道的特例，对于转移概率为P(0/1)=P(1/0)=p，P(0/0)=P(1/01)=1-p，求出其信道容量公式，并在matlab上绘制信道容量C与p的曲线。根据曲线说明其物理意义。参考代码： p = linspace(0,1,50);c = 1+p.*log2(p)+(1-p).*

9、log2(1-p);plot(p,c)xlabel(p)ylabel(c)四、实验结果C=1+plogp+（1-p）log（1-p）无噪声干扰时（p=0），损失熵H(X/Y)=0,信道容量等于信源发出的码元速率。P=1/2时，C=0，信道已无传输能力。实验四：Huffman编码软件实现（4个学时）一、实验目的（1）进一步熟悉Huffman编码过程；（2）练习matlab中哈夫曼编码函数的调用；（3）掌握Matlab中Huffman编码的思想；（4）掌握平均码长，编码效率的计算。二、实验原理二元哈夫曼编码的具体步骤归纳如下：统计n个信源消息符号，得到n个不同概率的信息符号。将这n个信源信息符号按

10、其概率大小依次排序： p(x1) p(x2) p(xn)取两个概率最小的信息符号分别配以0和1两个码元，并将这两个概率相加作为一个新的信息符号的概率，和未分配的信息符号构成新的信息符号序列。将剩余的信息符号，按概率大小重新进行排序。重复步骤3，将排序后的最后两个小概论相加，相加和与其他概率再排序。如此反复重复n-2次，最后只剩下两个概率。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字，构成霍夫曼编码字。编码结束。编码之后，哈夫曼编码的平均码长为：哈夫曼编码的效率为：三、实验内容（一）直接调用matlab哈夫曼编码函数进行编码，与人工编码结果做比较。huffmandict

11、函数： 为已知概率分布的信源模型生成哈夫曼编解码索引表。调用方法如下：dict ，L = huffmandict (symbols, p)调用Huffmandict函数，使用数组s（编码符号）及其概率数组P进行Huffman编码,编码后产生一个编码词典dict,以及平均码长L。求出熵H，并计算其效率H/L基本参考：symbols = 1: ;p = ;dict，L = huffmandict(symbols,p)code1= dict1,2. dict ,2（二）根据编码思想编写要求（1）输入：信源的概率分布P；（2）输出：每个信源符号对应的Huffman编码的码字。（3）计算平均码长 、信源

12、熵 及编码效率并对：输入的概率数组中有小于0的值输入的概率数组总和大于1作出判断实验结果（一） (二) 五、哈夫曼编码的MATLAB实现（基于0、1编码）：clc;clear;A=5,3,1,6,2;%原概率序列A=A/sum(A);A=fliplr(sort(A);%按降序排列T=A;m,n=size(A);B=zeros(n,n-1);%空的编码表（矩阵）for i=1:n B(i,1)=T(i);%生成编码表的第一列endr=B(i,1)+B(i-1,1);%最后两个元素相加T(n-1)=r;T(n)=0;T=fliplr(sort(T);t=n-1;for j=2:n-1%生成编码表的

13、其他各列 for i=1:t B(i,j)=T(i); end K=find(T=r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在该列的位置 r=(B(t-1,j)+B(t,j);%最后两个元素相加 T(t-1)=r; T(t)=0; T=fliplr(sort(T); t=t-1;endB;%输出编码表END1=sym(0,1);%给最后一列的元素编码END=END1;t=3;d=1;for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码 for i=1:t-2 if i1 & B(i,j)=B(i-1,j) d=d+1; else d=1; e

14、nd B(B(n,j+1),j+1)=-1; temp=B(:,j+1); x=find(temp=B(i,j); END(i)=END1(x(d); end y=B(n,j+1); END(t-1)=char(END1(y),0; END(t)=char(END1(y),1; t=t+1; END1=END;end A%排序后的原概率序列 END%编码结果for i=1:n a,b=size(char(END(i); L(i)=b;endavlen=sum(L.*A)%平均码长H1=log2(A);H=-A*(H1)%熵P=H/avlen%编码效率附录资料：不需要的可以自行删除Pascal/

15、C/C+语句对比（补充版）一、Hello world 先看三种语言的样例：Pascalbegin writeln(Hello world);end.C#include int main() printf(Hello world!n); return 0;C+#include using namespace std;int main()cout Hello world! endl; return 0; 从这三个程序可以看到一些最基本的东西。在Pascal中的begin和end，在C/C+里就是；Pascal主程序没有返回值，而C/C+返回0（好像在C中可以为NULL）。在C/C+中，main函数

16、以前的是头文件，样例中C为stdio.h，C+除了iostream还有第二行的using namespace std，这个是打开命名空间的，NOIP不会考这个，可以不管，只要知道就行了。 此外说明 注释单行用/，段落的话Pascal为，C/C+为/* */。* 常用头文件（模板）#include #include #include #include #include #include using namespace std;int main() system(“pause”);return 0;二、数据类型及定义 这里只列出常用的类型。1、整型PascalC/C+范围shortint-128

17、127integershort-32768 32767longintInt -2147483648 2147483647int64long long-9223372036854775808 9223372036854775807byte-0 255wordunsigned short0 65535longwordunsigned int0 4294967295qwordunsigned long long0 18446744073709551615 * 当对long long 变量赋值时，后要加LLLong long x=6327844632743269843LL* 如果位移 x2LL* Li

18、nux: printf(“%lldn”,x);* Windows: printf(“%I64dn”,x);2、实型PascalC/C+范围realfloat2.9E-39 1.7E38single-1.5E-45 3.4E38doubledouble5.0E-324 1.7E3083、字符即字符串 字符在三种语言中都为char，C里没有字符串，只有用字符数组来代替字符串，Pascal和C+均为string。Pascal中字符串长度有限制，为255，C+则没有。 字符串和字符在Pascal中均用单引号注明，在C/C+中字符用单引号，字符串用双引号。4、布尔类型 Pascal 中为 boolean

19、，C/C+ 为 bool。值均为True 或 False。C/C+中除0外bool都为真。5、定义 常量的定义均为 const，只是在C/C+中必须要注明常量的类型。在C/C+中还可以用宏来定义常量，此时不注明类型。PascalC/C+const a = 60; b = -a + 30; d = ;const int a = 60;const int b = - a + 30;const string d = “”;define MAXN 501 /这个是宏 * 宏定义其实就是直接在程序相应的位置替换： #define randomize srand(unsigned time(NULL) #

20、define wait for(int w=0;w a;cout a;cout a endl;特别说明C+中cin一个字符的话会自动跳过空格和回车，Pascal和C则会读入空格和回车。在Pascal中writeln(a:n:m) 表示在n个字符宽的输出域上输出a保留m位小数。例如：pascal write(a:6) c/c+ printf(“%6d”,a) Pascal write(a:6:2) c/c+ printf(“%6.2f”,a) C+ 如果用 cout ? (繁琐！) 需要加头文件 #inlude cout setprecision(2)a; /作用永久 cout setw(6)a

21、; /作用临时 以下三个进制设定都是永久作用： cout deca; 相当 printf(“%d”,a); /十进制 cout hexa; 相当 printf(“%X”,a); /十六进制 cout octa; 相当 printf(“%o”,a); /八进制例如：cout 12hex12oct1212endl;输出：12c1414 C 的输入输出里面的字符串中%表示变量，%后面的字目表示变量类型。下面是类型表：%hd1个short型整数%d1个int型整数%u1个unsigned int型整数%I64d1个long long型整数%c1个字符%s1个C字符串%f1个float型实数%lf1个d

22、ouble型实数%10.4f输出1个总宽度为10,保留4位小数的实数 文件输入输出：Pascalassign(input, test.in);assign(output, test.out);reset(input);rewrite(output);read(a, b);writeln(a, b);close(input);close(output);CFILE *fin = fopen(“test.in”, “r”);FILE *fout = fopen(“test.out”, “w”);fscanf(fin, “%d%d”, &a, &b);fprintf(fout, “%d%d”, a,

23、 b);fclose(fin); fclose(fout);C+#include using namespace std;ifstream fin(“test.in”);ofstream fout(“test.out”);fin a b;fout a b endl;fin.close(); fout.close();因为C+的读入较慢，个人建议C+的话使用C的输入方式。当然也有人用C的读入，C+的输出的，这种方式我们称之为城乡结合。*中国计算机学会竞赛须知发布的C读写程序：（C+ 也能用，cin,cout,scanf,printf 可混用）#include int main() int a,b

24、; freopen(“sum.in”,”r”,stdin);freopen(“sum.out”,”w”,stdout); scanf(“%d%d”,&a,&b); printf(“%dn”,a+b); return 0; 或者：freopen(“sum.in”,”r”,stdin);freopen(“sum.out”,”w”,stdout);ios:sync_with_stdio(false); 取消同步，cin,cout的速度就不慢了！ cinab;couta+bendl; return 0;以下扩充c/c+混用是可行的：#include #include using namespace s

25、td;int main() int a,b,c,d; freopen(sum.in,r,stdin); freopen(sum.out,w,stdout); scanf(%d%d,&a,&b); cincd; printf(%dn,a+b); couta+b+c+dsn).Cwhile(scanf(%s%d,s,&n)!=EOF).四、赋值语句及运算符号 一一对应的关系PascalC/C+赋值运算赋值:=基本运算加+减-乘*除（实数）/ (double)除法取整div(int) / (int)取余mod%比较等于=不等于!=大于大于等于=小于小于等于=逻辑且and&或or|非not!位运算左移

26、(*2)shl且and&或or|非not异或xor其他增一inc(x)x+减一dec(x)x- 在C/C+中对某个变量自身进行运算可以简写为 变量名 运算符号= 改变量 如 x += 8 就表示 x = x + 8， 即 inc(x, 8)。 在 C/C+里还存在一种三目运算 变量名 = 条件 ? 值A : 值B 如 x = x 0 ? x : -x; /表示若x 0 则取 x， 否则取 x， 同 if x 0 then x := x else x := -x;五、条件语句1、if C/C+中if 语句的条件必须要用括号括起来，后面不使用then。PascalC/C+if a b then f

27、lag := true else flag := false;if (a b) flag = true;else flag = false;2、多种分支 C/C+中为switch，Pascal为case：PascalC/C+case x of 1: inc(x); 2: dec(x); else x := x * x;end;switch (x) case 1: x +; break; case 2: x -; break; default: x *= x; 切记C/C+中一定要写break，后果你可以去掉break，运行看看就知道了。六、循环语句1、forPascalC/C+for 变量名

28、:= 初始值 to(downto) 终止值 dofor (变量名=初始值;条件;改变方式)for i := 5 to 10 do dec(a);/终止值大于初始值用 tofor i := 5 downto 1 do dec(a);/终止值小于于初始值用 downtofor (i = 5; i = 1; i-) a-;/*只要i 满足条件就会一直循环。C/C+中i是实数、指针都可以*/C/C+中for的特殊用法：/变量为实数for (double i = 1; i 符号为间接引用，后面会提到。for (type1 *p = head - next; p; p = p - next) printf

29、(“%d”, p - k);2、whilePascalC/C+while 条件 dowhile (条件)while i 0 do dec(i);while (i != 0) i-;/也可写作 while (i) i-;/在C/C+中非0即为真。3、repeat-until & do-whilePascalC/C+repeat 语句 until 结束条件;do while (运行条件)repeat int(i) until i 100;do i+; while (i = 100);七、数组 Pascal中数组的下标可以随意定义，而C/C+下标始终为从0开始到(数组大小1)。PascalC/C+定

30、义a : array 1.100 of integer;b :array 1.10,1.10 of int64;int a100;int b1010;含义a 为大小为100的integer数组，合法下标为1到100b 为大小为10*10的int64数组，合法下标为1,1到10,10a 为大小为100的int数组，合法下标为0到99b 为大小为10*10的int数组，合法下标为0,0到9,9;使用inc(a21);b2,2:=b1,1+b1,2+b2,1;a21+;b11=b01+b00+b10; 数组清零PascalC/C+Fillchar(a, sizeof(a), 0);memset(a,

31、 0, sizeof(a);/头文件包含 string.h*如果要填最大： memset(a,127,sizeof(a) （但达不到 INT_MAX） 如果要填最小： memset(a,128,sizeof(a) (但达不到 INT_MIN） 如果填0： memset(a,0,sizeof(a) 如果填-1： memset(a,-1,sizeof(a)八、字符串 C风格的字符串就是字符数组。 C+和Pascal的字符串使用基本相同，只是C+中字符串下标以0开始，Pascal以1开始。字符串处理很多这里不一一列举，只写最常用的几个。PascalC (包含)定义用：char sC+（包含）定义用：

32、string s输入输出Readln(s);Writeln(s);Scanf(“%s”,s);Printf(“%sn”,s);注：不能输入输出c+的字符串Cins;Couts = s 的区别： getline(cin,s)cins一次性整行读入，直至行末尾。只读入一个“单词”，遇空格和行末停止。例如输入；How are you?s=” How are you?”读入整串含空格例如输入；How are you?s=”How”如果三个都读：cins1s2s3*C+ 数字与数值之间的转换：#include #include #include /必须加入using namespace std;int

33、main() string text = 152; int number; stringstream ss;ss number; /string - int coutnumber+100endl; ss string string str = ss.str(); return 0;九、过程和函数1、过程 在C/C+中没有过程，但可以把返回值为“空”的函数理解为过程。PascalC/C+无参过程procedure 过程名;说明部分begin 语句部分 end;/说明部分、begin、end语句部分统称为过程体void 函数名(); 主体部分; return ;带参过程procedure 过程名(

34、形参表)过程体void 函数名(形参表)过程体 值传和址传：当一个参数是值传时，形参在子过程中相当于一个局部变量，对它的改变不影响实在的参数值。址传则会影响。下例中a为值传，b为址传。初始a = 5,b = 5，运行后a = 5,b = 10；PascalC/C+var a, b:integer;procedure doit(a:integer; var b:integer);begin b := a + b; a := a + b;end;begina := 5;b := 5;doit(a, b);writeln(a, , b);end.void doit(int a, int &b) HY

35、PERLINK a a认为值参，b认为变量传参 b += a; a += b; return ;int main()int a = 5, b = 5;doit(a, b);cout a b;return 0;* 用若干地址传参可以给调用者传回若干值 Void tryit(int &x,int &y,int &z) 调用时: tryit(a,b,c) ,可以传回 a,b,c的值。* 用数组名（也是地址）传参可以传回整组的数据 Void tryit( int a) 调用时: tryit(x),可以传回整个数组。例如：void tryit(int a) for(int i=0;i=10;i+) ai

36、=i*2; return; int main() int x10; tryit(x); for(int i=0;i=10;i+) coutxiendl; system(pause); return 0;*用指向函数的指针作为参数，可以执行指定的函数。(略)STL 的两个应用：* C+ 快排函数#include Bool com(int a,int b) Return ab;Int main() Int a10=5,7,3,2,6,8,4,3,5,7;Sort(a,a+10,com); /如果升序可以省略com.For(int i=0;i10;i+) Coutai” “;* 优先队列（以堆排为例

37、）#include #include using namespace std;priority_queue Q;int main() int n,a; cinn; while (n-) cina; Q.push(a); while (!Q.empty() cout Q.top() ; Q.pop(); return 0;* 队列、栈、优先队列 三种数据结构汇总：#include #include priority_queue Q;queue Q1;stack S;int main()Q.push(5); x = Q.top(); Q.pop();Q.empty()；Q.size()Q1.push(5); Q1.size(); Q1.front(); Q1.empty(); Q1.pop();S.push(5); S.size(); S.top(); S.emtpy(); S.pop();2、函数 . PascalC/C+funtion 函数名(形参表):返回值类型;函数体返回值类型 函数名(形参表) 主体; return 返回值; 注意在Pascal中： 在函数体的语句部分中，必须有对应的函数标识符赋值的语句，并且这些语句在函数被引用时至少要有一句被执行，最后赋给函数标识符的值就是函数值。或者exit(返回值);下面为求n阶乘的样例：PascalC/C+fun