实时LZW压缩算法的FPGA实现-论文.pdf

《实时LZW压缩算法的FPGA实现-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

算法分析实时LZW压缩算法的FPGA实现耿赞薄保林(中国电子科技集团公司第五十四研究所河北石家庄050081)摘要：为降低数据传输的数据量提高传输速度，提出了一种用FPGA实现Lzw无损压缩算法的设计方案。字典存储形式~_LZW算法中的关键，用内容可寻址存储器构建字典可大大提高字典查询速度。仿真分析了字典容量与压缩率间的关系，使用较少的FPGA资源就能达到较好的压缩效果。关键词：无损压缩LZW算法内容可寻址存储器FPGA中图分类号：TN958．98文献标识码：A文章编号：1007—9416(2014)04—0135—02在某工程应用中需要将前端大量的采样数据传输到后端进行与压缩流程类似，区别在于解压缩查询字典时输出的不是匹配地址处理，为实现高效快速的数据传输，可利用数据压缩技术减少数据而是匹配字符或字符串，解压缩算法可从压缩数据中重构出与压缩量和传输时间。系统要求压缩数据必须能完全恢复为原始数据，且算法相同的字典，并且压缩与解压缩都不用存储字典，易于工程实处理时间不能过长，LZw压缩算法是一种常用的无损压缩算法，具现。LZW算法充分利用了数据的重复性，只需扫描一次数据就可以有较好的实时性，本文利用FPGA的高速并行处理特点，提出了一完成压缩，能够实时处理数据。种实时LZW压缩算法的实现方案。2FPGA构建CAM字典1LzW算法LZW算法的关键在于构建字典和读写操作时间。传统的LZWLZW算法使用一种类似查字典的方式来进行压缩，通常针对算法实现中多使用RAM(随机存储器)来存储字典，查找词条时需逐计算机系统中的8位ASCII字符进行压缩。基本原理是将输入的字个查询从而造成压缩时间过长。建立字典地址与输入数据的哈希函符累积为字符串，把已出现的字符串作为词条存入字典，对重复出数可提高查询速度，但为解决地址冲突问题还要增加额外的开销。现的字符串输出其在字典中的位置而不是字符串来达到压缩数据本文将CAM(内容可寻址存储器)用于存储字典，CAM的原理是将的目的。输人数据与存储的数据进行比较，给出是否匹配以及匹配地址，这LZW算法流程主要是字典的维护和查询，字典包含D项词条，与LZW算法的字典查询是相符的，利用CAM构建字典简化了对字每项词条由m位前缀和n位后缀组成，后缀位宽与输入数据位宽相典的读写操作。等，且满足D=2m。压缩算法流程如下：(1)字典的前256项初始化为本文使用Virtex系列FPGA基于BRAM(块存储器)的实现方法8位ASCII字符集，(2)将第一个字符作为后缀与前缀0组成待查数据来构建CAM，这种方法读写时间都只需一个时钟周期，适合存储字进行查询，必与字典初始化项中的某一词条匹配，将前缀更新为匹典。CAM16x8表示可存储16项8bit数据，实现框图如图1所示。图中配地址；(3)将下一个输入字符作为后缀与前缀组成待查数据进行RAM_Dual为BRAM，将端lzlA配置成4096项lbit数据，端EIB配置查询，如果不匹配则将待查数据作为新词条写入到字典中，将前缀成256项16bit数据，RAM_Erase由8个分布式RAM构成，存储CAM输出并更新前缀为后缀的匹配地址，如果匹配则将前缀更新为匹配中每个地址已存的内容。地址，(4)依次输入字符并按上步进行处理。LZW算法的解压缩流程CAM16x8的写操作分为擦除和写入两个步骤。擦除是从RAM—Erase模块中读出地址addri中已存的数据，作为RADualWriteReadPortAPortB模块端口A写地址addra的高8位，addra的低4位为addri，数据dia写0x4096)(16x256)0表示这一地址存储的数据已清零；下一时钟周期再进行写操作，将dia【0】dobD5：D]datai与addri组合为addra，数据dia写1表示这一地址已存储数据，addm[11：O]addrb[7：0]同时更新RAM_EFase中地址addri存储的数据为datai。当查询数据图1CAM16x8实现框图datam在CAM中的地址时，将datam作为RAM_Dual模块端口B的表1字典容量与BRAM数量关系读地址，可读取数据dob，将dob进行按位或运算，如为1则表示匹配，为0则不匹配，并按照one—hot形式对d0b进行解码，获得实际匹容量基本CAM单元BRAM数量1024x18bitCAM16x8+CAMl6xlO128配的地址addrm。one-hot是一种数据编码方式，例~N4bit十六进制2o48xl9bitCAM16x10+CAMl6xl0256数据0x7可表示为16bit_--进制数据0000000010000000，CAM就是利4096x2ObitCAM16x10+CAM16xl0512用这种方式实现的。8l92x2lbitCAMl6xll+CAM16x1015363FPGA资源和性能分析表2字典容量与压缩率关系＼容量10242O4840968l92Virtex系列FPGA中的BRAM单元可配置成CAM16x8或类型＼xl8bitxl9bitx20bitx21bitCAM16xl0或CAM16xl1，通过并行组合多个CAM单元可扩展存频谱数据0．63510．6l110．59460．5893采样数据0．28760．27680．27240．2894⋯···下转第137页作者简介：耿赞，男，(1981一)，工程师，主要研究方向：数字信号处理、FPGA设计。 算法分析2．2全局聚类算法org．apache．axis．client．AdminCHentdeploy．wsdd．与局部聚类相反，全局聚类算法是将各局部站点传输来的局部在浏览器中查阅的情况如图3：模型，采用DBSCAN算法整合为全局聚类的数据集后，再传给各局4Triana下的分布式聚类分析实验部站点。局部与全局的关系如图2：对于SOA架构下分布式聚类算法的Web服务实现，下面将从2．3Web}I~．务设计要求Triana的实验过程进行验证其是否具有实用性。介绍了分布式聚类的过程，需要在SOA架构下进行操作设计，为此，我们准备了四台计算机，其中三台为局部挖掘，一台为全以web服务的形式来实现，对web的服务设计需要注重一下几点：局挖掘，然后将这四台计算机按照要求构建为一个分布式聚类分析首先，Web服务要做到客户满意，就需要注重自身的灵活性与的环境。这样各站点都发布了Web服务，局部站点和全局中心都部敏捷性，可以借助封装、信息隐藏及松散耦合等机制，最小化的降低署了web服务，通过这些web服务的URL地址，Triana可以发现并其服务之间的依赖性，其次是web的服务粒度，要在保证内聚、一致调用这些分布式聚类算法的Webg~务。实验结果证明，SOA架构下完整的前提下尽量放大，再次是命名上一定要浅显易懂，设置为与分布式聚类算法的web服务是可以操作的。实验结果见表1：上下文无关的无状态模式；还有就是在设计Web~i务时，要考虑到与SOA相一致，能与现存的部分组成服务组合，达到服务级别更高，5结语功能更全。分布式聚类算法实用性强，在SOA架构下实现web服务具有3SOA架构下分布式聚类算法的Web服务实现可操作性，希望在今后的生活生产中得到普及。上节根据分布式聚类算法的工作流程对SOA架构下的分布式参考文献聚类算法的Web服务模型做了设计，部署服务在Axis~境下分为即[1]杨恒字．基于SOA的WEB应用系统的研究与实现[D]．合肥工业大时和定制两种方式，前者只要将Java类的源文件后缀改为．jws并复学，2006年．制到Axis的app目录下，就会自动生成相应的WSDL文件。但定制部[2]丁兆青，董传良．基于SOA的分布式应用集成研究[J]．计算机工程。署就复杂多了，需要通过wsdd，即Web的服务部署描述符来完成。2007年1O期．下面就介绍一下利用Axis的AdminClent~来进行定制的web服务[3]朱晓娟，李敬兆．基于SOA&WebService的企业应用集成研究[J]．操作的基本过程：电脑知识与技术(学术交流)。2007年01期．对DBDC—S类编译成dass~件，然后复制到Axis的／WER—INF／[4]范新灿．张霞．肖正兴．基于SOA的WebServices扩展研究[J]．福建classes内，然后对web服务的局部及全局的wsdd文件deploy．wsdd电脑。2006年02期．分别编写，随后利用Axis工具发布web服务，基本格式如下：>java··⋯·上接第l35页资源与压缩率之间的关系进行了分析，在FPGA资源占用率与压缩储位宽，串行组合可扩展存储深度。令n=8，m=10，ll，12，13，表1给率之间找到平衡点，对FPGA器件选型有一定的指导意义。这种实出了不同的字典容量所需的BRAM单元数量。现方案不仅可用于原始采样信号和频谱数据的压缩传输，也可用于本文使用仿真工具对实际采集的低频信号原始采样数据和傅文本、图像等其他数字信号的压缩传输，具有较好的通用性。里叶变换后的频谱数据进行了仿真分析，两种数据均为15bit，需先参考文献将其转换为两个8bit数再进行压缩。压缩算法的性能用压缩率来表[1]陈晋敏，黄春明，周军．激光雷达数据无损压缩的FPGA实现[J]．军示，定义为压缩后数据量与原始数据量的比值，在不同的字典容量事测控技术。2007。15(1)：100—102．条件下，对100组每组80kB的数据进行压缩，将压缩率取均值，表2[2]陈世海。裴东兴，张琦．FPGA实现滑动平均滤波算法和LZW压缩算给出了字典容量与压缩率间的关系。法．电子设计工程。2010。18(2)：67—69．从表2可以看出，频谱数据的压缩率随字典容量增加逐步下降，[3]AnOverviwofMultipleCAMDesignsinVirtexFamliyDevice在字典容量为g192x21bit时压缩率变换不大，而采样数据的压缩率[H]。Xilinz~Xapp201．1999．9．甚至略有增加，这与字典容量扩大带来的输出位宽扩大有关。再结[4]UsingBlockRAMforHighPerformanceRead／WriteCAMs[M]，合所占FPGA资源，字典容量选取2048x19b~就能获得较好的压缩Xilinx。Xapp204。2000．5．率，对两种数据都能满足压缩传输的工程需求。4结语本文将基于FPGA实现的CAM存储器应用于LZW算法的字典存储，实现了对采集数据的实时无损压缩。对字典规模、FPGA占用