2024年信息论与编码实验实验报告.doc

中南大學

----------信息论与编码

題目有关编码的试验

學生姓名杨家骏

指导教師赵颖

學院信息科學与工程學院

學号

专业班级電子信息1002班

12月

目录

试验目的……3

二、试验原理……3

三、试验内容……5

四、试验规定……5

五、代码调试成果………………6

六、试验代码……8

一、试验目的

1.掌握香农码和Huffman编码原理和過程。

2.熟悉matlab软件的基本操作，练习使用matlab实現香农码和Huffman

编码。

3.熟悉C/C++語言，练习使用C/C++实現香农码和Huffman编码。

4.应用Huffman编码实現文献的压缩和解压缩。

试验原理

香农编码：香农第一定理指出了平均码長与信源之间的关系，同步也指出了可以通過编码使平均码長到达极限值，這是一种很重要的极限定理。怎样构造這种码？香农第一定理指出，选择每個码字的長度Ki满足下式

I(xi)≤K﹤I(xi)+1,

就可以得到這种码。這种编码措施就是香农编码。

香农第一定理：

设离散無记忆信源為

SP=s1s2.............sqp(s1)p(s2).....p(sq)

熵為H(S)，其N次扩展信源為

熵為H(SN)。码符号集X=（x1,x2,…,xr）。先對信源SN進行编码，總可以

找到一种编码措施，构成惟一可以码，使S中每個信源符号所需的平均码長满足：

當N→∞時

L是平均码長λ是ai對应的码字長度

哈夫曼编码：要完毕哈夫曼的编码和解码需要首先建立哈夫曼树，之後對所有字符根据权重進行编码，最终再對文献内容進行编码和解码。

首先定义适合哈夫曼树的节點类型，需要定义的有目前节點的字符，目前节點的左子、右子和父亲指针。在建立哈夫曼树之前還需要對出現的字符和权重進行记录和记录，并且定义一种可以筛选出最小权重的函数。

初始化树节點之後開始建立哈夫曼树。先在所有也許出現的字符中筛选出目前权重最小的两個字符，将這两個字符分别作為新节點的左子和右子建立一种小的二叉树，并将两個字符的权重之和赋值給新节點，将新二叉树放入筛选字符中，再将筛选過的两個字符從筛选列表中淘汰掉。依次對列表中剩余的字符進行权重最小的筛选，直到根节點（假如编码表共有N個字符，则2*N-1就為最终根节點）為止，也就是當筛选列表為空的時候，哈夫曼树即建立完毕。

對于哈夫曼编码树来說，由于哈夫曼编码是前缀码，因此所有要编码的字符最终都将是這颗树的叶子节點，而其他节點并没有真正的字符意义。即當哈夫曼编码树建立之後，對树的所有叶子节點進行打印可懂得与否有字符遗漏或多出。

建立哈夫曼编码表。

建立编码表時要根据每個出現的字符的权重對建立的哈夫曼树的每個叶子节點進行编码。编码時要從叶子节點出发向根节點進行逆向编码。判断假如目前节點為左子则對其编码‘0’，假如目前节點為右子则對其编码‘1’。以此类推進行编码直到根节點為止。此時的编码是逆向的，因此需要将码值逆向存储。依次對每一种叶子节點進行编码操作，即可得到目前哈夫曼树的编码表。

對于码值的逆向存储可以使用栈构造，先将一种码的每一步编码存入栈，再在一种码結束後出栈至空。當然也可以定义一种字符型数组，将值從後向前存入数组，再将数组有值部分粘贴到新的数组中進行存储。本次采用了後者，由于個人认為為此一步操作建立栈构造不划算，并且前一种设计也已經纯熟掌握了栈的措施，此处進行新的尝试會更好。

對文献進行编码。

首先需要建立一种原始文献，在文献中输入需要编码的内容。之後将文献打開，将其中的内容存储到字符串中以便程序编码调用。開始對需要编码的字符進行编码，将字符逐一讀取与刚刚建立的编码表中的每個叶子节點代表的字符進行比较，找出相似的對象，并将目前节點的编码打印到屏幕，并将编码存入到新建的密码文献當中。

對文献進行解码。

先打開密码文献，将之前编码後得到的密文内容存储到字符串中以便解码调用。開始對密文的字符串進行解码，树索引從根节點開始走，當密文中的目前字符是‘0’的時候，则索引走向左子节點；當是‘1’的時候，则走向右子节點。以此类推，一直走到叶子节點為止，则目前叶子节點所代表的字符即為前一段密文的解码成果，。再對下一种字符依次從根节點開始解码，如此循环對每