IEICE TRANSACTIONS on Fundamentals
A New Preprocessing Method for Efficient Construction of Decision Diagrams
Summary :
Many discrete functions are often compactly represented by Decision Diagrams (DD). The main problem in the construction of decision diagrams is the space and time requirements. While constructing a decision diagram the memory requirement may grow exponentially with the function. Also, large numbers of temporary nodes are created while constructing the decision diagram for a function. Here the problem of reducing the number of temporary nodes is addressed with respect to the PLA specification format of a function, where the function is represented using a set of cubes. Usually a DD is constructed by recursively processing the input cubes in the PLA specification. The DD, representing a sub function, is specified by a single cube. This DD is merged with a master DD, which represents the entire previously processed cubes. Thus the master DD is constructed recursively, until all the cubes in the input cube set are processed. In this paper, an efficient method is proposed, which reorders and also partitions the cube set into unequal number of cubes per subset, in such a way that, the number of temporary nodes created and the number of logical operations done, during the merging of cubes with the master DD are reduced. This results in the reduction of space and time required for the construction of DDs to a remarkable extent.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.2 pp.624-631
- Publication Date
- 2014/02/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1587/transfun.E97.A.624
- Type of Manuscript
- PAPER
- Category
- Algorithms and Data Structures
Authors
S. R. MALATHI
Sri Venkateswara College of Engineering
P. SAKTHIVEL
Anna University
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
S. R. MALATHI, P. SAKTHIVEL, "A New Preprocessing Method for Efficient Construction of Decision Diagrams" in IEICE TRANSACTIONS on Fundamentals,
vol. E97-A, no. 2, pp. 624-631, February 2014, doi: 10.1587/transfun.E97.A.624.
Abstract: Many discrete functions are often compactly represented by Decision Diagrams (DD). The main problem in the construction of decision diagrams is the space and time requirements. While constructing a decision diagram the memory requirement may grow exponentially with the function. Also, large numbers of temporary nodes are created while constructing the decision diagram for a function. Here the problem of reducing the number of temporary nodes is addressed with respect to the PLA specification format of a function, where the function is represented using a set of cubes. Usually a DD is constructed by recursively processing the input cubes in the PLA specification. The DD, representing a sub function, is specified by a single cube. This DD is merged with a master DD, which represents the entire previously processed cubes. Thus the master DD is constructed recursively, until all the cubes in the input cube set are processed. In this paper, an efficient method is proposed, which reorders and also partitions the cube set into unequal number of cubes per subset, in such a way that, the number of temporary nodes created and the number of logical operations done, during the merging of cubes with the master DD are reduced. This results in the reduction of space and time required for the construction of DDs to a remarkable extent.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.624/_p
Copy
@ARTICLE{e97-a_2_624,
author={S. R. MALATHI, P. SAKTHIVEL, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A New Preprocessing Method for Efficient Construction of Decision Diagrams},
year={2014},
volume={E97-A},
number={2},
pages={624-631},
abstract={Many discrete functions are often compactly represented by Decision Diagrams (DD). The main problem in the construction of decision diagrams is the space and time requirements. While constructing a decision diagram the memory requirement may grow exponentially with the function. Also, large numbers of temporary nodes are created while constructing the decision diagram for a function. Here the problem of reducing the number of temporary nodes is addressed with respect to the PLA specification format of a function, where the function is represented using a set of cubes. Usually a DD is constructed by recursively processing the input cubes in the PLA specification. The DD, representing a sub function, is specified by a single cube. This DD is merged with a master DD, which represents the entire previously processed cubes. Thus the master DD is constructed recursively, until all the cubes in the input cube set are processed. In this paper, an efficient method is proposed, which reorders and also partitions the cube set into unequal number of cubes per subset, in such a way that, the number of temporary nodes created and the number of logical operations done, during the merging of cubes with the master DD are reduced. This results in the reduction of space and time required for the construction of DDs to a remarkable extent.},
keywords={},
doi={10.1587/transfun.E97.A.624},
ISSN={1745-1337},
month={February},}
Copy
TY - JOUR
TI - A New Preprocessing Method for Efficient Construction of Decision Diagrams
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 624
EP - 631
AU - S. R. MALATHI
AU - P. SAKTHIVEL
PY - 2014
DO - 10.1587/transfun.E97.A.624
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2014
AB - Many discrete functions are often compactly represented by Decision Diagrams (DD). The main problem in the construction of decision diagrams is the space and time requirements. While constructing a decision diagram the memory requirement may grow exponentially with the function. Also, large numbers of temporary nodes are created while constructing the decision diagram for a function. Here the problem of reducing the number of temporary nodes is addressed with respect to the PLA specification format of a function, where the function is represented using a set of cubes. Usually a DD is constructed by recursively processing the input cubes in the PLA specification. The DD, representing a sub function, is specified by a single cube. This DD is merged with a master DD, which represents the entire previously processed cubes. Thus the master DD is constructed recursively, until all the cubes in the input cube set are processed. In this paper, an efficient method is proposed, which reorders and also partitions the cube set into unequal number of cubes per subset, in such a way that, the number of temporary nodes created and the number of logical operations done, during the merging of cubes with the master DD are reduced. This results in the reduction of space and time required for the construction of DDs to a remarkable extent.
ER -
English
