信息论与编码-课程设计报告

1、目录 实 验 原 理 1 程 源 代 1 三： 实 验 分 析 实 验 结 论 7 赫夫曼编码 实验原理 哈夫曼编码的具体步骤归纳如下: 概率统计(如对一幅图像，或m幅同种类型图像作灰度信 号统计)，得到n个不同概率的信息符号。 将n个信源信息符号的n个概率，按概率大小排序。 将n个概率中，最后两个小概率相加，这时概率个数减为 n-1 个。 将n-1个概率，按大小重新排序。 重复，将新排序后的最后两个小概率再相加，相加和与 其余概率再排序。 如此反复重复n-2次，得到只剩两个概率序列。 以二进制码元(0.1)赋值，构成哈夫曼码字。编码结束。 哈夫曼码字长度和信息符号出现概率大小次序正好相反，即

2、大 概信息符号分配码字长度短，小概率信息符号分配码字长度长。 C、哈夫曼编码的特点 (1) 哈夫曼编码的构造顺序明确，但码不是唯一的(因以大赋1还是小 的赋1而异； (2) 哈夫曼编码的字长参差不齐，硬件实现不方便； (3) 只有在概率分布很不均匀时，哈夫曼编码才有显著的效果，而在 信源分布均匀时，一般不使用哈夫曼编码。 二：程序源代码: ttdefine MAXVALUE 10000 define MAXLEAF 30 define MAXNODE 59 ttdefine MAXBIT 10 ttdefine LENTH 30 include stdio. h ncludeiost:rean

3、i typedef struct float gailv; int flag; int parent: int lchild; int rchild; char ch; int t; HNodeType; typedef struct int bitMAXBIT; int start; HCodeType; typedef struct float gailv; char letter; Jmytype; /*it, s the type of data save in file*/ typedef struct filehuff int count; mytype mydataMAXLEAF

4、; filehuff()count二0; ; ； filehuff filedata; char codeMAXVALUE; HNodeType HuffNodeMAXNODE; void savetofile () FILE *fp; if (fp=fopen(，zdatafile txt, wb)=NULL) printf(打开失败 return; if(fwrite( void openfile() FILE *fp; if (fp=fopen(，zdatafile txt, rb)=NULL) return; fread( void translate() char c; int i,

5、 j, k=0, m, n=0; printf r请输入你想要译码的二进制序列”)； printf(n); get char (); scanf (iMAXVALUE) i+) codei=c; scanf (，z%c/z, printf r对应的信源符号为：“)； for (j二0; j=MAXVALUE j+) nrj+l； for (j=0, k=m; j=i; j+) 辻(codej二二0,) n=HuffNodek lchild; if (n-l) printf(%c, HuffNodekj. ch); k=m;j一一:continue; k二n; else n=HuffNodek

6、rchild; if(n=-l) printfHuffNodekJ. ch); k=m;j-一;continue; k=n; void Huffman() HCodeType HuffCodeMAXLEAF, cd; int i, j, ml, m2, xl, x2, c, p, m; if (filedata count二二0) printf (n输入信源符号总数:”); scanf (，z%d，z, filedata count=m; for (i=0;i2*m-l;i+) HuffNodeiiZ. gailv=0; HuffNodeEi parent二T; HuffXodei.flag=

7、0; HuffNodeEil. lchild=-l; HuffXodeEi. rchild二T; HuffXodeEi. ch二a ; for (i=0; im; i+) printf r请输入(概率，信源符号)：)； scanf (z，%f %cz，, filedata mydata Lil. gailv=HuffNodeLi gailv; filedata mydata Lil. 1etter二HuffNodei ch; savetof ile (); else npf iledata count; for (i二0;i2*m-l;i+) HuffNodeCi. gailv=0; Huff

8、Nodei parent二T; HuffNodei.flag=0; Huffodeilchild二-1; HuffNodeEi rchild=-l; Huffodei.ch二3; for (i=0; im; i+) HuffNodeLi gailv=filedata mydatai gailv; HuffNodeEi ch=filedata mydatailetter; for (i=0;im-l;i+) ml二m2二MAXVALUE; xl二x2二0; for(j二0;jm+i;j+) if(HuffXodeEjl. gailvml x2=xl; ml=HuffNodejl. gailv;

9、xl二 j； else if(HuffNodej. gailvm2 x2二 j; HuffNodexl parent二m+i; HuffNodex2 parent二m+i; HuffNodexl. flag=l; HuffNodex2. flag=l; HuffNodem+i. gailv=Huffodexl. gailv+HuffNodex2.gailv; HuffXodem+i. lchild=xl; HuffNodem+i. rchild=x2; for (i=0; im; i+) cd startm-l; c=i； p=HuffNodec parent; while(p!=-l) if

10、 (HuffXodeEp. lchildc)cd. bit cd. start二0; else cdbitcd start=l; cd. start-； c 二p； p=HuffNodec parent; for(j=cd start+1:jm;j+)HuffCodei bitj=cd bitjZ； HuffCodeLi. start=cd start; printfC对应的赫夫曼编码如下:0； printf (n信源符号概率 编码)； for (i=0; im; i+) printf (z/%c%f、HuffNodeEi. ch, HuffNodeEi. gailv); for (j=Huf

11、fCodei start+1; jm; j+) printf(%d, HuffCodei. bitj); printf Cnz，); printf C按任意键继续n); main() char yn; printf(n); printf Cnz，); printf r信息论与编码实验n)； openfile(); Huffman (); for(;) printf Cn是否想要把序列译码为信源符号?:(输入y or n) 9; scanf (z，%c，z, 辻(yn二二y yn二二,Y，) translate (); else break; return 0; system(，zpause，z

12、); 三：实验分析 编码实例如下: 由图中可以看出，符合基本的赫夫曼编码的原理，概率大的用短码，概率小的用长码。 信息论与编码实验 灣髀天曼绳餌如下： a0 b0 0 槪率 100000 150000 200000 25UMWW 300000 按任恚键继纟卖 编碼 110 111 00 01 10 是否想要把序列译码为信源符号?： 巴日J 0原巴 扌*Jl_ly扌 要你00信要 想入01的想 否输01应否 是请10对是 为二 审玛10:为译 列译00兮列 序要01符序 _Jm3 -pno_J ? ed为 ed源 选择译码：结果如下: 四：实验结论 哈夫曼的具体实现，在数据结构的相关课程曾做相应的实验，所 以无论在理解上或是实现上，都不是很困难，程序上实现哈夫曼的编 码与译码，由于哈夫曼自身的特点，编码与译码均不是唯一，但是相 同的编译码规则还是能实现正确的译码的。木实验，除了实现编译码 的具体实现，还实现数据的存储与读取，这给实验实现方便，不必每 次从命令提示符输入数据。总的来说，通过木次实验，对哈夫曼的编 译码有了一个更好的认识。 通过本次试验，对书上的理论知识有了进一步的认识，但是由于 对编程软件的知识欠缺，导致有