Article

Compatible observability don't cares revisited

Author:

R. K. BraytonAuthors Info & Claims

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

Pages 618 - 623

Published: 04 November 2001 Publication History

Get Access

Abstract

CODCs stand for compatible observability don't cares. We first examine the definition of compatibility and when a set of CODCs is compatible. We then discuss Savoj's CODC computation for propagating CODCs from a node's output to its fanins, and show by example, that the results can depend on the current implementation of the node. Then we generalize the computation so that the result is independent of the implementation at the node. The CODCs propagated by this computation are proved to be maximal in some sense. Local don't cares (LDCs) are CODCs of a node, pre-imaged to the primary inputs and then imaged and projected to the local fanins of the node. LDCs combine CODCs with SDCs (satisfiability don't cares), but only the CODC part is propagated to the fanin network. Another form of local don't cares, propagates both the CODC and SDC parts to the fanin network. Both are shown to be compatible in some sense, but conservative. We give a method for updating both kinds of local don't cares incrementally when other nodes in the network are changed.

References

[1]

S. Muroga, Y. Kambayashi, H. C. Lai, and J. N. Culliney, "The Transduction Method - Design of Logic Networks Based on Permissible Functions," in IEEE Trans. Computers, Oct. 1989.

Digital Library

Google Scholar

[2]

H. Savoj and R. K. Brayton, "The Use of Observability and External Don't Cares for the Simplification of Multi-Level Networks," in Proc. of the Design Automation Conf., pp. 297-301, June 1990.

Digital Library

Google Scholar

[3]

E. M. Sentovich, K. J. Singh, C. Moon, H. Savoj, R. K. Brayton, and A. L. Sangiovanni-Vincentelli, "Sequential Circuit Design Using Synthesis and Optimization," in Proc. of the Intl. Conf. on Computer Design, pp. 328-333, Oct. 1992.

Digital Library

Google Scholar

[4]

Y. Watanabe and R. K. Brayton, "The Maximum Set of Permissible Behaviors for FSM Networks," in Proc. of the Intl. Conf. on Computer-Aided Design, 1993.

Digital Library

Google Scholar

[5]

Y. Watanabe, L. Guerra, and R. K. Brayton, "Logic optimization with multi-output gates," in Proceedings of the International Conference Computers and Devices, Sept. 1993.

Google Scholar

[6]

S. Yamashita, H. Sawada, and A. Nagoya, "A new method to express functional permissibilities for LUT based FPGAs and its applications," in Proceedings of the International Conference on Computer-Aided Design, pp. 254-61, Nov 1996.

Digital Library

Google Scholar

[7]

R. Brayton, "Understanding SPFDs: A new method for specifying flexibility," in Workshop Notes, International Workshop on Logic Synthesis, (Tahoe City, CA), May 1997.

Google Scholar

[8]

S. Sinha and R. Brayton, "Implementation and use of SPFDs in optimizing boolean networks," in Proceedings of the International Conference on Computer-Aided Design, pp. 103-10, Nov 1998.

Digital Library

Google Scholar

[9]

S. Khatri, S. Sinha, A. Kuehlmann, R. Brayton, and A. Sangiovanni-Vincentelli, "SPFD based wire removal in a network of PLAs," in Workshop Notes, International Workshop on Logic Synthesis, (Tahoe City, CA), May 1999.

Google Scholar

[10]

S. Sinha and R. K. Brayton, "Robust and efficient spfd computations," in IWLS, June 2001.

Google Scholar

Cited By

View all

Lam TYang STang WWu YBahar RLombardi FAtienza DBrunvand E(2010)Logic synthesis for low power using clock gating and rewiringProceedings of the 20th symposium on Great lakes symposium on VLSI10.1145/1785481.1785527(179-184)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.1145/1785481.1785527
Cobb JGulati KKhatri SLombardi FBhanja SMassoud YBahar R(2009)Robust window-based multi-node technology-independent logic minimizationProceedings of the 19th ACM Great Lakes symposium on VLSI10.1145/1531542.1531623(357-362)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.1145/1531542.1531623
Zhu QKitchen NKuehlmann ASangiovanni-Vincentelli ASentovich E(2006)SAT sweeping with local observability don't-caresProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1146970(229-234)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1146970
Show More Cited By

Index Terms

Compatible observability don't cares revisited

Recommendations

A robust algorithm for approximate compatible observability don't care (CODC) computation
DAC '04: Proceedings of the 41st annual Design Automation Conference

Compatible Observability Don't Cares (CODCs) are a powerful means to express the flexibility present at a node in a multi-level logic network. Despite their elegance, the applicability of CODCs has been hampered by their computational complexity. The ...
Polarized observability don't cares
ICCAD '96: Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

A new method is presented to compute the exact observability don't cares (ODC} for multilevel combinational circuits. A new mathematical concept, called polarization, is introduced. Polarization captures the essence of ODC calculation on the otherwise ...
Don't cares in multi-level network optimization

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ICCAD '01: Proceedings of the 2001 IEEE/ACM international conference on Computer-aided design

November 2001

656 pages

ISBN:0780372492

Conference Chair:
Rolf Ernst
Tech. Univ. of Braunschweig, Braunschweig, Germany

Publisher

IEEE Press

Publication History

Published: 04 November 2001

Check for updates

Qualifiers

Article

Conference

ICCAD01

Sponsor:

SIGDA

ICCAD01: International Conference on Computer Aided Design

November 4 - 8, 2001

California, San Jose

Acceptance Rates

Overall Acceptance Rate 457 of 1,762 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
168
Total Downloads

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

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Lam TYang STang WWu YBahar RLombardi FAtienza DBrunvand E(2010)Logic synthesis for low power using clock gating and rewiringProceedings of the 20th symposium on Great lakes symposium on VLSI10.1145/1785481.1785527(179-184)Online publication date: 16-May-2010
https://dl.acm.org/doi/10.1145/1785481.1785527
Cobb JGulati KKhatri SLombardi FBhanja SMassoud YBahar R(2009)Robust window-based multi-node technology-independent logic minimizationProceedings of the 19th ACM Great Lakes symposium on VLSI10.1145/1531542.1531623(357-362)Online publication date: 10-May-2009
https://dl.acm.org/doi/10.1145/1531542.1531623
Zhu QKitchen NKuehlmann ASangiovanni-Vincentelli ASentovich E(2006)SAT sweeping with local observability don't-caresProceedings of the 43rd annual Design Automation Conference10.1145/1146909.1146970(229-234)Online publication date: 24-Jul-2006
https://dl.acm.org/doi/10.1145/1146909.1146970
Saluja NKhatri SMalik SFix LKahng A(2004)A robust algorithm for approximate compatible observability don't care (CODC) computationProceedings of the 41st annual Design Automation Conference10.1145/996566.996688(422-427)Online publication date: 7-Jun-2004
https://dl.acm.org/doi/10.1145/996566.996688
Wang HBrayton RRudell R(1995)Multi-level logic optimization of FSM networksProceedings of the 1995 IEEE/ACM international conference on Computer-aided design10.5555/224841.225156(728-735)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.5555/224841.225156
Wang HBrayton RLorenzetti M(1994)Permissible observability relations in FSM networksProceedings of the 31st annual Design Automation Conference10.1145/196244.196613(677-683)Online publication date: 6-Jun-1994
https://dl.acm.org/doi/10.1145/196244.196613

View Options

Login options

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

Cited By

Index Terms

Recommendations

A robust algorithm for approximate compatible observability don't care (CODC) computation

Polarized observability don't cares

Don't cares in multi-level network optimization