收稿日期:2007-03-01
作者简介：马强(1969-)，男，河南焦作人，焦作建设银行工程师。
数据压缩算法在单片机上的实现
马 强1
王 琛
2
(1.焦作建设银行，河南焦作454000;2.焦作大学，河南焦作454003)
摘要：信息时代测量数据以爆炸形式倍增，对/海量0数据的压缩存储，保证数据主要特征基本不变的
前提下，研制数据压缩在单片机上来实现，对HUFF MAN 压缩算法研究，获得较快的压缩速度，减少数据存储空间和传输的通信流量，节省数据的存储空间，保证大压缩比，同时具有还原恢复特性。关键词:/海量0数据；数据压缩；静态数据压缩；压缩算法；编码中图分类号:TP311.13  文献标识码:A  文章编号:1008-7257(2008)04-0078-02
1.引言
随着计算机技术的发展，数据压缩技术的研究受到人们越来越多的关注与应用。数据压缩技术，作为信息论研究中的一个重要课题，一直受到人们的广泛关注。数据压缩技术的主要目的是力求用最少的数据表示信源所发出的信号，使信号占用的存储空间尽可能小，以达到提高信息传输速度的目的。各种压缩算法在一定程度上，都具有个性，对某一类型的数据其压缩率可能很大，但对于另一类型数据其压缩率则可能很小。所以在应用中，若想得到较好的综合压缩性能，必须考虑各种因素，并对现有算法进行综合比较，最终确定合适的压缩算法。
2.数据压缩的产生和发展及M SP430单片
机简介
2.1数据压缩的产生
关于数据压缩理论研究，有人认为始于19世纪末研制的莫尔斯代码是数据压缩的第一次尝试。早期信息论研究，是已知消息中各符号出现频率，设法构造一种编码，使消息所占空间尽可能少。尽管当时数字计算机尚未出现，但所进行的研究与当今数字计算机所使用的压缩技术有着密切联系，数据压缩是将输入数据流(原始数据)转变为另一种比较小的数据流(输出流或是压缩流)的过程，目的是通过数据压缩手段将数据流以压缩形式进行存储和传输。2.2M SP 430功能简介
M SP 430是T I 公司近几年推出的16位系列单片
机，最早面向于驱动LED 显示的应用设计，具有极好的
应用效果和很大的市场潜力，很快发展为通用单片机系列。M SP 430作为一种新型的单片机，低功耗技术在众多的单片机中独树一帜。在各种工作模式之间切换方便。低功耗使其在电池供电、便携式设备的应用中表现出非常优良的特性。M SP 430具有非常高的集成度，单片集成多通道12b it 的A /D 转换、片内精密比较器、多个具有P WM 功能的定时器、斜边A /D 转换、片内U S -ART 、看门狗定时器、片内数控振荡器(DCO )、大量的I /O 端口以及大容量的片内存储器，能满足绝大多数的应用需要。高集成度使应用人员不必在接口、外接I /O 及存储器上花太多的精力。采用冯#诺伊曼结构，因此,RAM 、ROM 和全部的外围模块都位于同一地址空间内。
3.压缩比
数据压缩技术所探讨和研究的各种压缩方法，是为了提高压缩比。衡量压缩程度指标之一是压缩比。到目前为止，关于压缩比定义尚无统一定论。在信息论中，压缩比定义为压缩前后数据的熵之比。基于对要压缩数据统计分析结果而提出。许多压缩技术并不依赖于数据统计结果。因此有相当局限性。为与实际概念相一致定义压缩比:
压缩比=(源代码长度-压缩后代码长度)A 源代码长度@100%
字符串长度压缩其含义是被压缩掉的数据占源数据的比例。
文件不同，压缩方法不同，图像分辨率不同，都会影响到压缩比。从数据压缩的角度看，压缩比越大越好。但实际压缩比有上限，对基于统计编码而言，上限与信
2008年10月                    焦作大学学报                    l 14
第4期              J OURNAL OF JI AOZUO UN I VERSI TY              O c.
t 2008
息的熵有着密切关系。如果压缩比超过上限，还原将无法恢复原状，出现失真而失去意义。
3.1HU FF M AN编码模型
数据压缩是将符号流或数据流转换成相应的代码。输出的代码流小于源符号流时，数据压缩为有效压缩。数据压缩工作是在模型基础上进行的。这里提到的模型是数据和规则的集合。规则用来处理输入符号，使之转换成相应的输出代码。构造数据压缩的模型和编码是不同的两件事情。编码仅仅是数据压缩的一部分。HU FF M AN码是一种常用的压缩代码。用HU FF M AN编码法进行数据压缩，模型构造和编码为两个分离部分。模型若不能提供合适规则和数据，编码器编码效果再好也无法完成预定的压缩工作。
3.2有损数据压缩无损数据压缩的不同
无损数据压缩通常使用两种不同类型的模型：统计模型和基于字典模型。统计模型读入字符，根据字符出现概率进行编码。基于字典压缩方法采用完全不同的概念。首先为源文件建立数据字典。字典中列出较长字符串。对应于该串代码，代码短于字符串。进行压缩处理时，由源文件读入数据，并在字典中寻与之匹配的字符串。则输出字符串所对应的代码流，这部分输出是被压缩了的数据或文件。源文件与字典相匹配的字符串越多，压缩效果越好。
有损数据压缩较之无损数据压缩的不同，在于所处理的数据出现有限数据损失。有损数据压缩通常要通过两次处理：用信号处理的方法对其进行量化，这时将会发生数据损失；然后用有关的压缩算法再进行处理。
实现数据压缩的算法有很多，主要采用无损数据压缩算法:H uff m an算法。
4.HU FF MAN算法的原理及程序实现
4.1静态数据压缩技术
用HUFFMAN方法进行编码，根据文本中字符出现概率统计规律制作出代码表，压缩时根据该代码表进行编码。编码效果不很理想。最简单的方法是先扫描要编码的文件，计算出各字符出现概率，然后再进
行编码，属于静态数据压缩技术。静态压缩有很大的局限性。压缩效果直接受到被压缩源文件的影响，压缩比很难达到理想状态。另外，在诸如通信等实时传输处理系统中，不允许分别对文件进行统计和压缩编码两次处理过程。解决这种问题的方法是采用动态处理技术)))自适应压缩。
4.2动态数据压缩技术
/动态0是指压缩用代码表在压缩处理过程中不断变化。源数据流读入一个字符，按字符发生频率重新调整各字符编码，保持编码始终处于编码效果最佳状态。相应自适应解压操作思路与压缩编码类似。解压释放一个字符，要更新所使用的模型。整个处理过程中编码和解码所使用的初始化模型和更新模型两个子程序都是相同的。编码器进行压缩编码并输出编码符号时，解码器就可以进行解码释放。
4.3HU FF M AN编码步骤
霍夫曼编码的基本方法是先对图像数据扫描一遍，计算出各种像素出现的概率，按概率的大小指定不同长度的唯一码字，由此得到一张该图像的霍夫曼码表。编码后的图像数据记录的是每个像素的码字，而码字与实际像素值的对应关系记录在码表中。
霍夫曼编码属于统计式压缩法，是根据源数据符号发生概率进行编码。在源数据中出现概率越高的符号，相应的码长越短；出现概率越小的符号，其码长越长，从而达到用尽可能少的码符号表示源数据，达到压缩的效果。
霍夫曼编码需要统计、编码两遍扫描源数据流，在压缩数据时，遵循固定的源数据符号代码表。压缩处理时，若源数据流中的符号与代码表中的符号相匹配，用与之相对应较短的代码替代该字符，否则不予处理。固定代码表与源文件匹配程度决定文件压缩比。在此基础上又提出自适应霍夫曼编码。自适应压缩方法则是根据不同源文件具体内容，采用完全不同的方法动态地构造代码表，并在构造代码表时同时进行编码压缩。
霍夫曼编码后，对信源中每一个符号给定编码，形成霍夫曼编码表。在信源存储和传输过程中，必须首先存储或传输霍夫曼编码表。解码必须参照霍夫曼编码表才能正确译码。
5.结束语
本文把压缩算法设计和并行编程原理结合起来，构成高效的并行压缩程序方案，以达到对/海量0数据压缩处理，实现该压缩方案，以检验该方案的可行性和实用性。实验证明，上面理论是正确的。该方案完全体现了两种技术的优点，达到了理想效果。
参考文献:
[1]樊昌信，张甫诩.通信原理[M].北京：国防工业出版社,
2000.
[2]袁玫，袁文.数据压缩技术及其应用[M].北京：电子工业
出版社,1994.3-  6.
[3]李小平.数据压缩及传输编码软件速查手册[M].北京:
科学出版社,2001.
[4]吴乐南.数据压缩[M].北京：电子工业出版社,2000.
[5]张柏雄.数据压缩的原理与实践[J].微电子学与计算机,
1994,(5).
(责任编辑陈永康)
79
第4期马强等：数据压缩算法在单片机上的实现

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。