C-element: Difference between revisions

Revision as of 23:51, 17 July 2024

Revision as of 23:52, 17 July 2024

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 }}</ref> (garbage branches <ref>{{Cite journal |lastlast1=Kushnerov |firstfirst1=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">I.{{cite Kimura,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, no.| issue=232/248, 1969,| pp.pages=109–123 109-123.}}</ref><ref>J. Gunawardena, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.51.3534&rep=rep1&type=pdf "A generalized event structure for the Muller unfolding of a safe net"], Int. Conference on Concurrency Theory (CONCUR) 1993, pp. 278–292.</ref> The C-element is closely related to the ''rendezvous''<ref>M. J. Stucki, S. M. Ornstein, W. A. Clark, [http://dl.acm.org/citation.cfm?doid=1465482.1465538 "Logical design of macromodules"], in Proceedings of AFIPS 1967, pp. 357–364.</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>[https://link.springer.com/article/10.1023%2FA%3A1008666605437?LI=true P.A. Beerel, J.R. Burch and T.H. Meng,"Checking combinational equivalence of speed-independent circuits," Formal Methods in System Design, vol. 13, no. 1, pp. 37-85, 1998.]</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.

== Truth table and delay assumptions ==