信息论课程设计实验

1、信息论课程设计实验报告题 目 1： 实现香农编码及计算其编码效率 题 目 2： 实现有噪信道编码中的循环码 院 系（部）： 计算机科学与技术学院 专业及班级： 信息与计算科学1301班 姓 名： 唐诗韵 学 号： 1308060105 日 期： 2016/01/10 目 录1. 课题描述12. 信源编码的相关介绍23. 香农编码（题目一）3 3.1. 香农编码算法3 3.2. 香农编码特点44. 香农编码的C+程序实现4 4.1. 程序设计4 4.2. 运行结果65. 实现有噪信道中的循环码编码方法（题目二）6 5.1. 循环码编码算法6 5.2. 循环码编码特点76. 循环码编码的C+程序实

2、现7 6.1. 程序设计7 6.2. 运行结果97. 总 结108. 参考文献111. 课题描述 信息论是一门理论和实践相结合的专业，因此相关题目都是来自于实践，同时具有上机练习的可操作性，此门科目是通信的基础。香农1984年发表的一篇论文标志着信息论诞生，在他的论文中主要用概率来描述有效传输信息的问题，用概率给予了信息的定量描述方法，并提出了信源熵的概念，在现实生活中，人们经常把消息和信息分不清，认为消息就是信息，实则不是，消息是描述实物，而信息是定量描述一个消息所传输的信息量，通常用自信息量来描述一个消息所传达的信息量，它取值为此事件发生的概率的负对数，它表示一个事件发生之前此事件发生的不

3、确定性大小，也表示一个事件发生后它所能提供的信息量，两个相互独立的消息所提供的信息量等于各自信息量之和。此外，还可用互信息来描述信息的传达，为一个事件给出关于另一个事件的信息量，也表示事件y出现后信宿获得的关于x的信息量，互信息的引出，使信息的传递得到了定量的表示。如果事件是以序列的形式表示的，及事件集，则用平均自信息量来表示信源所传递的信息，平均信息量表示信源的平均不确定性，比如抛掷一枚硬币的试验所包含的平均信息量。要表示序列集的互信息量则用平均互信息来表示，是一个事件集所给出的关于另一个事件集的平均信息量，比如今天的天气所给出关于明天的天气的信息量。这些关于信息的定量度量方法可以用到离散随

4、机变量和连续信源的情况中去，以此来描述信息的传达。信息论，顾名思义，是研究对信息的处理的课题，怎样把信息通过一定的渠道传给另一个机制，要首先选择一个通道，及信道，然后将信息转化成特定的数字信号即编码，然后在传输信道末端将信号转化为信息，即译码，这就把信息传输出去了。信源就是产生消息和消息序列的源，编码器就是把消息变成适合在信道传输的物理量，这种物理量成为信号，信号携带着消息，是消息的载体。信道是指通信系统把信号从发送端送到接收端的媒介通道，它还有储存信号的作用。译码就是把信道输出的已增加了干扰的信号进行反变换，使之变换成信宿能够理解的消息，译码器需要尽可能准确的再现信源输出的消息，就要求干扰尽

5、可能小，而且译码尽可能准确。信宿就是消息传送的对象，及接受消息的人、机器或其他事物。 信息论就是用概率描述抽象的消息通过一定渠道传输到另一个机制时的过程中的各种外部干扰或内部干扰对于传输结果的影响，信息的传递效果有很多的具体度量方式，例如：离散信源和连续信源的信源熵、离散及连续信道信道容量等。为了使信源转化为信号，就要对信源进行编码，编码效率与信源序列的平均码长及信源熵有关，有各种编码方法，如：香农编码、费诺编码、哈夫曼编码等。此外，还要对信道进行编码，在信道上编码会有错误，并且要设置编码规则，所以纠错编码就显得尤为重要，对信道的一般要求是，纠错检错能力强，信息传输效率高。但消息在传达过程中是

6、不可能不会出现失真，所以就要对信源编码进行限失真，以保证信息传输效率在一定范围内。2. 信源编码的相关介绍 信源来说，一个主要的问题是怎样能合理的描述并表示信源的输出，因为对方要接收到信源，就需要以一种特定的形式输出，为了能让输出的消息更容易理解并应用，就需要对输入的信源进行编码，使之变换成适合信道传输的符号序列，同时，为了尽量减少信源的失真度，应该尽可能减少码符号，以便于提高传输效率。信源编码是按照一定的规则将信源符号映射成数学符号，并进行传输的一种编码，完成编码功能的器件成为编码器，接收端的译码器完成相反的功能，为了使编码效率更高，就要对码字进行冗余度处理，去除冗余度有两个方法，第一个方法

