Revision as of 08:56, 30 December 2022 edit Thealik (talk \| contribs) Extended confirmed users 639 edits No edit summary ← Previous edit		Revision as of 09:43, 30 December 2022 edit undo Thealik (talk \| contribs) Extended confirmed users 639 edits No edit summary Next edit →
Line 3: [[Image:Join_element_stg.png\|thumb\|upright=1.5\|Behavior of the environment admissible for C-element and inadmissible for Join element]] [[Image:Realizations_of_C_element.png\|thumb\|upright=1.8\|Majority-gate realization of C-element and inclusive OR gate (a); Realizations proposed by Maevsky (b), Tsirlin (c) and Murphy (d)]] [[Image:Single_gate_C_elements.png\|thumb\|upright=2.2\|Static implementations of two- and three-input C-element<ref>I. E. Sutherland, [http://f-cpu.seul.org/new/micropipelines.pdf "Micropipelines]", Communications of the ACM, vol. 32, no. 6, pp. 720–738, 1989.</ref><ref>C. H. van Berkel, [http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=380B231B55BB4F45F6E4B72D4D273D44?doi=10.1.1.72.3108&rep=rep1&type=pdf "Beware the isochronic fork"], Report UR 003/91, Philips Research Laboratories, 1991.</ref>,<ref name="Mar10">V. B. Marakhovsky, [http://elib.spbstu.ru/dl/1945.pdf/download/1945.pdf Logic design of asynchronous circuits]. Slides on the course. CS&SE Department, SPbPU.</ref>]] [[Image:Semistatic_C-elements.png\|thumb\|upright=1.7\|Semi-static implementations of two- and multiple-input C-element.<ref>[http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=SU&NR=1562964A1&KC=A1&FT=D V. I. Varshavsky, N. M. Kravchenko, V. B. Marakhovsky, B. S. Tsirlin, "H flip-flop", USSR author's certificate SU1562964, Jul. 5, 1990.]</ref><ref>[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=665199 V. I. Varshavsky, "β-driven threshold elements", IEEE Great Lakes Symposium on VLSI 1998, pp. 52–58.]</ref><ref>[http://www.freepatentsonline.com/6338157.pdf V. I. Varshavsky, "Threshold element and method of designing the same," Patent US6338157, Jan. 8, 2002.]</ref> For a faster version see<ref>[https://worldwide.espacenet.com/publicationDetails/originalDocument?CC=RU&NR=2371842C2&KC=C2&FT=D& Y. A. Stepchenkov, Y. G. Dyachenko, A. N. Denisov, Y. P. Fomin, "H flip-flop", Patent RU2371842, Oct. 27, 2009.]</ref>]] [[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 name="Kim69">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 == Line 27: * delay1 must be greater than delay2. Thus, the naive implementation is correct ''only'' for slow environment.<ref>[[Jordi Cortadella\|J. Cortadella]], M. Kishinevsky, [https://www.inf.pucrs.br/~calazans/graduate/SSD/Tutorial_Cortadella_Lyngby_Summer_School_1997.pdf Tutorial: Synthesis of control circuits from STG specifications]. Summer school, Lyngby, 1997.</ref> The definition of C-element can be ~~easily~~ generalized for multiple-valued logic <ref name="Kim69"></ref>,<ref>[https://www.proquest.com/docview/303676273?pq-origsite=gscholar&fromopenview=true J. M. Johnson, Theory and Application of Self-Timed Integrated Systems Using Ternary Logic Elements. PhD thesis. University of California, Santa Barbara. 1989.]</ref> or even for continuous signals: :<math>\text { if } x_1=x_2=...=x_m, \text { then } y_n=\text{any}(x_1,x_2,...,x_m), \text { else } y_n=y_{n-1}.</math> For example, the truth table for a balanced ternary C-element with two inputs is

C-element: Difference between revisions