信息论与编码实验讲义
宋毅
淮阴师范学院物电学院
2012年9月15日
序言
本实验讲义配合电子信息类专业开设的专业课《信息论与编码》而编写,作为《信息论与编码》的配套讲义,供该课程配套实验用。
信息论与编码是现代信息科学的基础技术之一,也是理论与实践不可分离的一门学科,本讲义力求注重实践和培养学生动手能力,同时注重信息技术的仿真应用实验。
由于水平限制,书中难免有不足和差错之处,恳请广大师生批评指正。
编者
2012年9月
实验一、绘制二进制熵函数曲线
一、实验目的
1.掌握二进制符号熵的计算;
2.掌握MATLAB的应用;
3.掌握Matlab绘图函数;
4.掌握、理解熵函数表达式及其性质
二、实验条件
计算机一台,MATLAB仿真软件。
三、实验内容
(1)MATLAB的应用(请参阅相关书籍)
(2)打开MATLAB,在命令窗口中输入eidt,弹出编辑窗口,如图1:
图1 MATLAB的编辑窗口
(3)输入源程序:
clear;
x=0.001:0.001:0.999
y=-x.*log2(x)-(1-x).*log2(1-x);
plot(x,y);
grid on
(4)保存文件为entropy.m;
(5)单击Debug菜单下的Run,或直接按F5执行;
(6)执行后的结果图2:
四、实验分析
clear;
x=0.001:0.001:0.999
y=-x.*log2(x)-(1-x).*log2(1-x); plot(x,y);
xlabel('p');
ylabel('H(p)');
title('H(p)');
grid on
clear;
x=0.001:0.02:0.999
y=-x.*log2(x)-(1-x).*log2(1-x); plot(x,y);
xlabel('p');
ylabel('H(p)');
title('H(p)');
grid on
clear;
x=0.009:0.002:0.991
y=-x.*log2(x)-(1-x).*log2(1-x); plot(x,y);
xlabel('p');
ylabel('H(p)');
title('H(p)');
grid on
分析总结:
(1)熵函数是一个严格上凸函数
(2)熵的极大值,二进符号的熵在p(x1)=p(x2)=0.5取得极大值
(3)调调整p(x1)的取值步长,重画该曲线。当步长改变为0.02,步长变大的时候,可以看到函数图像有一段缺失,且图像不对称。
(4)调整p(x1)的取值区间可以发现(3)的问题就解决了,函数图像仍有缺失,但是图像对称。可以发现当步长改变时,p(x1)取值区间也应该改变,否则图像不对称 (5)当二元信源符号0和1以等概率发生的时候,信源熵达到极大值,等于1bit 信息量。 (6)实验需要多次操作,不断改变数值,观察图像,会有意想不到的结果出现。例如概率p 的取值以及取p 时的步长的改变,图像也随之改变,另外p 是对称出现的而不是只有一端缺失。
实验二、一般信道容量计算
一、实验目的
1.熟悉工作环境及Matlab 软件 2.理解平均互信息量表达式及其性质 3.理解信道容量的含义
二、 实验原理
1.平均互信息量(I(X;Y))是统计平均意义下的先验不确定性与后验不确定性之差,是互信息量的统计平均
:
()()()()()()
;/;/=-=-I X Y H X H X Y I Y X H Y H Y X
2.离散信道的数学模型
离散信道的数学模型一般如图1所示。图中输入和输出信号用随机矢量表示,输入信号为X= (X1, X2,…, XN),输出信号为Y= (Y1, Y2,…, YN);每个随机变量Xi 和Yi 又分别取值于符号集A={a1, a2, …, ar}和B={b1, b2, …, bs},其中r 不一定等于s ;条件概率P(y|x) 描述了输入信号和输出信号之间的统计依赖关系,反映了信道的统计特性。
),...,,(21N X X X X = )|(x y P ),...,,(21N Y Y Y Y =
∑=1
)|(x y P
图1离散信道模型
二元对称信道
这是很重要的一种特殊信道(简记为BSC ),。它的输入符号X 取值于{0,1},输出符号Y 取值于{0,1},r=s=2, a1=b1=0,a2=b2=1,传递概率为
p p P a b P =-==1)0|0()|(11, p p P a b P =-==1)1|1()|(22
p P a b P ==)1|0()|(21, p P a b P ==)0|1()|(12
其中,)0|1(P 表示信道输入符号为0而接收到的符号为1的概率,)1|0(P 表示信道输入符号为1而接受到的符号为0的概率,它们都是单个符号传输发生错误的概率,通常用p 表示。而)0|0(P 和)1|1(P 是无错误传输的概率,通常用
p
p =-1表示。
X 1-p Y
01=a 10b =
p
p
12=a 21b =
二元对称信道
用矩阵来表示,即得二元对称信道的传递矩阵为
???
-???-p p p
p 111100 依此类推,一般离散单符号信道的传递概率可用以下形式的矩阵来表示,即
b1 b2 … bs
?
??
??
??
?????)|()|()|()|()
|()|()|()|()|(212222
11121121
r s r r s s r
a b P a b P a b P a b P a b P a b P a b P a b P a b P a a a
并满足式
∑==s
j
i j a b P 1
1)|( (r i ,,2,1 =)。
为了表述简便,记ij i j p a b P =)|(,信道的传递矩阵表示为
?
?
???
???????=rs r r s s p p p p p p p p p P
1
1
22221
11211 而且满足
0>j i p ???是列的标号是行的标号
j i
平均互信息
平均互信息表示接收到输出符号后平均每个符号获得的关于输入变量X 的信息量,也表示输入与输出两个随机变量之间的统计约束程度。
∑
∑
-=
XY X y x P xy P x P x P Y X I )|(1log
)()(1
log
)();(
∑∑-=
XY
XY
y x P xy P x P xy P )|(1
log )()(1
log )(
∑=
XY
x P y x P xy P )
()|(log
)(
∑
=
XY
y P x P xy P xy P )()()(log )(
∑
=
XY y P x y P xy P )
()|(log
)( 其中X 是输入随机变量,Y 是输出随机变量。
平均互信息是互信息(即接收到输出符号y 后输入符号x 获得的信息量)的统计平均值,所以永远不会取负值。最差情况是平均互信息为零,也就是在信道输出端接收到输出符号Y 后不获得任何关于输入符号X 的信息量。
对于每一个确定信道,都有一个信源分布,使得信息传输率达到最大值,我们把这个最大值称为该信道的信道容量。
()
max {(;)}
P x C I X Y =
相应的输入概率分布称为最佳输入分布。 三、实验内容
1.绘制平均互信息量图形
对于二元对称信道的输入概率空间为0,1(),1ωωω????
=????=-????X P x 平均互信息:
根据:1
()()(|)1===∑r
j i j i i P b P a P b a
所以:
2
1(0)()(0|)(0)(0|0)(1)(0|1)ωω====+=+∑i i i P y P a P a P P P P p p
21
(1)()(0|)(0)(1|0)(1)(1|1)ωω====+=+∑i i i P y P a P a P P P P p p
1111
(;)()()()log ()log [log log ]
()()()
ωωωωωωωωωω=-=+++-+++=+-I X Y H Y H p p p p p p p p p p p p p
H p p H p 请绘制当
,ωp 从0到1之间变化时的平均互信息熵曲线
2. 信道容量图形
一个信道是一个二进制输入,二进制输出的信道,输入和输出字母表
{0,1}==X Y ,且该信道特性由发送1码和0码的两个错误转移概率(0|1)=P e 和(0|1)0=P 来表征。绘出当0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1=e 时的平均互信息(;)I X Y 和(1)==p P X 间的函数关系。确定每种情况下的信道容量。 四、实验报告要求
你能从实验图形中了解它的一些什么性质? 五、实验结果及分析
clear;
[w,p]=meshgrid(0.00001:0.003:1);
y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p)).*log(w.*p +(1-w).*(1-p))+p.*log(p)+(1-p).*log(1-p);
(;)()(/)
=-I X Y H Y H Y X 1()()(/)log
(/)
=-∑∑X
Y
H Y P x P y x P y x 11()()[log
log ]=-+∑X
H Y P x p p p p
11
()[log
log ]()()=-+=-H Y p p H Y H p p p
meshz(w,p,y);
title('二进制信道的信道容量');
Xlabel('w');ylabel('p');zlabel('I(W;Y)');
grid on
clear;
w=0.5;
p=0.001:0.001:0.999;
y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p)).*log(w.*p +(1-w).*(1-p))+p.*log(p)+(1-p).*log(1-p);
plot(p,y);
title('二进制信道的信道容量');
xlabel('p');
ylabel('I(W;Y)');
grid on
clear;
p=0.1;
w=0.001:0.001:0.999;
y=-(w.*(1-p)+(1-w).*p).*log(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p)).*log(w.*p +(1-w).*(1-p))+p.*log(p)+(1-p).*log(1-p);
plot(w,y);
title('二进制信道的信道容量');
Xlabel('w');ylabel('I(W;Y)');
grid on
w=0.9998
p=0:0.1:1
IXY=-(w.*(1-p)+(1-w).*p).*log2(w.*(1-p)+(1-w).*p)-(w.*p+(1-w).*(1-p)).*log2( w.*p+(1-w).*(1-p))+(p.*log2(p)+(1-p).*log2(1-p))
stem(p,IXY);grid on
title('信道容量')
xlable('p')
ylable('I(X;Y');
grid on
分析:
从第一个三维图上面可以看出是w,p与I(X;Y)之间的关系。而第二个图和第三个图都是第一个图的侧面图。从第二个侧面图发现当w=0时,错误概率为0,信道容量达到最大,每符号1bit;当w=1/2时,错误概率与正确概率相同,互信息为0,在信道接收端平均每个符号才获得最小的信息量,即信道容量为0;从第三个侧面图发现当固定信道时,只有当输入变量是等概率分布,即p(x=0)=p(x=1)=在信道接收端平均每个符号才获得最大的信息量,即等于1.
当w固定时,即信源固定后,I(p;y)是关于信道传递概率p的下凸函数。信道输出端获得关于信源的信息量是信道传递概率的下凸函数。也就是说输出端所获得的信息量最小。
当p固定时,即固定某信道时, I(w;y)是关于输入信源的概率分布的上凸函数,即对于每一个确定信道,都存在一个信源分布,使得信息传输率达到最大值,我们把这个最大值称为该信道的信道容量。
三、绘制离散信源信息率失真函数曲线
一、实验目的:
1.了解率失真函数性质、意义。
2.掌握简单的率失真函数计算方法;
3.掌握使用Matlab实现一般率失真函数的计算方法;
二、实验原理
二元对称信源的R(D)函数
1
ω≤
设二元信源U={0,1},其分布概率 而接收变量v={0,1},设汉明失真矩阵为: 因而最小失真度 。并能找到满足该最小失真的试验信道,且是一个
无噪无损信道,其信道矩阵为:
要达到最大允许失真,唯一确定 此时,可计算得信息传输率 一般情况下,当 时
三、实验内容
1.从理论上计算r=s=2。p(u=1)=p,p (u=2)=1-p;d=[0,1;1,0]的率失真函数R(D)。
2.对一般性的DMS 信源,计算率失真函数R(D)的理论公式进行推导。
3.找出比较合适的方程求解方法。
4.使用编制Matlab 编制程序求解一般的率失真函数R(D)。
5.给定r=s=2。p(u=1)=0.4,p=(u=2)=0.6;d=[0,1;1,0],测试程序,即比较
程序运行结果与理论计算结果,???≥≤≤-=w d w d d H w H D R
00)()()(
6.改变参数,画出函数图。
四、思考题
你能从实验图形中了解它的一些什么性质?
可以计算得:二元对称信源信息率失真函数为
()()()
R D H H D ω=-()()0()0H H D D R D D ωωω-≤≤?=?
>?
,[](,)(,)
U V
D E d p u v d u v ==∑(0,1)(1,0)E P u v P u v P ===+===max min ()(,)
V
U
D P u d u v =∑min[(0)(0,0)(1)(1,0);(0)(0,1)(1)(1,1)]
V
P d P d P d P d =++min[(1),]ωωω
=-=()[,1]P u ωω=-0110D ??
=????
min 0D =1
001P ??=????
(0)(;)()
R I U V H ω==0101P ??=?
???(;)0
I U V =max 0D D ω<<=
五、注意事项
1.提前预习实验,认真阅读实验原理。
2.认真高效的完成实验,实验过程中服从实验室管理人员以及实验指导老师
的管理。
3.实验报告要求有:
●问题的提出:包括R(D)的物理意义、用途(可以举出具体的用途)、
计算的困难性等。
●解决问题的原理方法:包括所有的公式推导的细节。
●解决问题的具体方法:包括程序框图及Matlab源程序。
●实验结果:利用你的程序给出不同参数得到的实验结果。
●结果分析:包括R(D)的性质、程序收敛情况、程序改进的方向等。
4.每个同学必须独立完成实验(不能抄袭,否则两人均为零分),实验成绩是该门课程成绩的主要依据。
六、实验结果及分析
p1=0.4;
d1=0:0.001:0.4
y1=-p1.*log2(p1)-(1-p1).*log2(1-p1)+d1.*log2(d1)+(1-d1).*log2(1-d1);
p2=0.3;
d2=0:0.001:0.3
grid on
y2=-p2.*log2(p2)-(1-p2).*log2(1-p2)+d2.*log2(d2)+(1-d2).*log2(1-d2);
plot(d1,y1,'k-');
hold;
plot(d2,y2);
grid on
title('离散信源信息率失真函数')
xlabel('D');ylabel('R(D)');
分析:
(1)R(D)在定义域内是失真度D的U型下凸函数;R(D)在定义域内是关于D的连续函数;R(D)的单调递减性,容许的失真度越大,所要求的信息率越小。
(2)对于固定的信源分布,平均互信息量I(X;Y)是信道转移概率 p(bj/ai) 的下凸函数。也就是说:存在一个信道使某一特定信源经过此信道传输时,信道的平均互信息达到极小值.
性质: R(D)是非负的实数,定义域为0到Dmax,其值为0到H(X);当D>Dmax时,R(D)=0。
R(D)是关于D的下凸函数,因而也是关于D的连续函数。
R(D)是关于D的严格递减函数。
对于同一D,信源分布越均匀,R(D)就越大,信源压缩的可能性越小,反之,若信源分布越不均匀,即信源剩余度越大R(D)就越小,压缩的可能性越大。
实验四、香农编码
一、实验目的
(1)了解香农编码的基本原理及其特点;
(2)熟悉掌握香农编码的方法和步骤;
(3)掌握Matlab编写香农编码的程序。
二、实验原理
香农编码的步骤如下:
⑴将信源符号按概率从大到小的顺序排列,
p(a1)≥ p(a2)≥…≥ p(an)
⑵确定满足下列不等式的整数Ki ,
-log2 p(ai)≤ Ki <1-log2 p(ai)
⑶令p(a1)=0,用Pi表示第i个码字的累加概率,
⑷将Pi用二进制表示,并取小数点后Ki位作为符号ai的编码。
三、实验内容
(1)根据香农编码的方法和步骤,用香农编码编写程序
(2)用编写的源程序验证书中例题的正确性。
四、实验报告要求
总结香农编码的基本原理及其特点?
五、实验结果和总结
function [C]=deczbin(A,B)
C=zeros(1,B);
temp=A;
for i=1:B
temp=temp*2;
if temp>1
temp=temp-1;
C(1,i)=1;
else
C(1,i)=0;
end
end
n=input('输入信源符号个数n=')
p=zeros(1,n);
for i=1:n
p(1,i)=input('输入信源符号概率:');
end
if sum(p)<1||sum(p)>1
error('输入概率不符合概率分布 ')
end
y=fliplr(sort(p));
D=zeros(n,4);
D(:,1)=y; for i=2:n D(1,2)=0;
D(i,2)=D(i-1,1)+D(i-1,2);
end
for i=1:n
D(i,3)=-log2(D(i,1)); D(i,4)=ceil(D(i,3));
end
D
A=D(:,2);
B=D(:,4);
for j=1:n
C=deczbin(A(j),B(j))
end
输入信源符号个数n=7
n =
7
输入信源符号概率:0.2
输入信源符号概率:0.19
输入信源符号概率:0.18
输入信源符号概率:0.17
输入信源符号概率:0.15
输入信源符号概率:0.10
输入信源符号概率:0.01
D =
0.2000 0 2.3219 3.0000 0.1900 0.2000 2.3959 3.0000 0.1800 0.3900 2.4739 3.0000 0.1700 0.5700 2.5564 3.0000 0.1500 0.7400 2.7370 3.0000 0.1000 0.8900 3.3219 4.0000 0.0100 0.9900 6.6439 7.0000
C =
0 0 0
C =
0 0 1
C =
0 1 1
C =
1 0 0
C =
1 0 1
C =
1 1 1 0
C =
1 1 1 1 1 1 0
香农第一定理指出,选择每个码字的长度Ki满足下式 I(xi)≤K﹤I(xi)+1,i为任意值就可以得到这种码。这种编码方法就是香农编码。
香农编码多余度稍大,效率低,实用性不强。
香农编码是码符号概率大的用短码表示,概率小的是用长码表示,程序中对概率排序,最后求得的码字就依次与排序后的符号概率对应。
实验五、Huffman编码
一、实验目的
1.进一步熟悉Huffman编码过程;
2.掌握Matlab程序的设计和调试技术。
二、实验原理
1、二进制Huffman编码的基本原理及算法
(1) 把信源符号集中的所有符号按概率从大到小排队。
(2) 取概率最小的两个符号作为两片叶子合并(缩减)到一个节点。
(3) 视此节点为新符号,其概率等于被合并(缩减)的两个概率之和,参与概率排队。
(4) 重复(2)(3)两步骤,直至全部符号都被合并(缩减)到根。