当前位置：文档之家› 信息论与编码实验报告

信息论与编码实验报告

学院：计算机与通信工程学院

专业：计算机科学与技术

班级：计1203班

学号：

姓名：

2014年12月29日

实验一唯一可译码判别准则

实验目的：

1.进一步熟悉唯一可译码判别准则；

2.掌握C语言字符串处理程序的设计和调试技术。

实验内容：

1.已知：信源符号数和码字集合C；

2.输入：任意的一个码，码字的个数和每个具体的码字在运行时从键盘输入；

3.输出：判决（是唯一可译码/不是唯一可译码）；循环（若继续判决则输入1循环判决，否则输入0结束运行）。

实验原理：

根据唯一可译码的判别方法，利用数据结构所学的知识，定义字符串数据类型并利用指针进行编程来实现算法。

算法：1、考察C 中所有的码字，若Wi是Wj的前缀，则将对应的后缀作为一个尾随后缀码放入集合Fi+1中；

2、考察C和Fi俩个集合，若Wi ∈C是Wj∈F的前缀或Wi ∈F是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；

3、F=∪Fi即为码C的尾随后缀集合；

4、若F中出现了C中的元素，算法终止，返回假（C不是唯一可译码）；否则若F中没有出现新的元素，则返回真。

实验环境及实验文件存档名：

1.实验环境：visual C++ 6.0

2.文件名：weiyikeyi.cpp

实验结果及分析：

1.源代码：

#include

char c[100][50];

char f[300][50];

int N,sum=0; //N为输入码字的个数，sum为尾随后缀集合中码字的个数

int flag;//判断是否唯一可译标志位

void patterson(char c[],char d[]) //检测尾随后缀

