（电力电子与电力传动专业论文）多功能电力参数监测仪的研制——系统结构与通信设计.pdf

东南大学硕士学位论文 a b s t r a c t m e a s u r e m e n to f e l e c t r i cp a r a m e t e ri sq u i t ep o p u l a rs i n c ep o w e rs y s t e mi sb u i l du p t h ea u t o m a t i o no f e l e c t r i cp o w e rs y s t e mi sa l w a y so n eo ft h eg o a l s w i t hm o d e md e v e l o p m e n ta n de n o r m o u sp r o g r e s so f t e c h n o l o g ya tf u l ls p e e do f i n d u s t r y ，m e a s u r e m e n ta n dc o n t r o li n s t r u m e n tt r a d eg o e st h r o u 9 1 lag r e a tc h a n g e o no n eh a n d ，m o d e r ns e m i c o n d u c t o rc r a f ta n dp r o g r e s so f t e c h n o l o g yh a v eo f f e r e dt h er e a l i s t i cf o u n d a t i o n f o rr e s e a r c ha n dd e v e l o p m e n to fi n t e l l i g e n ti n s t r u m e n t ；o nt h eo t h e rh a n d ，t r a d i t i o n a lt e c h n o l o g ya n d d e v i c ec a l ln o tm e e tt h er e q u e s to ft h es c i e n t i f i ca n dt e c h n o l o g i c a lp r o g r e s sm o d ea n dm o r e a so n eo ft h e m o s tb a s i ct r a d e si nt h ec o u n t r y ，i ti sa l li n e x o r a b l et r e n dt or e a l i z et h ea u t o m a t i o no ft h ep o w e rs y s t e m w i t ht h ep o p u l a r i z a t i o no ft h en a t i o n a le l e c t r i cm a r k e tp o l i c y ，t h er e q u e s tf o ra u t o m a t i o no ft h ep o w e r s y s t e mi sh i 曲e l a n dh i 曲e r m o d e me l e c t r i cp a r a m e t e rm e a s u r e m e n tn o tm e r e l yr e q u i r e sc a r r y i n go n s i m p l ep a r a m e t e r ，i ta l s od e m a n d sal o to f o p e r a t i o n ，a n a l y s i sb ym e a s u r e m e n t ，s y n t h e s i so f e v e r ym o d u l e a st h eb a s i cf u n c t i o no f a u t o m a t i cp o w e rs y s t e m i ti se s s e n t i a lt ou s et l l eo c c a s i o ni ne a c he l e c t r i c i t y t h i sa r t i c l ep u t sf o r w a r da ni n s t r u m e n tt h a ta p p l i e st oa u t o m a t i ce l e c t r i ce n e r g ym e a s u r e m e n tm a d c h a r g eu s e db yt r a n s f o r m e rs u b s t a t i o n so rs o m el a r g eu s e r s i t sa p p l i c a t i o nf i e l d sa l es u b s t a t i o na u t o m a t i o n ， i n t e l l i g e n tb u i l d i n g ， e l e c t r i ce n e r g ym a n a g e m e n ti n s i d ee n t e r p r i s e s , p o w e rq u a l i t ym e a s u r e m e n t ， m a n a g e m e n ta n de x a m i n a t i o n t h i gt h e s i sp r o p o s e sm u l t i f u n c t i o n a le l e c t r i cp a r a m e t e rs y s t e m a t i cd e s i g np r i n c i p l ea n dw h o l es y s t e m o fm o n i t o r i n gi n s t r u m e n t si n t e r n a la n db e l i e v et ot h eo u t s i d ef b r t h e ru n d e ra c t u a lb a c k g r o u n do fp r o j e c t ， a n dh a sc a r d e do nr e l e v a n td e m o n s t r a t i o nt ot h i ss c h e m e t h e l lt h ed e t a i l e di n t r o d u c t i o nr e g a r d ss p l i n t e r f a c ea st h eo p e r a t i o np r i n c i p l ea n dc o u r s eo f t h es y s t e m a t i cm u l t i - p r o c e s s o rs y s t e m so nf o u n d a t i o no f c o m m u n i c 撕o n a n dp r o v i d et h er e l e v a n ts o f t w a r ea n dh a r d w a r et od e s i g n f i n a l l y ，s o m es u g g e s t i o n sa r ep r e s e n tt oi m p r o v e t h ep e r f o r m a n c e a tt h es a m et i m e , s o m es u m m a r i e so fi d e a sa n de x p e r i e n c e sh a v ea l s ob e e ni n 仃o d u c e d ，i n c l u d i n g d i s c u s s i n gt h ed e v e l o p m e n tt r e n d sa n ds t r u c t u r ec h a r a c t e r i s t i c so ft h em o d e r nj n s t m m e n tt h a te x p l a i n s w h i l ec o m p a r i n gi nt h es c h e m eo ft h es y s t e m ，e r r o rw a v er e c o r dt e c h n o l o g ya n dh o wt oc h o o s es e r i a l c o m m u n i c a t i o nd e v i c e s ，e t c k e c w o r d sa d s p 2 1 9 xm o d b u sg p s c a nr t c e r r o rw a v er e c o i - d i i - 学位论文独创性声明 v - 7 9 0 8 9 6 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人己经发 表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用 过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说朗 并表示了谢意。 签名： 关于学位论文使用授权的说明 日期：鲨! ! ：! ：；1 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内 容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可 以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东南大学研究生 院办理。 签名 r ，一 鲨 期 第一 严 名签师导 群 l 缸 第一章绪论 1 1 电力参数测量技术背景 第一章绪论 电力参数的测量是一个具有相当历史的技术，随着现代丁业的发展以及技术的进步，今天的测 控仪器行业正在经历着一场翻天覆地的变革。一方面，计算机技术进步为新型的测控仪器产生提供 了现实基础，另一方面，传统的测控仪器越来越满足不了科技进步的要求。传统的基于单片机的测 量方式在实时性要求很高的场合，具有太大的局限性，例如，测量速度不高，精度不够，运算速度 与数据分析能力不能满足要求，综合性较差。现代电力参数测量不单要求对电参数进行简单测量， 还要求完成对单个甚至多个被测量进行运算、分析，得出对各系统的综合分析、评估。 与传统的电力参数测试装置相比，微机测试装置具有如下优点”。： 1 )性能优。微机具有高速运算、逻辑判断和记忆功能，微机测量装置是通过其软件程序来实 现的，因而它除了可以实现传统测试装置的功能外，还能实现很多传统测量装置无法实现 的功能。微机测量抓过年之还具有分时段记录参数、故障参数追忆等功能。此外，微机测 试装置的软件不受电压波动，环境温度改变，以及元件老化的影响。 2 ) 可靠性高。微机测量具有故障自诊断能力，能不断地对装置各部分进行自动检查，可以准 确地发现装置故障部位，及时地进行报警，以利处理。另外，微机测量在硬件上采取了电 磁屏蔽、光电隔离等措施；在软件上采取了数据有效性分析，自动纠错算法等抗干扰措施， 因而抗干扰性强，运行可靠。 3 )灵活性强。很多微机测量装置使用的硬件和外围设备可通用，装置要实现不同的原理、特 性和功能主要取决于软件，因而，在硬件不变的情况下，只需对软件进行更改就能灵活配 置各种功能。 4 ) 调试维护工作量小。微机测量装置具有自诊断功能，如果加电后没有报警信号，就可确认 装置完好，维护工作量小。 5 ) 经济性好。相对传统装置，微机测量装置的投资费用和运行维护费用都要小得多。 可见，微机测控装置具有广泛的应用背景，我国电力系统要实现自动化，大量采用智能测控设 备是一种必然的要求。 1 2 课题的提出 要实现电力市场，其中一条措施是必不可少的，即电能量采集以及计费自动化系统。电能量采 集以及计费自动化系统是集成电能量自动采集、传输、计费、结算于一体的自动化系统，是电网推 行商业化运营管理，电力走向市场的技术保障之一。从结构上来看，电能量采集以及计费自动化系 统是集主站系统，集中抄表装置，多功能费率装置于一体，全面实现发、输、配电网用户电能量自 动采集、分析和计费功能的自动化系统。 电能量采集和计费自动化系统按照用户类型可以大致分为变电站、大用户和一般居民用户三种 类型。变电站电能量自动采集系统主要对各级厂站的进线、出线、变压器、母线、电容器等无功补 偿的有功电能量，无功电能量，功率因素等电力参数进行自动抄录，以便进行计费管理和负荷控制 等。 本文提出了一种应用于变电站以及大用户的电能量采集以及计费自动化的装置，可以用于变电 站自动化，配电自动化，智能建筑，企业内部电能，电能质量测量，管理，考核。 东南人学硕士学位论文 1 3 论文的主要结构 为了条理清晰，循序渐进的讲述多功能电力参数监测仪的设计与研究，论文总其分为五章。第 一章绪论，阐述论文的选题背景、课题研究内容和文章的组织结构。第二章系统结构，讲述装基 本系统框图，针对每个模块做出概述性声明并简约的给出了系统模块之间通信的初步方案。第三 章模块硬件设计，特别针对装置中主控模块和人机界面的设计和研究，提出解决方案，给出了硬件 原理以及相关技术。第四章监控测试软件设计，讨论了装置软件开发的基本框图和流程，特别针对 系统内部、外部通信和故障记录以及在线显示等问题给出了解决方案。第五章总结，论文对已完成 的工作做出总结，对后续需要进行的工作提出建议，并对整个毕业设计做了简短回顾和评价。 2 一 第二章系统设计方案论证 第二章系统设计方案论证 当代测控仪表行业的技术在飞速发展，传统的单一功能的仪表一般已经在市场上没有生命力了。 电力工业作为国家晟为基础的行业，已经开始大量采用智能仪器作为控制与管理的基本设备，为此， 需要设备生产商能够设计制造出许多有特色的仪器来满足系统的不同要求。 2 1 需求分析 电力参数监测仪一般都需要对电网交流信号进行采样，做出诸如f f t 之类的实时运算，并且用 户可以在线的设置与观察某些参数，甚至还需要操作某些可执行部件( 例如继电器) 。 针对当今电力参数监测的行业背景，要想使得某一款仪器具有市场生命力与实际应用价值，必 须具有以下的全部或者部分功能： 电能测量：能够测量三相电网中的电压、电流、频率、功率等。 电能计量：能记录四象限电能，有功，无功等，支持多时段、多费率等计费方式，可以产 生电能计量脉冲。 显示负荷曲线。 电能质量分析：可以分析电网中的各次谐波分量，以及三相电压的不平衡度。 故障录波：可以记录电网或者用户端的各种故障现象，如过压，过流等等，并可以进行故 障分析。 开关量：支持一定程度的开关量操作以便监测或者执行各种动作。 可编程设置：可以现场改变仪表的各种设置参数。 通讯接口：可以支持远处数据传送。 可见，仪表的功能要求比较多，如果采用传统的单一处理器的方式，c p u 可能会面临资源极度 紧张，很难进行功能扩展等开发危险，增加开发的难度。而针对不同的功能设计出不同的模块，以 多处理器的思想来设计系统构架，可以较好的满足仪表设计的需求，减小开发设计失败的可能性。 2 2 方案提出与论证 多功能电力参数监测仪采用模块化结构设计 独立的完成各自的功能。本装置一共有六个模块 电源模块、传感器模块构成，如图2 1 所示。 各个模块大多具有独立的处理器系统，可以相对 即信号采集模模块、人机界面模块、主控模块、 图2 1 装置整体结构框图 多处理器系统的优点是可扩展性较好，自由度较高，但随之而来的是需要解决各个模块之间的 通信问题。 系统从模块间的结构关系来看一般可以分为并列结构和主从结构两种。并列结构的各个模块的 地位都是平等的，例如采用c a n 总线之类不分主从的通讯模式就可以实现并列结构。并列结构的 3 东南大学硕士学位论文 优点是系统逻辑结构也较为简单，但是一般通信协议较负责。目前并列结构的系统是广为研究的课 题，具有非常大的生命力，可惜的是目前支持这种结构的通信方式不是很多，且成本一般较高。目 前在工业控制领域占主导的还是主从式结构。这个系统结构的特点是系统内有一个主控单元，其他 单元都在其控制之下进行数据的交互。多功能电力参数监测仪正是采用了这样的一种通信方式。这 种通信方式一般用户可以直接的定义自己的应用协议，使用较为方便。相对地，通信的效率不如并 行式系统，在高速通信的场合应用受到了限制。 绝人多数多处理系统模块间的通信是通过总线方式来实现的。目前工业控制中使用的总线较多， 有并行的i s a ，p c i 等，也有串行的u s b ，r s 2 3 2 等。并行总线的优点是速度较快，但是占用口线 太多，并且通信距离有相当的制约。相对的，串行通信速率较慢，但是其抗干扰性能较好，可以传 输的距离较大，因此在一般速率要求不是非常高的情况f ，串行总线优先被采用。 控制c p u 决定后，设计时总是尽可能的使用c p u 片上集成的外设接口来进行通信设计。由于 a d s p 2 1 9 x 系列在工业控制中具有较为明显的优势与特点，其片上集成的两个主从式结构的s p i 接 口为设计人员提供了解决通信的一个简单易行的方案。关于s p i 通信的论述，在后文会有详细分析。 2 3 传感器模块 电流互感器( c t ) 、电压互感器( p t ) 仍然是电力测量中不可或缺的器件，在本次设计中分别 用于电参数检测的三相电压u a 、l i b 、u e ，中线电压3 u o ，三相测量电流i a 、i b 、i c ，三相分析电流 i a l 、l b l 、i e l ，中线电流3 i o 信号。当代技术发展使得对每一种电力参数都有专门的芯片直接实现 测量，但是对予一个多功能的仪表来说，针对每一个功能都配各一个硬件，不仅经济上不合理，在 实现上也有不少困难。通过对某些特定信号的采样，经过一定的信号分析处理，除了可以直接得出 用于电网质量监测的电压、电流信号以外，还可以用于功率、无功、功率因素、各次谐波以及频率 等重要电网质量参数的计算和统计。显然，这种做法是比较合理而可行的。 2 4 信号采集与处理 信号在采集与处理之前，一般都需要作滤波之类的前端处理才能被输入各个通道进行采样。作 为数据采集与处理的核心，采集模块正是负责这一任务。另外，该模块还需要对采集的信号作计算 与统计处理，包括数字滤波、f f t 、功率计算、频率计算、电能计算等。 计算后等待主控模块命令，通过s p i 通信接口将数据传送至主模块。具体该模块的设计原理与 实现过程，已经超出了本文设计的讨论范围。详细请参见裴亚强所著多功能电力参数监测仪的研 制一信号处理与参数计算一文。 图2 2 采集模块硬件框图 - 4 一 第二章系统设计方案论证 2 5 人机界面模块 叽乎当今所有的只能仪器都配备有人机交互界面。人机界面给操作人员提供了观察仪器参数， 设定仪器功能的一个非常直观的途径。人机界面设计的好坏，直接影响仪表的使用和市场销售。就 多功能电力参数监测仪来说，人机界面必须实现下列功能： 面板可以显示各个当前测量的电力参数。 一 可以通过按键操作，对仪表的各个测量参数进行设置，对于某些信息，还必须有定的记 忆功能。 _ 能够醒目而直观的指示系统工作状态。 关于人机界面的设计，第三章将详细讲述。 2 6 开关量模块 对于应用于电力工业的设备来说，几乎都具有一定的开关量输入输出通道用以继电控制的开出 与继电监测的开入。对于本仪器，同样也需要作相应设计作为仪表的选配部件，具体功能指标如。f ： 提供8 路继电器输出和8 路开关量输入。 _提供2 路o 5 v 或4 2 0 m a 模拟通道输入通道。 - 通过s p i 串行通信接口与主模块交互信息。 i 图2 3 开关量结构框图 2 7 主控模块 主控模块是整个仪器的调度核心，负责接收信号采集模块、人机交互模块的信息，对采集的信 息进行统计处理和分析处理。同时，主控模块必须对上微机的信号作出反应，通过通信接口，将记 录的电量参数信息、统计信息、分析结果和故障记录信息传送至上微机。关于主控模块的设计在下 一章有详细的描述。 东南大学硕士学位论文 第三章系统通信与设计 由前文分析可知，对于主从式通信方式的系统来说，系统通信的主要难点在于主控单元的控制 与调度。由于主从式通信的特点，主控单元必须决定通信的对象、时间、通道等等参数，以类似令 牌网的方式进行各种调度。以下就主控模块的设计进行详细说明。 3 1 主控模块硬件结构框架 主控模块作为各个模块调度的枢纽，主要负责各个模块之间信息的传送以及对外部系统做出正 确的反应与动作。就主模块的通信对象而言，主要有系统内部的采集模块、人机界面、开关量模块 以及系统外部的m o d b u s 设备和c a n 设备。下图给出了主模块的硬件结构框架。 3 1 1 微处理器与存储器扩充 图3 1主控模块硬件结构框图 由丁主模块处理的任务较为烦琐，需要有功能强劲的处理器支持。现代半导体技术的发展使得 d s p 逐渐普及。a d s p 一2 1 9 x 系列d s p 是由美国a d i 公司出品的广泛用于通信，仪表，工控，语音处理， 医疗，军事等场合的定点d s p 处理器，其片上集成了许多外设，诸如定时器，s r a m ，中断控制器等 等。该d s p 的多总线机制使其具有很高的运算性能，每条指令的执行只需要一个周期，总线与指令 高速缓存提供核高速数据流，保持高运算率。 d s p 的一个显著特点是单周期内可以多次存取数据，主要是因为d s p 大多具有两套或者两套以 上的总线。a d s p 一2 1 9 x 系列d s p 具有三种片内总线，程序存储器总线( 蹦) ，数据存储器总线( d m ) ， 以及d m a 总线( d m a ) 。在一个周期内，处理器可以通过这些总线进行两次数据访问和一次取指令操 作，这种特性对于作类似f f t 之类特定运算的时候具有明显的速度优势。”1 上述总线连接到d s p 的外部端口，从而可以访问外部的存储器，i o 映射空间以及b o o t 存储器。 外部端口提供了总线仲裁与控制信号，开发人员可以方便的将各种外设连接到d s p 总线上。 本装置的主控模块使用a d s p 一2 1 9 1 ，其片内集成了6 4 k 字的大容量r a m ，该r a m 映射到d s p 地址 空间的第0 页，并且分成两块，可以分别作为程序c a c h e 和数据c a c h e ，需要告诉运算的时候，片 内r a m 的容量将起到很大的作用。另外，该d s p 具有较大的外部存储空间，并采用分页技术来访问 存储器。d s p 最多支持2 5 6 页的寻址空间，空间每一页最大支持6 4 k 字，包括第0 页的片内r a m 。外 部存储空间采用分段式寻址方式，对于每一段空间，都有对应的片选信号( m s o - 3 ) ，并且可以 配置页边界，等待时间，等待模式等等。片上还集成了l k 字的r o m ，用于放置b o o t 内核代码，占 用第2 5 5 页，其他2 5 4 页对应于外部存储空间。另外，d s p 采用i o 空间与存储器空间独立编址的方 6 第三章系统通信与设计 式，i o 空间每一页都是由1 k 字构成，外部1 0 空间也有元i i 西选通信号。1 0 空间的第o 7 页对应 片内i o 空间，对应于片上集成外设的控制寄存器。”1 d s p 外部存储器接口的一个显著特点就是支持8 位1 6 位存储器，并且可以在程序运行时修改接 口模式。这样，8 位存储器就可以直接挂接到d s p 的总线上，逻辑上可以认为d s p 就是外扩了1 6 位 存储器。而对某些特殊存储器如f l a s h ，需要编程的时候，可以配置成1 6 位模式，按照数据手册指 定的时序对其进行各种操作“。 d s p 具有6 4 kw o r d s 片内s r a m ，包括3 2 kw o r d s ( 2 4 b i t s ) 程序r a m ，3 2 kw o r d s ( 1 6 b i t s ) 数 据r a m ，支持高速访问，可以以片内核心频率工作，大量实时数据保存在该区域内。“ 根据主控模块的实际外设连接，主控模块的存储空间具体设置见表3 1 ： 地址空间存储区功能实际使用空间存储区类型 o x 0 10 0 0 0 o x f ef f f fb o o t 存储器空间1 2 8 k 8f l a s h 0 x 0 00 0 0 0 0 x 0 08 0 0 0d s p 内部r a m 3 2 k 2 4 +r a 醵 3 2 k 1 6 0 x 0 20 0 0 0 “0 x 4 00 0 0 0片外工作区2 5 6 k x 8r a m 0 x 4 10 0 0 0 “0 x 8 00 0 0 0数据记录区5 1 2 k x 8f l a s h 0 x 8 10 0 0 0 0 x 9 00 0 0 0g p s 接口寄存器设置若干外设 铁电存储器等 3 1 2s p i 接口与驱动 表3 1 主控模块存储器空间 s p i ( s e r i a l p e r i p h e r a l i n t e r f a c e ) ，即串行外部设备接口，它是一种同步串行通信方式。本仪表中 各个模块的通信全部使用s p l 接口互连。 由8 p i 接口相连的串行总线是一种四线同步总线。通过s p i 总线不仅可以连接各种外围设备， 而且多个c p u 也可以通过s p i 相互通信，形成功能强大的多处理器系统。在任意时刻，总线只允许 一个设备作为主机，总线的时钟信号s c k 由主机来控制，另外三根信号分别是主入从出( m i s o ) 、 主出从入( m o s i ) 以及设备片选信号( 丽i 两) ，其典型结构如图3 2 所示。 图3 2s p i 设备典型连接结构图 由于a d s p 2 1 9 1 本身自带有两个独立工作的s p i 接口，s p i 本身又是点对多形式的连接，故此 7 一 东南大学硕士学位论文 设计时具有较大的自由度。考虑到主控模块和采集模块之间的数据通信营比较大，敲这两个模块之 间单独使用一个s p i 接口，并且工作于d m a 模式，可以快速的交互信息。其他s p i 子设备作为另 一个s p i 接口的子站连接。 图3 3 s p i 各个模块通信框图 为了保证s p i 主机与子设备之间高速率通信时的正确性，仪表采用了差分传输的方法作为信号 驱动“j ，如图3 4 。为清晰起见，图中电源和地接线未给出。 根据c p h a 和c p o l 设置的不同, a d s p 一2 1 9 1 支持最多可以支持4 种不同的传输模式，用户可 以在应用的时候根据其他外接设备的要求，设置s p i 控制寄存器中相应的位以满足要求。 图3 5 和图3 6 分别给出了在c p h a = 0 和c p h a 一1 时，s p i 传输协议时序图。比较两幅图， 可以看出，c p h a = 0 和c p h a = 1 时，s p l 数据传输具有一些不同点，见表3 2 。 c p h a = 0c p h a = l s c k 在数据传输中间时刻才开始翻转s c k 在数据开始传送时就发生翻转 片选信号在8 位数据发送完毕后， 片选信号在8 位数据发送完毕后立刻翻转， 仍然需要保持段时间但是l s b 发送时间变长 片选信号由硬件自动控制，只有实际数据传片选信号由软件设置，需要协调软件时序 输时，片选自动置低，用户软件无需干预 传输速率较快传输速率较慢 表3 2 c p h a = 0 和c p h a = 1 时序比较 婴 划器含l 。8 1 m 蛐i 鼬s ob a 5 m 。m 。i s 。o 引留引黼i 6 7 8 差分驱动 _ h v c c a 1 一 5 订 丁1u ”导广gs a ( z 。 - 。 1 了d i鲁 s c k y 8 图3 4s p i 差分驱动电路图 - - 8 - 鹭 m o s 第三章系统通信与设计 对钟计数 9 c k ( 期删 s 0 t a 悱1 - 螨i 时钟计数 s 嘎 蚪 s 嘎 口旺f l l 12345678 _ u s b ) 、 ； l s 8j i i m ，因此该算法时间复杂度是o ( i 2 m 、。 改进模式匹配算法 造成上述算法计算缓慢的原因是有回溯，而这些回溯是可以避免的。假定t = a b b a b a ，p = a b a ”，下图给出了朴素模式匹配算法的过程。 以图3 1 4 的第一趟比较为例，t o = p o ，= p i ，t 2 p 2 ，但是p o p l ，由此推知，( = p 1 ) p o 将p 右移一位，用和p o 比较肯定不等；又由于p o = p 2j j t 2 ( p 2 = ) 风，将p 再右移一位，用t 2 和比较也肯定不等。这样，我们可以将p 直接右移3 位，跳过第二趟，第三趟，执行第四趟，从 而消除了回溯。这种改进算法由k n u t h 等人提出，称为k m p 算法。 t 口bbabatabb 口ba 第一趟 lj | j 第二趟 p a t 口bb p a t ba t 口bbaba tabbaba 第三趟 第二趟 i li l p a t口bpat abn 图3 1 4 般性的，设t = t o t l 0 p = p o p l “i 醵用朴素模式匹配算法进行第s + l 趟比较 时，从t 的第s 位置与p 的第0 位置p o 开始比价宜到在t 的第s + j + j 位置失配： t t o t 2t s + l+ ，一l + ，t + 1 + i一1 i | l | p a tp op t 乃lp ，p j + 图3 1 5 这时应有： t s t t s + j2p o p t p j ( 3 1 ) 按照朴素模式匹配算法，下一次应从t 的s + 1 处用t 。与p o 开始匹配比较。若要匹配，则有 p o p l p = - i2 ts “t i + z t l + f - - t s + m - 1 4 第三章系统通信与设计 如果p 中 p o p , - p f t p i p 2 p i 则第s + l 趟不需要真正进行比较，因为有 po 乳- p 卜1 革ts + i ts + 2 - - 因此，第s + l 趟可以不作，一般性的如有对于没个值k ，有： p op l - - p 女十l p ，一一1 p ，一 - p ，且- p o p l - p p ：- l p 卜“1 - 才角p o p z p k = t5 + - 一5 + j - k 札ts = p j - k p 卜k h p i 因此，可以将第s 趟比较失配时p 从当前位置直接向右移动i k 位。在这个算法中，扫描指针s 不必 回溯：而p 中扫描指针应退回到“+ 处。 k 值的确定与t 无关，只和p 自身有关。可以用失效函数f 来确定。 ， 一j 七，当0 k 。 ， ， ，* h h 显然地，需要从缓冲里检索出“$ g p r m c ”这个字符串作为帧起始。从前文分析可知，如何正 确的计算出失效函数嘶) ，是实现无回溯匹配算法的关键。 从定义出发，计算f 0 ) - 就是要在串p 。p p ，中找出最长的相等的前缀子串po p 。p t 和后缀子串p j - k p j m l p ，这个查找过程实际上还是一个模式匹配的过程，只不过目标和模式都 是p 而