Abstract: To reduce high complexity in extraction of functional regularity in digital ICs,a template called CHAIN generation algorithm is proposed based on data mining.Weights of edges are encoded,and a complex subcircuit isomorphism problem is solved by comparing edge weight sequences of the subcircuit.To reduce complexity and accelerate the algorithm,a pruning strategy is introduced into expending of templates to delete non-frequent subcircuits gradually.By merging template generation process and subcircuit isomorphism searching process,the regularity extraction flow is simplified.Experiments show that this CHAIN template algorithm is more effective.It obtains better circuit covering result than SPOG and TREE methods.

Key words: regularity extraction, frequent subcircuits, data mining, regularity index