7、是去除相关性，及使得各个信源之间独立性提高，这一般是对信源序列进行编码，第二种方法是使得各个信源出现的概率尽可能相等，使概率分布均匀，小概率消息对应长码，大概率消息对应短码，以此来去除冗余度，提高编码效率。 第一个完成的主要任务是实现香农编码，香农编码主要是对出现概率的信源符号进行编码，而对出现概率较小的信源符号编长码，从而使平均码长最短，达到最佳的编码目的，在编码领域占有重要地位，属于变长编码方法，及在保证不失真的前提下对信源进行编码，来提高编码效率，此编码方法依赖于信源的概率，每个信源的概率都不同，因此码长也就不同，概率大的信源码长短，概率小的信源码长大，编码时应该尽可能使平均码长较小，能

8、达到便于传输的目的。 线性分组码是一种有实用价值的码，属于有噪信道编码的一部分，信道输出时要输出结果为输入时的结果，难免会出错，发生错误的概率成为译码错误概率，这一错误概率取决于信道特性，且不可能为零，香农的研究表明，如果将信源在传入信道之前进行编码，并在最后进行译码，有可能实现无误的传输，及可以通过不可靠的信道对信源进行可靠性传输。线性分组码是将信源分为信息位和监督位，如，码长为n，信息位为k，则监督位为n-k，以此为原型，写出校验矩阵，然后根据校验矩阵和生成矩阵之间满足的关系写出生成矩阵，再用生成矩阵与信息序列异或相乘，则得到其线性分组码。此课题完成的任务是循环码编码，循环码是线性分组码的

9、一个子类，具有完整的代数结构，它满足循环移位特性，码中任何一个码字的循环移位仍是码中的一个码字，一般（n,k）线性分组码的k个基底之间不存在规则的联系，因此需要用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就可以表示一个码的特征，我们可以用不大于（n-1）次的码多项式C（x）来表示：移n位后又回到，一个码字的移位最多能得到n个码字，因此循环码码字的循环并不意味着循环码可以仅从一个码字循环而得，一个（n，k）循环码有个码字，它们都是同一基底的线性组合根据线性码空间的封闭性，码字的线性组合仍是码字。3.香农编码（题目一） 3.1香农编码算法

10、 香农算法步骤如下：（1） 将所有q个信源符号按其概率的递减次序排列。 例如，一组信源序列为0.18，0.20，0.19，0.17，0,15，0.10,，0,01则将其按从大到小的顺序排列为0.20,0.19,0.18,0.17,0.15,0.10,0.01 （2）按下式依次计算每个信源符号的二元码码长 例如，自信息量为2.34的信源的码长为3. （3）计算每个信源符号的累加概率，并变换成二进制小数得到其码字。累加概率： 将累加概率变换成二进制小数，取小数点后位数作为第i个信源符号的码字.3.2香农编码特点 香农编码的特点是：它需要对信源符号概率进行排序，要计算累加概率，还要计算码长。香农编码

11、是对出现概率较高的信源符号编短码，而对出现概率较小的信源符号编长码，从而使平均码长最短，达到最佳编码的目的。它的缺点是需要对输入的信源概率进行排序，而且计算结果和费诺编码比起来不是很准确，但操作较简单。4.香农编码的C+程序实现 4.1程序设计 此题目是完成香农编码，设计的程序要完成的任务是：人工输入信源个数及各个信源出现的概率（之和必须为1，如果不为1，则跳转回重新输入信源概率）、计算累加概率、计算各个信源的自信息量、由自信息量计算码长、根据累加概率得出二元码、求信源熵和平均码长，然后求信源熵和平均码长的商即为编码效率。此程序就是按照求二元码及其编码效率的计算步骤一步一步设计，在设计过程中计

12、算累加概率时看似简单，只进行加运算，但要注意的是累加概率是对之前概率相加，不包括当前概率，这块容易出错，然后就是计算码长时是取自信息量的整数值，此程序的难点是二元码的计算，二元码的长度与码长相同，且计算时是用二进制数相乘运算，容易出错，而且输出时还要注意每个二元码之间要有间隔。后面求编码效率比较容易，是把信源熵和平均码长相除得到。程序设计框图如下：4.2运行结果5.实现有噪信道编码中的循环码（题目二）5.1循环码编码算法 一般（n,k）线性分组码的k个基底之间不存在规则的联系，因此需要用k个基底组成生成矩阵来表示一个码的特征。而循环码的k个基底可以是同一个基底循环k次得到，因此用一个基底就可以

