This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.
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.
Copy
Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, "A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams" in IEICE TRANSACTIONS on Information,
vol. E93-D, no. 8, pp. 2059-2067, August 2010, doi: 10.1587/transinf.E93.D.2059.
Abstract: This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E93.D.2059/_p
Copy
@ARTICLE{e93-d_8_2059,
author={Shinobu NAGAYAMA, Tsutomu SASAO, Jon T. BUTLER, },
journal={IEICE TRANSACTIONS on Information},
title={A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams},
year={2010},
volume={E93-D},
number={8},
pages={2059-2067},
abstract={This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.},
keywords={},
doi={10.1587/transinf.E93.D.2059},
ISSN={1745-1361},
month={August},}
Copy
TY - JOUR
TI - A Systematic Design Method for Two-Variable Numeric Function Generators Using Multiple-Valued Decision Diagrams
T2 - IEICE TRANSACTIONS on Information
SP - 2059
EP - 2067
AU - Shinobu NAGAYAMA
AU - Tsutomu SASAO
AU - Jon T. BUTLER
PY - 2010
DO - 10.1587/transinf.E93.D.2059
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E93-D
IS - 8
JA - IEICE TRANSACTIONS on Information
Y1 - August 2010
AB - This paper proposes a high-speed architecture to realize two-variable numeric functions. It represents the given function as an edge-valued multiple-valued decision diagram (EVMDD), and shows a systematic design method based on the EVMDD. To achieve a design, we characterize a numeric function f by the values of l and p for which f is an l-restricted Mp-monotone increasing function. Here, l is a measure of subfunctions of f and p is a measure of the rate at which f increases with an increase in the dependent variable. For the special case of an EVMDD, the EVBDD, we show an upper bound on the number of nodes needed to realize an l-restricted Mp-monotone increasing function. Experimental results show that all of the two-variable numeric functions considered in this paper can be converted into an l-restricted Mp-monotone increasing function with p=1 or 3. Thus, they can be compactly realized by EVBDDs. Since EVMDDs have shorter paths and smaller memory size than EVBDDs, EVMDDs can produce fast and compact NFGs.
ER -