IEICE TRANSACTIONS on Information
A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions
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.
- Publication
- IEICE TRANSACTIONS on Information 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
Authors
Shinobu NAGAYAMA
Hiroshima City University
Tsutomu SASAO
Meiji University
Jon T. BUTLER
Naval Postgraduate School
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, "A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions" in IEICE TRANSACTIONS on Information,
vol. E100-D, no. 8, pp. 1583-1591, August 2017, doi: 10.1587/transinf.2016LOP0013.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2016LOP0013/_p
Copy
@ARTICLE{e100-d_8_1583,
author={Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, },
journal={IEICE TRANSACTIONS on Information},
title={A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions},
year={2017},
volume={E100-D},
number={8},
pages={1583-1591},
abstract={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.},
keywords={},
doi={10.1587/transinf.2016LOP0013},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Balanced Decision Tree Based Heuristic for Linear Decomposition of Index Generation Functions
T2 - IEICE TRANSACTIONS on Information
SP - 1583
EP - 1591
AU - Shinobu NAGAYAMA
AU - Tsutomu SASAO
AU - Jon T. BUTLER
PY - 2017
DO - 10.1587/transinf.2016LOP0013
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E100-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2017
AB - 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.
ER -
English
