信息论课程设计实验报告

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

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

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

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

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

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

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

8、不同，因此码长也就不同，概率大的信源码长短，概率小的信源码长大，编码时应该尽可能使平均码长较小，能达到便于传输的目的。线性分组码是一种有实用价值的码， 属于有噪信道编码的一部分， 信道输出时要输出结果为输入时的结果， 难免会出错，发生错误的概率成为译码错误概率，这一错误概率取决于信道特性，且不可能为零，香农的研究表明，如果将信源在传入信道之前进行编码，并在最后进行译码， 有可能实现无误的传输， 及可第 2 页以通过不可靠的信道对信源进行可靠性传输。 线性分组码是将信源分为信息位和监督位，如，码长为 n，信息位为 k，则监督位为 n-k，以此为原型，写出校验矩阵，然后根据校验矩阵和生成矩阵之间满

9、足的关系写出生成矩阵， 再用生成矩阵与信息序列异或相乘，则得到其线性分组码。此课题完成的任务是循环码编码， 循环码是线性分组码的一个子类， 具有完整的代数结构， 它满足循环移位特性， 码中任何一个码字的循环移位仍是码中的一个码字，一般（ n,k）线性分组码的 k 个基底之间不存在规则的联系，因此需要用 k 个基底组成生成矩阵来表示一个码的特征。 而循环码的 k 个基底可以是同一个基底循环 k 次得到，因此用一个基底就可以表示一个码的特征， 我们可以用不大于（ n-1）次的码多项式 C（x）来表示：C( x)cn 1 x n 1c2 x2c1 x1c0C ( x) 移 n 位后又回到 C ( x

10、) ，一个码字的移位最多能得到n 个码字，因此循环码码字的循环并不意味着循环码可以仅从一个码字循环而得，一个（n，k）循环码有 2k 个码字，它们都是同一基底的线性组合根据线性码空间的封闭性，码字的线性组合仍是码字。3.香农编码（题目一）3.1 香农编码算法香农算法步骤如下：（ 1）将所有 q 个信源符号按其概率的递减次序排列。p(s1)p(s2 )p(s3 )p( sq )例如，一组信源序列为 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）按下式依次计算每个

11、信源符号的二元码码长l i1i 1,2, qlogp(si )例如，自信息量为2.34 的信源的码长为 3.（ 3）计算每个信源符号的累加概率F（si），并变换成二进制小数得到第 3 页其码字。累加概率：i 1F（ si）p(sk )i1,2,qk 1将累加概率 F（si）变换成二进制小数，取小数点后l i 位数作为第i个信源符号的码字 .3.2 香农编码特点香农编码的特点是： 它需要对信源符号概率进行排序， 要计算累加概率，还要计算码长。 香农编码是对出现概率较高的信源符号编短码，而对出现概率较小的信源符号编长码， 从而使平均码长最短， 达到最佳编码的目的。 它的缺点是需要对输入的信源概率进

12、行排序，而且计算结果和费诺编码比起来不是很准确，但操作较简单。4.香农编码的C+ 程序实现4.1 程序设计此题目是完成香农编码，设计的程序要完成的任务是：人工输入信源个数及各个信源出现的概率 （之和必须为1，如果不为 1，则跳转回重新输入信源概率）、计算累加概率、计算各个信源的自信息量、由自信息量计算码长、根据累加概率得出二元码、求信源熵和平均码长，然后求信源熵和平均码长的商即为编码效率。此程序就是按照求二元码及其编码效率的计算步骤一步一步设计，在设计过程中计算累加概率时看似简单，只进行加运算，但要注意的是累加概率是对之前概率相加，不包括当前概率，这块容易出错，然后就是计算码长时是取自信息量的

13、整数值，此程序的难点是二元码的计算，二元码的长度与码长相同，且计算时是用二进制数相乘运算，容易出错，而且输出时还要注意每个二元码之间要有间隔。后面求编码效率比较容易，是把信源熵和平均码长相除得到。程序设计框图如下：第 4 页开始输入信源个数否输入信源概率概率和为 1是信源从大到小排序计算累加概率计算各信源符号自信息量计算码长写出码字计算信源熵和平均码长计算编码效率结束第 5 页4.2 运行结果5.实现有噪信道编码中的循环码（题目二）5.1 循环码编码算法一般（ n,k）线性分组码的k 个基底之间不存在规则的联系，因此需要用 k 个基底组成生成矩阵来表示一个码的特征。 而循环码的 k 个基底可以

