当前位置：文档库 › 信息论三种编码

信息论三种编码

LZW编码

LZW压缩算法的基本原理：

提取原始文本文件数据中的不同字符，基于这些字符创建一个编译表，然后用编译表中的字符的索引来替代原始文本文件数据中的相应字符，减少原始数据大小。看起来和调色板图象的实现原理差不多，但是应该注意到的是，我们这里的编译表不是事先创建好的，而是根据原始文件数据动态创建的，解码时还要从已编码的数据中还原出原来的编译表.

LZW编码的流程图：

LZW编码的源代码：

#include

void copy1(char *prefix,char *s,int i,int j)

{ int k;

for(k=0;k<20;k++)

prefix[k]=0;

for(k=i;k

prefix[k-i]=s[k];

}

void main()

{int i ,j,k,n,t,m;

char s[30],prefix[30],dic[20][30]={"A","B","C"},c[20]; k=3;m=0;j=1;i=0;

printf(“Please input some words:\n");

gets(s);

while(i

{

copy1(prefix,s,i,j);

for(n=0;n

{

if(strcmp(prefix,dic[n])==0) //比较两字符串

{ j++; m=n;

if( (i+j)<=strlen(s) )

copy1(prefix,s,i,j);

else

strcpy(prefix,"");

}

printf(“%d\n",m);

if(strlen(prefix)!=0)//求字符串长度

{strcpy(dic[k],prefix);//把后面的字符复给到前面

printf("%s\n",dic[k]);}

k=k+1;

i=i+j-1;

j=1;

}

getch();

}

实验结果：

Huffman编码

Huffman编码原理简介：

霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

Huffman编码过程的几个步骤：

l）将信号源的符号按照出现概率递减的顺序排列。

2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。

3）重复进行步骤1和2直到概率相加的结果等于1为止。

4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。

5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。

Huffman编码源代码：

#include

#define sy_max 100

#define sy_max2 30

#define sy_max3 59

#define DEEP 10 /*定义sycode1类*/

typedef struct{

float weight;

int flag;int father;

int leftchilde;

int rightchilde;

}sycode1; /*定义类sycode2类*/

typedef struct{ int sy_array[sy_max2];int start;}sycode2; int main(void)

{sycode1 sy1[sy_max3];

sycode2 sy2[sy_max2],cd;

int i,j,x1,x2,n,c,p;

float m1,m2,temp,hx=0,KL=0;

printf("please input the signal's length\n");

scanf("%d",&n); /*根据输入长度，初始化编码变量*/

for(i=0;i<=2*n-1;i++)

{sy1[i].weight=0;

sy1[i].father=0;

sy1[i].flag=0;

sy1[i].leftchilde=-1;

sy1[i].rightchilde=-1;

}

printf("input the probability for every signal:\n");

/*根据输入长度，接收相应数目的概率数*/

for(i=0;i

{ printf("input %dth probability:",i+1);

scanf("%f",&temp);

sy1[i].weight=temp;

hx=hx-temp*3.332*log10(temp);

}

for(i=0;i

{

m1=m2=sy_max;

x1=x2=0;

for(j=0;j

if(sy1[j].weight

{

m2=m1;

x2=x1;

m1=sy1[j].weight;

x1=j;

}

else

if(sy1[j].weight

{

m2=sy1[j].weight;

x2=j;

}

sy1[x1].father=n+i;

sy1[x2].father=n+i; /*将找出的两棵子树合并为一棵子树*/ sy1[x1].flag=1;

sy1[x2].flag=1;

sy1[n+i].weight=sy1[x1].weight+sy1[x2].weight;

sy1[n+i].leftchilde=x1;

sy1[n+i].rightchilde=x2;

}

for(i=0;i

{

cd.start=n;

c=i;

p=sy1[c].father;

while(p!=0)

if(sy1[p].leftchilde==c) cd.sy_array[cd.start]=1;

else cd.sy_array[cd.start]=0;

cd.start=cd.start-1;

c=p;

p=sy1[p].father;

}

cd.start++;

for(j=cd.start;j<=n;j++)

{

sy2[i].sy_array[j]=cd.sy_array[j];

sy2[i].start=cd.start;

}

printf("\nweight\thuffmancode\n");

for(i=0;i

{

printf("%2.3f:\t",sy1[i].weight);

for(j=sy2[i].start;j<=n;j++)

printf("%d",sy2[i].sy_array[j]);/*计算平均码长以及信源熵*/ KL=KL+(n-sy2[i].start+1)*sy1[i].weight;

printf("\n");

}

printf("\nH(X)=%f\tKL=%f\nR=%f",hx,KL,hx/KL);

getch();

}

实验结果：

Shannon编码

Shannon编码源代码

#include

#define sy_CL 10 /*最大码长*/

#define sy_PN 100 /*最大码数*/

typedef float sy_type;

typedef struct SHNODE {sy_type pb;sy_type sy_sum;int kl;int

code[sy_CL];struct SHNODE *next;}sy_class;

sy_type sym_arry[sy_PN]; /*序列的概率*/

int sy; /*定义全局变量sy代表码数也就是符号数*/

void sy_pb_scan()

{int i;sy_type sum=0;

printf("Think you for using this Shannon program!\nPlease input length\n");

scanf("%d",&sy);printf("input%dsignal's probability:\n",sy);

printf(">>");

for(i=0;i

{scanf("%f",&sym_arry[i]);

sum=sum+sym_arry[i];

}

if(sum>1.0001||sum<0.99)

{printf("sum=%f,sum must(<0.999

sy_pb_scan();

}

} /*定义函数sy_pb_scan()，输入数据，并且检验输入概率和是否等于1*/

void sy_sort()

{ int i,j,pos;sy_type max;

for(i=0;i

{max=sym_arry[i];

pos=i;

for(j=i+1;j

if(sym_arry[j]>max)

{max=sym_arry[j];pos=j;}

sym_arry[pos]=sym_arry[i];

sym_arry[i]=max;}

} /*定义函数sy_sort()，对输入概率进行由小到大排序*/

void valuelist(sy_class *L)

{sy_class *head,*p;int j=0;int i;sy_type temp,s;head=L; temp=0;

p=head->next;

while(j

{p->sy_sum=temp;

temp=temp+p->pb;

p->kl=-3.322*log10(p->pb)+1;

{s=p->sy_sum;

for(i=0;ikl;i++)

p->code[i]=0;

for(i=0;ikl;i++)

{p->code[i]=2*s;

if(2*s>=1)s=2*s-1;

else

if(2*s==0)break;

else s=2*s;}

}

j++;

p=p->next;}

} /*算法函数*/

void codedisp(sy_class *L)

{

int i,j;

sy_class *p;

sy_type hx=0,KL=0;

p=L->next;

printf("num\tgailv\tsum\t-lb(p(ai))\tlenth\tcode\n");

printf("\n");

for(i=0;i

{printf("a%d\t%1.3f\t%1.3f\t%f\t%d\t",i,p->pb,p->sy_sum,-3.332*l og10(p->pb),p->kl);

j=0;

for(j=0;jkl;j++)

printf("%d",p->code[j]);

printf("\n");

hx=hx-p->pb*3.332*log10(p->pb); /*计算信源序列的熵*/ KL=KL+p->kl*p->pb; /*计算平均码字*/

p=p->next;

}

printf("H(x)=%f\tKL=%f\nR=%fbit/code",hx,KL,hx/KL);

/*计算编码效率*/ }

sy_class *setnull()

{ sy_class *head;

head=(sy_class *)malloc(sizeof(sy_class));

head->next=NULL;

return(head);

}

sy_class *my_creat(sy_type a[],int n)

{

sy_class *head,*p,*r;

int i;

head=setnull();

r=head;

for(i=0;i

{ p=(sy_class *)malloc(sizeof(sy_class));

p->pb=a[i];

p->next=NULL;

r->next=p;

r=p;

}

return(head);

}

int main(void) /*主函数*/

{

sy_class *head;

sy_pb_scan();

sy_sort();

head=my_creat(sym_arry,sy); valuelist(head);

codedisp(head);

getch();

}

实验结果

信息论与编码

第2章离散信息的度量本章主要内容（1）自信息的概念（2）平均自信息的概念（信源熵的概念）（3）互信息的概念（4）平均互信息的概念（5）相对熵的概念在通信系统中，信源发出的不同消息携带不同的信息量，不同的信源输出信息的能力也不同；同一消息通过载体信号在不同的信道中传输后，接收端获得的信息量不同，不同的信道传递信息的能力也不同。为了衡量一个通信系统质量好坏，必须有一些评价标准。例如误码率、接收信噪比、传信率等。而系统的传信率就是指单位时间内信道所传递的信息量。为了评价系统的传信率，必须对消息或信源所含有的信息有一个数量上的度量方法。这就是我们要研究信息度量的目的。本章将介绍信息度量的一些基础概念。 2.1自信息信源发出的消息的形式可以是语言、文字、公式、数据、声音、图像等等。信源发出信息，通过信道传送信息。假如学生上课时，教师在全部时间内仅反复说一句同样的话。显然，从后面教师（信源）发出的同一句话（消息）中，学生（信宿）得不到任何信息。同样的，把“2008年在北京召开了奥运会”这样一则消息告诉大家，那么大家也不会从中获得任何信息。从这些例子我们可以看出，学生要想再课堂上获得信息，必须要从教师那里学到事先不知道的知识。也就是说，对于信宿来说，使其获得解惑的是消息中的未知部分，借助通信，信宿明确了原来不明确的一些事情，获得了一些信息。一则消息包含有多少信息量，通过理想信道传输后信宿就可以获得多少信息量（或说消除了多少不确定性）。

2.1.1 自信息的定义绪论中我们给出了香农对于信息的定义：信息是客观事物存在方式或运动状态的不确定性的描述。一般地说，信源要发出的消息的状态应该存在着某种程度的不确定性，通过通信，将信息传给了收信者，收信者得到信息之后，消除了不确定性。这里所说的不确定性，也就是随机性，不确定性程度可以直观地看成是猜测某些随机事件是否会发生的难易程度。我们可以用概率统计方法来描述随机事件发生后提供信息的大小。即概率大的事件，出现的可能性大，不确定性小，事件发生后带给我们的信息量就少。反之，小概率事件出现的可能性小，不确定性大，事件发生后带给我们的信息量就多。定义2.1 随机事件i x 的自信息量定义为 ()log ()=-i r i I x p x （2.1）由定义可以看出，随机事件所含信息量的多少用消息出现概率的对数的负值来表示。下面我们借助通信过程的研究来分析自信息量的含义。对应在通信系统中，信源发出消息（符号）i x 的概率为()i p x ，则i x 含有的自信息量即为)(i x I ，正确传输，收信者就可以获得)(i x I 这么多的信息量。而通信过程发生前，信源发出的消息存在某种不确定性，借助通信，信宿明确了原来不明确的一些事情，获得了一些信息。通信过程消除掉的不确定性越多，信宿获得信息量就越大。所以通信系统中，自信息量)(i x I 的含义可以由两方面来理解：（1）表示信源发出符号i x 前，发出符号i x 的不确定性的大小；（2）表示信源发出符号i x 后，符号i x 提供的信息量的多少。由定义我们可以绘制出自信息量的函数曲线如图2.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 =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

信息论与编码总结

信息论与编码 1. 通信系统模型信源—信源编码—加密—信道编码—信道—信道解码—解密—信源解码—信宿 | | | （加密密钥）干扰源、窃听者（解密秘钥）信源：向通信系统提供消息的人或机器信宿：接受消息的人或机器信道：传递消息的通道，也是传送物理信号的设施干扰源：整个系统中各个干扰的集中反映，表示消息在信道中传输受干扰情况信源编码：编码器：把信源发出的消息变换成代码组，同时压缩信源的冗余度，提高通信的有效性（代码组 = 基带信号；无失真用于离散信源，限失真用于连续信源）译码器：把信道译码器输出的代码组变换成信宿所需要的消息形式基本途径：一是使各个符号尽可能互相独立，即解除相关性；二是使各个符号出现的概率尽可能相等，即概率均匀化信道编码：编码器：在信源编码器输出的代码组上增加监督码元，使之具有纠错或检错的能力，提高通信的可靠性译码器：将落在纠检错范围内的错传码元检出或纠正基本途径：增大码率或频带，即增大所需的信道容量 2. 自信息：()log ()X i i I x P x =-，或()log ()I x P x =- 表示随机事件的不确定度，或随机事件发生后给予观察者的信息量。条件自信息：//(/)log (/)X Y i j X Y i j I x y P x y =- 联合自信息：(,)log ()XY i j XY i j I x y P x y =- 3. 互信息：;(/) () (;)log log ()()()i j i j X Y i j i i j P x y P x y I x y P x P x P y == 信源的先验概率与信宿收到符号消息后计算信源各消息的后验概率的比值，表示由事件y 发生所得到的关于事件x 的信息量。 4. 信息熵：()()log ()i i i H X p x p x =-∑ 表示信源的平均不确定度，或信源输出的每个信源符号提供的平均信息量，或解除信源不确定度所需的信息量。条件熵：,(/)()log (/)i j i j i j H X Y P x y P x y =- ∑ 联合熵：,()()log ()i j i j i j H XY P x y P x y =-∑ 5. 平均互信息：,()(;)()log ()() i j i j i j i j p x y I X Y p x y p x p y =∑

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

信息论与编码理论习题解第二章-信息量和熵解: 平均每个符号长为: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)“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 )(36 1 )2(17.418log log )(362)1(36 662221111 616==-=∴====-=∴== =?==样本空间： * (3)信源空间： bit x H 32.436log 36 16236log 36215)(=??+?? =∴

bit x H 71.3636 log 366536log 3610 436log 368336log 366236log 36436log 362)(=??+?+?+??= ∴＋＋ (5) bit P a I N n P 17.111 36 log log )(3611333==-=∴== ? 如有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 =?=-=-=∴?=∑?=是同时落入某两格的概率从大量统计资料知道,男性中红绿色盲的发病率为7%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量平均每个回答中各含有多少信息量如果你问一位女士，则她的答案中含有多少平均信息量解：

信息论与编码题库(最新整理六套)

（一）一、填空题 1. 在无失真的信源中，信源输出由 H (X ) 来度量；在有失真的信源中，信源输出由 R (D ) 来度量。 2. 要使通信系统做到传输信息有效、可靠和保密，必须首先信源编码，然后_____加密____编码，再______信道_____编码，最后送入信道。 3. 带限AWGN 波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是log(1)C W SNR =+；当归一化信道容量C/W 趋近于零时，也即信道完全丧失了通信能力，此时E b /N 0为 -1.6 dB ，我们将它称作香农限，是一切编码方式所能达到的理论极限。 4. 保密系统的密钥量越小，密钥熵H (K )就越小，其密文中含有的关于明文的信息量I (M ； C )就越大。 5. 已知n ＝7的循环码4 2 ()1g x x x x =+++，则信息位长度k 为 3 ，校验多项式 h(x)= 31x x ++ 。 6. 设输入符号表为X ＝{0，1}，输出符号表为Y ＝{0，1}。输入信号的概率分布为p ＝(1/2，1/2)，失真函数为d (0，0) = d (1，1) = 0，d (0，1) =2，d (1，0) = 1，则D min ＝ 0 ， R (D min )＝ 1bit/symbol ，相应的编码器转移概率矩阵[p(y/x )]＝1001?? ???? ；D max ＝ 0.5 ，R (D max )＝ 0 ，相应的编码器转移概率矩阵[p(y/x )]＝1010?? ? ??? 。 7. 已知用户A 的RSA 公开密钥(e,n )=(3,55)，5,11p q ==,则()φn = 40 ，他的秘密密钥(d,n )＝(27,55) 。若用户B 向用户A 发送m =2的加密消息，则该加密后的消息为 8 。二、判断题 1. 可以用克劳夫特不等式作为唯一可译码存在的判据。（√ ） 2. 线性码一定包含全零码。（√ ） 3. 算术编码是一种无失真的分组信源编码，其基本思想是将一定精度数值作为序列的编码，是以另外一种形式实现的最佳统计匹配编码。（×） 4. 某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就有信息量。（×） 5. 离散平稳有记忆信源符号序列的平均符号熵随着序列长度L 的增大而增大。（×） 6. 限平均功率最大熵定理指出对于相关矩阵一定的随机矢量X ，当它是正态分布时具有最大熵。（√ ） 7. 循环码的码集中的任何一个码字的循环移位仍是码字。（√ ） 8. 信道容量是信道中能够传输的最小信息量。（×） 9. 香农信源编码方法在进行编码时不需要预先计算每个码字的长度。（×） 10. 在已知收码R 的条件下找出可能性最大的发码i C 作为译码估计值，这种译码方法叫做最佳译码。（√ ）三、计算题

《信息论与编码》教学大纲

《信息论与编码》教学大纲一课程简介课程编号：04254002 课程名称：信息论与编码Informatics & Coding 课程类型：基础课必修课学时：32 学分：2 开课学期：第六学期开课对象：通信、电子专业先修课程：概率论与数理统计、信号与系统、随机信号原理。参考教材：信息论与编码，陈运，周亮，陈新，电子工业出版社，2002年8月二课程性质、目的与任务信息论在理论上指出了建立最佳编码、最佳调制和最佳接收方法的最佳系统的理论原则，它对通信体制和通信系统的研究具有指导意义。提高信息传输的可靠性和有效性始终是通信工作所追求的目标。因此，信息论与编码是从事通信、电子系统工程的有关工程技术人员都必须掌握的基本理论知识。内容提要：本课程包括狭义相对论和提高通信可靠性的差错控制编码理论。信息论所研究的主要问题是在通信系统设计中如何实现有效性和可靠性。三教学基本内容与基本要求本课程总学时为32。其中理论教学为28，实验学时为4。主要的理论教学内容包括：离散信源和连续信源的熵、条件熵、联合熵和平均互信息量的概念及性质；峰值功率受限和平均功率受限下的最大熵定理和连续信源熵的变换；变长码的霍夫曼编码方法，熟悉编码效率和平均码长的计算；最大后验概率准则和最大似然译码准则等。实验内容主要包括：离散无记忆信道容量的迭代算法，循环码的编译码。四教学内容与学时分配第3章离散信源无失真编码

第6章网络信息论（教学要求：A—熟练掌握；B—掌握；C—了解）五实习、实验项目及学时分配 1．离散无记忆信道容量的迭代算法2学时要求用Matlab编写计算离散信道容量的实用程序并调试成功，加深对信道容量的理解。 2．循环码的编译码2学时要求用Matlab编写程序，用软件完成循环码的编译码算法。六教学方法与手段常规教学与多媒体教学相结合。

(完整版)信息论与编码概念总结

第一章 1.通信系统的基本模型: 2.信息论研究内容：信源熵，信道容量，信息率失真函数，信源编码，信道编码，密码体制的安全性测度等等第二章１.自信息量：一个随机事件发生某一结果所带的信息量。２.平均互信息量：两个离散随机事件集合X 和Y ，若其任意两件的互信息量为 I （Xi;Yj ），则其联合概率加权的统计平均值，称为两集合的平均互信息量，用I （X;Y ）表示３.熵功率：与一个连续信源具有相同熵的高斯信源的平均功率定义为熵功率。如果熵功率等于信源平均功率，表示信源没有剩余；熵功率和信源的平均功率相差越大，说明信源的剩余越大。所以信源平均功率和熵功率之差称为连续信源的剩余度。信源熵的相对率(信源效率)：实际熵与最大熵的比值信源冗余度： 0H H ∞=ηη ζ-=1

意义：针对最大熵而言，无用信息在其中所占的比例。３.极限熵：平均符号熵的N 取极限值，即原始信源不断发符号，符号间的统计关系延伸到无穷。４. ５.离散信源和连续信源的最大熵定理。离散无记忆信源，等概率分布时熵最大。连续信源，峰值功率受限时，均匀分布的熵最大。平均功率受限时，高斯分布的熵最大。均值受限时，指数分布的熵最大６.限平均功率的连续信源的最大熵功率：称为平均符号熵。定义：即无记忆有记忆N X H H X H N X H X NH X H X H X H N N N N N N )() ()()()()()(=≤∴≤≤

若一个连续信源输出信号的平均功率被限定为p ，则其输出信号幅度的概率密度分布是高斯分布时，信源有最大的熵，其值为 1log 22 ep π.对于N 维连续平稳信源来说，若其输出的N 维随机序列的协方差矩阵C 被限定，则N 维随机矢量为正态分布时信源的熵最大，也就是N 维高斯信源的熵最大，其值为1log ||log 222N C e π+ 7.离散信源的无失真定长编码定理：离散信源无失真编码的基本原理原理图说明：（1）信源发出的消息：是多符号离散信源消息，长度为L,可以用L 次扩展信源表示为： X L =(X 1X 2……X L ) 其中，每一位X i 都取自同一个原始信源符号集合（n 种符号）： X={x 1，x 2，…x n } 则最多可以对应n L 条消息。（2）信源编码后，编成的码序列长度为k,可以用k 次扩展信宿符号表示为： Y k =(Y 1Y 2……Y k ) 称为码字/码组其中，每一位Y i 都取自同一个原始信宿符号集合： Y={y 1，y 2，…y m } 又叫信道基本符号集合（称为码元，且是m 进制的）则最多可编成m k 个码序列，对应m k 条消息定长编码：信源消息编成的码字长度k 是固定的。对应的编码定理称为定长信源编码定理。变长编码：信源消息编成的码字长度k 是可变的。 8.离散信源的最佳变长编码定理最佳变长编码定理：若信源有n 条消息，第i 条消息出现的概率为p i ，且 p 1>=p 2>=…>=p n ，且第i 条消息对应的码长为k i ，并有k 1<=k 2<=…<=k n

《信息论与编码技术》复习题3-4

一、填空题（共20分，每空2分） 1. 信息的基本概念在于它的。 2. 一个随机事件的定义为其出现概率对数的负值。 3. 按树图法构成的码一定满足的定义。 4. 称为香农第二极限定理。 5. 纠错码的检、纠错能力是指。 6. 信息率失真函数R (D )是关于D 的严格单调函数。 7. 如果转移概率矩阵P 的每一行，称该矩阵是输入对称的。 8. 加密编码的主要目的是。 9. 若最小码距为d min 的码同时能检测e d 个错误、纠正e c 个错误，则三个量之间的关系为。 10. 稳定的马尔可夫信源必须有不可约性和。二、选择题（共10分，每题2分） 1. 给定x i 条件下，随机事件y j 所包含的不确定度和条件自信息量I (y j |x i )，（a ）数量上不等，单位不同；（b ）数量上不等，单位相同；（c ）数量上相等，单位不同；（d ）数量上相等，单位相同。 2. 下面哪一项不属于熵的性质：（a ）非负性；（b ）完备性；（c ）对称性；（d ）确定性。 3. 下面哪一项不是增加信道容量的途径：（a ）减小信道噪声功率；（b ）增大信号功率；（c ）增加码长；（d ）增加带宽。 4. 香农编码方法是根据推导出来的。（a ）香农第一极限定理；（b ）香农第二极限定理；（c ）香农第三极限定理；（d ）香农第四极限定理。 5. 下面哪一项不属于最简单的通信系统模型：（a ）信源；（b ）加密；（c ）信道；（d ）信宿。三、名词解释（共10分，每题5分） 1. 唯一可译码。 2. 最小码距。四、简答题（共20分，每10分） 1. 利用公式介绍无条件熵、条件熵、联合熵和平均互信息量之间的关系。 2. 简单介绍霍夫曼编码的步骤。五、计算题（共40分）（log 2(3)=1.585，log 2(5)=2.322） 1. 某信源含有三个消息，概率分别为p (0)=0.2，p (1)=0.3，p (2)=0.5，失真矩阵为??????????=102230124D 。求D max 、D min 和R (D max )。（10分） 2. 设对称离散信道矩阵为?? ????=3/13/16/16/16/16/13/13/1P ，求信道容量C 。（10分） 3. 有一稳态马尔可夫信源，已知转移概率为p(S 1/S 1)=2/3，p(S 1/S 2)=1。求：（1）画出状态转移图和状态转移概率矩阵；（2）求出各状态的稳态概率；（3）求出信源的极限熵。（20分）

信息论与编码理论1(B卷答案)

2011-2012 信息论与编码理论1 B 卷答案一、单项选择题（每题3分，总计15分） 1．当底为e 时，熵的单位为（ C ）。 A 奈特 B 哈特 C 奈特/符号 D 哈特/符号 2．下列关系式中( B )正确。 A )();(X I Y X I ≥ B );(),(Y X I Y X H ≥ C )|()|(X Y H Y X H ≥ D );();(Y X H Y X I ≤ 3．下列（ D ）陈述是正确的。 A Shannon 编码是最优码 B LZ 编码是异字头码 C Huffman 编码可以不需要知道信源的分布 D 典型序列的数目不一定比非典型的多 ) 4．下列数组中（ A ）不满足二个字母上的Kraft 不等式。 A (1，1，1) B (2,2,2,2) C (3,3,3) D （4，4，4） 5．下列（ D ）是只对输出对称的。 A ????? ? ??316 12121613 1 B ????? ??2.04.04.04.02.04.04.04.02.0 C ??????? ? ??32313132 3231 D ??? ? ??2.04.04.04.02.02.0 二、填空题（每空2分，总计20分） 1．若二元离散无记忆中25.0)0(=p ，75.0)1(=p ，则当给出100比特的信源序列，其中有5个1，则其自信息为3log 52002-比特，整个序列的熵为)3log 4 3 2(1002- 比特/符号. 2．若某离散信道信道转移概率矩阵为?? ????????5.025.025.025.05.025.025.025.05.0，则其信道容量为5.13log 2-比特/符号；转移概率矩阵为???? ? ?????25.05.025.05.025.025.025.025.05.0，则其信道容量为5.13log 2-比特/符号。 3. 两个相同的BSC 做级联信道，其信道转移矩阵分别为??? ? ??--p p p p 11 ，则级联信道的信道转移矩阵为??????+---+-22222212222221p p p p p p p p ，无穷多个级联后的矩阵为??? ???5.05.05.05.0。 4．若一个信道的输入熵为6.2)(=X H 比特/符号，输出熵为3.2)(=Y H 比特/符号，

信息论与编码试卷与答案

一、概念简答题（每题5分，共40分） 1.什么是平均自信息量与平均互信息，比较一下这两个概念的异同？答：平均自信息为表示信源的平均不确定度，也表示平均每个信源消息所提供的信息量。平均互信息表示从Y获得的关于每个X的平均信息量，也表示发X前后Y的平均不确定性减少的量，还表示通信前后整个系统不确定性减少的量。 2.简述最大离散熵定理。对于一个有m个符号的离散信源，其最大熵是多少？答：最大离散熵定理为：离散无记忆信源，等概率分布时熵最大。最大熵值为。 3.解释信息传输率、信道容量、最佳输入分布的概念，说明平均互信息与信源的概率分布、信道的传递概率间分别是什么关系？答：信息传输率R指信道中平均每个符号所能传送的信息量。信道容量是一个信道所能达到的最大信息传输率。信息传输率达到信道容量时所对应的输入概率分布称为最佳输入概率分布。平均互信息是信源概率分布的∩型凸函数，是信道传递概率的U型凸函数。 4.对于一个一般的通信系统，试给出其系统模型框图，并结合此图，解释数据处理定理。答：通信系统模型如下：

数据处理定理为：串联信道的输入输出X、Y、Z组成一个马尔可夫链，且有，。说明经数据处理后，一般只会增加信息的损失。 5.写出香农公式，并说明其物理意义。当信道带宽为5000Hz，信噪比为30dB时求信道容量。 .答：香农公式为，它是高斯加性白噪声信道在单位时间内的信道容量，其值取决于信噪比和带宽。由得，则 6.解释无失真变长信源编码定理。 .答：只要，当N足够长时，一定存在一种无失真编码。 7.解释有噪信道编码定理。答：当R＜C时，只要码长足够长，一定能找到一种编码方法和译码规则，使译码错误概率无穷小。 8.什么是保真度准则？对二元信源，其失真矩阵，求a>0时率失真函数的和？答：1）保真度准则为：平均失真度不大于允许的失真度。 2）因为失真矩阵中每行都有一个0，所以有，而。二、综合题（每题10分，共60分） 1.黑白气象传真图的消息只有黑色和白色两种，求：

信息论与编码第一章答案

第一章信息论与基础 1.1信息与消息的概念有何区别？信息存在于任何事物之中,有物质的地方就有信息，信息本身是看不见、摸不着的，它必须依附于一定的物质形式。一切物质都有可能成为信息的载体，信息充满着整个物质世界。信息是物质和能量在空间和时间中分布的不均匀程度。信息是表征事物的状态和运动形式。在通信系统中其传输的形式是消息。但消息传递过程的一个最基本、最普遍却又十分引人注意的特点是：收信者在收到消息以前是不知道具体内容的；在收到消息之前，收信者无法判断发送者将发来描述何种事物运动状态的具体消息；再者，即使收到消息，由于信道干扰的存在，也不能断定得到的消息是否正确和可靠。在通信系统中形式上传输的是消息,但实质上传输的是信息。消息只是表达信息的工具，载荷信息的载体。显然在通信中被利用的（亦即携带信息的）实际客体是不重要的，而重要的是信息。信息载荷在消息之中，同一信息可以由不同形式的消息来载荷；同一个消息可能包含非常丰富的信息，也可能只包含很少的信息。可见，信息与消息既有区别又有联系的。 1.2 简述信息传输系统五个组成部分的作用。信源：产生消息和消息序列的源。消息是随机发生的，也就是说在未收到这些消息之前不可能确切地知道它们的内容。信源研究主要内容是消息的统计特性和信源产生信息的速率。信宿：信息传送过程中的接受者，亦即接受消息的人和物。编码器：将信源发出的消息变换成适于信道传送的信号的设备。它包含下述三个部分：(1)信源编码器：在一定的准则下，信源编码器对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。(2)纠错编码器：纠错编码器是对信源编码器的输出进行变换，用以提高对于信道干扰的抗击能力，也就是说提高信息传输的可靠性。(3)调制器：调制器是将纠错编码器的输出变换适合于信道传输要求的信号形式。纠错编码器和调制器的组合又称为信道编码器。信道：把载荷消息的信号从发射端传到接受端的媒质或通道，包括收发设备在内的物理设施。信道除了传送信号外，还存储信号的作用。译码器：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。 1.3 同时掷一对骰子，要得知面朝上点数之和，描述这一信源的数学模型。解：设该信源符号集合为X

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

一填空题（本题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 之比。

(完整版)信息论与编码试题集

1. 在无失真的信源中，信源输出由 H (X ) 来度量；在有失真的信源中，信源输出由 R (D ) 来度量。 2. 要使通信系统做到传输信息有效、可靠和保密，必须首先信源编码，然后_____加密____编码，再______信道_____编码，最后送入信道。 3. 带限AWGN 波形信道在平均功率受限条件下信道容量的基本公式，也就是有名的香农公式是log(1)C W SNR =+；当归一化信道容量C/W 趋近于零时，也即信道完全丧失了通信能力，此时E b /N 0为 -1.6 dB ，我们将它称作香农限，是一切编码方式所能达到的理论极限。 4. 保密系统的密钥量越小，密钥熵H (K )就越小，其密文中含有的关于明文的信息量I (M ；C )就越大。 5. 设输入符号表为X ＝{0，1}，输出符号表为Y ＝{0，1}。输入信号的概率分布为p ＝(1/2，1/2)，失真函数为d (0，0) = d (1，1) = 0，d (0，1) =2，d (1，0) = 1，则D min ＝ 0 ，R (D min )＝ 1bit/symbol ，相应的编码器转移概率矩阵[p(y/x )]＝1001?? ???? ；D max ＝ 0.5 ，R (D max )＝ 0 ，相应的编码器转移概率矩阵[p(y/x )]＝1010?? ???? 。二、判断题 1. 可以用克劳夫特不等式作为唯一可译码存在的判据。（√ ） 2. 线性码一定包含全零码。（√ ） 3. 算术编码是一种无失真的分组信源编码，其基本思想是将一定精度数值作为序列的编码，是以另外一种形式实现的最佳统计匹配编码。（×） 4. 某一信源，不管它是否输出符号，只要这些符号具有某些概率特性，就有信息量。（×） 5. 离散平稳有记忆信源符号序列的平均符号熵随着序列长度L 的增大而增大。（×） 6. 限平均功率最大熵定理指出对于相关矩阵一定的随机矢量X ，当它是正态分布时具有最大熵。（√ ） 7. 循环码的码集中的任何一个码字的循环移位仍是码字。（√ ） 8. 信道容量是信道中能够传输的最小信息量。（×） 9. 香农信源编码方法在进行编码时不需要预先计算每个码字的长度。（×） 10. 在已知收码R 的条件下找出可能性最大的发码i C 作为译码估计值，这种译码方法叫做最佳译码。（√ ）三、计算题某系统（7，4）码 )()(01201230123456c c c m m m m c c c c c c c ==c 其三位校验位与信息位的关系为：

信息论与编码课后答案

一个马尔可夫信源有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分，共32分）。 1.在现代通信系统中，信源编码主要用于解决信息传输中的，信道编码主要用于解决信息传输中的，加密编码主要用于解决信息传输中的 2.离散信源?? ????=??????8/18/14/12/1)(4321x x x x x p X ，则信源的熵为。 3.采用m 进制编码的码字长度为K i ，码字个数为n ，则克劳夫特不等式为，它是判断的充要条件。 4.如果所有码字都配置在二进制码树的叶节点，则该码字为。 5.齐次马尔可夫信源的一步转移概率矩阵为P ，稳态分布为W ，则W 和P 满足的方程为。 6.设某信道输入端的熵为H(X)，输出端的熵为H(Y)，该信道为无噪有损信道，则该信道的容量为。 7.某离散无记忆信源X ，其符号个数为n ，则当信源符号呈分布情况下，信源熵取最大值。 8.在信息处理中，随着处理级数的增加，输入消息和输出消息之间的平均互信息量趋于。二．选择题（共10分，每小题2分） 1、有一离散无记忆信源X ，其概率空间为? ? ????=??????125.0125.025.05.04321x x x x P X ，则其无记忆二次扩展信源的熵H(X 2)=( ) A 、1.75比特/符号； B 、3.5比特/符号； C 、9比特/符号； D 、18比特/符号。 2、信道转移矩阵为112132425363(/)(/) 000000(/)(/)000000(/)(/)P y x P y x P y x P y x P y x P y x ?????? ???? ，其中(/)j i P y x 两两不相等，则该信道为 A 、一一对应的无噪信道 B 、具有并归性能的无噪信道 C 、对称信道 D 、具有扩展性能的无噪信道 3、设信道容量为C ，下列说法正确的是：（） A 、互信息量一定不大于C

信息论与编码复习总结

信息论与编码复习总结题型：填空、解答、计算 1、编码：无失真与限失真信源编码定理编码分为信源编码和信道编码，其中信源编码又分为无失真和限失真三大定理: 无失真信源编码定理（第一极限定理）（可逆）信道编码定理（第二极限定理）限失真信源编码定理（第三极限定理）（不可逆） Shannon(香农)信息论：在噪声环境下，可靠地、安全地、有效地传送信息理论。通信系统模型方框图: 信道的种类很多，如电信中常用的架空明线、同轴电缆、波导、光纤、传输电磁波的空间等都是信道。也可以从信道的性质或其传送的信号情况来分类，例如：无干扰信道和有干扰信道、恒参信道和变参信道、离散信道（Discrete Channel）和连续信道（Continuous Channel）、单用户信道和多用户信道等。信源的描述：通过概率空间描述

平稳包含齐次，而齐次不包含平稳（重要，第二章计算题）定义：若齐次马尔可夫链对一切i,j存在不依赖于i的极限，则称其具有遍历性，p j称为平稳分布（如下）设有一齐次马尔可夫链，其状态转移矩阵为P，其稳态分布为w j=p(s j) 自信息量的特性： p(x i)=1,I(x i)=0; p(x i)=0,I(x i)=∞;非负性；单调递减性；可加性；定义：联合概率空间中任一联合事件的联合（自）信息量为：定义：对于给定离散概率空间表示的信源，在出现y事件后所提供有关事件x的信息量定义互信息，单位为比特

信道模型：二进制离散信道BSC；离散无记忆信道DMC；波形信道信源编码器的目的：是使编码后所需的信息传输率R尽量小。信源编码：主要任务就是减少冗余，提高编码效率。

信息论与编码技术复习题3-4

《信息论与编码技术》复习题（3）一、填空题（共20分，每空2分） 1. ___________________________________ 信息的基本概念在于它的。 2. 一个随机事件的___________ 定义为其出现概率对数的负值。 3. 按树图法构成的码一定满足____________ 的定义。 4. _______________________ 称为香农第二极限定理。 5. 纠错码的检、纠错能力是指___________________________________________________ 。 6. 信息率失真函数R（D）是关于D的严格单调___________ 函数。 7. 如果转移概率矩阵P的每一行 ________________________ ，称该矩阵是输入对称的。 8. 加密编码的主要目的是____________________________________ 。 9. 若最小码距为d min的码同时能检测e d个错误、纠正e c个错误，则三个量之间的关系为_____________________________ 。 10. 稳定的马尔可夫信源必须有不可约性和_________________________________ 。二、选择题（共10分，每题2分） 1. 给定为条件下，随机事件y j所包含的不确定度和条件自信息量l（y j|X i）, （a）数量上不等，单位不同；（b）数量上不等，单位相同；（c）数量上相等，单位不同；（d）数量上相等，单位相同。 2. 下面哪一项不属于熵的性质：（a ）非负性；（b ）完备性；（c）对称性；（d ）确定性。 3. 下面哪一项不是增加信道容量的途径：（a）减小信道噪声功率；（b ）增大信号功率；（c）增加码长；（d）增加带宽。 4. 香农编码方法是根据_______ 推导出来的。（a）香农第一极限定理；（b）香农第二极限定理；（c）香农第三极限定理；（d）香农第四极限定理。 5. 下面哪一项不属于最简单的通信系统模型：（a）信源；（b）加密；（c）信道；（d）信宿。三、名词解释（共10分，每题5分） 1. 唯一可译码。 2. 最小码距。四、简答题（共20分，每10分） 1. 利用公式介绍无条件熵、条件熵、联合熵和平均互信息量之间的关系。 2. 简单介绍霍夫曼编码的步骤。五、计算题（共40 分）（Iog2（3） =，log2（5）=） 1. 某信源含有三个消息，概率分别为P（0）=, P（1）=，P（2）=，失真矩阵为 4 2 1。求 D max、 D 0 3 2 2 0 1 D min 和R（D max）。（10 分） 2. 设对称离散信道矩阵为P1/3 1/3 1/6 1/6，求信道容量G（10分） 1/6 1/6 1/3 1/3 3. 有一稳态马尔可夫信源，已知转移概率为p（S1/S1）=2/3, p（S1/S2）=1。求：