C-element: Difference between revisions

Content deleted Content added
No edit summary
No edit summary
Line 7:
[[Image:Dual-rail C-element.png|thumb|upright=1.5|An STG of dual-rail C-element with 00 transit and its circuit realized only on NAND2 as a particular case of<ref name="Varsh85" /> considered by V.B. Marakhovsky.]]
[[Image:David cell graph.png|thumb|upright=1.7|David cell (a) and its fast implementations: gate-level (b) and transistor-level (c)<ref>A. Bystrov, A. Yakovlev, [http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=9FB34454CF987BC939FF0377A3EAD0BB?doi=10.1.1.16.5667&rep=rep1&type=pdf Asynchronous circuit synthesis by direct mapping: Interfacing to environment]. Technical Report, CS Department, University of Newcastle upon Tyne, October 2001.</ref>]]
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>I. Kimura, "[https://www.jstor.org/stable/43698723 A comparison between two mathematical models of asynchronous circuits]," Science Reports of the Tokyo Kyoiku Daigaku, Section A 10, no. 232/248, 1969, pp. 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 ==