14、是同一个基底循环 k 次得到，因此用一个基底就可以表示一个码的特征， 我们可以用不大于（ n-1）次的码多项式C（x）来表示：C( x) cn 1 x n 1c2 x2c1 x1c0循环码的循环特性可以用码多项式表示为（1）移 1 位： C （x）（2）移 2 位： C （x）xC( x)Cn 2 x n 1x2 C(x)Cn 3 xn 1C1 x2C0 xCn 1C0 x2Cn 1 xCn 2移 n-1 位：（n 1）n 1n 12C（ ）C3x C2 x C1x x C( x) C0 xC ( x) 移 n 位后又回到 C ( x) ，一个码字的移位最多能得到 n 个码字，因此循环码码字的

15、循环并不意味着循环码可以仅从一个码字循环而得，一个（n，k）循第 6 页环码有 2k 个码字，它们都是同一基底的线性组合根据线性码空间的封闭性，码字的线性组合仍是码字。在 2k 个码字的码多项式中取一个次数最低即（ n-k）次的多项式作为生成多项式，用 g（ x）表示。可以证明， g(x) 是嘛多项式中唯一一个（ n-k）次多项式且常数项不为 0，由生成多项式可以得到循环码的生成矩阵，然后用初等行变换将此生成矩阵转化为系统形式的生成矩阵， 再写出信息序列， 用信息序列与系统矩阵异或相乘则得到循环码。5.2 循环码编码特点循环码编码过程较简单， 只要根据生成多项式写出生成矩阵然后转换成系统矩阵，

16、再用信息序列与其相乘就得到循环码， 但得到生成多项式较困难， 因为要对多项式进行分解然后寻找最高次数为 n-k 的那项作为生成多项式， 而且循环码与汉明码相比， 循环码的码长和信息位之间的关系没有限制， 而汉明码的码长和信息位存在一定的关系，所以在设置循环码的码长时选择空间较大。循环码是线性分组码的一子类，它具有完整的代数结构，此外，它还满足循环移位特性：码C 中任何一个码字的循环移位仍是码C 中的一个码字。码字的线性组合仍是码字。循环码时有实用价值的一种纠错码。6.循环码编码的C 程序实现6.1 程序设计编此循环码的实现过程时要设置一些变量， 最重要的是该如何表示最后输出的结果， 最后的输出

17、结果为两列， 左边那列是信息序列， 右边那列是循环码序列，因此设计程序的时候用一个 16 行 11 列的数组表示，前四列为信息序列，后七列为循环码序列。设计程序的步骤为：先设定线性分组码的码长及信息位，以此计算出监督位， 然后得出它的生成多项式， 根据生成多项式及移位规则写出生成多项式，用初等行变换将此矩阵转化为系统形式的生成矩阵， 然后用二进制方法写出信息序列， 用信息序列与系统矩阵相乘， 则得出循环码， 容易出错的地方是矩阵 T 的设置以及编写过程中的赋值，因为输入信息序列时是按照二进制规则写的，所以前四列较容易写出来， 求循环码时是用信息序列与系统矩阵异或第 7 页相乘，所以相乘后的数字

18、要进行转化，这一块是此代码的难点， 如果稍有不慎就会出现数据溢出或传值时未传进去等问题，最后输出T 矩阵时还要注意格式，为了使得输出结果与课本上的形式相同，就要注意空格键的使用对于16 行 11 列来说，遍历时从0 开始，到 15，（从 0 到 10），行数和列数的设置容易出错。在两个矩阵相乘时要注意第一个矩阵的行乘以第二个矩阵的列，所以第一个矩阵的列数和第二个矩阵的行数相同，这些细节都要注意。算法设计框图如下：开始定义变量i,j及数组G,T定义码长及信息位得出循环码的生成多项式写出生成矩阵将生成矩阵转化为系统矩阵利用二进制数获取信息序列信息序列与系统矩阵布尔乘得到循环码，C=m*G输出矩阵T, 得到线性分组码序列结束第 8 页6.2 运行结果7.总 结此次写代码难度较大，因为所要解决的问题也较复杂，之前接触的这课程第 9 页的相关编程不多， 所以只是学到了理论知识， 但是此次的编程需要用到大一大二学到的相关编程知识， 所以我首先复习了编程的相关知识点， 再根据选题， 对相关的编码进行系统复习， 最后才开始编写代码， 写代码时要从数学问题出发， 用计算机构造数学式， 虽然用的是最简单的 VC 环境和 C+语言，但编此代码需要较强的逻辑思维， 计算的每一个步骤都不能出错， 否则会影响下一步的计算直至最终结果，编程过程中需非常细心， 变量常量的设定， 以及计算各个部分的参数值，各