C-element: Difference between revisions

Revision as of 23:35, 6 April 2025

Revision as of 08:25, 9 June 2025

Line 2:

[[Image:Delay assumptions.png|thumb|upright=1.5|Delays in the naive (based on [[Earle latch]]) implementation and environment]]

[[Image:Timing diagram of inclusive OR.png|thumb|upright=1.5|Timing diagram of a C-element and inclusive OR gate]]

[[Image:Join_element_stg.png|thumb|upright=1.5|Behavior of the environment with multiple input transitions <ref name="Kim71">{{cite journal | url=https://www.sciencedirect.com/science/article/pii/S0022000071800314 | doi=10.1016/S0022-0000(71)80031-4 | title=Extensions of asynchronous circuits and the delay problem. Part II: Spike-free extensions and the delay problem of the second kind | date=1971 | last1=Kimura | first1=Izumi | journal=Journal of Computer and System Sciences | volume=5 | issue=2 | pages=129–162 | doi-access=free }}</ref> (garbage branches <ref>{{Cite journal |last1=Kushnerov |first1=Alex |last2=Bystrov |first2=Sergey |date=2023 |title=Signal Transition Graphs for Asynchronous Data Path Circuits |journal=Modeling and Analysis of Information Systems |volume=30 |issue=2 |pages=170–186 |doi=10.18255/1818-1015-2023-2-170-186 |doi-access=free}}</ref>) admissible for C-element and inadmissible for Join element]]

In [[Logic gate|digital computing]], the Muller '''C-element''' ('''C-gate''', '''hysteresis flip-flop''', '''coincident flip-flop''', or '''two-hand safety circuit''') is a small binary [[sequential logic|logic circuit]] widely used in design of [[asynchronous circuit]]s 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]]<ref name="Mull55">D. E. Muller, [https://archive.org/stream/theoryofasynchro66mull#page/n3/mode/2up Theory of asynchronous circuits]. Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955.</ref> and first used in [[ILLIAC II]] computer.<ref>H. C. Breadley, [http://bitsavers.informatik.uni-stuttgart.de/pdf/univOfIllinoisUrbana/illiac/ILLIAC_II/Brearley_ILLIAC_II_A_Short_Description_and_Annotated_Bibliography_Jun65.pdf "ILLIAC II — A short description and annotated bibliography"], IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 399–403, 1965.</ref> In terms of the theory of [[Lattice (order)|lattices]], the C-element is a semimodular distributive circuit, whose operation in time is described by a [[Hasse diagram]].<ref name="Mul59">D. E. Muller and W. S. Bartky, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Muller_Bartky_1959.pdf "A theory of asynchronous circuits"], Int. Symposium on the Switching Theory in Harvard University, pp. 204–243, 1959.</ref><ref>W. J. Poppelbaum, [http://bitsavers.informatik.uni-stuttgart.de/pdf/univOfIllinoisUrbana/Poppelbaum_Introduction_to_the_Theory_of_Digital_Machines.pdf Introduction to the Theory of Digital Machines]. Math., E.E. 294 Lecture Notes, University of Illinois at Urbana-Champaign.</ref><ref name="Kim69">{{cite journal | url=https://www.jstor.org/stable/43698723 | jstor=43698723 | title=A comparison between two mathematical models of asynchronous circuits | last1=Kimura | first1=Izumi | journal=Science Reports of the Tokyo Kyoiku Daigaku, Section A | date=1969 | volume=10 | issue=232/248 | pages=109–123 }}</ref><ref>{{cite book | chapter-url=https://doi.org/10.1007/3-540-57208-2_20 | doi=10.1007/3-540-57208-2_20 | chapter=A generalized event structure for the Muller unfolding of a safe net | title=Concur'93 | series=Lecture Notes in Computer Science | date=1993 | last1=Gunawardena | first1=Jeremy | volume=715 | pages=278–292 | isbn=978-3-540-57208-4 }}</ref> The C-element is closely related to the ''rendezvous''<ref>{{Cite book |last1=Stucki |first1=Mishell J. |title=Proceedings of the April 18-20, 1967, spring joint computer conference on - AFIPS '67 (Spring) |last2=Ornstein |first2=Severo M. |last3=Clark |first3=Wesley A. |date=1967 |isbn=978-1-4503-7895-6 |pages=357–364 |chapter=Logical design of macromodules |doi=10.1145/1465482.1465538 |doi-access=free}}</ref> and ''join''<ref>J. C. Ebergen, J. Segers, I. Benko, [https://cs.uwaterloo.ca/research/tr/1994/10/CS94-10.pdf "Parallel Program and Asynchronous Circuit Design"], Workshops in Computing, pp. 50–103, 1995.</ref> 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.<ref>{{cite journal | url=https://link.springer.com/article/10.1023%2FA%3A1008666605437?LI=true | doi=10.1023/A:1008666605437 | date=1998 | last1=Beerel | first1=Peter A. | last2=Burch | first2=Jerry R. | last3=Meng | first3=Teresa H. | title=Checking Combinational Equivalence of Speed-Independent Circuits | journal=Formal Methods in System Design | volume=13 | issue=1 | pages=37–85 }}</ref><ref>H. Park, A. He, M. Roncken and X. Song, [http://pdxscholar.library.pdx.edu/cgi/viewcontent.cgi?article=1306&context=ece_fac "Semi-modular delay model revisited in context of relative timing"], IET Electronics Letters, vol. 51, no. 4, pp. 332–334, 2015.</ref> Earlier techniques for implementing the C-element<ref>[https://archive.org/stream/quarterlytechnic1959univ#page/n5/mode/2up Technical Progress Report, Jan. 1959], University of Illinois at Urbana-Champaign.</ref><ref name="Pop59">W . J. Poppellbaum, N. E. Wiseman, [https://archive.org/stream/circuitdesignfor90popp#page/n5/mode/2up "Circuit design for the new Illinois computer"], Report no. 90, University of Illinois at Urbana-Champaign, 1959.</ref> include [[Schmitt trigger]],<ref>N. P. Singh, [http://publications.csail.mit.edu/lcs/pubs/pdf/MIT-LCS-TR-258.pdf A design methodology for self-timed systems]. MSc thesis, MIT, 1981, 98 p.</ref> Eccles-Jordan flip-flop and last moving point flip-flop.