{

int i,j,k;

for(i=0;;i++)

{

if(c[i]=='\0'&&d[i]=='\0')//2字符串一样，跳出

break;

if(c[i]=='\0') //d比c长，将d的尾随后缀放入f中

{

for(j=i;d[j]!='\0';j++) f[sum][j-i]=d[j];

f[sum][j-i]='\0';

for(k=0;k

{

if(strcmp(f[sum],f[k])==0) //查看当前生成的尾随后缀在f集合中是否存在

{

sum--;break;

}

sum++;

break;

}

if(d[i]=='\0') //c比d长，将c的尾随后缀放入f中

{

for(j=i;c[j]!='\0';j++) f[sum][j-i]=c[j];

f[sum][j-i]='\0';

for(k=0;k

{

if(strcmp(f[sum],f[k])==0) //查看当前生成的尾随后缀在f集合中是否存在

{

sum--;break;

}

sum++;

break;

}

if(c[i]!=d[i])//字符不一样了也退出

break;

}

void yima()

{

int i,j;

printf(" ********唯一可译码判别********\n");

printf("请输入码字的个数:");//输入码得个数

scanf("%d",&N);

while(N>100)

{

printf("输入码字个数过大，请输入小于100的数\n");

printf("请输入码字的个数:");

scanf("%d",&N);

}

flag=0;

printf("请分别输入码字:\n");

for(i=0;i

{

scanf("%s",&c[i]);

}

for(i=0;i

for(j=i+1;j

{

if(strcmp(c[i],c[j])==0)

{flag=1;break;}

}

if(flag==1)//如果码本身有重复，就可以断定它不是唯一可译码

{

printf("这不是唯一可译码。\n");

}

else

{

for(i=0;i

{

for(j=i+1;j

{

patterson(c[i],c[j]);

}

for(i=0;;i++) //根据原始码与s[i]生成s[i+1]也放入f[i]

{

int s=0;

for(j=0;j

{

if(i==sum)

{ s=1;break;}

else

patterson(f[i],c[j]);

}

if(s==1)break;

}

for(i=0;i

{

for(j=0;j

{

if(strcmp(f[i],c[j])==0)

{

flag=1;

break;

}

if(flag==1)

{

printf("这不是唯一可译码！\n");

}

else

printf("这是唯一可译码！\n");

}

void main()

{

int flag=1;

while(flag){

yima();

printf("是否继续判别？1/0\n");

scanf("%d",&flag);

}

2.运行结果

（1）输入0,01,001时：

（2）继续执行，输入1,01,10,1010

（3）结束执行

实验二霍夫曼编码

实验目的：

1.进一步熟悉Huffman 编码过程；

2.掌握C 语言递归程序的设计和调试技术。

实验内容：

1. 输入：信源符号个数r 、信源的概率分布P ；

2. 输出：每个信源符号对应的Huffman 编码的码字。

实验原理：

1.将q 个信源符合按概率大小递减排列()()()s s s q

p p p ≥≥21; 2.用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源

s 1； 3.把缩减信源s 1

的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源s 2；

4.依次继续下去，直至信源符号最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；

5.然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即对应的码字。

实验环境及实验文件存档名：

1.实验环境：visual C++ 6.0

2.文件名：Huffman.cpp

实验结果及分析：

1.程序源代码：

#include

#define N 50

#define maxval 10000.0

#define maxsize 100

typedef struct

{

char ch;

float weight;

int lchild,rchild,parent;

}hufmtree;

typedef struct

{

char bits[N]; //位串

int start; //编码在位串中的起始位置

char ch; //字符

}codetype;

void huffman(hufmtree tree[]);//建立哈夫曼树

void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码

int n;

int m;

void main()

{

printf("输入信源符号个数\n");

scanf("%d",&n);

getchar();

m = 2*n-1;

printf(" *****霍夫曼哈夫曼编码*****\n");

printf("总共有%d个字符\n",n);

hufmtree tree[2*N-1];

codetype code[N];

int i,j;//循环变量

huffman(tree);//建立哈夫曼树

huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码

printf("输出每个字符的哈夫曼编码\n");

for(i=0;i

{

printf("%c: ",code[i].ch);

for(j=code[i].start;j

printf("%c ",code[i].bits[j]);

printf("\n");

}

void huffman(hufmtree tree[])//建立哈夫曼树

{

int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标float small1,small2,f;

char c;

for(i=0;i

{

tree[i].parent=0;

tree[i].lchild=-1;

tree[i].rchild=-1;

tree[i].weight=0.0;

}

printf("依次读入前%d个结点的字符及权值(中间用空格隔开)\n",n);

for(i=0;i

{

printf("输入第%d个字符为和权值",i+1);

scanf("%c %f",&c,&f);

getchar();

tree[i].ch=c;

tree[i].weight=f;

}

for(i=n;i

{

p1=0;p2=0;

small1=maxval;small2=maxval; //maxval是float类型的最大值

for(j=0;j

if(tree[j].parent==0)

if(tree[j].weight

{

small2=small1; //改变最小权、次小权及对应的位置

small1=tree[j].weight;

p2=p1;

p1=j;

}

else

if(tree[j].weight

{

small2=tree[j].weight; //改变次小权及位置

p2=j;

}

tree[p1].parent=i;

tree[p2].parent=i;

tree[i].lchild=p1; //最小权根结点是新结点的左孩子

tree[i].rchild=p2; //次小权根结点是新结点的右孩子

tree[i].weight=tree[p1].weight+tree[p2].weight;

}

}//huffman

void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码//codetype code[]为求出的哈夫曼编码

//hufmtree tree[]为已知的哈夫曼树

{

int i,c,p;

codetype cd; //缓冲变量

for(i=0;i

{

cd.start=n;

cd.ch=tree[i].ch;

c=i; //从叶结点出发向上回溯

p=tree[i].parent; //tree[p]是tree[i]的双亲

while(p!=0)

{

cd.start--;

if(tree[p].lchild==c)

cd.bits[cd.start]='0'; //tree[i]是左子树，生成代码'0' else

cd.bits[cd.start]='1'; //tree[i]是右子树，生成代码'1' c=p;

p=tree[p].parent;

}

code[i]=cd; //第i+1个字符的编码存入code[i]

}

2.运行结果

信息论与编码实验

实验五霍夫曼编码一、实验目的 1、熟悉Matlab 工作环境及工具箱； 2、掌握霍夫曼编码的基本步骤； 3、利用MATLAB实现霍夫曼编码。二、实验内容（1）熟悉理解Huffman编码的过程（2）将给定的数据进行Huffman编码知识要点： 1、霍夫曼编码的基本原理。参照教材及参考书。 2、二进制霍夫曼编码方法。 1. 基本原理：变长编码不要求所有码字长度相同，对不同概率的信源符号或序列，可赋予不同长度的码字。变长编码力求平均码长最小，此时编码效率最高，信源的冗余得到最大程度的压缩。 1）几种常用变长编码方法：霍夫曼编码费若编码香农编码。 2）霍夫曼编码：二进制霍夫曼编码 r进制霍夫曼编码符号序列的霍夫曼编码。 3）二进制霍夫曼编码的编码过程：将信源中n个符号按概率分布的大小，以递减次序排列起来；用0和1码分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新符号，并用这两个最小概率之和作为新符号的概率，从而得到只包含n-1个符号的新信源，称为其缩减信源；把缩减信源的符号仍按概率大小以递减次序排列，再将最后两个概率最小的符号合并

成一个新符号，并分别用0和1码表示，这样又形成一个新缩减信源；依次继续下去，直到缩减信源最后只剩两个符号为止。再将最后两个新符号分别用0和1 码符号表示。最后这两个符号的概率之和为1，然后从最后一级缩减信源开始，依编码路径右后向前返回，就得到各信源符号所对应得码符号序列，即对应得码字。 r进制霍夫曼编码由二进制霍夫曼编码可推广到r进制霍夫曼编码，只是每次求缩减信源时，改求r个最小概率之和，即将r个概率最小符号缩减为一个新符号，直到概率之和为1。但要注意，即缩减过程中可能到最后没有r个符号。为达次目的，可给信源添加几个概率为零的符号。符号序列的霍夫曼编码对信源编码除了对信源符号编码以外，也可对信源符号序列编码，一般来说，对序列编码比对单个符号更为有效。 2 数据结构与算法描述 1）变量及函数的定义 3 实验数据与实验结果（可用文字描述或贴图的方式进行说明） 1）测试数据 0.2 0.1 0.3 0.1 0.1 0.2 2）实验结果

信息论与编码理论习题答案

信息论与编码理论习题答案 LG GROUP system office room 【LGA16H-LGYY-LGUA8Q8-LGA162】

第二章信息量和熵八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息量。解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log = bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log = bit 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？解：(a) )(a p =! 521 信息量=) (1 log a p =!52log = bit (b) ? ??????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C = bit 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和， Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。

信息论与编码课后习题答案

1．有一个马尔可夫信源，已知p(x 1|x 1)=2/3，p(x 2|x 1)=1/3，p(x 1|x 2)=1，p(x 2|x 2)=0，试画出该信源的香农线图，并求出信源熵。解：该信源的香农线图为： 1/3 ○ ○ 2/3 (x 1) 1 (x 2) 在计算信源熵之前，先用转移概率求稳定状态下二个状态x 1和 x 2 的概率)(1x p 和)(2x p 立方程：)()()(1111x p x x p x p =+)()(221x p x x p =)()(2132x p x p + )()()(1122x p x x p x p =+)()(222x p x x p =)(0)(2131x p x p + )()(21x p x p +=1 得4 3 1)(=x p 4 12)(=x p 马尔可夫信源熵H = ∑∑- I J i j i j i x x p x x p x p )(log )()( 得 H=0.689bit/符号 2．设有一个无记忆信源发出符号A 和B ，已知4 341)(.)(= =B p A p 。求： ①计算该信源熵； ②设该信源改为发出二重符号序列消息的信源，采用费诺编码方法，求其平均信息传输速率； ③又设该信源改为发三重序列消息的信源，采用霍夫曼编码方法，求其平均信息传输速率。解：①∑- =X i i x p x p X H )(log )()( =0.812 bit/符号 ②发出二重符号序列消息的信源,发出四种消息的概率分别为用费诺编码方法代码组 b i BB 0 1 BA 10 2 AB 110 3 AA 111 3 无记忆信源 624.1)(2)(2 ==X H X H bit/双符号平均代码组长度 2B =1.687 bit/双符号 B X H R )(22==0.963 bit/码元时间 ③三重符号序列消息有8个,它们的概率分别为用霍夫曼编码方法代码组 b i BBB 64 27 0 0 1 BBA 64 9 0 )(6419 1 110 3

信息论与编码实验报告.

本科生实验报告实验课程信息论与编码学院名称信息科学与技术学院专业名称通信工程学生姓名学生学号指导教师谢振东实验地点6C601 实验成绩二〇一五年十一月二〇一五年十一月

实验一：香农（Shannon ）编码一、实验目的掌握通过计算机实现香农编码的方法。二、实验要求对于给定的信源的概率分布，按照香农编码的方法进行计算机实现。三、实验基本原理给定某个信源符号的概率分布，通过以下的步骤进行香农编码 1、将信源消息符号按其出现的概率大小排列 )()()(21n x p x p x p ≥≥≥ 2、确定满足下列不等式的整数码长K i ； 1)(l o g )(l o g 22+-<≤-i i i x p K x p 3、为了编成唯一可译码，计算第i 个消息的累加概率 ∑ -== 1 1 )(i k k i x p p 4、将累加概率P i 变换成二进制数。 5、取P i 二进制数的小数点后K i 位即为该消息符号的二进制码。四、源程序： #include #include #include #include #include using namespace std; int main() { int N; cout<<"请输入信源符号个数：";cin>>N; cout<<"请输入各符号的概率："<

int i,j; for(i=0;i

信息论与编码习题参考答案

bit/s 104.98310661.130)/)(()/(R bit/frame 10661.1322.3105)(H 105)(H bit/pels 322.310log )(log )()(H 76650510 10?=??=?=∴?=??=??====∑=frame bit X H s frame r x X a p a p x i i i 所需信息速率为：每帧图像的熵是：每个像素的熵是：，由熵的极值性：由于亮度电平等概出现 . 5.2,,5.25.2477.210 log 300log )(H )(H pels /bit 300log )(log )()(H bit 3001030,10,,3001300 11倍左右比黑白电视系统高彩色电视系统信息率要图形所以传输相同的倍作用大信息量比黑白电视系统彩色电视系统每个像素每个像素的熵是：量化所以每个像素需要用个亮度每个色彩度需要求下在满足黑白电视系统要个不同色彩度增加∴≈====∴=?∑=x x b p b p x i i i 个汉字最少需要数描述一帧图像需要汉字每个汉字所包含信息量每个汉字所出现概率每帧图象所含信息量556 6 5 5 10322.6/10322.61 .0log 101.2)()()()(,log H(c):1.010000 1000 symble /bit 101.2128log 103)(103)(: ?∴?=-?=≥ ≤-=∴== ?=??=??=frame c H X H n c nH X H n p p x H X H ),...,,(21n p p p n m ≤≤0∑=-=m i i m p q 1 1)log(),,...,,(),...,,(2121m n q q p p p H p p p H m m m n -+≤ ∑∑+==- -=>-=<-=''-=''∴>- =''-=''>-=n m i i i m i i i n p p p p p p p H x x x x f x e x x x f x x e x x x f x x x x f 1 121log log ),...,,( )0(log )( 0log )log ()(0 log )log ()()0(log )( 又为凸函数。即又为凸函数，如下：先证明时等式成立。当且仅当时等式成立。当且仅当即可得：的算术平均值的函数，函数的平均值小于变量由凸函数的性质，变量n m m m m m n m m m i i i m m m m m m i i i n m i i i m i i i n n m m m m m n m i i i m m n m i i n m i i n m i i n m i i n m i i i p p p m n q q p p p H p p p H q q p p q p p p H m n q q q p p p p p p p p p H p p p m n q q q p p m n q q m n p m n p m n m n p f m n m n p f m n p p ===-+≤--=-+--≤- -=∴===-+-≤- --=----=---≤---=- ++==+==+++=+=+=+=+=+=∑∑∑∑∑∑∑∑∑ ∑...)log(),,...,,(),...,,(log log ),,...,,() log(log log log log ),...,,(...) log(log log log log )()()() ()(log 2121211 211 1 1 21211 1111 1 X n

信息论与编码实验报告材料

实验报告课程名称：信息论与编码姓名：系：专业：年级：学号：指导教师：职称：

年月日目录实验一信源熵值的计算 (1) 实验二Huffman 信源编码. (5) 实验三Shannon 编码 (9) 实验四信道容量的迭代算法 (12) 实验五率失真函数 (15) 实验六差错控制方法 (20) 实验七汉明编码 (22)

实验一信源熵值的计算、实验目的 1 进一步熟悉信源熵值的计算 2 熟悉Matlab 编程、实验原理熵(平均自信息)的计算公式 q q 1 H(x) p i log2 p i log2 p i i 1 p i i 1 MATLAB实现：HX sum( x.* log2( x))；或者h h x(i)* log 2 (x(i )) 流程：第一步：打开一个名为“ nan311”的TXT文档，读入一篇英文文章存入一个数组temp，为了程序准确性将所读内容转存到另一个数组S，计算该数组中每个字母与空格的出现次数( 遇到小写字母都将其转化为大写字母进行计数) ，每出现一次该字符的计数器+1；第二步：计算信源总大小计算出每个字母和空格出现的概率；最后，通过统计数据和信息熵公式计算出所求信源熵值(本程序中单位为奈特nat )。程序流程图：三、实验内容 1、写出计算自信息量的Matlab 程序 2、已知：信源符号为英文字母(不区分大小写)和空格输入：一篇英文的信源文档。输出：给出该信源文档的中各个字母与空格的概率分布，以及该信源的熵。四、实验环境 Microsoft Windows 7

五、编码程序 #include"stdio.h" #include #include #define N 1000 int main(void) { char s[N]; int i,n=0; float num[27]={0}; double result=0,p[27]={0}; FILE *f; char *temp=new char[485]; f=fopen("nan311.txt","r"); while (!feof(f)) { fread(temp,1, 486, f);} fclose(f); s[0]=*temp; for(i=0;i='a'&&s[i]<='z') num[s[i]-97]++; else if(s[i]>='A'&&s[i]<='Z') num[s[i]-65]++; } printf（" 文档中各个字母出现的频率:\n"）; for(i=0;i<26;i++) { p[i]=num[i]/strlen(s); printf("%3c:%f\t",i+65,p[i]); n++; if(n==3) { printf("\n"); n=0; } } p[26]=num[26]/strlen(s); printf(" 空格:%f\t",p[26]);

信息论与编码理论课后习题答案高等教育出版社

信息论与编码理论习题解第二章-信息量和熵解: 平均每个符号长为:154 4.0312.032= ?+?秒每个符号的熵为9183.03log 3 1 23log 32=?+?比特/符号所以信息速率为444.34 15 9183.0=?比特/秒解: 同步信号均相同不含信息,其余认为等概, 每个码字的信息量为 3*2=6 比特；所以信息速率为600010006=?比特/秒解:(a)一对骰子总点数为7的概率是 36 6 所以得到的信息量为 585.2)366(log 2= 比特 (b) 一对骰子总点数为12的概率是36 1 所以得到的信息量为 17.536 1 log 2= 比特解: (a)任一特定排列的概率为 ! 521 ,所以给出的信息量为 58.225! 521 log 2 =- 比特 (b) 从中任取13张牌,所给出的点数都不相同的概率为 1352 13 13 521344!13C A =? 所以得到的信息量为 21.134 log 1313 52 2=C 比特. 解:易证每次出现i 点的概率为 21 i ,所以

比特比特比特比特比特比特比特398.221 log 21)(807.1)6(070.2)5(392.2)4(807.2)3(392.3)2(392.4)1(6,5,4,3,2,1,21 log )(26 12=-==============-==∑ =i i X H x I x I x I x I x I x I i i i x I i 解: 可能有的排列总数为 27720! 5!4!3! 12= 没有两棵梧桐树相邻的排列数可如下图求得， Y X Y X Y X Y X Y X Y X Y X Y 图中X 表示白杨或白桦，它有???? ??37种排法，Y 表示梧桐树可以栽种的位置，它有???? ??58种排法，所以共有???? ??58*???? ??37=1960种排法保证没有两棵梧桐树相邻，因此若告诉你没有两棵梧桐树相邻时，得到关于树排列的信息为1960log 27720log 22-= 比特解: X=0表示未录取，X=1表示录取； Y=0表示本市，Y=1表示外地； Z=0表示学过英语，Z=1表示未学过英语，由此得

《信息论与信源编码》实验报告

《信息论与信源编码》实验报告 1、实验目的 (1) 理解信源编码的基本原理； (2) 熟练掌握Huffman编码的方法； (3) 理解无失真信源编码和限失真编码方法在实际图像信源编码应用中的差异。 2、实验设备与软件 (1) PC计算机系统 (2) VC++6.0语言编程环境 (3) 基于VC++6.0的图像处理实验基本程序框架imageprocessing_S (4) 常用图像浏览编辑软件Acdsee和数据压缩软件winrar。 (5) 实验所需要的bmp格式图像（灰度图象若干幅） 3、实验内容与步骤 (1) 针对“图像1.bmp”、“图像2.bmp”和“图像3.bmp”进行灰度频率统计（即计算图像灰度直方图），在此基础上添加函数代码构造Huffman码表，针对图像数据进行Huffman编码，观察和分析不同图像信源的编码效率和压缩比。 (2) 利用图像处理软件Acdsee将“图像1.bmp”、“图像2.bmp”和“图像 3.bmp”转换为质量因子为10、50、90的JPG格式图像（共生成9幅JPG图像），比较图像格式转换前后数据量的差异，比较不同品质因素对图像质量的影响； (3) 数据压缩软件winrar将“图像1.bmp”、“图像2.bmp”和“图像3.bmp”分别生成压缩包文件，观察和分析压缩前后数据量的差异； (4) 针对任意一幅图像，比较原始BMP图像数据量、Huffman编码后的数据量（不含码表）、品质因素分别为10、50、90时的JPG文件数据量和rar压缩包的数据量，分析不同编码方案下图像数据量变化的原因。 4、实验结果及分析 (1)在VC环境下，添加代码构造Huffman编码表，对比试验结果如下： a.图像1.bmp：

信息论与编码课后答案

一个马尔可夫信源有3个符号{}1,23,u u u ，转移概率为：()11|1/2p u u =，()21|1/2p u u =， ()31|0p u u =，()12|1/3p u u =，()22|0p u u =，()32|2/3p u u =，()13|1/3p u u =，()23|2/3p u u =，()33|0p u u =，画出状态图并求出各符号稳态概率。解：状态图如下状态转移矩阵为： 1/21/2 01/302/31/32/30p ?? ?= ? ??? 设状态u 1，u 2，u 3稳定后的概率分别为W 1，W 2、W 3 由1231WP W W W W =??++=?得1231132231231 112331223 231W W W W W W W W W W W W ?++=???+=???=???++=? 计算可得1231025925625W W W ?=??? =?? ?=?? 由符号集{0，1}组成的二阶马尔可夫链，其转移概率为：(0|00)p =，(0|11)p =，(1|00)p =， (1|11)p =，(0|01)p =，(0|10)p =，(1|01)p =，(1|10)p =。画出状态图，并计算各状态的稳态概率。解：(0|00)(00|00)0.8p p == (0|01)(10|01)0.5p p == (0|11)(10|11)0.2p p == (0|10)(00|10)0.5p p == (1|00)(01|00)0.2p p == (1|01)(11|01)0.5p p == (1|11)(11|11)0.8p p == (1|10)(01|10)0.5p p ==

信息论与编码实验报告

实验一绘制二进熵函数曲线（2个学时）一、实验目的： 1. 掌握Excel 的数据填充、公式运算和图表制作 2. 掌握Matlab 绘图函数 3. 掌握、理解熵函数表达式及其性质二、实验要求： 1. 提前预习实验，认真阅读实验原理以及相应的参考书。 2. 在实验报告中给出二进制熵函数曲线图三、实验原理： 1. Excel 的图表功能 2. 信源熵的概念及性质 ()()[] ()[]())(1)(1 .log )( .) ( 1log 1log ) (log )()(10 , 110)(21Q H P H Q P H b n X H a p H p p p p x p x p X H p p p x x X P X i i i λλλλ-+≥-+≤=--+-=-=≤≤? ?????-===??????∑ 单位为比特/符号或比特/符号序列。当某一符号xi 的概率p(xi)为零时，p(xi)log p(xi) 在熵公式中无意义，为此规定这时的 p(xi)log p(xi) 也为零。当信源X 中只含有一个符号x 时，必有p(x)=1，此时信源熵H （X ）为零。四、实验内容：用Excel 和Matlab 软件制作二进熵函数曲线。根据曲线说明信源熵的物理意义。（一） 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)-(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) 五、实验结果

信息论与编码理论习题答案全解

第二章信息量和熵 2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息量。解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p =366=6 1 得到的信息量 =) (1 log a p =6log =2.585 bit (2) 可能的唯一，为 {6，6} )(b p =361 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克（52张），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13张牌，所给出的点数都不相同时得到多少信息量？解：(a) )(a p =! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit

信息论与编码试题集与答案(新)

一填空题（本题20分，每小题2分） 1、平均自信息为表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。平均互信息表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2、最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。 3、最大熵值为。 4、通信系统模型如下： 5、香农公式为为保证足够大的信道容量，可采用（1）用频带换信噪比；（2）用信噪比换频带。

6、只要，当N足够长时，一定存在一种无失真编码。 7、当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8、在认识论层次上研究信息的时候，必须同时考虑到形式、含义和效用三个方面的因素。 9、1948年，美国数学家香农发表了题为“通信的数学理论”的长篇论文，从而创立了信息论。按照信息的性质，可以把信息分成语法信息、语义信息和语用信息。按照信息的地位，可以把信息分成客观信息和主观信息。人们研究信息论的目的是为了高效、可靠、安全地交换和利用各种各样的信息。信息的可度量性是建立信息论的基础。统计度量是信息度量最常用的方法。熵是香农信息论最基本最重要的概念。事物的不确定度是用时间统计发生概率的对数来描述的。 10、单符号离散信源一般用随机变量描述，而多符号离散信源一般用随机矢量描述。 11、一个随机事件发生某一结果后所带来的信息量称为自信息量，定义为其发生概率对

数的负值。 12、自信息量的单位一般有比特、奈特和哈特。 13、必然事件的自信息是 0 。 14、不可能事件的自信息量是 ∞ 。 15、两个相互独立的随机变量的联合自信息量等于两个自信息量之和。 16、数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量趋于变小。 17、离散平稳无记忆信源X 的N 次扩展信源的熵等于离散信源X 的熵的 N 倍。 18、离散平稳有记忆信源的极限熵，=∞H )/(lim 121-∞→N N N X X X X H 。 19、对于n 元m 阶马尔可夫信源，其状态空间共有 nm 个不同的状态。 20、一维连续随即变量X 在[a ，b]区间内均匀分布时，其信源熵为 log2（b-a ）。 21、平均功率为P 的高斯分布的连续信源，其信源熵，Hc （X ）=eP π2log 21 2。 22、对于限峰值功率的N 维连续信源，当概率密度均匀分布时连续信源熵具有最大值。 23、对于限平均功率的一维连续信源，当概率密度高斯分布时，信源熵有最大值。 24、对于均值为0，平均功率受限的连续信源，信源的冗余度决定于平均功率的限定值P 和信源的熵功率P 之比。

信息论与编码实验报告

信息论与编码实验报告-标准化文件发布号：（9456-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII

实验一关于硬币称重问题的探讨一、问题描述：假设有N 个硬币，这N 个硬币中或许存在一个特殊的硬币，这个硬币或轻或重，而且在外观上和其他的硬币没什么区别。现在有一个标准天平，但是无刻度。现在要找出这个硬币，并且知道它到底是比真的硬币重还是轻，或者所有硬币都是真的。请问： 1）至少要称多少次才能达到目的； 2）如果N=12，是否能在3 次之内将特殊的硬币找到；如果可以，要怎么称？二、问题分析：对于这个命题，有几处需要注意的地方： 1）特殊的硬币可能存在，但也可能不存在，即使存在，其或轻或重未知； 2）在目的上，不光要找到这只硬币，还要确定它是重还是轻； 3）天平没有刻度，不能记录每次的读数，只能判断是左边重还是右边重，亦或者是两边平衡； 4）最多只能称3 次。三、解决方案： 1.关于可行性的分析在这里，我们把称量的过程看成一种信息的获取过程。对于N 个硬币，他们可能的情况为2N+1 种，即重（N 种），轻（N 种）或者无假币（1 种）。由于这2N+1 种情况是等概率的，这个事件的不确定度为： Y=Log(2N+1) 对于称量的过程，其实也是信息的获取过程，一是不确定度逐步消除的过程。每一次称量只有3 种情况：左边重，右边重，平衡。这3 种情况也是等概率的，所以他所提供的信息量为： y=Log3 在K 次测量中，要将事件的不确定度完全消除，所以 K= Log(2N+1)/ Log3 根据上式，当N=12 时，K= 2.92< 3 所以13 只硬币是可以在3 次称量中达到

信息论与编码理论第二章习题答案

I (X ;Y=1)= P(x/Y 1)I(x;Y 1) x P(x/Y 1)log P(x/Y 1) P(x) = P(X 0/Y 1)log P(X 0/Y 1) P(X 0) P(X 1/Y 1)log P(X 1/Y 1) P(X 1) 部分答案，仅供参考。信息速率是指平均每秒传输的信息量点和划出现的信息量分别为log3Jog3， 2’ 一秒钟点和划出现的次数平均为 1 15 2 1 ~4 0.20.4 - 3 3 一秒钟点和划分别出现的次数平均为巴5 4 4 那么根据两者出现的次数，可以计算一秒钟其信息量平均为10 log 3 5 竺 5 4 2 4 4 2 解： ⑻骰子A和B，掷出7点有以下6种可能： A=1,B=6; A=2,B=5; A=3,B=4; A=4,B=3; A=5,B=2; A=6,B=1 概率为6/36=1/6，所以信息量 -log(1/6)=1+log3 ~ bit (b)骰子A和B,掷出12点只有1种可能： A=6,B=6 概率为1/36，所以信息量 -log(1/36)=2+log9 ~ bit 解：出现各点数的概率和信息量： 1 点：1/21 , log21 ?bit ; 2 点：2/21 , log21-1 ?bit ; 3 点：1/7 , log7 4 点：4/21 , log21-2 5 点：5/21 , log (21/5 )~; 6 点：2/ 7 , log(7/2)? 平均信息量： (1/21) X +(2/21) X +(1/7) X +(4/21) X +(5/21) X +(2/7) 解： X=1:考生被录取；X=0考生未被录取； Y=1：考生来自本市；Y=0考生来自外地； Z=1:考生学过英语；z=o：考生未学过英语 P(X=1)=1/4, P( X=q=3/4; P( Y=1/ X=1)=1/2 ；P( Y=1/ X=0)=1/10 ；P(Z=1/ Y=1 )=1, P( Z=1/ X=0, Y=0 )=, P( Z=1/ X=1, Y=0 )=, P(Z=1/Y=0)= (a)P(X=0,Y=1)=P(Y=1/X=0)P(X=0)=, P(X=1,Y=1)= P(Y=1/X=1)P(X=1)= P(Y=1)= P(X=0,Y=1)+ P(X=1,Y=1)= P(X=0/Y=1)=P(X=0,Y=1)/P(Y=1)=, P(X=1/Y=1)=P(X=1,Y=1)/P(Y=1)=

信息论与编码理论习题答案

第二章信息量和熵 2.2 八元编码系统，码长为3，第一个符号用于同步，每秒1000个码字，求它的信息速率。解：同步信息均相同，不含信息，因此每个码字的信息量为 2?8log =2?3=6 bit 因此，信息速率为 6?1000=6000 bit/s 2.3 掷一对无偏骰子，告诉你得到的总的点数为：(a) 7; (b) 12。问各得到多少信息量。解：(1) 可能的组合为 {1，6},{2，5},{3，4},{4，3},{5，2},{6，1} )(a p = 366=6 1 得到的信息量 =) (1 log a p =6log =2.585 bit (2) 可能的唯一，为 {6，6} )( b p = 36 1 得到的信息量=) (1 log b p =36log =5.17 bit 2.4 经过充分洗牌后的一副扑克（52），问： (a) 任何一种特定的排列所给出的信息量是多少？ (b) 若从中抽取13牌，所给出的点数都不相同时得到多少信息量？

解：(a) )(a p = ! 521 信息量=) (1 log a p =!52log =225.58 bit (b) ???????花色任选种点数任意排列 13413!13 )(b p =13 52134!13A ?=1352 13 4C 信息量=1313 52 4log log -C =13.208 bit 2.9 随机掷3颗骰子，X 表示第一颗骰子的结果，Y 表示第一和第二颗骰子的点数之和，Z 表示3颗骰子的点数之和，试求)|(Y Z H 、)|(Y X H 、),|(Y X Z H 、 )|,(Y Z X H 、)|(X Z H 。解：令第一第二第三颗骰子的结果分别为321,,x x x ，1x ，2x ，3x 相互独立，则1x X =，21x x Y +=，321x x x Z ++= )|(Y Z H =)(3x H =log 6=2.585 bit )|(X Z H =)(32x x H +=)(Y H =2?( 361log 36+362log 18+363log 12+364log 9+365log 536)+36 6log 6 =3.2744 bit )|(Y X H =)(X H -);(Y X I =)(X H -[)(Y H -)|(X Y H ] 而)|(X Y H =)(X H ，所以)|(Y X H = 2)(X H -)(Y H =1.8955 bit 或)|(Y X H =)(XY H -)(Y H =)(X H +)|(X Y H -)(Y H 而)|(X Y H =)(X H ，所以)|(Y X H =2)(X H -)(Y H =1.8955 bit

信息论霍夫曼编码

信息论与编码实验报告课程名称：信息论与编码实验名称：霍夫曼编码班级：学号：姓名：

实验目的 1、熟练掌握Huffman编码的原理及过程，并熟练运用； 2、熟练运用MATLAB应用软件，并实现Huffman编码过程。一、实验设备装有MATLAB应用软件的PC计算机。二、实验原理及过程原理： 1、将信源符号按概率从大到小的排列，令P （X1）>=P(X2)>=P(X3)......P(Xn) 2、给两个概率最小的信源符号P（Xn-1）和P（Xn）各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含（n-1）个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。 3、将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含（n-2）个符号的缩减信源S2. 4、重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。过程：用MATLAB编写代码实现Huffman编码其程序为： %哈夫曼编码的MA TLAB实现（基于0、1编码）：

clc; clear; A=[0.3,0.2,0.1,0.2,0.2];信源消息的概率序列 A=fliplr(sort(A));%按降序排列 T=A; [m,n]=size(A); B=zeros(n,n-1);%空的编码表（矩阵） for i=1:n B(i,1)=T(i);%生成编码表的第一列 end r=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%生成编码表的其他各列 for i=1:t B(i,j)=T(i); end K=find(T==r); B(n,j)=K(end);%从第二列开始，每列的最后一个元素记录特征元素在

信息论与编码习题参考答案(全)

信息论与编码习题参考答案第一章单符号离散信源 1.1同时掷一对均匀的子，试求： (1)“2和6同时出现”这一事件的自信息量； (2)“两个5同时出现”这一事件的自信息量； (3)两个点数的各种组合的熵； (4)两个点数之和的熵； (5)“两个点数中至少有一个是1”的自信息量。解： bit P a I N n P bit P a I N n P c c N 17.536log log )(361 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： (3)信源空间： bit x H 32.436log 36 62log 3615)(=??+?? =∴ (4)信源空间： bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.11136 log log )(3611333==-=∴==

1.2如有6行、8列的棋型方格，若有两个质点A 和B ，分别以等概落入任一方格，且它们的坐标分别为（Xa ，Ya ）, （Xb ，Yb ）,但A ，B 不能同时落入同一方格。（1）若仅有质点A ，求A 落入任一方格的平均信息量；（2）若已知A 已落入，求B 落入的平均信息量；（3）若A ，B 是可辨认的，求A ，B 落入的平均信息量。解： bit a P a P a a P a I a P A i 58.548log )(log )()(H 48log )(log )(481 )(:)1(48 1 i i i i i ==-=∴=-=∴= ∑=落入任一格的概率 bit b P b P b b P b I b P A i 55.547log )(log )()(H 47 log )(log )(47 1 )(:B ,)2(48 1i i i i i ==-=∴=-=∴=∑=落入任一格的概率是落入任一格的情况下在已知 bit AB P AB P AB H AB P AB I AB P AB i i i i i i i 14.11)4748log()(log )()() (log )(47 1 481)()3(47481 =?=-=-=∴?=∑?=是同时落入某两格的概率 1.3从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为0.5%.如果你问一位男士：“你是否是红绿色盲？”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量？平均每个回答中各含有多少信息量？如果你问一位女士，则她的答案中含有多少平均信息量？解： bit w P w P w P w P m m P m I w P w I bit m P m P m P m P m bit m P m I bit m P m I n n y y n n y y n n y y n n y y 0454.0log99.5%99.5%-log0.5%-0.5% )(log )()(log )()(H % 5.99log )(log )(%5.0log )(log )(36 6.0log93%93%-log7%-7% )(log )()(log )()(H 105.0%93log )(log )(84.3%7log )(log )(: =??=?-?-=-=-=-=-==??=?-?-==-=-==-=-=平均每个回答信息量：：回答“不是”的信息量回答“是”的信息量：对于女：平均每个回答信息量：：回答“不是”的信息量回答“是”的信息量：对于男士