摘要
UIO序列是对有限状态机进行功能测试的有效手段 ,在VLSI、通信协议等时序系统中有很强的实际应用背景 .本文基于可区分状态组这一概念设计了一个搜索算法 ,进一步利用搜索信息建立了一个基于“小于”关系的启发策略 ,有效的剪枝策略的设计将尽可能消除没有意义的搜索分枝 ,新设计出的多路OPEN/CLOSED表存储机制也加快了相关的判别、处理过程 .根据实验结果 ,分析了优化措施对于改进了搜索过程、减少搜索信息的产生、提高搜索速度有显著的贡献 .该算法与以往的算法相比 。
Unique Input/Output (UIO) sequence is an efficient method to perform functional test of Finite State Machine (FSM),which arises in many applications,such as VLSI designs and communication protocols,etc.A heuristic algorithm based on Distinguished State Group (DSG) is described to generate UIO sequences.The optimizing methods include a hellristic strategy based on a specific 'less' relation,several pruning strategies,and a novel access mechanism of multiple OPEN/CLOSED lists,and these methods eliminate ono sense nodes and branches to a great extent.According to the experimental results,the practicability of all the measures is analyzed.Compared with brute algorithms,the optimized one is improved in terms of time and space complexities.
出处
《电子学报》
EI
CAS
CSCD
北大核心
2002年第5期667-671,共5页
Acta Electronica Sinica
基金
国家自然科学基金 (No .698760 1 0 )
国家教委高等学校博士学科专项科研基金 (No .980 3590 1 )
关键词
搜索算法
有限状态机
UIO序列
启发式搜索
finite state machine (FSM)
unique input/output sequence
heuristic search
optimization strategy
functional test
