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.