A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions

作者：Nagayama Shinobu^*; Sasao Tsutomu; Butler Jon T

来源：IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2017, E100D(8): 1583-1591.

DOI：10.1587/transinf.2016LOP0013

• index generation functions
• linear decomposition
• incompletely specified functions
• balanced decision tree
• content-addressable memory
• logic design
• heuristic

Index generation functions model content-addressable memory, and are useful in virus detectors and routers. Linear decompositions yield simpler circuits that realize index generation functions. This paper proposes a balanced decision tree based heuristic to efficiently design linear decompositions for index generation functions. The proposed heuristic finds a good linear decomposition of an index generation function by using appropriate cost functions and a constraint to construct a balanced tree. Since the proposed heuristic is fast and requires a small amount of memory, it is applicable even to large index generation functions that cannot be solved in a reasonable time by existing heuristics. This paper shows time and space complexities of the proposed heuristic, and experimental results using some large examples to show its efficiency.

• 出版日期2017-8