信息电子学院实验指导书格式信息论.docx

信息电子学院实验指导书格式信息论.docx

《信息电子学院实验指导书格式信息论.docx》由会员分享，可在线阅读，更多相关《信息电子学院实验指导书格式信息论.docx（14页珍藏版）》请在冰点文库上搜索。

信息电子学院实验指导书格式信息论

《—信息论基础—》

实验指导书

童基均编写

适用专业：

通信工程

浙江理工大学信息电子学院

二○○八年三月

前言

信息论是现代通信与信息工程的理论基础.作为电子信息科学与技术专业本科生的学科基础课，本课程主要讲授：

信息的定义和测度、信源和信息熵、连续熵和信息变差、信道和互信息、平均互信息和信道容量、数据处理和信息测量理论、无失真信源编码理论和编码方法等内容.

本课程按“单符号离散信息系统”、“多符号离散信息系统”、“连续信息系统”三个“系统”层面，逐步深入展开，以严密的数学分析贯串始终.通过教学，使学生掌握信息理论的基本概念和信息分析方法，为今后进一步研究信息科学和信息技术打下坚实的理论基础.

实验一：

离散信道容量的迭代计算

实验学时：

3

实验类型：

（演示、验证、综合、√设计、研究）

实验要求：

（√必修、选修）

一、实验目的

通过本实验的学习，理解和掌握信道容量的概念和物理意义；了解信道容量的计算方法尤其是迭代计法；采用计算机编程实现迭代算法.

二、实验内容

信道容量的概念和物理意义；

信道容量的计算方法；

采用计算机编程实现信道容量的计算

三、实验原理、方法和手段

1．离散信道的物理模型为：

信道容量定义为平均互信息的最大值：

.

2．信道容量表征了一个信道传送信息的最大能力，实际中传送的信息量小于信道容量，否则传送过程中出现错误.

3．由信道容量的定义可知，I（X,Y）的值由信道的传送概率决定的，因而信道的传递概率决定了信道的信道容量.给定了信道的传递概率，可以通过推导方法求得信道的信道容量，一般可以求出传递效率达到信道容量时候的输入信号的分布，但是这种方法不方便计算机实现.

4．迭代法，便于计算机实现：

迭代法分成三个模块，一个迭代计算反向实验信道

，另一个迭代计算

，第三个检查一次迭代前后信道容量误差的变化是否小于检测值ε（可取0.0001）,如果小于检测值则停止计算，输出结果.

信道容量的迭代计算具体如下：

求信道容量C就是在Pi的约束下，求I（X;Y）的极大值.为计算方便，重写下I（X;Y）式，公式中的对数取自然数.

（1）

首先引入反条件概率，即

（2）

则

（3）

迭代算法的要点是，当信道固定（即

固定）时，把I（X;Y）看成是pi和qji的函数，用公式（3）进行信道容量计算的迭代.每一次迭代有两步组成：

（a）将

固定，在约束

的条件下变动

，得到I（X;Y）的极大值，记为

；此时

满足

（2）式，重写为：

（4）

（b）（b）将

固定，在约束

的条件下变动

，得到I（X;Y）的极大值，记为

；此时

满足：

（5）

（4）与（5）是迭代的基本公式.先取一组

（n=1）的初始值，通常选取均匀分布，由（4）计算

，再将此值代入（5）计算

，依此反复计算下去.每次迭代都要利用（3）计算I（X;Y）的值.可以设置门限值，当相临的两次计算值I（X;Y）小于门限值时，就结束迭代过程，此时I（X;Y）的值就是信道容量C.

可以采用下述方法，避免计算反向条件概率，使算法简化：

将（4）代入（5）得

（6）

其中

（7）

将（6）（5）代入（3），得

（8）

现将算法归纳如下：

设信道输入输出符号集的大小分别为r，s，且ε为一个小的正数.且初始概率分布为均匀分布，即设pi=1/r

1）计算

；

2）计算

；

3）计算

；

4）计算

；

5）若（IU-IL）<ε，转到6），

否则

返回1）

6）输出信道容量的值C=IL（比特/符号）

四、实验数据源

1．P（a1）=p（a2）=0.5

2．P（a1）=p（a2）=0.5

五、实验组织运行要求

以学生自主训练为主的开放模式组织教学

六、实验条件

（1）微机

（2）MATLAB编程工具

七、实验报告

实验预习：

离散信道容量的定义以及信道容量的迭代计算方法

实验记录：

通过迭代算法计算能够得到的信道容量的结果

实验报告

