More Web Proxy on the site http://driver.im/

Article

Synthesis of irregular combinational functions with large don't care sets

Authors:

H.-J. Wunderlich,

R. D. Mascarenhas,

M. GarbersAuthors Info & Claims

GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI

Pages 287 - 292

https://doi.org/10.1145/1228784.1228856

Published: 11 March 2007 Publication History

Abstract

A special logic synthesis problem is considered for Booleanfunctions which have large don't care sets and are irregular. Here, a function is considered as irregular if the input assignmentsmapped to specified values ('1' or '0') are randomly spread overthe definition space. Such functions can be encountered in the field of design for test. The proposed method uses ordered BDDs forlogic manipulations and generates free BDD-like covers. For the considered benchmark functions, implementations were found witha significant reduction of the node/gate count as compared to SISor to methods offered by a state-of-the-art BDD package.

References

[1]

S.B. Akers "Binary Decision Diagrams," Trans. on Computers, Vol. C-27, No. 6, 1978, 509--516.

[2]

B. Becker "Synthesis For Testability: Binary Decision Diagrams," STACS. LNCS, Vol. 577, Springer Verlag, 1992, 501--512.

Digital Library

[3]

R.K. Brayton et al. "MIS: A Multiple-Level Logic Optimization System," Trans. on CAD, 1987, 1062--1081.

[4]

R.K. Brayton et al. "Logic Minimization Algorithms for VLSI Synthesis," Kluver Academic Publishers, 1997.

Digital Library

[5]

R.E. Bryant "Graph-Based Algorithms for Boolean Function Manipulation," Trans. on Computers, Vol. C-35, No. 8, 1986, 677--691.

Digital Library

[6]

R.E. Bryant "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication," Trans. on Computers, Vol. 40, No. 2, 1991, 205--213.

Digital Library

[7]

S.-C. Chang et al. "Minimizing ROBDD Size of Incompletely Specified Multiple Output Functions," European Design and Test Conference, 1994, 620--624.

[8]

O. Coudert et al. "Verification of Sequential Machines using Boolean Functional Vectors," IFIP International Workshop on Applied Formal Methods for Correct VLSI Design, 1989, 111--128.

[9]

O. Coudert, J. Madre "Verification of Synchronous Sequential Machines Based on Symbolic Execution," Automatic Verification Methods for Finite State Systems, Springer-Verlag, 1990, 365--373.

Digital Library

[10]

V. Gherman et al. "Efficient Pattern Mapping for Deterministic Logic BIST," Int. Test Conference, 2004, pp. 48--56.

Digital Library

[11]

W. Günther, R. Drechsler "Minimization of Free BDDs," INTEGRATION, The VLSI Journal, 32 (1--2), Nov. 2002, 41--59.

Digital Library

[12]

J. Hlavicka, P. Fiser "BOOM - a Heuristic Boolean Minimizer," Int. Conference on Computer Aided Design, 2001, pp. 439--442.

Digital Library

[13]

Y. Hong et al. "Sibling-Substitution-Based BDD Minimization using Don't Cares," Trans. on CAD of Integrated Circuits and Systems, 2000, pp. 44--55.

Digital Library

[14]

B. Koenemann et al. "A SmartBIST Variant with Guaranteed Encoding," Asian Test Symposium, 2001, 325--300.

Digital Library

[15]

R. Michalski "On the Quasi-Minimal Solution of the General Covering Problem," Int. Symposium on Information Processing (FCIP 69) (Switching Circuits), Vol. A3, 1969, 125--128.

[16]

S. Minato "Binary Decision Diagrams and Applications For VLSI Computer-Aided Design," Kluver Academic Publishers, 1997.

Digital Library

[17]

A.L. Oliveira et al. "Exact Minimization of Binary Decision Diagrams using Implicit Techniques," Trans. on Computers, Vol. 47, No. 11, 1998, 1282--1296.

Digital Library

[18]

S. Panda et al. "Symmetry Detection and Dynamic Variable Ordering of Decision Diagrams," Int. Conference on Computer-Aided Design, San Jose, CA, 1994, 628--631.

Digital Library

[19]

J. Rajski et al. "Embedded deterministic test for low cost manufacturing test," Int. Test Conf., 2002, 301--310.

Digital Library

