（电路与系统专业论文）基于GSMGPRS的机车信息实时传输系统的研究与设计[电路与系统专业优秀论文].pdf

硬士学位论文摘要 摘要 随着铁路的大提速，对铁路安全保护和铁路管理的信息化要求越来越 高。为解决i c 卡转储带来的信息分析滞后问题，实现列车运行状态的实时 监控，本文探讨了无线数据传输技术在铁路系统中的应用，并分析了利用 g p r s 网络实现机车数据传输的可行性。针对g s m g p r s 网络的不足和机车 记录信息量大的特点，提出了利用数据压缩技术来实现机车信息传输的解 决方案。改进了h u f f m a n 编码的实现方法，提高了算法的执行效率。介绍了 基于字典模型的两种无损数据压缩实现方法并进行了局部改进。通过对数 据进行b u r r 0 、v s w h l e r 字符块变换( b w t ) ，再结合h u f f m a n 编码和l z w 编 码，有效地提高机车数据的压缩效率。通过比较，基于对分二叉树的l z s s 算法更适合于机车数据压缩。在此基础上，本文构建了基于g s m g p r s 的 机车信息实时传输系统，利用g s m 短信息业务和g p r s 网络实现机车信息可 靠地传输。分析并设计了基于s m s 和g p r s 闭环通信链路的组网方案、基于 u s b 总线的地面无线终端和基于分布式总线的车载无线终端，并给出了基 于该系统的一个应用案例。 关键词g s m g p r s 网络，机车数据压缩，字符块变换，l z s s ，实时传输 系统，u s b 总线 硕士学位论文 w i t hh i g h e rr u n n i n gs p e e do fv e h i c l e s , t h ei n f o r m a t i o ns y s t e mf o rt r a i n s a f e t yp r o t e c t i o na n dr a i l w a ym a n a g e m e n tb e c o m e se x i g e n t i no r d e rt os o l v e t h ep r o b l e mo fp o s t p o n e da n a l y s i so ft r a i ni n f o r m a n t i o nt r a n s m i t t e db yi cc a r d a n dr e a l - t i m em o n i t o r i n gt h er u n n i n gs t a t u so ft r a i n , t h ea u t h o rd i df o l l o w i n g w o r k ：a n a l y s et h ea p p l i c a t i o no f w i r e l e s st r a n s m i s s i o ns y s t e mi nr a i l w a yh i s t o r y a n dd i s c u s st h ef e a s i b i l i t yo fa p p l y i n gg p r st e c h n o l o g yf o rt r a n s m i t t i n gt r a i n r u n n i n gi n f o r m a t i o nb a s e d0 1 1m o b i l et r a n s m i s s i o ns y s t e m am e t h o do fu s i n g t r a i nd a t ac o m p r e s s i o ni sp r o p o s e dt os o l v et h ep r o b l e mo fh u g ed a t aq u a n t i t y a n dt h ed e f i c i e n c yo fg s m 必恻t r a n s m i s s i o ns y s t e m 1 h eh u f f m a nc o d i n g a l g o r i t h mr 蒯o r m sb e t t e rw i t hi m p l e m e n t a t i o ni m p r o v e d t w ol o s s l e s sd a t a c o m p r e s s i o na l g o r i t h m sb a s e d0 1 1d i c t i o n a r ym o d ea r ei n t r o d u c e da n dp a r t l y i m p r o v e d a n d t h e c o m p r e s s i o n r a t i oo ft r a i nd a t ai n c r e a s e sb yu s i n g b u r r o w s - w h e e l e rb l o c k - s o r t i n go fs t r i n g sa n dh u f f m a nc o d i i l go rl z w c o d i n g c o m p a r e dw i t ho t h e ra l g o r i t h m s ，l z s sa l g o r i t h mb a s e do nb i n a r ys o r tt r e ei s b e t t e rf o rt r a i nd a t ac o m p r e s s i o n ar e a lt i m ed a t at r a n s m i s s i o ns y s t e mb a s e do n g s 哪r sn e t w o r kh a sb e e nd e s i g n e d t r a i nd a t ac a r lb er e l i a b l ya n dc o r r e c t l y t r a n s m i t e dw i t has y s t e mc o m p o s e do fs m su n i ta n dg p r su n i t 1 1 圮c l o s e d l o o pl i n k 1 a y e rc o m m u n i c a t i o ns y s t e mb a s e do i ls m sa n dg p i 峪w i r e l e s s t e r m i n a li n s t a l l c do nl a n da n dw i r e l e s st e r m i n a lw h i c hi sb a s e do nd i s t r i b u t e d b u sa n di n s t a l l e do nt r a i na r ea n a l y s e da n di m c o m p l e t e d i na d d i t i o n , a n a p p l i c a t i o no f t h i sw i r e l e s st r a n s i m s s i o ns y s t e mi sg i v e n k e yw o r d sg s m g p r sn e t w o r k ，t r a i nd a t ac o m p r e s s i o n ，b l o c k - s o r t i n g o fs t r i n g s ，l z s s ，r e a lt i m ed a t at r a n s m i s s i o ns y s t e m ，u s bb u s 硕士学位论文 符号说明 符号说明 英文全称中文名称 a c c e s sp o i n tn a m e接入点名称 a d c h e s sr e s o l u t i o np r o t o c o l地址解柝协议 b a s es t a t i o nc o n t r o l l e r基站控制器 b a s es t a t i o ns u b s y s t e m基站子系统 b a s et r a n s c e i v e rs y s t e m基站收发信机 c o n t r o u e r a r e a n e t w o r k控制器局部网 c h a l l e n g eh a n d s h a k e a u t h e n t i c a t i o np r o t o c o l 挑战握手认证协议 c h i n e s ct r a i nc o n t r u ls y s t e m中国列车控制系统 d o m a i nn a m es y s t e m动态域名服务系统 d a t at e r m i n a t i o nu n i t数据传输终端 e n h a n c e dm e s s a g es e r v i c e强型短消息服务 e l e c t r om a g n e t i cc o m p a t i b i l i t y电磁兼容性 e u r o p e a nt r a i nc o n t r o ls y s t e m 欧洲铁路控制系统 f a s ti n t e r r u p tq u e s t快速中断请求 g e n e r a lp h i p o s ed e v i c ed r i v e r通用驱动程序 g a t e w a yg p r ss u p p o r tn o d e 网关支持节点 g e n e r a lp a c k e tr a d i os e r v i c e通用分组无线业务 g e n e r i cr o u t i n ge n c a p s u l a t i o n通用路由封装 g l o b a ls y s t e mf o rm o b i l es y s t e mf o rr a i l w a y s 铁路移动通信网络 h o m el o c a t i o nr e g i s t e r本地位置寄存器 i n t e m e tc o n t r o lm e s s a g ep r o t o c o l互联网络控制报文协议 i or e q u e s tp a c k e tf o 请求包 i n t e r r u p tr e q u e s t 中断请求 i n t e m e ts e r v i c ep r o v i d e r互联网服务提供商 l i n kc o n t r o lp r o t o c o l连接控制协议 m u l t i m e d i am e s s a g es e r v i c e多媒体短信业务 m o b i l es w i t c h i n gc e n t e r移动交换中心 m o b i l eo r i g i n a t e d移动起始短消息 m o v et of o n tt r a n s f o r m前移变换 v 一删脚眦l耋l言洲一一|耋啪|詈眦一眦一一|；一眦时政研船|耋眦啪胁 硕士学位论文符号说明 m t n c p 脚 p c u p d n p d u p p p r a r p s g s n s i m s m s s m s g m s c s m s i w m s c t c p t v s u 黼 啪 u d p u s b v i c v l r m o b i l et r e m i n a l 移动终接短消息 n e t w o r kc o r ec o n t r o l网络核心控制 p a s s w o r da u t h e n t i c a t ep r o t o c o l密码认证协议 p a c k e tc o n t r o lu n i t分组控制单元 p a c k e td a t an e t w o r k分组数据网 p r o t o c o ld e s c r i p t i o nu n i t 协议描述单元 p o i n tt op o i n tp r o t o c o l 点对点通信协议 r e v e r s ea d d r e s sr e s o l u t i o np r o t o c o l 反地址解析协议； s e r v i c eg p r ss u p p o r tn o d e 业务支持节点 s u b s c r i b e ri d e n t i t ym o d u l e 用户识别模块 s h o r tm e s s a g es e r v i c e 短消息服务 g a t em s c短消息入口交换中心 i n t e r w o r k i n gm s c短消息出口交换中心 t r a n s m i s s i o nc o n t r o lp r o t o c o l 传输控制协议 t r a n s i e n tv o l t a g es u p p r e s s e r 瞬态电压抑制器 u n i v e r s a la s y n c h r o n o u sr e c e i v e r t r a n s m i t t e r 通用异步收发器 u s br e q u e s tb l o c k 总线驱动程序发送包 u s e r d a t a g r a m p r o t o c o l 用户数据包协议 u n i v e r s a ls e r i a lb u s 通用串行总线 v e c t o ri n t e r m p tc o n t r o l l e r 向量中断控制器 v i s i t o rl o c a t i o nr e g i s t e r 访问位置寄存器 v i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。论文主要是自己的研究所得，除了已注明的地方外，不 包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其 他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作 的贡献，已在论文的致谢语中作了说明。 作者签名： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以采用复印、缩印或其他手段保存学位论文；学校可根据 国家或湖南省有关部门的规定，送交学位论文。对以上规定中的任何一项， 本人表示同意，并愿意提供使用 储躲酩幻师躲脚眺牛月监日 硕士学位论文第一章绪论 1 1 项目的背景和意义 第一章绪论 目前。国内在正线运行的内燃机车和电力机车上全部安装了机车信号及列车运行监 控记录装置，有效解决了正线列车运行的安全防护问题，使列车行车事故大幅度地下降。 与此同时，随着信息化管理和节能要求的不断提高，需要监控和记录的信息量大幅度增 加，不得不在机车上加装各式各样的信息记录装置。这些信息通常通过i c 卡转储方式 转送至地面有关监控管理部门，这一过程只有当机车返回所在的机务段后才能完成，使 得数据处理严重滞后，不利于铁路枢纽的高速、高效和安全运行。此外i c 卡存储容量 有限，机车上的运行数据必需分开存储，加上国内运营的机车成分复杂，装备不统一， 未能实现数据采集和处理的标准化，不便于列车的联网统一调度和信息化实时管理。因 此，引进现代先进的信息技术，构建一个能够满足机车信息的实时无线传输系统已成为 铁路运营管理的迫切需要。 1 2 无线通信技术在列车通信中发展概况 为了确保高速列车安全运行，实现列车状态监控和自动控制，列车与地面调度之间 必须进行双向的信息传输。对此，国外提出几种不同的方案，其中包括：德国连续式列 车自动闭塞系统中的轨道电缆方式，日本上越新干线的泄漏电缆方式以及7 0 0 系列的动 车组的扩频通信方式【1 1 ，欧洲e t c s 系统的g s m - r 纯无线方式等等 2 1 1 3 1 我国铁路无线通信是运输指挥和作业的重要通信手段，列车无线调度通信系统、站 场平面调车无线通信系统已经普及。车辆自动识别、驼峰机车信号和调车作业安全监控、 客货场作业、公安保卫、线路和道口防护、歹h 车安全预警、战备应急等运输生产各环节 均采用了无线通信技术，对保障铁路行车安全，提高运输作业效率发挥了重大作用但 我国铁路无线通信存在着技术落后、功能单一、频率利用率低、干扰严重、数据传输能 力差、系统分散、不具备网络能力等缺陷，与铁路的发展和现代化需要不相适应，与发 达国家铁路无线通信技术差距很大。不能满足铁路新一代基于无线通信的列车控制系统 c 1 s 对车地控制信息传输的需求，同时也不适应客运专线和高速铁路等现代铁路运输 对信息化和提高客运服务质量的需要国内的无线列调系统一般是基于4 0 0 m h z 频段的 无线通信系统，长期以来一直存在枢纽地区同频干扰严重、信道接入困难、语音不清晰 和相互干扰的问题【4 1 我国要在2 0 1 0 年前实现主要铁路干道的g s m - r 网络覆盖，目前青 藏铁路部分路段已经实现接近连续式g s m - r 两j 络覆盖 s l l 6 1 。g s m r 符合通信信号一体化 技术发展的需要，其规范的技术条件，统一的技术标准，成熟的产品和生产技术，成为 硕士学位论文第一章绪论 既有无线通信系统的更新换代的方向。 在g s m r 无线通信系统没有完全覆盖铁路运输网的情况下，彭春华等提出了利用现 有无线列车调度平台和铁路分组数据交换网，采用话音压缩和扩展技术实现数话同传【7 】 的方法，有效解决了现有无线列车调度系统的不足，但没有从根本上解决问题。郑州铁 路开发局技术开发公司主持开发的“机车运用状态实时监测系统”，采用t g s m g p r s 数 据传输，该系统从2 0 0 4 年9 月份运行以来，数据传输的可靠性得到验证嗍，但传输数据量 大，系统的实时性不能保证。利用g s m g p r s 无线网络进行数据传输符合铁道部第六次 铁路提速的要求，同时也便于晦j g s m r 无线网络过渡。构建基于g s m g p r s 的数据传输 系统是一个比较经济的选择，但是机车数据的实时传输成为系统能否实用化的一个关键 问题。 1 3g s m g p r s 技术介绍 g p r s 是通用分组无线业务的简称，是一种以全球手机系统( g s m ) 为基础的数据传输 技术，是在现有g s m 系统上发展出来的一种新的数据承载业务，目的是为g s m 用户提 供分组形式的数据业务。网络设备主要包括：g p r s 交换设备，如g p r s 网关支持节点 g g s n 和g p r s 业务支持节点s g s n ，以及其他一些功能实体；g p r s 基站子系统附加设备， 主要包括引入g p r s 业务后，在基站子系统b s s 或基站收发信机b t s 中新增加的硬件分组 控制单元p c u ；其它设备如本地位置寄存器h l r 、访问位置寄存器v l r 、移动交换中心 m s c 、短消息入口交换中, d s m s g m s c 和短消息出口交换中, t = c s m s i w m s c 等，g s m 系 统原有设备被升级以支持相应的与g p r s 有关的功能；移动台必须是g p r s 移动台或 g s m g p r s 移动台 g p r s 具有以下几方面的技术优势： 1 ) 资源利用率高 g p r s 引入了分组交换的传输模式，用户只有在发送或接收数据期间所占用资源，这 意味着多个用户可高效率地共享同一无线信道，从而提高了资源的利用率。g p r s 用户 的计费以通信的数据量为主要依据，体现了“得到多少、支付多少”的原则。 2 1 传输速率高 g p r s 可提供高达1 1 5 k b p s 的传输速率。这意味着通过便携式电脑，g p r s 用户能快 速地上网浏览，同时也使移动多媒体应用成为可能。 3 1 接入时间短 分组交换接入时间短，能提供快速即时的连接，可使已有的i n t e m e t 应用( 如e - m a i l 、 网页浏览等) 操作更加便捷、流畅 钔支持球协议和x 2 5 协议 g p r s 支持因特网上应用最广泛的m 协议和x 2 5 协议。而且由于g s m 网络覆盖面 2 硕士学位论文第一章绪论 广，使得g p r s 能提供i n t e m e t 和其它分组网络的全球性无线接入 g p r s 的缺点是： 1 ) 实际传输速率受网络和实现终端的制约 g p r s 的理论传输速率是在占用所有可能时隙的情况下获得的，实际上用户很难使用 足够多的时隙，所以实际传输速率大概在4 0 8 0 k b p s 左右 受地形的和终端信号强度的影响，g p r s 在传输过程中会有中断和丢包现象 1 4 课题的研究内容 列车信息无线传输系统应满足以下要求： 1 1 数据传输可靠性高。采取各种容错、纠错和冗余等技术，使系统的传输误码率达 到l o 击1 0 4 ； 合适的信息吞吐量和实时性对于运行速度为3 0 0 k m h 的高速列车，5 0 m s 内传输 1 0 2 4 b i t 信息，信道传输速率必需达到2 0 - 4 8 k b p s ： 3 ) 大容量信息的短时传输； 钔多终端信息的并发传输。 现行的g p r s 系统基本能满足上述要求，但受各种条件制约，仍存在数据传输的安 全隐患。 本论文结构如下： 第一章，探讨了无线数据传输技术在铁路系统中的应用，分析了利用g p r s 网络实 现机车数据传输的可行性。针对g s m g p r s 网络传输的缺点和机车记录信息量大的特 点，提出了利用数据压缩技术来实现机车信息传输的解决办法。 第二章，分析了数据压缩技术在机车信息传输中应用的可行性通过研究当前几种 流行的数据压缩算法，实现并提出了改进方法。其中，介绍了基于字符块变换( b w t ) 的综合数据压缩算法，给出了实现方法通过比较，最终将基于对分二叉树的l z s s 算 法作为机车信息的压缩算法。 第三章，这是本文的重点和核心内容，构建了基于g s m g p r s 的机车信息实时传输 系统，介绍了此系统的设计原理和实现方法。 第四章，简单介绍了系统装车方案，并给出了该系统的一个应用方案。 第五章，对本文工作进行了总结，并提出了展望。 硕士学位论文 第二章数据压缩技术分析与实现 第二章数据压缩技术分析与实现 数据压缩是一种信源编码，通过减少信源的冗余度来达到高效传输信息的目的【9 】。 按照通用的分类方法，数据压缩分为有损压缩和无损压缩。无损压缩是一种冗余度压缩， 尽量除去原始数据中冗余部分，而不丢失任何有用信息，它是可逆的，即可以从压缩数 据中完全恢复出原始数据，用于不容许出现数据失真的场合。有损压缩是一种熵压缩， 它是不可逆的，以丢失部分信息来达到比较高的压缩比率，当然前提是不能破坏原始数 据的基本信息。机车数据主要是机车运行的安全数据，数据的转储过程中，必须保证数 据的正确性和完整性，故采用无损数据压缩算法。 2 1 机车数据类型与传输概况 ( 1 ) 机车运行信息数据 t a x 2 型机车安全信息综合监测装置为用户提供了3 个备用插件单元位置，在其中 加装一个接口卡，通过串行通讯协议可以获得如下信息： 机车型号；机车号；客，货车；本席 机；牵引辆数；车辆换长；牵引重量；车站号； 列车实时速度；公里标；车次；区段号；日期时间：司机号；副司机号； 正常情况下，通讯记录单元( 主机) 每隔5 0 m s 周期向总线发送以上数据，共有4 0 个字节，从机接收到以上数据后进行相关处理。实时性要求高的数据不需要压缩。完整 的记录数据由上述数据的关键部分和其他专用设备采集的数据构成，由于每一条记录都 包含时间信息、机车身份识别、司机身份识别信息和线路信息，数据冗余量相对较大。 ( 2 ) 机车记录数据 机车电量统计装置记录机车电量使用状况，包括t a x 箱的机车识别信息、机车速 度时间信息与机车功率，是机车电量分析的基础数据，便于地面进行电量统计分析。电 量信息由4 个基本数据组成：公里标、机车速度信息、时间、功率，1 0 s 记录一次，信 息冗余度大。 监控装置记录日期、时间、里程坐标、机车条件变化、运行状态、按键、检修人员 乘务人员输入、系统自检、揭示控制、点式信息等内容，信息冗余度大。 ( 3 ) 数据分类与分析 机车信息可以归纳为实时运行信息和安全记录信息。实时运行信息记录了机车安全 行车的关键数据，如：机车速度、机车信号、司机操作等信息，这类数据突发性强、数 据量少、实时性要求较高，需要定时发送到地面，供地面监控人员时刻监控机车运行状 4 硕士学位论文第二章数据压缩技术分析与实现 态。及时发现非正常现象，避免事故发生一条完整的安全信息不足5 1 2 字节，勿需压 缩。安全记录信息包括机车能耗记录，司机操作记录、监控安全行车记录等等，不需要 实时传输，但需要定时转储到地面进行分析，数据量大、准确性要求高。此类信息利用 g p r s 传输时，经历时间较长，可靠性难以保障。 现有g p r s 技术可以保证单帧数据( 5 1 2 字节) 不失真传输，但难以保证连续帧数 据不失真传输。解决这一问题的基本对策是：1 ) 制定多帧信息完整性验证协议，实现 通信续传功能；2 ) 尽量减少传输的信息量，缩短信息传输时间。本文研究目标是引入 优质的数据压缩算法，制定安全的用户层通信协议，力争为实现机车信息的实时安全传 输提供技术方案 2 2 无损数据压缩理论的发展概况 1 9 4 8 年，s h a n n o n 在提出信息熵理论的同时给出了一种简单的编码方法一s h a n n o n 编码。1 9 5 2 年，& m f a n o 又进一步提出了f a n o 编码。这些早期编码方法揭示了变长编 码的基本规律，获得一定的压缩效果1 9 5 2 年，d a h u f f m a n i l o 】在论文“最小冗余度代 码的构造方法( am e t h o df o rt h ec o n s t r u c t i o no fm i n i m u m - r e d u n d a n c yc o d e s ) ”中提出 了第一个实用的编码方法抽】缶n a n 编码，影响深远，直至今日，仍在广泛的应用 h u i f n a a 编码效率高，运算速度快，实现方式灵活。早期u n i x 系统上的压缩程序 c o m p a c t 实际上就是一种h u f f m a n 0 阶自适应编码。2 0 世纪8 0 年代初，h u f f m a n 编 码又出现在c p m 和d o s 系统中，代表程序为s q 。今天，许多知名的压缩工具和压 缩算法( 如w i n r a r 、g z i p 和j p e g ) 中，还都显现h u f f m m a 编码的身影。1 9 6 8 年前后， e e l i a s 发展了s h a n n o n 和f a n o 的编码方法，构造出从数学角度看来更为完美的 s h a n n o n - f a n o - e l i a s 编码。1 9 7 6 年，j r i s s a n e n 提出了一种可以成功地逼近信息熵极限 的编码方法算术编码1 9 8 2 年，r i s s a n e n 和g g l a n g d o n 一起改进了算术编码 之后，人们又将算术编码与j g c l e a t ) , 和i h w i t t c n 于1 9 8 4 年提出的部分匹配预测 模型( p p m ) 相结合，开发出了压缩效果近乎完美的算法z i v 和l e m p e l 于1 9 7 7 年发 表题为“a u n i v e r s a l a l g o r i t h m f o r s e q u e n t i a l d a t a c o m p r e s s i o n 论文i l l l ，文中描述的算法 被后人称为l z 7 7 算法。1 9 7 8 年，二人又发表了该论文的续篇 c o m p r e s s i o n o f i n d i v i d u a l s e q 啪c 豁、，i a 、a b l er a t ec o d i n g 1 2 1 ，后被称为l z 7 8 压缩算法。1 9 8 4 年，t a w e l c h 发表了名为 a t e c h n i q u e f o r h i g h p e r f o r m a n c e d a t a c o m p r e s s i o n 的论文【1 3 1 ，描述了他在 s p e r r y 研究中心( 该研究中心后来并入了u n i s y s 公司) 的研究成果，这是l z 7 8 算法 的一个变种，也就是后来非常有名的l z w 算法1 9 9 0 年后，t c b e l l 等人又陆续提 出了许多l z 系列算法的变体或改进版本。1 9 9 4 年，m b u r r o w s 和d - j w h e e l e r 共同提 出了一种全新的通用数据压缩算法，其核心思想是对字符串轮转后得到的字符矩阵进行 排序和变换( 称为b u r r o w s w h e e l e r 变换，简称b w r ) 【1 4 1 。此后，b w t 算法在开放 5 硕士学位论文第二章数据压缩技术分析与实现 源码的压缩工具b z i p 中获得了巨大成功，针对文本文件，b z i p 的压缩效果远优于l z 系 列算法的工具软件。 通常，以s h a n n o n 信息熵为标准计算基于信源熵的压缩编码效率，但这种方法不适 合基于字典模型的压缩编码。为了比较这两类压缩编码的效率，一般采用标准文件进行 压缩试验，否则，算法的有效性就不能得到充分验证f 1 5 】【1 6 1 。这些标准文件应满足如下 条件： a ) 包含的文件种类多样化； b ) 选择的文件是大家熟知的，便于重复实验； c ) 文件长度合适，一般不超过1 兆字节； d ) 文件是有效的，应用范围广，充分反映压缩算法的有效性和适应性。 根据以上条件，r o s sa r n o l d 和t w ab e l l 等人通过调查和分析【1 7 , 1 s , 1 9 1 ，认为文件 c a l g a r yc o r p u s ( 见表2 - 1 ) 符合标准测试文件的要求本文采用这些测试文件 表2 - 1 c a l g a r yc o r p u s k 件 另外，为了检验算法对机车数据的压缩效率，采用了三个机车记录数据文件，例 于表( 2 2 ) 。 表2 - 2 机车数据记录文件 6 硕士学位论文 第二章数据压缩技术分析与实现 2 3h u f f i n a n 算法 2 3 1 算法原理 h u f f i n a n 编码是利用信息的统计特性进行数据压缩的一种信息熵编码。基本原理是 按照信源符号出现的概率的大小进行排序，出现概率大的分配短码，反之则分配长码 首先把所有的字符按概率降序排列，建立列表。然后由下至上构造一棵树，每片叶子放 一个字符。具体的做法是；每一步都找出两个概率最小的者相加后用一个辅助符号表示， 置于该树的顶部，同时把两个字符从列表中删去，如此继续，直到列表中只剩一个辅助 符号，这样就完成树的构造最后由树来决定每个字符的码字 随着数据压缩的进行，计数值和程序代码的长度迅速增加，可能导致溢出，使压缩 紊乱主要有两种溢出原因： 1 ) 当根节点的权值( 出现次数的总和) 超过h u f f m a n 树中计数器的取值范围时， 将发生溢出。 例如：当节点权值长度为k 位时，而节点出现次数超过2 ，则计数器溢出 2 ) 当程序编码的长度超过用于传输代码的整数范围时，发生溢出 例如：随着数据量的增大，字母表增加，最小概率字符的长度k 也会增加，当k 值 超过设定的最长编码长度时，发生溢出。 针对第一个原因，可以通过扩充计数器的取值范围的方法克服在实际应用中，特 别在列车数据传输过程中一次性传输的数据量不会很大，每次编码时对要压缩文件进行 长度判别，当文件长度过长时就对文件进行分割压缩，这样就可以防止计数器溢出 第二个原因可以通过定长( 8 - b i t ) 字符型数据扫描方式在机车信息数据的处理与传 输中避免发生，但牺牲了一定的压缩效率 2 3 2 改进及实现 h u f f m a n 算法必须先扫描文件进行字符出现的概率统计，然后再次进行扫描文件进 行编码，两次扫描时间之和决定了算法编码的速度。解码时只需要对文件进行一次扫描， 但同时必须进行编码匹配操作，匹配过程决定了解码速度。下面介绍一种快速h u f f m a n 实现算法，此方法在编码和解码的过程中进行了优化。其原理是将读输入的文件按照字 节进行存储，字母表为a s c i i 码，共有2 5 6 个码值，先进行概率统计，再构建h u f f a n a n 树，最后实现遍历压缩其具体步骤如下： 步骤一：定义数据结构 节点的数据结构包括频率，a s c i i 码值，节点编码，码长度等变量。节点结构为二 叉链表存储结构。例如构造一个类： c l a s sc h u t f i n a n n o d e 7 硕士学位论文第二章数据压缩技术分析与实现 p u b l i c ： c h u f f m a n n o d e o m e m s c t ( t h i s ，0 ，s i z e o f ( c h u f f m a n n o d e ) ) ；) i n tn f r e q u e n c y ： 出现频率，最大值2 ”一l b y t e b y a s c i i ； ，字母表 d w o r dd w c o d e ：，码长度不超过8 位，定义3 2 位空间，便于码的操作 i n tn c o d e l e n g t h ：码的长度； ； 为了防止频率计数器溢出，每个文件的大小不大于2 m b y t e 。 步骤二：构造h u f f i n a n 树 构造字母表，为o 到2 5 5 的a s c i i 码值。遍历文件，扫描各个字母出现的频率，然 后利用q s o r t o 程序进行捧序利用最小的两个频率节点构造一个新的节点1 2 0 l ，新节点 的频率为两个叶子节点的频率之和。然后将新节点和剩余的节点进行重新捧序，采用上 面同一步骤再构造新节点，直到最后一个自由节点( 称为树根) 在构造h u f f m a n 树时， 将每一个节点赋一个二进制的值，左节点值为0 ，右节点值为l 。编码时，从叶子节点 开始，从下至上进行编码。叶子节点的二进制码值放在最高位，根节点码值放在最低位。 编码的流程图如图2 1 所示。 图2 1h u f f m a n 编码流程图 8 硕士学位论文第二章数据压缩技术分析与实现 根据二叉树的性质可以确定部分参数： 性质l ：在二叉树的第f 层节点上至多有2 “个节点。 字母表的数目最大为2 5 6 个，则h u f l i n a n 树的叶子节点最多有2 5 6 ，层数最大为9 层，即树的深度为9 性质2 ：深度为k 的二叉树至多有2 t 1 个节点。 本程序中的二叉树节点最多为5 1 1 个，构造h u f l 陆a a n 树的节点缓冲区为5 1 1 个大小。 低2 5 6 个区间大小为叶子节点存储区域，高2 5 6 个区间大小为分枝节点的存储区域。它 们之间利用链表指针连接起来 步骤三：文件遍历编码 文件是按照8 位读入的，每扫描到一个8 位时，就可以在树种找到一个对应的a s c i i 值的节点，将这个8 位数据用节点的编码替换。这里就涉及到位的操作问题，因为 h u f f m a n 码是非等长码定义一种位的操作模式： 假设累计码长为整数一，新读入码长为j ，文件输出指针为p 。令王k ( 一) = l 斗s j ， 其中l - j 为取整数；l s s ，( ) = 刀m o d8 。假设前 k q ) 个字节已经填充，p 指向文件的 第0 ) + 1 个字节，这个字节的低上船，伽) 位已经填充。将新读入的码向左移二。，o ) 位， 然后与p 指向的字节值( 一般把p 的空间强制转换成1 6 位或3 2 位) 进行或的操作。p 指针指向的8 位填充后，p 自动指向下一个8 位空间，新码多余的码字填充到p 所指空 间的低位。 图2 - 2 位操作模式示意图 文件指针定义成字节( b y i e ) 类型，在进行内容操作时，可以利用强制类型转换 的办法每次进行4 b y 腰位进行操作，防止移位溢出。 步骤四：文件解码 文件解码有两种方式：a ) 被压缩文件包含叶子节点的字母表和对应的非等长编码， 以及被压缩文件编码。解码时按位读入数据，每读一位需要对编码进行匹配，直到匹配 成功输出对应字母，然后进入下一轮匹配。假设字母表长度为j ，一个码长为三的码需 要匹配l s 次，文件长度为竹，平均码长为三，则总共匹配l 行s 次。文件越长，算法 耗费的时间就越长”被压缩的文件要包含如下信息；原文件长度，树的叶子节点数 9 硕士学位论文第二章数据压缩技术分析与实现 目，叶子节点的信息( 字母，频率) ，被压缩的文件编码。解码时需要重新构建h u f f m a n 树。读入一定长度的编码，编码的最低位对应树的根节点，然后从上到下进行节点判别， 直到找到叶子节点，就输出一个字母。如此循环，直到文件结束。每次搜索h u f f n m n 树最大的次数为k ，其中k 为树的深度( 七 9 ) ，对于一个长为行的文件只需要操作n k 次，比方法曲时间大大缩短。 步骤二中编码保证了最低位为根节点二进制值，最高位为叶子节点二进制值。而步 骤三中的位操作模式使得解码比较方便。文件读入编码数据时，最低位为树的根节点， 从根节点开始，开始搜索树直到寻找到叶子节点，一次解码就完成了。假设码长计数器 为玎，遍历指针为p ，日。( ”) = l s j ，其中l j 为取整数；工璐，( 功= 疗m o d8 。解码程 序流程图如图2 - 3 所示。 图2 - 3 快速h u f f m a n 解码流程图 2 3 l z s s 算法 2 3 1 算法原理 l z 7 7 主要思想是把已经输入的数据流的一个部分作为字典，编码器为输入流开辟 l o 硕士学位论文第二章数据压缩技术分析与实现 一个窗口，窗口在输入流上滑动 搜索缓冲区 向前缓冲区输入数据流 - - - i输出压缩码( 偏爹量，长度，字符) 图2 - 41 2 7 7 编码器原理图 这个窗口分为两个部分：一个是已经编码的数据流，叫搜索缓冲区；一个是向前缓 冲区。搜索缓冲区比向前缓冲区要大通常l z 7 7 算法输出标识由3 部分组成：偏移、 串长度、向前缓冲区的下一个字符1 2 l 】。其编码原理图如图2 4 所示l z 7 7 算法经过很 多改进，其中一种改进的l z 7 7 标识只包含偏移和串长，如果找不到匹配串，编码器就 输出一个不压缩的字符，需要一个标志位来表示此字节字符是否被压缩。 搜索缓冲区长度为几千字节长，偏移字段的典型值为1 1 1 3 位的数据，加上向前缓 冲区的长度，整个标识的长度为1 6 位在编码器先采集8 个输出项，然后在编码器的 输出流中先输出上8 个输出项的标识位，再紧随8 个输出项。0 代表没有压缩，l 代表 已经压缩。解码器首先读取标志位，当为0 时，直接复制字符，当为l 时，进行解码 图2 - 5l z 7 7 编码程序字符匹配流程图 向前缓冲区和搜索缓冲区的字符匹配流程如图2 5 所示： 硕士学位论文第二章数据压缩技术分析与实现 假设s r g 指向搜索缓冲区下边界，p 和s t r 指向向前缓冲区下边界，其中搜索缓冲区 上边界和向前缓冲区下边界是相邻的。 l z 7 7 算法对于很多类型的数据都能取得很好的压缩比，但l z 7 7 算法中有一个主要 性能瓶颈：进行编码时，正文窗口中的每个位置都要与搜索缓冲区进行比较，当试图通 过增加窗口大小以增大字典来改进压缩性能时，此性能瓶颈将变的更坏，但进行数据还 原的时候却不受此瓶颈的影响，因为它只拷贝短语，所以能够较高速率地运行。 为了解决l z 7 7 的性能瓶颈问题，l z s s 有两个变更：1 ) 首先是正文窗口维护方法 的改变。在l z 7 7 算法中搜索缓冲区的数据以正文相邻的模式存在，没有更高层次的组 织。进行短语匹配时，所需时间与搜索缓冲区的大小及短语的长度的乘积成正比。搜索 缓冲区的数据由一个树的结构组织起来，该树为二叉搜索树，通过对二叉搜索树中短语 的排序，寻找树中最长的匹配短语。所需时间与搜索缓冲区的大小和短语长度的乘积的 2 的对数成正比从而在不增加太多时间开销下使用更长的窗口来改进压缩效果成为可 能。2 ) 实际输出标记的改变。l z 7 7 的输出标记为一个短语偏移量、一个匹配长度和紧 跟后面的字符组成。l z s s 允许指针和字符随意混合在一起。一个l z s s 标识只含有偏 移量和串长度。如果没有找到匹配的串，编码器就输出下一个字符的不压缩代码。因此 为了区别标识和未压缩字符，就需要在它们前面增加一个标识位。 2 3 2 改进与实现方法 s t o r c r 和s z y m a n s k i 在1 9 8 2 年发表的l z 7 7 改进算法 2 2 1 有如下特点：1 ) 把向前缓 冲区包含在一个循环队列中：2 ) 把搜索缓存器包含在一个对分查找树中；3 ) 用两个字 段的标识取代3 个字段的标识。在对分二叉树中进行字符串的匹配，时间复杂度缩减为 0 0 0 9 ， r ) ，比利用循环队列进行匹配的算法的速度快。 ( 1 ) 树结构的构造 定义一个大小为n + f