C-element

Delays in the naive (based on Earle latch) implementation and environment
Timing diagram of a C-element and inclusive OR gate
Behavior of the environment with multiple input transitions [1] (garbage branches [2]) admissible for C-element and inadmissible for Join element

In digital computing, the Muller C-element (C-gate, hysteresis flip-flop, coincident flip-flop, or two-hand safety circuit) is a small binary logic circuit widely used in design of asynchronous circuits and systems. It outputs 0 when all inputs are 0, it outputs 1 when all inputs are 1, and it retains its output state otherwise. It was specified formally in 1955 by David E. Muller[3] and first used in ILLIAC II computer.[4] In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by a Hasse diagram.[5][6][7][8] The C-element is closely related to the rendezvous[9] and join[10] elements, where an input is not allowed to change twice in succession. In some cases, when relations between delays are known, the C-element can be realized as a sum-of-product (SOP) circuit.[11][12] Earlier techniques for implementing the C-element[13][14] include Schmitt trigger,[15] Eccles-Jordan flip-flop and last moving point flip-flop.

  1. ^ Kimura, Izumi (1971). "Extensions of asynchronous circuits and the delay problem. Part II: Spike-free extensions and the delay problem of the second kind". Journal of Computer and System Sciences. 5 (2): 129–162. doi:10.1016/S0022-0000(71)80031-4.
  2. ^ Kushnerov, Alex; Bystrov, Sergey (2023). "Signal Transition Graphs for Asynchronous Data Path Circuits". Modeling and Analysis of Information Systems. 30 (2): 170–186. doi:10.18255/1818-1015-2023-2-170-186.
  3. ^ D. E. Muller, Theory of asynchronous circuits. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.
  4. ^ H. C. Breadley, "ILLIAC II — A short description and annotated bibliography", IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 399–403, 1965.
  5. ^ D. E. Muller and W. S. Bartky, "A theory of asynchronous circuits", Int. Symposium on the Switching Theory in Harvard University, pp. 204–243, 1959.
  6. ^ W. J. Poppelbaum, Introduction to the Theory of Digital Machines. Math., E.E. 294 Lecture Notes, University of Illinois at Urbana-Champaign.
  7. ^ Kimura, Izumi (1969). "A comparison between two mathematical models of asynchronous circuits". Science Reports of the Tokyo Kyoiku Daigaku, Section A. 10 (232/248): 109–123. JSTOR 43698723.
  8. ^ Gunawardena, Jeremy (1993). "A generalized event structure for the Muller unfolding of a safe net". Concur'93. Lecture Notes in Computer Science. Vol. 715. pp. 278–292. doi:10.1007/3-540-57208-2_20. ISBN 978-3-540-57208-4.
  9. ^ Stucki, Mishell J.; Ornstein, Severo M.; Clark, Wesley A. (1967). "Logical design of macromodules". Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring). pp. 357–364. doi:10.1145/1465482.1465538. ISBN 978-1-4503-7895-6.
  10. ^ J. C. Ebergen, J. Segers, I. Benko, "Parallel Program and Asynchronous Circuit Design", Workshops in Computing, pp. 50–103, 1995.
  11. ^ Beerel, Peter A.; Burch, Jerry R.; Meng, Teresa H. (1998). "Checking Combinational Equivalence of Speed-Independent Circuits". Formal Methods in System Design. 13 (1): 37–85. doi:10.1023/A:1008666605437.
  12. ^ H. Park, A. He, M. Roncken and X. Song, "Semi-modular delay model revisited in context of relative timing", IET Electronics Letters, vol. 51, no. 4, pp. 332–334, 2015.
  13. ^ Technical Progress Report, Jan. 1959, University of Illinois at Urbana-Champaign.
  14. ^ W . J. Poppellbaum, N. E. Wiseman, "Circuit design for the new Illinois computer", Report no. 90, University of Illinois at Urbana-Champaign, 1959.
  15. ^ N. P. Singh, A design methodology for self-timed systems. MSc thesis, MIT, 1981, 98 p.