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

• NAGAYAMA Shinobu

  Department of Computer and Network Engineering, Hiroshima City University

• SASAO Tsutomu

  Department of Computer Science, Meiji University

• T. BUTLER Jon

  Department of Electrical and Computer Engineering, Naval Postgraduate School

抄録

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.

収録刊行物

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E100.D (8), 1583-1591, 2017

  一般社団法人 電子情報通信学会

キーワード

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

詳細情報

• CRID: 1390001204377412608
• NII論文ID: 130005876136
• DOI: 10.1587/transinf.2016lop0013
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E100.D/8/E100.D_2016LOP0013/_pdf
• 本文言語コード: en
• データソース種別:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• 抄録ライセンスフラグ: 使用不可