Radiate Path Matching: A Subcircuit Extraction Algorithm From Gate Level to Function Level

A high performance radiate path matching algorithm is proposed for logic synthesis of integrated circuit reverse analysis. The algorithm transforms the subgraph isomorphism problem into a matching problem between vertexes through the introduction of similarity features for every vertex.The dismatched vertexes are deleted gradually from the searching space,therefore the complexity of the algorithm is reduced significantly.Theoretical analysis and experimental results show that both the time and space complexity of our algorithm are only linearly dependent on the number of gates of the object circuit and the function module.