#include 

  using namespace std;

  #define FLOAT_MINUS_PRECISION 0.00001

  typedef vector VEC_PFLOAT;

  //迭代计算信道容量,参数值为信源,信宿符号个数和信道转移概率矩阵,返回信道容量< /pre> 

  float GetCapacity（int nSourceSymbol,int nHostSymbol,const VEC_PFLOAT& vTransMatrix）

  {

  //信道容量初始化为最小值

  float fCapacity = FLT_MIN;

  //信源概率分布

  float *pfSoureProb = new float[nSourceSymbol];

  //初始化信源分布为均匀分布

  int i;

  for （i = 0; i < nSourceSymbol; i++）

  {

  pfSoureProb[i] = 1.0 / nSourceSymbol;

  }

  //初始化φ函数

  VEC_PFLOAT vPhi;

  for （i = 0; i < nSourceSymbol; i++）

  {

  float *pfTemp = new float[nHostSymbol]; 

  vPhi.push_back（pfTemp）;

  }

  //设置精度;

  const float cfDelta = 0.02f;

  float fPrecision;

  //迭代计算

  int j,k;

  float *pfSum = new float[nSourceSymbol];

  do 

  {

  for （i = 0; i < nSourceSymbol; i++）

  {

  for （j = 0; j < nHostSymbol; j++）

  { 

  //计算ΣPi*Pji

  float fSum = 0.0f;

  for （k = 0; k < nSourceSymbol; k++）

  {

  fSum += pfSoureProb[i] * vTransMatrix[k][i];

  }

  vPhi[i][j] = pfSoureProb[i] * vTransMatrix[j][i] / fSum;

  } 

  }

  float fSumDeno = 0.0f; //分母求和 

  for （i = 0; i < nSourceSymbol; i++）

  { 

  float fSum = 0.0f;

  for （j = 0; j < nHostSymbol; j++）

  {

  fSum += vTransMatrix[j][i] * logf（vPhi[i][j]）;

  }

  pfSum[i] = expf（fSum）;

  fSumDeno += pfSum[i];

  }

  for （i = 0; i < nSourceSymbol; i++）

  { 

  pfSoureProb[i] = pfSum[i] / fSumDeno;

  }

  //计算新一轮的容量

  float fNewC = logf（fSumDeno）;

  //计算精度

  fPrecision = fabs（fNewC - fCapacity） / fCapacity;

  fCapacity = fNewC;

  } while（fPrecision - cfDelta > 0.0f）;

  //释放临时资源

  delete []pfSum;

  for （i = 0; i < vPhi.size（）; i++）

  {

  float* pfTemp = vPhi.at（i）;

  delete pfTemp;

  }

  vPhi.clear（）;

  return fCapacity;

  }

  int main（）

  {

  //转移矩阵

  VEC_PFLOAT vTransMatrix;

  int nCol,nLine;

  cout<<"请输入信源符号个数:

";

  cin>>nLine;

  cout<<"请输入信宿符号个数:

";

  cin>>nCol;

  cout<<"请依次输入"<<<"行信道转移概率矩阵:

（以空格隔开每个概率）\n";< /pre> 

  for （int i = 0; i < nLine; i++）

  {

  float *pfTemp = new float[nCol];

  Label

  float fSum = 0.0f; 

  cout<<"X"<<<":

";

  for （int j = 0; j < nCol - 1; j++）

  {

  cin>>pfTemp[j];

  fSum += pfTemp[j];

  }

  if （1.0f - fSum < 0）

  {

  cout<<"转移概率和应该为1,请重新输入!

\n";

  goto Label1;

  }

  else

  {

  pfTemp[j] = 1.0f - fSum;

  cout<<"信源符号 X"<<<"的转移概率分别为:

";

  for（int k = 0; k < nCol; k++）

  cout<

  cout<

  }

  vTransMatrix.push_back（pfTemp）;

  }

  cout<<"信道容量为:

"<< /pre> 

  for （int k = 0; k < vTransMatrix.size（）; k++）

  {

  float* pfTemp = vTransMatrix.at（k）;

  delete pfTemp;

  }

  vTransMatrix.clear（）;

  return 0;

  }

八、实验心得：

1、由于长时间未编程了，对编程有点生疏，通过在网上找了一些代码，通过修改已有代码来逐步学习离散信道容量的迭代计算.

2、

3、

4、

实验二：

Huffman编码的实现

实验学时：

3

实验类型：

（演示、验证、综合、√设计、研究）

实验要求：

（√必修、选修）

一、实验目的

理解和掌握huffman编码的基本原理和方法，实现对信源符号的huffman编码.

二、实验内容

1.理解和掌握huffman编码的基本原理和方法

2.通过MATLAB编程实现对单信源符号的huffma编码

3.计算信源的信息熵、平均码长以及编码效率

三、实验原理

1．Huffman编码按信源符号出现的概率而编码，其平均码长最短，所以是最优码.

2．无失真信源编码定理：

对于熵为H（X）的离散无记忆的平稳信源，必存在一种无失真编码，使每符号的平均码长满足不等式：

3．二元Huffman编码：

若将编码设计为长度不等的二进制编码，即让待传字符串中出现概率大的字符采用尽可能短的码字，而把长的码字分配给概率小的信源符号.

构造方法如下：

（a）将信源概率分布按大小以递减次序排列；合并两概率最小者，得到新信源；并分配0/1符号.

（b）新信源若包含两个以上符号返回（a），否则到（c）.

（c）从最后一级向前按顺序写出每信源符号所对应的码字.

4．Huffman编码算法

ProcedureHUFFMAN（{si},{pi}）

ifq==2then

returns0→0,s1→1

else

降序排序{pi}

缩减信源:

创建一个符号s′以取代sq-2,sq-1,其概率为p′=pq-2+pq-1

递归调用Huffman算法以得到s0,…,sq-3,s′的编码:

w0,…,wq-3,w′,相应的概率分布为p0,…,pq-3,p′

Returns0→w0,…,sq-3→wq-3,sq-2→w′0,sq-1→w′1

endif

endprocedure

四、实验数据源

1．

2．

五、实验组织运行要求

以学生自主训练为主的开放模式组织教学

六、实验条件

（1）微机

（2）MATLAB编程工具

七、实验报告

实验预习：

Huffman编码的基本方法

实验记录：

通过编码实现单信源符号的码字

实验记录：

实验报告

八、实验心得：