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

Shinobu NAGAYAMA  Tsutomu SASAO  Jon T. BUTLER  

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
index generation functions,  linear decomposition,  incompletely specified functions,  balanced decision tree,  content-addressable memory,  logic design,  heuristic,  

Full Text: PDF(694.2KB)>>
Buy this Article

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.

open access publishing via