13、表示一个码的特征，我们可以用不大于（n-1）次的码多项式C（x）来表示：循环码的循环特性可以用码多项式表示为移1位：移2位：移n-1位： 移n位后又回到，一个码字的移位最多能得到n个码字，因此循环码码字的循环并不意味着循环码可以仅从一个码字循环而得，一个（n，k）循环码有个码字，它们都是同一基底的线性组合根据线性码空间的封闭性，码字的线性组合仍是码字。 在2k个码字的码多项式中取一个次数最低即（n-k）次的多项式作为生成多项式，用g（x）表示。可以证明，g(x)是嘛多项式中唯一一个（n-k）次多项式且常数项不为0，由生成多项式可以得到循环码的生成矩阵，然后用初等行变换将此生成矩阵转化为系统形式

14、的生成矩阵，再写出信息序列，用信息序列与系统矩阵异或相乘则得到循环码。5.2循环码编码特点循环码编码过程较简单，只要根据生成多项式写出生成矩阵然后转换成系统矩阵，再用信息序列与其相乘就得到循环码，但得到生成多项式较困难，因为要对多项式进行分解然后寻找最高次数为n-k的那项作为生成多项式，而且循环码与汉明码相比，循环码的码长和信息位之间的关系没有限制，而汉明码的码长和信息位存在一定的关系，所以在设置循环码的码长时选择空间较大。循环码是线性分组码的一子类，它具有完整的代数结构，此外，它还满足循环移位特性：码C中任何一个码字的循环移位仍是码C中的一个码字。码字的线性组合仍是码字。循环码时有实用价值的

15、一种纠错码。6.循环码编码的C程序实现6.1程序设计 编此循环码的实现过程时要设置一些变量，最重要的是该如何表示最后输出的结果，最后的输出结果为两列，左边那列是信息序列，右边那列是循环码序列，因此设计程序的时候用一个16行11列的数组表示，前四列为信息序列，后七列为循环码序列。设计程序的步骤为：先设定线性分组码的码长及信息位，以此计算出监督位，然后得出它的生成多项式，根据生成多项式及移位规则写出生成多项式，用初等行变换将此矩阵转化为系统形式的生成矩阵，然后用二进制方法写出信息序列，用信息序列与系统矩阵相乘，则得出循环码，容易出错的地方是矩阵T的设置以及编写过程中的赋值，因为输入信息序列时是按照

16、二进制规则写的，所以前四列较容易写出来，求循环码时是用信息序列与系统矩阵异或相乘，所以相乘后的数字要进行转化，这一块是此代码的难点，如果稍有不慎就会出现数据溢出或传值时未传进去等问题，最后输出T矩阵时还要注意格式，为了使得输出结果与课本上的形式相同，就要注意空格键的使用对于16行11列来说，遍历时从0开始，到15，（从0到10），行数和列数的设置容易出错。在两个矩阵相乘时要注意第一个矩阵的行乘以第二个矩阵的列，所以第一个矩阵的列数和第二个矩阵的行数相同，这些细节都要注意。算法设计框图如下：6.2运行结果 7.总 结此次写代码难度较大，因为所要解决的问题也较复杂，之前接触的这课程的相关编程不多，

17、所以只是学到了理论知识，但是此次的编程需要用到大一大二学到的相关编程知识，所以我首先复习了编程的相关知识点，再根据选题，对相关的编码进行系统复习，最后才开始编写代码，写代码时要从数学问题出发，用计算机构造数学式，虽然用的是最简单的VC环境和C+语言，但编此代码需要较强的逻辑思维，计算的每一个步骤都不能出错，否则会影响下一步的计算直至最终结果，编程过程中需非常细心，变量常量的设定，以及计算各个部分的参数值，各个赋值语句等都需要多多注意细节。第一个香农编码较简单，因为是根据教材上的步骤一步一步往下操作，每一步都能得出相应的值，并且香农编码是唯一可译码，一般无需考虑其它编码方式的问题。需要注意的是输入信源概率后需要对其进行从大到小的排列，此处用的是冒泡排序法，然后再对排序后的概率进行相关操作。第二个程序是实现循环码，最大的问题在于矩阵布尔乘及最后如何表示输出结果，信息序列的设定，把这些问题一一解决了，程序就变得简单了许多。 此次写代码用的是最基础的c语言，在代码编写的过程中需要不断地改进，完善，调试，分析，和尝试，才能最终得出结果，而且为了符合设计的基本要求，就要在设计过程中多做思考，程序总体来说比较复杂，因为要区分字母的大小写，还要区分标点符号，写的过程中