The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
BDD(이진 결정 다이어그램)는 부울 함수를 그래프로 표현한 것입니다. 특히, Obdd(순서형 BDD)는 표준 표현을 제공하고 효율적으로 조작되므로 많은 상황에서 유용합니다. OBDD를 자동으로 생성하는 BDD 패키지가 개발되어 정형검증, 논리합성 등 논리설계 분야에서 널리 사용되고 있다. 패스 트랜지스터 회로의 합성은 BDD 패키지의 성공적인 응용 중 하나입니다. 패스 트랜지스터 회로는 각 노드를 89개 또는 32개의 패스 트랜지스터로 구성된 선택기에 매핑하여 BDD에서 생성됩니다. 더 작은 BDD에서 회로를 생성하는 경우 생성된 회로는 더 적은 수의 트랜지스터를 가지므로 칩 면적과 전력 소비가 절약됩니다. 본 논문에서는 경로의 가변 순서 및 가변 출현 횟수에 제한이 없는 보다 일반적인 BDD를 GBDD(Generic BDD)라고 하며, 패스 트랜지스터 회로의 합성을 목적으로 GBDD를 생성하는 알고리즘을 제안합니다. 제안하는 알고리즘은 두 단계로 구성된다. 첫 번째 단계에서는 주어진 부울 공식에 대한 구문 분석 트리(PT)가 생성됩니다. 여기서 PT는 부울 공식의 방향성 트리 표현이며 리터럴 노드와 작업 노드로 구성됩니다. 이 단계에서 우리의 알고리즘은 PT의 리터럴 노드 수를 줄이려고 시도합니다. 두 번째 단계에서는 Concatenation Method를 사용하여 PT에 대해 GBDD를 생성하는데, Concatenation Method는 GBDD를 수직으로 연결하여 GBDD를 생성한다. 이 단계에서 우리의 알고리즘은 동형 하위 그래프를 공유하려고 시도합니다. ISCAS'680 및 MCNC 벤치마크 회로에 대한 실험에서 우리 프로그램은 4개의 단일 출력 기능 중 49개의 GBDD를 성공적으로 생성했으며 크기가 크기가 OBDD보다 작은 23.1개의 다중 출력 기능 중 XNUMX개의 GBDD를 성공적으로 생성했습니다. 최적의 경우 GBDD 크기는 OBDD에 비해 XNUMX% 감소합니다.
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.
부
Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA, "An Algorithm for Generating Generic BDDs" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 12, pp. 2505-2512, December 2000, doi: .
Abstract: Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_12_2505/_p
부
@ARTICLE{e83-a_12_2505,
author={Tetsushi KATAYAMA, Hiroyuki OCHI, Takao TSUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Algorithm for Generating Generic BDDs},
year={2000},
volume={E83-A},
number={12},
pages={2505-2512},
abstract={Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.},
keywords={},
doi={},
ISSN={},
month={December},}
부
TY - JOUR
TI - An Algorithm for Generating Generic BDDs
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2505
EP - 2512
AU - Tetsushi KATAYAMA
AU - Hiroyuki OCHI
AU - Takao TSUDA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2000
AB - Binary Decision Diagrams (BDDs) are graph representation of Boolean functions. In particular, Ordered BDDs (OBDDs) are useful in many situations, because they provide canonical representation and they are manipulated efficiently. BDD packages which automatically generate OBDDs have been developed, and they are now widely used in logic design area, including formal verification and logic synthesis. Synthesis of pass-transistor circuits is one of successful applications of such BDD packages. Pass-transistor circuits are generated from BDDs by mapping each node to a selector which consists of two or four pass transistors. If circuits are generated from smaller BDDs, generated circuits have smaller number of transistors and hence save chip area and power consumption. In this paper, more generic BDDs which have no restrictions in variable ordering and variable appearance count on its paths are called Generic BDDs (GBDDs), and an algorithm for generating GBDDs is proposed for the purpose of synthesis of pass-transistor circuits. The proposed algorithm consists of two steps. At the first step, parse trees (PTs) for given Boolean formulas are generated, where a PT is a directed tree representation of Boolean formula(s) and it consists of literal nodes and operation nodes. In this step, our algorithm attempts to reduce the number of literal nodes of PTs. At the second step, a GBDD is generated for the PTs using Concatenation Method, where Concatenation Method generates a GBDD by connecting GBDDs vertically. In this step, our algorithm attempts to share isomorphic subgraphs. In experiments on ISCAS'89 and MCNC benchmark circuits, our program successfully generated 32 GBDDs out of 680 single-output functions and 4 GBDDs out of 49 multi-output functions whose sizes are smaller than OBDDs. GBDD size is reduced by 23.1% in the best case compared with OBDD.
ER -