[20]

M. Sauerhoff et al. "On the Complexity of Minimizing the OBDD Size for Incompletely Specified Functions," Trans. on CAD of Integrated Circuits and Systems, Vol. 15, 1996, 1435--1437.

Digital Library

[21]

C. Scholl et al. "BDD Minimization using Symmetries," Trans. on CAD of Integrated Circuits and Systems, Vol. 18, No 2, 1999, 81--100.

Digital Library

[22]

E. Sentovich et al. "Sequential Circuit Design Using Synthesis and Optimization," ICCD, 1992, 328--333.

Digital Library

[23]

T. Shiple et al. "Heuristic Minimization of BDDs Using Don't Cares," Design Automation Conference, 1994, 225--231.

Digital Library

[24]

D. Sieling, I. Wegener "Graph Driven BDDs - a New Data Structure for Boolean Functions," Theoretical Computer Science, Vol. 141, No.1--2, 1995, 283--310.

Digital Library

[25]

Y. Tang et al. "X-Masking during Logic BIST and its Impact on Defect Coverage," Int. Test Conference, 2004, 442--451.

Digital Library

[26]

N.A. Touba, E.J. McCluskey "Altering a Pseudo-random Bit Sequence for Scan-Based BIST," Int. Test Conf., 1996, 167--175.

Digital Library

[27]

http://vlsi.colorado.edu/~fabio/CUDD/cuddIntro.html

[28]

http://www.ra.informatik.unistuttgart.de/~ghermanv/benchmarks/index.phtml

Cited By

Gherman VLaffond C(2024)Sequential Decoders for Binary Linear Block ECCs2024 IEEE 42nd VLSI Test Symposium (VTS)10.1109/VTS60656.2024.10538823(1-5)Online publication date: 22-Apr-2024
https://doi.org/10.1109/VTS60656.2024.10538823
Kochte MZoellin CWunderlich H(2010)Efficient Concurrent Self-Test with Partially Specified PatternsJournal of Electronic Testing: Theory and Applications10.1007/s10836-010-5167-626:5(581-594)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s10836-010-5167-6

Index Terms

Synthesis of irregular combinational functions with large don't care sets
1. Hardware
  1. Electronic design automation
    1. High-level and register-transfer level synthesis
    2. Logic synthesis
      1. Circuit optimization

Recommendations

The synthesis of cyclic combinational circuits
DAC '03: Proceedings of the 40th annual Design Automation Conference

Digital circuits are called combinational if they are memoryless: they have outputs that depend only on the current values of the inputs. Combinational circuits are generally thought of as acyclic (i.e., feed-forward) structures. And yet, cyclic ...
Synthesis of the optimal 4-bit reversible circuits
DAC '10: Proceedings of the 47th Design Automation Conference

Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a ...
Systematic synthesis of approximate adders and multipliers with accurate error calculations
Abstract
In this study, we perform logic synthesis and area optimization of approximate ripple-carry adders and Wallace-tree multipliers with a given error constraint. We first implement approximate 1-bit adders having different error rates as ...
Highlights
- Logic synthesis and area optimization of approximate ripple-carry adders and Wallace-tree multipliers is presented.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI

March 2007

626 pages

ISBN:9781595936059

DOI:10.1145/1228784

General Chairs:
Hai Zhou
Northwestern University
,
Enrico Macii
Politecnico di Torino
,
Program Chairs:
Zhiyuan Yan
Lehigh University
,
Yehia Massoud
Rice University

Copyright © 2007 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

GLSVLSI07

Sponsor:

GLSVLSI07: Great Lakes Symposium on VLSI 2007

March 11 - 13, 2007

Stresa-Lago Maggiore, Italy

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
131
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gherman VLaffond C(2024)Sequential Decoders for Binary Linear Block ECCs2024 IEEE 42nd VLSI Test Symposium (VTS)10.1109/VTS60656.2024.10538823(1-5)Online publication date: 22-Apr-2024
https://doi.org/10.1109/VTS60656.2024.10538823
Kochte MZoellin CWunderlich H(2010)Efficient Concurrent Self-Test with Partially Specified PatternsJournal of Electronic Testing: Theory and Applications10.1007/s10836-010-5167-626:5(581-594)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s10836-010-5167-6

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents