Summary
|
For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE. |
|
A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions Shinobu NAGAYAMA Tsutomu SASAO Jon T. BUTLER Publication IEICE TRANSACTIONS on Information and Systems Vol.E100-D No.8 pp.1583-1591 Publication Date: 2017/08/01 Publicized: 2017/05/19 Online ISSN: 1745-1361 DOI: 10.1587/transinf.2016LOP0013 Type of Manuscript: Special Section PAPER (Special Section on Multiple-Valued Logic and VLSI Computing) Category: Logic Design Keyword: index generation functions, linear decomposition, incompletely specified functions, balanced decision tree, content-addressable memory, logic design, heuristic, Full Text: PDF(694.2KB)>>
Summary: 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. | ||||||||||
| ||||||||||
