Study on UIO sequence generation for sequential machine's functional test
Haiping Sun, Minglun Gao, Alei Liang · 2002
Unique input/output (UIO) sequence is a basic element to generate vector sequences for a sequential machine's functional test, which arises in many applications, such as VLSI design and communication protocols. A new heuristic algorithm based on distinguishable state group (DSG) is proposed in this paper to optimize UIO sequences generation. The optimizing methods, including a insertion strategy based on a specified 'less' relation, several pruning strategies, and a novel store mechanism of multiple OPEN/CLOSED lists, are also presented. Experimental results show that the proposed algorithm greatly improves the efficiency of the UIO sequence calculation in terms of both the time and space complexities.