Benchmark circuit complexity validation using binary decision diagram characteristics
It has been shown that when Binary Decision Diagrams (BDDs) are formed from uniformly distributed random Boolean Functions (BFs), the average number of nodes in the BDDs is in a simple relation to the number of variables and terms in the BFs. In the present work, the node counts for BBDs formed from...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Published: |
2006
|
| Subjects: | |
| Online Access: | http://shdl.mmu.edu.my/2140/ |
| _version_ | 1848789973942140928 |
|---|---|
| author | Mills,, Bruce Prasad,, P. W. C Prasad,, V. C. |
| author_facet | Mills,, Bruce Prasad,, P. W. C Prasad,, V. C. |
| author_sort | Mills,, Bruce |
| building | MMU Institutional Repository |
| collection | Online Access |
| description | It has been shown that when Binary Decision Diagrams (BDDs) are formed from uniformly distributed random Boolean Functions (BFs), the average number of nodes in the BDDs is in a simple relation to the number of variables and terms in the BFs. In the present work, the node counts for BBDs formed from ISCAS benchmark circuits are examined and compared to the results for random BFs. The model for random BFs is shown to have strong descriptive power for the benchmark data. Therefore, the model is promoted as a method of predicting, for a given BF, circuit complexity measures such as the area of a VLSI implementation. |
| first_indexed | 2025-11-14T18:05:14Z |
| format | Article |
| id | mmu-2140 |
| institution | Multimedia University |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:05:14Z |
| publishDate | 2006 |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | mmu-21402011-09-21T08:13:25Z http://shdl.mmu.edu.my/2140/ Benchmark circuit complexity validation using binary decision diagram characteristics Mills,, Bruce Prasad,, P. W. C Prasad,, V. C. QA75.5-76.95 Electronic computers. Computer science It has been shown that when Binary Decision Diagrams (BDDs) are formed from uniformly distributed random Boolean Functions (BFs), the average number of nodes in the BDDs is in a simple relation to the number of variables and terms in the BFs. In the present work, the node counts for BBDs formed from ISCAS benchmark circuits are examined and compared to the results for random BFs. The model for random BFs is shown to have strong descriptive power for the benchmark data. Therefore, the model is promoted as a method of predicting, for a given BF, circuit complexity measures such as the area of a VLSI implementation. 2006 Article NonPeerReviewed Mills,, Bruce and Prasad,, P. W. C and Prasad,, V. C. (2006) Benchmark circuit complexity validation using binary decision diagram characteristics. Benchmark circuit complexity validation using binary decision diagram characteristics. pp. 462-466. |
| spellingShingle | QA75.5-76.95 Electronic computers. Computer science Mills,, Bruce Prasad,, P. W. C Prasad,, V. C. Benchmark circuit complexity validation using binary decision diagram characteristics |
| title | Benchmark circuit complexity validation using binary decision diagram characteristics |
| title_full | Benchmark circuit complexity validation using binary decision diagram characteristics |
| title_fullStr | Benchmark circuit complexity validation using binary decision diagram characteristics |
| title_full_unstemmed | Benchmark circuit complexity validation using binary decision diagram characteristics |
| title_short | Benchmark circuit complexity validation using binary decision diagram characteristics |
| title_sort | benchmark circuit complexity validation using binary decision diagram characteristics |
| topic | QA75.5-76.95 Electronic computers. Computer science |
| url | http://shdl.mmu.edu.my/2140/ |