信息论实验报告
姓名胡小辉
班级电子信息工程0902
学号 0909091112
1.实验目的
1、掌握哈夫曼编码、费诺编码、汉明码原理；
2、熟练掌握哈夫曼树的生成方法；
3、学会利用matlab、C语言等实现Huffman编码、费诺编码以及hamming编码。
2.实验原理
Huffman编码：
哈夫曼树的定义：假设有n个权值，试构造一颗有n个叶子节点的二叉树，每个叶子带权值为wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；
实现Huffman编码原理的步骤如下：
1. 首先将信源符号集中的符号按概率大小从大到小排列。
2. 用0和1表示概率最小的两个符号。可用0表示概率小的
符
号，也可用1表示概率小的符号，但整个编码需保持一致。
3. 将这两个概率最小的符号合并成一个符号，合并符号概率
为
最小概率之和，将合并后的符号与其余符号组成一个N-1的新信源符号集，称之为缩减符号集。
4. 对缩减符号集用步骤1,2操作
5. 以此类推，直到只剩两个符号，将0和1分别赋予它们。
6. 根据以上步骤，得到0,1赋值，画出Huffman码树，并从
最
后一个合并符号回朔得到Huffmaan编码。
费诺编码：
费诺编码的实现步骤：
1、将信源消息符号按其出现的概率大小依次排列：。
2、将依次排列的信源符号按概率值分为两大组，使两个组的
概率之和近似相同，并对各组赋予一个二进制码元“0”和“1”。
3、将每一大组的信源符号再分为两组，使划分后的两个组的
概率之和近似相同，并对各组赋予一个二进制符号“0”和“1”。
4、如此重复，直至每个组只剩下一个信源符号为止。
5、信源符号所对应的码字即为费诺码。
hamming编码：
若一致监督矩阵H 的列是由不全为0且互不相同的所有二进制m(m≥2的正整数)重组成，则由此H矩阵得到的线性分组码称为[2m-1,2m-1-m，3]汉明码。
我们通过（7，4）汉明码的例子来说明如何具体构造这种码。设分组码（n，k）中，k = 4，为能纠正一位误码，要求r≥3。现取r＝3，则n＝k＋r＝7。我们
用a
0a
l
a
2
a
3
a
4
a
5
a
6
表示这7个码元，用S
1
、S
2
、S
3
表示由三个监督方程式计算得到的校
正子，并假设三位S
1、S
2
、S
3
校正子码组与误码位置的对应关系如表1所示。
表1 校正子和错码位置关系
由表可知，当误码位置在a
2、a
4
、a
5
、a
6
时，校正子S
1
＝1；否则S
1
＝0。因此有S
1
＝a
6⊕a
5
⊕a
4
⊕a
2
，同理有S
2
＝a
6
⊕a
5
⊕a
3
⊕a
1
和S
3
＝a
6
⊕a
4
⊕a
3
⊕a
。在编码时a
6
、
a 5、a
4
、a
3
为信息码元，a
2
、a
1
、a
为监督码元。则监督码元可由以下监督方程唯
一确定
a 6⊕a
5
⊕a
4
⊕a
2 = 0
a 6⊕a
5
⊕a
3
⊕a
1 = 0
(1.1.1)
a 6⊕a
4
⊕a
3
⊕a
0 = 0
也即
a 2＝a 6⊕a 5⊕a 4
a 1＝a 6⊕a 5⊕a 3 （
1.1.2）
a 0 = a 6⊕a 4⊕a 3
由上面方程可得到表2所示的16个许用码组。在接收端收到每个码组后，计算出S 1、S 2、S 3，如果不全为0，则表示存在错误，可以由表1确定错误位置并予以纠正。举个例子，假设收到码组为0000011，可算出S 1S 2S 3=011,由表1可知在a 3上有一误码。通过观察可以看出，上述（7，4）码的最小码距为d min ＝3，纠正一个误码或检测两个误码。如果超出纠错能力则反而会因“乱纠”出现新的误码.
表2 （7,4）汉明码的许用码组
3.1 (7,4)汉明码的编码思路
(7,4)汉明码的编码就是将输入的四位信息码编成七位的汉明码，即加入三位监督位。根据式(2.2.0）A = [a 6 a 5 a 4 a 3] ·G 可知，信息码与生成矩阵G 的乘积就是编好以后的(7,4)汉明码，而生成矩阵G 又是已知的，由式(1.1.9)得
1 0 0 0 1 1 1
G = 0 1 0 0 1 1 0 0 0 1 0 1 0 1 0 0 0 1 0 1 1
所以，可以得出如下方程组
a
6 =a
6
a
5 =a
5
a
4 = a
4
a
3 = a
3
a
2 = a
6
+ a
5
+ a
4
a
1 = a
6
+ a
5
+ a
3
a
0 = a
6
+ a
4
+ a
3
根据此式子编出编码程序。
3.实验过程及结果
1、哈弗曼编码
例如：当p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4
则根据其原理得到的matlab程序如下：
clc;
clear;
A=[0.3,0.15,0.05,0.1,0.4];%信源消息的概率序列
A=fliplr(sort(A));%按降序排列
T=A;
[m,n]=size(A);
B=zeros(n,n-1);%空的编码表（矩阵）
fori=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%生成编码表的其他各列
fori=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;
end
B;%输出编码表
END1=sym('[0,1]');%给最后一列的元素编码
END=END1;
t=3;
d=1;
for j=n-2:-1:1%从倒数第二列开始依次对各列元素编码
fori=1:t-2
ifi>1 & B(i,j)==B(i-1,j)
d=d+1;
else
d=1;
end
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%编码结果
fori=1:n
[a,b]=size(char(END(i)));
L(i)=b;
end
avlen=sum(L.*A)%平均码长
H1=log2(A);
H=-A*(H1')%熵
P=H/avlen%编码效率
输出结果：
费诺编码：
同样，例如：p1=0.3、p2=0.15、p3=0.05、p4=0.1、p5=0.4时根据其原理所得到的matlab程序如下：
clc;
clear;
A=[0.3,0.15,0.05,0.1,0.4];
A=fliplr(sort(A));%降序排列
[m,n]=size(A);
fori=1:n
B(i,1)=A(i);%生成B的第1列
end
%生成B第2列的元素
a=sum(B(:,1))/2;
for k=1:n-1
if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a)
break;
end
end
for i=1:n%生成B第2列的元素
ifi<=k
B(i,2)=0;
else
B(i,2)=1;
end
end
%生成第一次编码的结果
END=B(:,2)';
END=sym(END);
%生成第3列及以后几列的各元素
j=3;
while (j~=0)
p=1;
while(p<=n)
x=B(p,j-1);
for q=p:n
if x==-1
break;
else
if B(q,j-1)==x
y=1;
continue;
y=0;
break;
end
end
end
if y==1
q=q+1;
end
if q==p|q-p==1
B(p,j)=-1;
else
if q-p==2
B(p,j)=0;
END(p)=[char(END(p)),'0'];
B(q-1,j)=1;
END(q-1)=[char(END(q-1)),'1'];
else
a=sum(B(p:q-1,1))/2;
for k=p:q-2
if abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a); break;
end
end
fori=p:q-1
ifi<=k
B(i,j)=0;
END(i)=[char(END(i)),'0'];
else
B(i,j)=1;
END(i)=[char(END(i)),'1'];
end
end
end
end
p=q;
end
C=B(:,j);
D=find(C==-1);
[e,f]=size(D);
if e==n
j=0;
else
j=j+1;
end
B
A
END
fori=1:n
[u,v]=size(char(END(i))); L(i)=v;
end
avlen=sum(L.*A)
输出结果：
汉明码：
clc;
clear;
close;
N=100;
display('随机产生二进制信源消息序列:');
[a]=randint(1,100);
%************转换矩阵[a]
fori=0:(length(a)/4-1)
for j=0:(4-1)
P(i+1,j+1)=a(j+i*4+1);
end
end
[P]
%function g=hammingdecod(R)
%H=input('生成汉明码:');
H=[1 1 1 0 1 0 0;1 1 0 1 0 1 0;1 0 1 1 0 0 1];%生成汉明码
G=[1 0 0 0 1 1 1;0 1 0 0 1 1 0;0 0 1 0 1 0 1;0 0 0 1 0 1 1] %(7,4)汉明码的生成矩阵%t=input('输入0或1:'); %t=0则产生（7，4）汉明码，t=1则对输入序列进行编码
%if t==1
c=mod(P*G,2); %编码的码字c
%function [X]=turnRow(c)
n=size(c);
fori=0:(n(1)-1)
for j=0:(n(2)-1)
X(j+i*n(2)+1)=c(i+1,j+1);
end
end
X1=randerr(1,175,1);
%************相加
Q=mod(X1+X,2);
%************转换矩阵X1
%**********编码
fori=0:(length(Q)/7-1)
for j=0:(7-1)
Q1(i+1,j+1)=Q(j+i*7+1);
end
end
disp('输出编码后序列为：');
Q1
Z=mod(Q1*H',2);
Z
%**********编码
n=size(Z);
%T=T();
fori=0:(n(1)-1)
T(i+1)=4*Z(i+1,1)+2*Z(i+1,2)+Z(i+1,3); if T(i+1)
Q1(i+1,8-T(i+1))=1-Q1(i+1,8-T(i+1));
end
end
T=Q1;
disp('(经过信道后变为：');
T
%**************译码function C=yima(B,k) n=size(T);
fori=1:n(1)
for j=1:4
C(i,j)=T(i,j);
end
end
disp('输出译码序列:');
disp(C);
输出结果：
实验心得：
通过这次实验，我更深入了解了哈夫曼编码的构造原理。在实验过程中，我掌握了哈曼树的构造方法，学会了如何将理论知识传换成实际应用。同时，在解决程序中遇到的一些问题的同时，我也对调试技巧有了更好的掌握，分析问题的能力也略有提高。同时，进一步使用了matlab这个软件工具，进一步熟悉了在matlab 中的编程的语法和结构。认识到了软件工具在通信科研仿真方面的重要作用和方便性。
正所谓“纸上得来终觉浅，觉知此事要躬行。”学习任何知识，仅从理论上去求知，而不去实践、探索是不够的。
在整个实验过程中我懂得了许多东西，虽然很多东西都是从网上找的，但是在查找的过程中我们也知道了许多原来不知道的东西，对于源代码的修改以及成功利用也树立了对知识应用的信心，相信会对今后的学习工作和生活有非常大的帮助，并且提高了自己的动手实践操作能力，使自己充分体会到了在实验过程中的成功喜悦。虽然这个实验做的不怎么好，但是在过程中所学到的东西是这次实验的最大收获和财富，使我终身受益。
信息论复习提纲 第一章绪论 1．通信系统模型； 2．香浓信息的概念； 3．信源、信道、信源编码和信道编码研究的核心问题。 第二章离散信源及信源熵 1．离散信息量、联合信息量、条件信息量、互信息量定义； 2．信源熵、条件熵、联合熵定义； 3．平均互信息量定义、性质、三种表达式及物理意义，与其它熵的关系（不证明）； 4．最大信源熵定理及证明； 5．本章所有讲过的例题； 第三章离散信源的信源编码 1．信息传输速率、编码效率定义； 2．最佳编码定理（即节定理：概率越大，码长越小；概率越小，码长越大）及证明； 3．码组为即时码的充要条件； 4．单义可译定理（Kraft不等式）及应用； 5．费诺编码方法、霍夫曼编码方法应用（二进制，三进制，四进制）；6．本章所有讲过的例题； 第四章离散信道容量 1．利用信道矩阵计算信道容量（离散无噪信道、强对称离散信道、对称离
散信道、准对称离散信道）； 2．本章讲过的例题； 第五章连续消息和连续信道 1．相对熵的定义； 2．均匀分布、高斯分布、指数分布的相对熵及证明； 3．峰值功率受限条件下的最大熵定理及证明，平均功率受限条件下的最大熵定理及证明，均值受限条件下的最大熵定理及证明； 4．香农公式及意义； 5．本章所有讲过的例题； 第六章差错控制 1．重量、最小重量、汉明距离、最小汉明距离、编码效率的定义；2．最小距离与检错、纠错的关系（即节定理）； 3．本章所有讲过的例题； 第七章线性分组码 1．线性分组码定义； 2．线性分组码的最小距离与最小重量的关系及证明； 3．生成矩阵、一致校验矩阵定义，给出线性方程组求出生成矩阵和一致校验矩阵的标准形式，生成矩阵与一致校验矩阵的关系； 4．制作标准阵列并利用标准阵列译码； 5．本章所有讲过的例题； 第八章循环码 1．生成多项式的特点，有关定理（三定理1，定理2，定理3）及证明；
实验五霍夫曼编码 一、实验目的 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）实验结果
第二章课后习题 【2.1】设有12 枚同值硬币，其中有一枚为假币。只知道假币的重量与真币的重量不同，但不知究竟是重还是轻。现用比较天平左右两边轻重的方法来测量。为了在天平上称出哪一枚是假币，试问至少必须称多少次？ 解：从信息论的角度看， “12 枚硬币中，某一枚为假币”该事件发生的概率为P = 1 12 ； “假币的重量比真的轻，或重”该事件发生的概率为P = 1 2 ； 为确定哪一枚是假币，即要消除上述两事件的联合不确定性，由于二者是独立的，因此有 I = log12 + log 2 = log 24 比特 而用天平称时，有三种可能性：重、轻、相等，三者是等概率的，均为P = 平每一次消除的不确定性为I = log 3 比特 因此，必须称的次数为1 3 ，因此天 I 1 I 2 log 24 log 3 H 2.9 次 因此，至少需称3 次。 【延伸】如何测量？分 3 堆，每堆4 枚，经过 3 次测量能否测出哪一枚为假币。【2.2】同时扔一对均匀的骰子，当得知“两骰子面朝上点数之和为2”或“面朝上点数之和为8”或“两骰子面朝上点数是 3 和4”时，试问这三种情况分别获得多少信息量？解： “两骰子总点数之和为2”有一种可能，即两骰子的点数各为1，由于二者是独立的， 因此该种情况发生的概率为P = 1 1 6 6 1 36 ，该事件的信息量为： ?
? ? 5 = ? ? 2 = I = log 36 H 5.17 比特 “两骰子总点数之和为 8”共有如下可能：2 和 6、3 和 5、4 和 4、5 和 3、6 和 2，概 率为 P = 1 1 6 6 5 36 ，因此该事件的信息量为： 36 I = log H 2.85 比特 5 “两骰子面朝上点数是 3 和 4”的可能性有两种：3 和 4、4 和 3，概率为 P = 1 1 6 6 1 18 ， 因此该事件的信息量为： I = log18 H 4.17 比特 【2.3】如果你在不知道今天是星期几的情况下问你的朋友“明天星期几？”则答案中含有 多少信息量？如果你在已知今天是星期四的情况下提出同样的问题，则答案中你能获得多 少信息量（假设已知星期一至星期日的顺序）？ 解： 如果不知今天星期几时问的话，答案可能有七种可能性，每一种都是等概率的，均为 P = 1 7 ，因此此时从答案中获得的信息量为 I = log 7 = 2.807 比特 而当已知今天星期几时问同样的问题，其可能性只有一种，即发生的概率为 1，此时获得 的信息量为 0 比特。 【2.4】居住某地区的女孩中有 25%是大学生，在女大学生中有 75%是身高 1.6 米以上的， 而女孩中身高 1.6 米以上的占总数一半。假如我们得知“身高 1.6 米以上的某女孩是大学 生”的消息，问获得多少信息量？ 解： 设 A 表示女孩是大学生， P ( A ) = 0.25 ； B 表示女孩身高 1.6 米以上， P ( B | A ) = 0.75 ， P ( B ) = 0.5 “身高 1.6 米以上的某女孩是大学生”的发生概率为
本科生实验报告 实验课程信息论与编码 学院名称信息科学与技术学院 专业名称通信工程 学生姓名 学生学号 指导教师谢振东 实验地点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 int i,j; for(i=0;i 《信息论与编码技术》复习题（2） 一、（32分）综合概念题 1. 什么是系统码和典型矩阵？写出常用的典型生成矩阵的两种形式。 2. 根据平均互信息定义的信道容量是指： a. 信道固定时的最大平均互信息； b. 信道固定时的最小平均互信息； c. 信源固定时的信道的最小平均互信息； d. 信源固定时的信道的最大平均互信息。 3. 什么是离散平稳信源？ a. 任意两个不同时刻随机矢量的各维概率分布都相同； b. 任意两个不同时刻随机矢量的各维概率分布都不相同； c. 任意两个不同时刻随机矢量的各维概率密度函数都相同； d. 任意两个不同时刻随机矢量的各维概率密度函数都不相同。 4. 设计一个信道容量为22 kbit/s 的电话信道，若信道上的信号与噪声的平均功率比值为20 dB ，请问该信道的通频带应该为多少？ 5. 设信源有q 个符号，则当信源 分布时熵最大，其最大值为 。 6. 当信道固定时，平均互信息是输入分布的 函数；当信源固定时，平均互信息是信道转移概率的 函数。 7. 信源编码是通过压缩信源冗余度来提高 ，而信道编码是增加冗余度来提高 。 8. 请判断具有下列码长{1, 2, 3, 3, 3, 4}的二进制码是否可构成唯一可译码。 二、（10分）设有对称信源(s = r = 4)，信源X = {a 1, a 2, ..., a r } = {0, 1, 2, 3}，信宿Y = { b 1, b 2, ..., b s } = {0, 1, 2, 3}。若失真度定义为：d (a i , b j ) = (b j -a i )2，求其失真矩阵D 。 三、（15分）某离散无记忆信源?? ????=??????4.06.0)(21a a x p X ，通过图1的信道传输，求： 图1 离散信道 （1）该信源中a 1和 a 2分别含有的自信息； （2）X 和Y 的信息熵； （3）信道的疑义度H (X|Y )； （4）接收到信息Y 后获得的平均互信息量。 四、（16分）设有一个离散无记忆信源?? ????=??????5.03.02.0)(321a a a x p X ， （1）对该信源进行二元费诺编码，计算其平均码长和编码效率； 实验报告 课程名称：信息论与编码姓名： 系： 专业： 年级： 学号： 指导教师： 职称： 年月日 目录 实验一信源熵值的计算 (1) 实验二 Huffman信源编码 (5) 实验三 Shannon编码 (9) 实验四信道容量的迭代算法 (12) 实验五率失真函数 (15) 实验六差错控制方法 (20) 实验七汉明编码 (22) 实验一 信源熵值的计算 一、 实验目的 1 进一步熟悉信源熵值的计算 2熟悉 Matlab 编程 二、实验原理 熵（平均自信息）的计算公式 ∑∑=--==q i i i q i i i p p p p x H 1 212log 1 log )( MATLAB 实现：))(log *.(2x x sum HX -=；或者))((log *)(2i x i x h h -= 流程：第一步：打开一个名为“nan311”的TXT 文档，读入一篇英文文章存入一个数组temp ，为了程序准确性将所读内容转存到另一个数组S ，计算该数组中每个字母与空格的出现次数(遇到小写字母都将其转化为大写字母进行计数)，每出现一次该字符的计数器+1； 第二步：计算信源总大小计算出每个字母和空格出现的概率； 最后，通过统计数据和信息熵公式计算出所求信源熵值（本程序中单位为奈特nat ）。 程序流程图： 三、实验内容 1、写出计算自信息量的Matlab 程序 2、已知：信源符号为英文字母（不区分大小写）和空格。 输入：一篇英文的信源文档。 输出：给出该信源文档的中各个字母与空格的概率分布，以及该信源的熵。 四、实验环境 Microsoft Windows 7 Matlab 6.5 五、编码程序 #include"stdio.h" #include 信息论与编码习题参考答案 第一章 单符号离散信源 同时掷一对均匀的子，试求： (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%,女性发病率为%.如果你问一位男士：“你是否是红绿色盲”他的回答可能是：“是”，也可能“不是”。问这两个回答中各含有多少信息量平均每个回答中各含有多少信息量如果你问一位女士，则她的答案中含有多少平均信息量 解： 实验一 绘制二进熵函数曲线（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) 五、实验结果 2011级信息论期末复习 一、单项选择题 1. 十六进制脉冲所含信息量是四进制脉冲的( b )倍。 A 、1 B 、4 C 、3 D 、2 2. 设信道的输入X 的符号个数为n ，输出Y 的符号个数为m ，对于具有归并功能的无噪信道（即m 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 “信息论与编码”复习 1．消息、信号、信息的含义、定义及区别。 信息是指各个事物运动的状态及状态变化的方式。 消息是指包含信息的语言，文字和图像等。 信号是消息的物理体现。 消息是信息的数学载体、信号是信息的物理载体 信号：具体的、物理的 消息：具体的、非物理的 信息：非具体的、非物理的 同一信息，可以采用不同形式的物理量来载荷，也可以采用不同的数学描述方式。同样，同一类型信号或消息也可以代表不同内容的信息 2．信息的特征与分类。 1接收者在收到信息之前，对其内容是未知的，所以信息是新知识，新内容； 2信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识； 3信息可以产生，也可以消失，同时信息可以被携带，被存储及处理； 4信息是可以量度的，信息量有多少的差别。 31948年，Shannon提出信息论，“通信中的数学理论”—现代信息论的开创性的权威论文，为信息论的创立作出了独特的贡献。 4．通信系统的物理模型（主要框图），各单元（方框）的主要功能及要解决的主要问题。 信源的核心问题是它包含的信息到底有多少，怎样将信息定量地表示出来，即如何确定信息量。 信宿需要研究的问题是能收到或提取多少信息。 信道的问题主要是它能够传送多少信息，即信道容量的多少。 5．通信的目的？要解决的最基本问题？通信有效性的概念。提高通信有效性的最根本途径？通信可靠性的概念。提高通信可靠性的最根本途径？通信安全性的概念，提高通信安全性的最根本途径？ 通信系统的性能指标主要是有效性，可靠性，安全性和经济性。通信系统优化就是使这些指标达到最佳。 从提高通信系统的有效性意义上说，信源编码器的主要指标是它的编码效率，即理论上所需的码率与实际达到的码率之比。提高通信有效性的最根本途径是信源编码。减少冗余。 提高可靠性：信道编码。增加冗余。 提高安全性：加密编码。 6．随机事件的不确定度和它的自信息量之间的关系及区别？单符号离散信源的数学模型，自信息量、条件自信息量、联合自信息量的含义？ 信源符号不确定度：具有某种概率的信源符号在发出之前，存在不确定度，不确定度表征该符号的特性。符号的不确定度在数量上等于它的自信息量，两者的单位相同，但含义不同： ?不确定度是信源符号固有的，不管符号是否发出； ?自信息量是信源符号发出后给予收信者的； ?为了消除该符号的不确定度，接受者需要获得信息量。 自信息量 8．信息量的性质？含义？分别从输入端、输出端和系统总体来理解互信息量的含义。 自信息量指的是该符号出现后，提供给收信者的信息量。 9. 各种熵（信源熵，条件熵，联合熵（共熵），等）的含义及其关系。 信源熵： 一填空题（本题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.通信系统的基本模型: 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 第一章信息论与基础 1.1信息与消息的概念有何区别？ 信息存在于任何事物之中,有物质的地方就有信息，信息本身是看不见、摸不着的，它必须依附于一定的物质形式。一切物质都有可能成为信息的载体，信息充满着整个物质世界。信息是物质和能量在空间和时间中分布的不均匀程度。信息是表征事物的状态和运动形式。 在通信系统中其传输的形式是消息。但消息传递过程的一个最基本、最普遍却又十分引人注意的特点是：收信者在收到消息以前是不知道具体内容的；在收到消息之前，收信者无法判断发送者将发来描述何种事物运动状态的具体消息；再者，即使收到消息，由于信道干扰的存在，也不能断定得到的消息是否正确和可靠。 在通信系统中形式上传输的是消息,但实质上传输的是信息。消息只是表达信息的工具，载荷信息的载体。显然在通信中被利用的（亦即携带信息的）实际客体是不重要的，而重要的是信息。 信息载荷在消息之中，同一信息可以由不同形式的消息来载荷；同一个消息可能包含非常丰富的信息，也可能只包含很少的信息。可见，信息与消息既有区别又有联系的。 1.2 简述信息传输系统五个组成部分的作用。 信源：产生消息和消息序列的源。消息是随机发生的，也就是说在未收到这些消息之前不可能确切地知道它们的内容。信源研究主要内容是消息的统计特性和信源产生信息的速率。 信宿：信息传送过程中的接受者，亦即接受消息的人和物。 编码器：将信源发出的消息变换成适于信道传送的信号的设备。它包含下述三个部分：(1)信源编码器：在一定的准则下，信源编码器对信源输出的消息进行适当的变换和处理，其目的在于提高信息传输的效率。(2)纠错编码器：纠错编码器是对信源编码器的输出进行变换，用以提高对于信道干扰的抗击能力，也就是说提高信息传输的可靠性。(3)调制器：调制器是将纠错编码器的输出变换适合于信道传输要求的信号形式。纠错编码器和调制器的组合又称为信道编码器。 信道：把载荷消息的信号从发射端传到接受端的媒质或通道，包括收发设备在内的物理设施。信道除了传送信号外，还存储信号的作用。 译码器：编码的逆变换。它要从受干扰的信号中最大限度地提取出有关信源输出消息的信息，并尽可能地复现信源的输出。 1.3 同时掷一对骰子，要得知面朝上点数之和，描述这一信源的数学 模型。 解：设该信源符号集合为X 信研10“信息论与编码”期末复习题 1.信息论基础(狭义信息论/景点信息论/香农信息论)主要研究的三个方面是什么？ 信息测度、信道容量、信息率失真函数 2.全信息同时考虑的三个方面的内容是什么？ 语法信息、语义信息、语用信息 3.研究信息论的目的是什么？ 寻找信息传输过程的共同规律，以提高信息传输的可靠性、有效性、保密性等，已达到信息传输系统的最优化 4.消息、信号、信息的含义、定义及区别。 信息--事物运动的状态及状态变化的方式。 消息--包含信息的语言，文字和图像等。 信号--消息的物理体现。 消息是信息的数学载体、信号是信息的物理载体 同一信息，可以采用不同形式的物理量来载荷，也可以采用不同的数学描述方式同一类型信号或消息也可以代表不同内容的信息 5.信息的特征与分类。 1.接收者在收到信息之前，对其内容是未知的，所以信息是新知识，新内容； 2.信息是能使认识主体对某一事物的未知性或不确定性减少的有用知识； 3.信息可以产生，也可以消失，同时信息可以被携带，被存储及处理； 4.信息是可以量度的，信息量有多少的差别 6.狭义信息论、广义信息论、一般信息论研究的领域。 狭义信息论：信息论是在信息可以量度的基础上，对如何有效，可靠地传递信息进行研究的科学。它涉及信息量度，信息特性，信息传输速率，信道容量，干扰对信息传输的影响等方面的知识。 广义信息论：信息是物质的普遍属性，所谓物质系统的信息是指它所属的物理系统在同一切其他物质系统全面相互作用（或联系）过程中，以质、能和波动的形式所呈现的结构、状态和历史。包含通信的全部统计问题的研究，除了香农信息论之外，还包括信号设计，噪声理论，信号的检测与估值等。 概率信息：信息表征信源的不定度，但它不等同于不定度，而是为了消除一定的不定度必须获得与此不定度相等的信息量 信息论与编码实验报告-标准化文件发布号：（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 次称量中达到 信息论与编码复习总结 题型：填空、解答、计算 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尽量小。 信源编码：主要任务就是减少冗余，提高编码效率。 实验一 关于信源熵的实验 班级：电子131501 姓名：赵英凯 学号：201315020137 时间：2016.5.22 一、实验目的 1. 掌握离散信源熵的原理和计算方法。 2. 熟悉matlab 软件的基本操作，练习使用matlab 求解信源的信息熵。 3. 自学图像熵的相关概念，并应用所学知识，使用matlab 求解图像熵。 二、实验原理 1. 离散信源相关的基本概念、原理和计算公式 产生离散信息的信源称为离散信源。离散信源只能产生有限种符号。随机事件的自信息量I（xi）为其对应的随机变量xi 出现概率对数的负值。 即： I （xi ）= -log2p ( xi) 随机事件X 的平均不确定度（信源熵）H（X）为离散随机变量 xi 出现概率的数学期望，即： 2.二元信源的信息熵 设信源符号集X={0，1} ，每个符号发生的概率分别为p(0)= p，p(1)= q，p+ q =1，即信源的概率空间为： 则该二元信源的信源熵为： H( X) = - plogp–qlogq = - plogp –(1 - p)log(1- p) 即：H (p) = - plogp –(1 - p)log(1- p) 其中 0 ≤ p ≤1 3. MATLAB二维绘图 用matlab 中的命令plot( x , y) 就可以自动绘制出二维图来。例1-2，在matlab 上绘制余弦曲线图，y = cos x ，其中 0 ≤ x ≤2 >>x =0:0.1:2*pi； %生成横坐标向量，使其为 0，0.1，0.2，…， 6.2 >>y =cos(x )； %计算余弦向量 >>plot(x ,y ) %绘制图形 4. MATLAB求解离散信源熵 求解信息熵过程： 1) 输入一个离散信源，并检查该信源是否是完备集。 2) 去除信源中符号分布概率为零的元素。 3) 根据平均信息量公式，求出离散信源的熵。 5. 图像熵的相关知识 图像熵是一种特征的统计形式，它反映了图像中平均信息量的多少。信息论与编码技术复习题2
信息论与编码实验报告材料
信息论与编码习题参考答案(全)
信息论与编码实验报告
信息论与编码期末复习
信息论与编码课后习题答案
信息论与编码复习资料(新)
信息论与编码试题集与答案(新)
(完整版)信息论与编码概念总结
信息论与编码第一章答案
信息论与编码”期末复习题
信息论与编码实验报告
信息论与编码复习总结
信息论与编码实验1-3
相关主题
文本预览