Four-valued reasoning and cyclic circuits

Graeme Gange, Benjamin Horsfall, Lee Naish, Harald Søndergaard

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

Allowing cycles in a logic circuit can be advantageous, for example, by reducing the number of gates required to implement a given Boolean function, or a set of functions. However, a cyclic circuit may easily be ill behaved. For instance, it may have some output wire oscillation instead of reaching a steady state. Propositional three-valued logic has long been used in tests for good behavior of cyclic circuits; a symbolic evaluation method known as ternary analysis provides one criterion for good behavior under certain assumptions about wire and gate delay. We revisit ternary analysis and argue for the use of four truth values. The fourth truth value allows for the distinction of undefined and underspecified behavior. Ability to under specify behavior is useful, because, in a quest for smaller circuits, an implementor can capitalize on degrees of freedom offered in the specification. Moreover, a fourth truth value is attractive because, rather than complicating (ternary) circuit analysis, it introduces a pleasant symmetry, in the form of contra-duality, as well as providing a convenient framework for manipulating specifications. We use this symmetry to provide fixed point results that clarify how two-, three-, and four-valued analyses are related, and to explain some observations about ternary analysis.

Original languageEnglish
Article number6835151
Pages (from-to)1003-1016
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume33
Issue number7
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Boolean functions
  • circuit optimization
  • combinational circuits
  • multivalued logic

Cite this