- 1、本文档共8页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
信息论编码实验
信息论实验报告
自动化学院2007302171 马志强
0摘要:
用预先规定的方法将文字、数字或其他对象编成数码,或将信息、数据转换成规定的电脉冲信号。编码在电子计算机、电视、遥控和通讯等方面广泛使用。其中Huffman编码和LZ编码由于自身的巨大优势在编码领域有更为广泛的应用,通过本次实验,具体了解编码的具体过程,通过编程实现编码,利用GUI制作可视化界面,实现编码的方便应用。
1关键字:信息论,Huffman编码,LZ编码,GUI编程。
2前言:
2.1Huffman编码
Huffman编码:基本原理是频繁使用的数据用较短的代码代替,较少使用的数据用较长的代码代替,每个数据的代码各不相同。这些代码都是二进制码,且码的长度是可变的。举个例子:假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7,那么每种符号要编码,至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)。
那么符号序列
S0S1S7S0S1S6S2S2S3S4S5S0S0S1
编码后变成
000001111000001110010010011100101000000001,
共用了42比特。我们发现S0,S1,S2这三个符号出现的频率比较大,其它符号出现的频率比较小,如果我们采用一种编码方案使得S0,S1,S2的码字短,其它符号的码字长,这样就能够减少占用的比特数。例如,我们采用这样的编码方案:S0到S7的码字分别01,11,101,0000,0001,0010,0011,100,那么上述符号序列变成011110001110011101101000000010010010111,共用了39比特,尽管有些码字如S3,S4,S5,S6变长了(由3位变成4位),但使用频繁的几个码字如S0,S1变短了,所以实现了压缩。
上述的编码是如何得到的呢?随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况,比如说,如果S0的码字为01,S2的码字为011,那么当序列中出现011时,你不知道是S0的码字后面跟了个1,还是完整的一个S2的码字。我们给出的编码能够保证这一点。
下面给出具体的Huffman编码算法。
(1)首先统计出每个符号出现的频率,上例S0到S7的出现频率分别为4/14,3/14,2/14,1/14,1/14,1/14,1/14,1/14。
(2) 从左到右把上述频率按从小到大的顺序排列。
(3)每一次选出最小的两个值,作为二叉树的两个叶子节点,将和作为它们的根节点,这两个叶子节点不再参与比较,新的根节点参与新一轮比较。(从下往上)
(4) 重复(3),直到最后得到和为1的根节点。
(5)将形成的二叉树的左节点标0,右节点标1。把从最上面的根节点到最下面的叶子
节点途中遇到的0,1序列串起来,就得到了各个符号的编码。
下图展示了编码过程:
最终获得的编码表:
Label
Sign
P(x)
11
S0
4/14
4/14
4/14
4/14
4/14
6/14
8/14
1
00
S1
3/14
3/14
3/14
3/14
4/14
4/14
6/14
011
S2
2/14
2/14
2/14
3/14
3/14
4/14
010
S3
1/14
2/14
2/14
2/14
3/14
1011
S4
1/14
1/14
2/14
2/14
1010
S5
1/14
1/14
1/14
1001
S6
1/14
1/14
1000
S7
1/14
2.2LZ编码
LZ编码:编码的码字由段号加一个符号组成。设u构成的字典中的短语共有M(u)个。若编码为二元码,段号所需码长n=「log M(u)「(注:代表上取整符号),每个符号需要的码长为「log K「。单符号的码字段号为0,非单字符的码字段号为除最后一个符号外字典中相同短语的段号。
例如,设U={a1,a2,a3,a4},信源序列为a1,a3,a2,a3,a2,a4,a3,a2,a1,a4,a3,a2,a1,共13位,字典如表所示:
表1 编码字典
段号
短语
编码
1
a1
00000
2
a3
00010
3
a2
00001
4
a3a2
01001
5
a4
00011
6
a3a2a1
10000
7
a4a3
10110
8
a2a1
01100
表2 符号编码表
a1
a2
a3
a4
00
01
10
11
表1中,8个短语使用3bit可以表示段号
文档评论(0)