信息论与编码实验报告

NANCHANGUNIVERSITY信息论与编码实验报告（2018年11月27日）学院：信息工程学院系电子信息工程系专业班级：学生姓名：学号：指导教师：目录实验一自信息量和熵源..............................................................................................实验二准对称信道容量..............................................................................................实验三费诺不等式......................................................................................................实验四香农编码..........................................................................................................实验五费诺编码..........................................................................................................实验六霍夫曼编码......................................................................................................实验一自信息量和熵源一、实验要求1、画出I=-log2𝑝的函数图；2、画出H(p)=-plog2𝑝-(1-p)log2(1−𝑝)函数图。二、实验原理及理论分析自信息量：一个事件的自信息量就是对其不确定性的度量。直观地把自信息量定义为收到某消息获得的信息量=不确定性减少的量。而事件x发生的不确定性与事件发生的概率q(x)有关，概率越小，不确定性越大。定义I(x)=-logq(x)。熵（平均自信息量）：实际信源包含许多消息X=(x1,x2,…)，因此需要考虑整个信源自信息量的统计平均值。无记忆信源的平均自信息量定义为各消息自信息量的概率加权平均值，即平均自信息量H(X)定义为H(X)=-∑𝑞(𝑥𝑖)𝑙𝑜𝑔𝑞(𝑥𝑖)𝑖，简称熵。H(X)是唯一确定集合X中任一事件𝑥𝑖(𝑖=1,2,…)所需要的平均信息量，反应了X中事件𝑥𝑖出现的平均不确定性。三、实验结果四、实验结果分析由图可知，I(x)是p的单调递减函数，概率小的事件一旦发生则赋予的信息量大，概率大的事件如果发生则赋予的信息量小。当p=1时，I(x)=0，表示确定事件发生得不到任何信息。当p=0时，I(x)→∞，表示不可能事件一旦发生，信息量将无穷大。由图可知，对于二元信源，p=0或者p=1都对应确定事件的分布，因此熵值H(X)为0，而等概分布时，熵值H(X)取最大值为1。五、实验总结通过这次实验，使用Matlab数值模拟信源熵和自信息量，进一步理解了自信息量和熵的概念、计算和它们的物理意义。理论和实践的结合让我对这个知识点了解得更加深刻。实验二准对称信道容量一、实验要求画出强对称信道容量数值模拟图。二、实验原理及理论分析信道是信息传输的通道。信道可以按不同得特性进行分类，根据输入输出信号得特点可以分为以下四类：离散信道、连续信道、半连续信道、波形信道。根据统计特性，即转移概率得不同，信道又分为无记忆信道和有记忆信道两类。强对称信道是一种常见的离散无记忆信道，每一子集关于行、列都对称，它的输入符号x∈{0，1}，输出符号y∈{0，1}，信道特性可表示为信道矩阵。信道转移概率p(y=0|x=0)=p(y=1|x=1)=1-p,p(y=1|x=0)=p(y=0|x=1)=p。强对称信道的容量计算公式：C=logK+∑𝑝(𝑦𝑗|𝑥𝑖)𝑙𝑜𝑔𝑝(𝑦𝑗|𝑥𝑖)𝑗=logK−H(P的行矢量)三、实验结果四、实验结果分析由图可知，p=0时，信道的输入符号和输出符号是一一对应的关系，此时信道容量C=log2，达到最大值。p=0.5时，信道的不确定性最大，此时信道容量C=0，这是一种最差的信道。p=1时，这是一种强噪信道，也是一种确定信道，此时信道容量也会达到最大值C=log2。五、实验总结通过Matlab数值模拟强对称信道容量，观察最高点最低点，加深了对强对称信道这一类特殊信道的理解，验证了理论计算的正确性。实验三费诺不等式一、实验要求画出费诺不等式示意图，以H(X|Y)为纵坐标，Pe为横坐标，画出函数H(Pe)+Pelog(r-1)随Pe变化的曲线图，标注logr点以及log(r-1)点。二、实验原理及理论分析设信道输入符号X和输出符号Y取自同一符号集A={𝑎1,𝑎2,…,𝑎𝑘}，则传输过程中的错误概率Pe和信道疑义度H(X|Y)之间满足下列关系式，也即著名的费诺不等式：H(X|Y)≤𝐻2(𝑝𝑒)+𝑝𝑒log(𝑘−1)费诺不等式的物理意义：进行一次判决后，关于X的疑义度可分为两项：1、是否判对，疑义度为𝐻2(𝑝𝑒)；2、如果判决出错（概率为𝑝𝑒），错在k-1个符号中的哪一个？疑义度不会超过log(k-1)。三、实验结果四、实验结果分析根据极大离散熵定理，信源的消息个数为M，则H(X)≤logM，等号当且仅当信源X中各消息等概时成立。如图所示，各消息等概分布时，信道疑义度即信源熵最大为log(r)。如图所示，当错误概率为1时，判决出错，错误发生在k-1个符号中，疑义度最大为log(k-1)。五、实验总结使用Matlab模拟时，𝑝0和𝑝𝑑的值不能直接取到0和1，这样围不成一个封闭区域，𝑝0和𝑝𝑑可以取到两个无限接近0和1的值。很好地掌握极大离散熵定理是理解费诺不等式的基础。实验四香农编码一、实验要求1、根据香农编码的方法和步骤，编写香农编码程序，得到码字和编码效率；2、用编写的源程序验证书中例题的正确性，并用图表示码长结果。二、实验原理及理论分析香农编码法是一种常用的变长编码法，对于证明变长编码定理起了很重要的作用。香农编码具体步骤如下：1、将信源发出的M个消息，按其概率递减顺序进行排列，得q(𝑥1)≥q(𝑥2)≥q(𝑥3)≥⋯≥q(𝑥𝑀);2、计算出各消息的-logq(𝑥𝑚)值，m=1，2，…，M;3、根据：−logq(𝑥𝑚)≤𝑛𝑚−logq(𝑥𝑚)+1,−logq(𝑥𝑚)为整数时取等。计算出每个消息的二进制代码的长度𝑛𝑚(m=1,2,…,M)，𝑛𝑚取正整数；4、为得到唯一可译码，计算出第m个消息的累加概率𝑝𝑚=∑𝑞(𝑥𝑖)𝑚−1𝑖=1，再将𝑝𝑚变换成二进制小数，取小数点后面𝑛𝑚位作为第m个消息的码字。三、实验结果四、程序流程图开始代码初始化判断信源是否合法重新输入否按递减顺序排列，并计算累加概率是计算码字长度k十进制小数转二进制小数取小数点后k位作为码字顺序重排计算平均码长、信源熵、编码效率结束五、实验结果分析香农编码严格意义上来说不是最佳码，它是采用信源符号的累计概率分布函数来分配码字。从结果中可以看出，香农编码法中，码符号概率大的用短码表示，概率小的是用长码表示。香农编码的编码效率并不是特别高。六、实验总结和后面两种编码方法相比，香农编码的效率不高，实用性不大。按照香农编码方法编出来的码，其平均码长不是最短的，不是最佳码。但是对其他编码方法有很好的理论指导意义，所以我们也应该掌握。实验五费诺编码一、实验要求1、根据费诺编码的方法和步骤编写费诺编码程序，得到码字和编码效率；2、用编写的源程序验证书中例题的正确性，并用图表示码长结果。二、实验原理及理论分析香农第一定理的物理意义阐明：信源等概分布时，信息传输率最大，应用到对信源进行编码，应使编码后的码集尽可能等概分布，如果将该码集看成一个新的信源，这时新信源所包含的信息量最大。据此，产生了费诺编码法。费诺编码法的具体步骤如下：1、将信源发出的M个消息，按其概率递减顺序进行排列，得q(𝑥1)≥q(𝑥2)≥q(𝑥3)≥⋯≥q(𝑥𝑀)，把消息集{𝑥1,𝑥2,𝑥3,…𝑥𝑀}按其概率大小分解成两个子集，使两个子集的概率之和尽可能相等，把第一个子集编码为“0”，第二个子集编码为“1”，作为代码组的第一个码元；2、对子集做第二次分解，同样分解成两个子集，并使两个子集的概率之和尽可能接近相等，再把第一个子集编码为“0”，第二个子集编码为“1”，作为代码组的第二个码元；3、如此一直进行下去，直到各子集仅含一个消息为止；4、将逐次分解过程当中得到的码元排列起来就是各消息的代码。三、实验结果四、程序流程图开始代码初始化判断信源是否合法重新输入否按概率递减顺序排列是累加求和，确定分组后每组概率累加和尽可能相近第一组的信源码字加0，第二组的信源码字加1结束判断信源个数是否大于2否是判断分组点是不是第一个编号以分组点为界，重新编号分为两组否判断分组点是不是该组倒数第二个否分组点为新分组的第一个编号，其他依次编号是分组点为新分组的最后一个编号，其他编号不变是计算平均码长、信源熵、编码效率五、实验结果分析从结果中可以看出来，费诺编码法中，码符号概率大的，分解次数小；码符号概率小的，分解次数大。这种编码方法不一定能使短码得到充分利用。尤其当信源符号较多，并且有一些符号概率分布很接近时，分两大组的组合方法就很多。可能存在某种分配结果，会出现后面分组的概率和相差较远，因而使平均码长增加，所以费诺编码不一定是最佳码。六、实验总结费诺编码方法不唯一，费诺编码适合于对分组概率相等或相近的信源编码，费诺编码法编M进制码，M越大，信源的符号数越多，可能的编码方式就越多，编码过程就越复杂，当信源符号个数越多，编码效率就越低。实验六霍夫曼编码一、实验要求1、根据霍夫曼编码的方法和步骤，编写霍夫曼编码程序，得到码字和编码效率；2、用编写的源程序验证书中例题3.18的正确性，通过码长均值和均方差结果比较两种霍夫曼编码方法（用图形表示）。二、实验原理及理论分析霍夫曼编码法的具体步骤如下：以M个消息的D进制编码为例1、计算M+r=D+m(D-1)，m为整数，r为满足等式的最小正整数；2、若r≠0，添加r个概率为0的信源消息；3、将信源的M+r个消息按概率递减顺序排列；4、将概率最小的D个消息分别编码为D-1，D-2，…，1，0；5、将上述D个消息合并，求概率之和，并与余下的消息组成一个新的信源，再按概率递减顺序重新排列。如果概率之和与某个消息的概率相等，应把合并消息排在上面，这样可使合并消息重复编码的次数减少，使短码得到充分利用；6、重复步骤4、5，直到合并消息的概率之和为1；7、从最后一步开始，沿编码逆过程取各步骤得到的码符号，如此构成的码符号序列即为对应消息的码字。r个0消息是人为添加的，不需要取码符号。三、实验结果四、程序流程图开始代码初始化判断信源是否合法重新输入否是是按递减顺序排列，并将概率最小的两个编号为1，2将概率最小的两个加起来，和其他的一起作为一个新信源结束判断信源个数是否大于2否是计算平均码长、方差、码长均方差、信源熵、编码效率重新按递减顺序排列，概率相同的向上排/向下排五、实验结果分析因为在Matlab中，首位的0会被自动省略，不适合编码。所以这里利用1，2进行编码。从结果中可以看出，每次缩减信源的最后两个码字总是最后一位码元不同，前面各位码元相同。霍夫曼编码法中，概率小的消息码长更大，概率大的消息码长更小。可以看出霍夫曼编码法得到的码并不是唯一的，因为对于每次选出的两个消息，哪个编码为“1”，哪个编码为“0”是可以任意选取的，由此可以得到不同的编码，而且平均码长是不会变的。新组成的概率之和和原信源中的某概率相等时，将新组成的概率之和往上排和往下排