Content deleted Content added
MadeOfAtoms (talk | contribs) →External links: Fix dead link |
Citation bot (talk | contribs) Removed URL that duplicated identifier. Removed parameters. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 335/1032 |
||
| (38 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Short description|Digital logic circuit}}
[[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 | 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">
[[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 26 ⟶ 22:
* delay2 is a propagation delay from node 1 via internal feedback to node 3,
* 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 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:▼
==Implementations of the C-element==▼
Depending on the requirements to the switching speed and power consumption, the C-element can be realized as a coarse- or fine-grain circuit. Also, one should distinguish between single-output and dual-rail<ref>A. Mokhov, V. Khomenko, D. Sokolov and A. Yakovlev, [http://async.org.uk/tech-reports/NCL-EECE-MSD-TR-2010-162.pdf "On dual-rail control logic for enhanced circuit robustness"], IEEE Int. Conference on Application of Concurrency to System Design (ACSD) 2012, pp. 112–121.</ref> realizations of C-element. A dual-rail C-element can be realized on 2-input NANDs (NORs) only.<ref name="Varsh85">[https://www.researchgate.net/profile/Vuacheslav-Marakhovsky/publication/265767101_Functional_completeness_in_the_class_of_semimodular_circuits/links/54dfbec00cf2953c22b42dd7/Functional-completeness-in-the-class-of-semimodular-circuits.pdf V. Varshavskiy, M. Kishinevskiy, V. Marakhovskiy, L. Rozenblyum, "Functional completeness in the class of semimodular circuits," Soviet Journal of Computer and Systems Sciences, vol. 23, no. 6, pp. 70-80, 1985.]</ref> A single-output realization is workable if and only if:<ref>B. S. Tsirlin, "A Survey of Equivalent Problems of Realizing Circuits in the AND-NOT Basis that are Speed-Independent", Soviet Journal of Computer and Systems Sciences, vol. 24, 1986, pp. 58–69 (Б. С. Цирлин, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Varshavsky%20and%20Co/Tsirlin/Tsirlin_Review%20of%20realization%20problems%20in%20NAND%20basis.pdf "Обзор эквивалентных проблем реализации схем в базисе И-НЕ, не зависящих от скорости"] {{Webarchive|url=https://web.archive.org/web/20170729013055/http://www.ee.bgu.ac.il/~kushnero/asynchronous/Varshavsky%20and%20Co/Tsirlin/Tsirlin_Review%20of%20realization%20problems%20in%20NAND%20basis.pdf |date=2017-07-29 }}, Изв. АН СССР, Техническая кибернетика, №2, 1986, с. 159–171).</ref>▼
# The circuit, where each input of a C-element is connected through a separate inverter to its output, is semimodular relatively to the state, where all the inverters are excited.▼
# This state is live for the output gate of C-element.▼
===[[Static logic (digital logic)|Static]] and semistatic implementations===▼
▲[[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>
▲[[Image:Semistatic_C-elements.png|thumb|upright=1.7|
In his report<ref name="Mull55" /> Muller proposed to realize C-element as a majority gate with feedback. However, to avoid hazards linked with skews of internal delays, the majority gate must have as small number of transistors as possible.<ref>D. Hampel, K. Prost, and N. Scheingberg, [http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=US&NR=3900742A&KC=A&FT=D&ND=3&date=19750819&DB=EPODOC&locale=en_EP "Threshold logic using complementary MOS device"], Patent US3900742, Aug. 19, 1975.</ref><ref>D. Doman, [http://samples.sainsburysebooks.co.uk/9781118273111_sample_406813.pdf Engineering the CMOS Library: Enhancing Digital Design Kits for Competitive Silicon] {{Webarchive|url=https://web.archive.org/web/20151008213805/http://samples.sainsburysebooks.co.uk/9781118273111_sample_406813.pdf |date=2015-10-08 }}. Wiley, 2012, 327 p.</ref> Generally, C-elements with different timing assumptions<ref>K. S. Stevens, R. Ginosar and S. Rotem, [http://webee.technion.ac.il/~ran/papers/TVLSI-RelativeTiming-2002.pdf "Relative timing [asynchronous design<nowiki>]</nowiki>"], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 1, pp. 129–140, 2003.</ref> can be built on [[AND-OR-Invert]] (AOI)<ref name="Zema62">H. Zemanek, [http://www.degruyter.com/view/j/itit.1962.4.issue-1-6/itit.1962.4.16.248/itit.1962.4.16.248.xml "Sequentielle asynchrone Logik"], Elektronische Rechenanlagen, vol. 4, no. 6, pp. 248–253, 1962. Also available in Russian as Г. Цеманек, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Zemanek.pdf "Последовательная асинхронная логика"] {{Webarchive|url=https://web.archive.org/web/20151005144323/http://www.ee.bgu.ac.il/~kushnero/asynchronous/Zemanek.pdf |date=2015-10-05 }}, Mеждународный симпозиум ИФАК Теория конечных и вероятностных автоматов 1962, с. 232—245.</ref><ref>W. Fleischhammer, [http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=GB&NR=1199698A&KC=A&FT=D&ND=8&date=19700722&DB=EPODOC&locale=en_EP "Improvements in or relating to asynchronous bistable trigger circuits"], UK patent specification GB1199698, Jul. 22, 1970.</ref> or its dual, OR-AND-Invert (OAI) gate<ref>T.-Y. Wuu and S. B. K. Vrudhula, [
<ref>V. I. Varshavsky, N. M. Kravchenko, V. B. Marakhovsky and B. S. Tsirlin, [https://worldwide.espacenet.com/publicationDetails/originalDocument?CC=SU&NR=1443137A1&KC=A1&FT=D&ND=3&date=19881207&DB=EPODOC&locale=en_EP "H flip-flop"], USSR Author's certificate SU1443137, Dec. 7, 1988.</ref> is to shunt the input signals when they are not equal each other. Being very simple, these realizations dissipate more power due to the short-circuits. Connecting an additional majority gate to the inverted output of C-element, we obtain ''inclusive'' OR (EDLINCOR) function:<ref>
Semistatic C-element stores its previous state using two cross-coupled inverters, similar to an [[Static random-access memory|SRAM]] cell. One of the inverters is weaker than the rest of the circuit, so it can be overpowered by the [[CMOS|pull-up and pull-down networks]]. If both inputs are 0, then the pull-up network changes the [[Latch (electronics)|latch]]'s state, and the C-element outputs a 0. If both inputs are 1, then the pull-down network changes the latch's state, making the C-element output a 1. Otherwise, the input of the latch is not connected to either <math>V_\text{dd}</math> or ground, and so the weak inverter dominates and the latch outputs its previous state. There are also versions of semistatic C-element built on devices with negative differential resistance (NDR).<ref>C.-H. Lin, K. Yang, A. F. Gonzalez, J. R. East, P. Mazumder, G. I. Haddad, [
===Gate-level implementations===▼
▲[[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: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>]]
There is a number of different single-output circuits of C-element built on logic gates.<ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/bd/d8/4b/81b12c002a0615/SU1096759A1.pdf "H flip-flop"], USSR author's certificate SU1096759, Jun. 7, 1984.</ref><ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/b1/bf/92/42303ee73cf5ac/SU1162019A1.pdf "Multiple input H flip-flop"], USSR author's certificate SU1162019, Jun. 15, 1985.</ref> In particular, the so-called Maevsky's implementation <ref name="Kuwa94">M. Kuwako, T. Nanya, [
,<ref name="Kim71" /><ref name="Kuwa94" /> and can operate without the input latch.
Note that both the Maevsky and Tsirlin circuits are based actually on so-called David cell.<ref>[https://web.archive.org/web/20170905042145/http://ieeexplore.ieee.org/document/4244956/ M. Courvoisier and P. Azema, "Asynchronous sequential machines with request/acknowledge operating mode," IEE Electronics Letters, Vol. 10, no. 1, pp.8-10, 1974.]</ref> Its fast transistor-level implementation is used in the semistatic C-element proposed.<ref>S. M. Fairbanks, [http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=US&NR=6281707B1&KC=B1&FT=D&ND=3&date=20010828&DB=EPODOC&locale=en_EP "Two-stage Muller C-element"], United States Patent US6281707, Aug. 28, 2001.</ref> Yet another semistatic circuit using pass transistors (actually MUX 2:1) has been proposed.<ref>A. Morgenshtein, M. Moreinis, R. Ginosar, [http://webee.technion.ac.il/~ran/papers/Async-GDI-circuits-Nov02.pdf "Asynchronous gate-diffusion-input (GDI) circuits"], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 12, no. 8, pp. 847–856, 2004.</ref> Yet another version of the C-element built on two [[RS latch#Simple set-reset latches|SR-latches]] has been synthesized by Murphy<ref>J. P. Murphy, [https://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6317230 "Design of latch-based C-element"], Electronics Letters, vol. 48, no. 19, 2012, pp. 1190–1191.</ref> using Petrify tool. However, this circuit includes inverter connected to one of the inputs. This inverter should have small delay. However, there are realizations of RS latches that already have one inverted input, for example.<ref>V. A. Maksimov and Ya. Ya. Petrichkovich [https://yandex.ru/patents/doc/SU1164867A1_19850630 "RS flip-flop,"] USSR author's certificate SU1164867, Jun. 30, 1985.</ref> Some speed-independent approaches<ref>P. Beerel and T. H.-Y. Meng. [http://dl.acm.org/citation.cfm?id=304171 "Automatic gate-level synthesis of speed-independent circuits"], IEEE/ACM Int. Conference on Computer-Aided Design (ICCAD) 1992, pp. 581–587.</ref><ref>A. Kondratyev, M. Kishinevsky, B. Lin, P. Vanbekbergen, and A. Yakovlev, [http://dl.acm.org/citation.cfm?id=196275 "Basic gate implementation of speed-independent circuits"], ACM Design Automation Conference (DAC) 1994, pp. 56–62.</ref> assume that zero-delay input inverters are available on all gates, which is a violation of true speed-independence but is fairly safe in practice. Other examples of using this assumption also exist.<ref>{{cite journal | url=http://www.sciencedirect.com/science/article/pii/S0167926096000107 | doi=10.1016/S0167-9260(96)00010-7 | title=Modelling, analysis and synthesis of asynchronous control circuits using Petri nets | journal=Integration | date=December 1996 | volume=21 | issue=3 | pages=143–170 | last1=Yakovlev | first1=A. V. | last2=Koelmans | first2=A. M. | last3=Semenov | first3=A. | last4=Kinniment | first4=D. J. | url-access=subscription }}</ref>
Other technologies suitable for realizing asynchronous primitives including C-element, are: carbon nanotubes,{{Citation needed|date=December 2019|reason=removed citation to predatory publisher content}} single-electron tunneling devices,<ref>S. Safiruddin, S. D. Cotofana, [https://www.researchgate.net/profile/Sorin_Cotofana/publication/224326348_Building_Blocks_for_Delay-Insensitive_Circuits_using_Single_Electron_Tunneling_Devices/links/0c9605230deb723cac000000.pdf "Building blocks for delay-insensitive circuits using single electron tunneling devices"], IEEE Conference on Nanotechnology 2007, pp. 704–708.</ref> quantum dots,<ref>V. I. Varshavsky, [
===Generalization for multiple-valued logic===
▲The definition of C-element can be generalized for multiple-valued logic
:<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
Line 51 ⟶ 73:
| 1 || 1 || 1
|}
▲==Implementations of the C-element==
▲Depending on the requirements to the switching speed and power consumption, the C-element can be realized as a coarse- or fine-grain circuit. Also, one should distinguish between single-output and dual-rail<ref>A. Mokhov, V. Khomenko, D. Sokolov and A. Yakovlev, [http://async.org.uk/tech-reports/NCL-EECE-MSD-TR-2010-162.pdf "On dual-rail control logic for enhanced circuit robustness"], IEEE Int. Conference on Application of Concurrency to System Design (ACSD) 2012, pp. 112–121.</ref> realizations of C-element. A dual-rail C-element can be realized on 2-input NANDs (NORs) only.<ref name="Varsh85">[https://www.researchgate.net/profile/Vuacheslav-Marakhovsky/publication/265767101_Functional_completeness_in_the_class_of_semimodular_circuits/links/54dfbec00cf2953c22b42dd7/Functional-completeness-in-the-class-of-semimodular-circuits.pdf V. Varshavskiy, M. Kishinevskiy, V. Marakhovskiy, L. Rozenblyum, "Functional completeness in the class of semimodular circuits," Soviet Journal of Computer and Systems Sciences, vol. 23, no. 6, pp. 70-80, 1985.]</ref> A single-output realization is workable if and only if:<ref>B. S. Tsirlin, "A Survey of Equivalent Problems of Realizing Circuits in the AND-NOT Basis that are Speed-Independent", Soviet Journal of Computer and Systems Sciences, vol. 24, 1986, pp. 58–69 (Б. С. Цирлин, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Varshavsky%20and%20Co/Tsirlin/Tsirlin_Review%20of%20realization%20problems%20in%20NAND%20basis.pdf "Обзор эквивалентных проблем реализации схем в базисе И-НЕ, не зависящих от скорости"], Изв. АН СССР, Техническая кибернетика, №2, 1986, с. 159–171).</ref>
▲# The circuit, where each input of a C-element is connected through a separate inverter to its output, is semimodular relatively to the state, where all the inverters are excited.
▲# This state is live for the output gate of C-element.
▲===Gate-level implementations===
▲There is a number of different single-output circuits of C-element built on logic gates.<ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/bd/d8/4b/81b12c002a0615/SU1096759A1.pdf "H flip-flop"], USSR author's certificate SU1096759, Jun. 7, 1984.</ref><ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/b1/bf/92/42303ee73cf5ac/SU1162019A1.pdf "Multiple input H flip-flop"], USSR author's certificate SU1162019, Jun. 15, 1985.</ref> In particular, the so-called Maevsky's implementation <ref name="Kuwa94">M. Kuwako, T. Nanya, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=656283 "Timing-reliability evaluation of asynchronous circuits based on different delay models"], IEEE Int. Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC) 1994, pp. 22–31.</ref><ref name="Brz95">J. A. Brzozowski, K. Raahemifar, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=514652 "Testing C-elements is not elementary"], Working Conference on Asynchronous Design Methodologies (ASYNC) 1995, pp. 150–159.</ref><ref>P. A. Beerel, J. R. Burch, T. H. Meng, [https://link.springer.com/article/10.1023/A:1008666605437 "Checking combinational equivalence of speed-independent circuits"], Formal Methods in System Design, vol. 13, no. 1, 1998, pp. 37–85.</ref> is a semimodular, but non-distributive (OR-causal) circuit loosely based on.<ref>V. I. Varshavsky, O. V. Maevsky, Yu. V. Mamrukov, B. S. Tsirlin, [https://patentimages.storage.googleapis.com/fb/81/d2/fa3a9d86aa6917/SU1081801A1.pdf "H flip-flop"], USSR author's certificate SU1081801, Mar. 23, 1984</ref> The NAND3 gate in this circuit can be replaced by two NAND2 gates. Note that Maevsky's C-element is actually a Join element, whose input signals cannot switch twice.<ref name="Kuwa94"/> Yet another circuit with OR-causality, which operates as a Join element.<ref>G. S. Brailovsky, L. Ya. Rozenblyum, B. S. Tsirlin, [https://patentimages.storage.googleapis.com/41/1a/f8/394838c3c7d619/SU1432733A1.pdf "H-flip-flop"], USSR author's certificate SU1432733, Oct. 23, 1988.</ref> A realization of C-element on two-input gates only has been proposed by Tsirlin <ref>B. S. Tsirlin, [https://patentimages.storage.googleapis.com/d0/78/f9/43bc147866ddb5/SU1324106A1.pdf "H-flip-flop"], USSR author's certificate SU1324106, Jul. 15, 1987.</ref> and then synthesized by Starodoubtsev et al. using Taxogram language<ref name="Star04">N. A. Starodoubtsev, S. A. Bystrov, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1354042&matchBoolean=true&searchWithin%5B%5D=%22Last+Name%22%3Astarodoubtsev&newsearch=true "Monotonic behavior refinement for synthesis of two-input-gate asynchronous circuits"], IEEE Int. Midwest Symposium on Circuits and Systems (MWSCAS) 2004, vol. I, pp. I-521–524.</ref> This circuit coincides with that attributed (without reference) to Bartky<ref name="Kuwa94" /> and can operate without the input latch. Yet another version of the C-element built on two [[RS latch#Simple set-reset latches|RS latches]] has been synthesized by Murphy<ref>J. P. Murphy, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6317230 "Design of latch-based C-element"], Electronics Letters, vol. 48, no. 19, 2012, pp. 1190–1191.</ref> using Petrify tool. However, this circuit includes inverter connected to one of the inputs. This inverter should have small delay. However, there are realizations of RS latches that already have one inverted input, for example.<ref>V. A. Maksimov and Ya. Ya. Petrichkovich [https://yandex.ru/patents/doc/SU1164867A1_19850630 "RS flip-flop,"] USSR author's certificate SU1164867, Jun. 30, 1985.</ref> Some speed-independent approaches<ref>P. Beerel and T. H.-Y. Meng. [http://dl.acm.org/citation.cfm?id=304171 "Automatic gate-level synthesis of speed-independent circuits"], IEEE/ACM Int. Conference on Computer-Aided Design (ICCAD) 1992, pp. 581–587.</ref><ref>A. Kondratyev, M. Kishinevsky, B. Lin, P. Vanbekbergen, and A. Yakovlev, [http://dl.acm.org/citation.cfm?id=196275 "Basic gate implementation of speed-independent circuits"], ACM Design Automation Conference (DAC) 1994, pp. 56–62.</ref> assume that zero-delay input inverters are available on all gates, which is a violation of true speed-independence but is fairly safe in practice. Other examples of using this assumption also exist.<ref>A. V. Yakovlev, A. M. Koelmans, A. Semenov, D. J. Kinniment, [http://www.sciencedirect.com/science/article/pii/S0167926096000107 "Modelling, analysis and synthesis of asynchronous control circuits using Petri nets"], Integration, the VLSI Journal, vol. 21, no. 3, pp. 143—170, 1996.</ref>
▲===[[Static logic (digital logic)|Static]] and semistatic implementations===
▲In his report<ref name="Mull55" /> Muller proposed to realize C-element as a majority gate with feedback. However, to avoid hazards linked with skews of internal delays, the majority gate must have as small number of transistors as possible.<ref>D. Hampel, K. Prost, and N. Scheingberg, [http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=US&NR=3900742A&KC=A&FT=D&ND=3&date=19750819&DB=EPODOC&locale=en_EP "Threshold logic using complementary MOS device"], Patent US3900742, Aug. 19, 1975.</ref><ref>D. Doman, [http://samples.sainsburysebooks.co.uk/9781118273111_sample_406813.pdf Engineering the CMOS Library: Enhancing Digital Design Kits for Competitive Silicon] {{Webarchive|url=https://web.archive.org/web/20151008213805/http://samples.sainsburysebooks.co.uk/9781118273111_sample_406813.pdf |date=2015-10-08 }}. Wiley, 2012, 327 p.</ref> Generally, C-elements with different timing assumptions<ref>K. S. Stevens, R. Ginosar and S. Rotem, [http://webee.technion.ac.il/~ran/papers/TVLSI-RelativeTiming-2002.pdf "Relative timing [asynchronous design<nowiki>]</nowiki>"], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 11, no. 1, pp. 129–140, 2003.</ref> can be built on [[AND-OR-Invert]] (AOI)<ref name="Zema62">H. Zemanek, [http://www.degruyter.com/view/j/itit.1962.4.issue-1-6/itit.1962.4.16.248/itit.1962.4.16.248.xml "Sequentielle asynchrone Logik"], Elektronische Rechenanlagen, vol. 4, no. 6, pp. 248–253, 1962. Also available in Russian as Г. Цеманек, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Zemanek.pdf "Последовательная асинхронная логика"], Mеждународный симпозиум ИФАК Теория конечных и вероятностных автоматов 1962, с. 232—245.</ref><ref>W. Fleischhammer, [http://worldwide.espacenet.com/publicationDetails/originalDocument?CC=GB&NR=1199698A&KC=A&FT=D&ND=8&date=19700722&DB=EPODOC&locale=en_EP "Improvements in or relating to asynchronous bistable trigger circuits"], UK patent specification GB1199698, Jul. 22, 1970.</ref> or its dual, OR-AND-Invert (OAI) gate<ref>T.-Y. Wuu and S. B. K. Vrudhula, [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=238414 "A design of a fast and area efficient multi-input Muller C-element"], IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 1, no. 2, pp. 215–219, 1993.</ref><ref>H. K. O. Berge, A. Hasanbegovic, S. Aunet, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5783079 "Muller C-elements based on minority-3 functions for ultra low voltage supplies"], IEEE Int. Symposium on Design and Diagnostics of Electronic Circuits & Systems (DDECS) 2011, pp. 195–200.</ref> and inverter. Yet another option patented by Varshavsky et al.<ref>V. I. Varshavsky, A. Y. Kondratyev, N. M. Kravchenko, and B. S. Tsirlin, [https://worldwide.espacenet.com/publicationDetails/originalDocument?CC=SU&NR=1411934A1&KC=A1&FT=D&ND=3&date=19880723&DB=EPODOC&locale=en_EP "H flip-flop"], USSR Author's certificate SU1411934 Jul. 23, 1988.</ref>
▲<ref>V. I. Varshavsky, N. M. Kravchenko, V. B. Marakhovsky and B. S. Tsirlin, [https://worldwide.espacenet.com/publicationDetails/originalDocument?CC=SU&NR=1443137A1&KC=A1&FT=D&ND=3&date=19881207&DB=EPODOC&locale=en_EP "H flip-flop"], USSR Author's certificate SU1443137, Dec. 7, 1988.</ref> is to shunt the input signals when they are not equal each other. Being very simple, these realizations dissipate more power due to the short-circuits. Connecting an additional majority gate to the inverted output of C-element, we obtain ''inclusive'' OR (EDLINCOR) function:<ref>D. A. Pucknell, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=210334 "Event-driven logic (EDL) approach to digital systems representation and related design processes"], IEE Proceedings E, Computers and Digital Techniques, vol. 140, no. 2, pp. 119—126, 1993.</ref><ref>A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, M. Pietkiewicz-Koutny, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.19.4630&rep=rep1&type=pdf "On the models for asynchronous circuit behaviour with OR causality"], Formal Methods in System Design, vol. 9, no. 3, pp. 189—233. 1996.</ref> <math>z_n = x_1 x_2 + (x_1 + x_2) \overline{y_n}</math>. Some simple asynchronous circuits like pulse distributors<ref>J. C. Nelson, [https://archive.org/stream/speedindependent71nels#page/n5/mode/2up Speed-independent counting circuits]. Report no. 71, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1956.</ref> can be built solely on majority gates.
▲Semistatic C-element stores its previous state using two cross-coupled inverters, similar to an [[Static random-access memory|SRAM]] cell. One of the inverters is weaker than the rest of the circuit, so it can be overpowered by the [[CMOS|pull-up and pull-down networks]]. If both inputs are 0, then the pull-up network changes the [[Latch (electronics)|latch]]'s state, and the C-element outputs a 0. If both inputs are 1, then the pull-down network changes the latch's state, making the C-element output a 1. Otherwise, the input of the latch is not connected to either <math>V_\text{dd}</math> or ground, and so the weak inverter dominates and the latch outputs its previous state. There are also versions of semistatic C-element built on devices with negative differential resistance (NDR).<ref>C.-H. Lin, K. Yang, A. F. Gonzalez, J. R. East, P. Mazumder, G. I. Haddad, [http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=773722 "InP-based high speed digital logic gates using an RTD/HBT heterostructure"], Int. Conference on Indium Phosphide and Related Materials (IPRM) 1999, pp. 419–422.</ref><ref>P. Glosekotter, C. Pacha, K. F. Goser, W. Prost, S. Kim, H. van Husen, et al., [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=1137684 "Asynchronous circuit design based on the RTBT monostable-bistable logic transition element (MOBILE)"], Symposium Integrated Circuits and Systems Design 2002, pp. 365–370.</ref> NDR is usually defined for small signal, so it is difficult to expect that such a C-element will operate in full range of voltages or currents.{{or|date=March 2020}}
▲===Generalizations and non-transistor implementations===
Since the majority gate is a particular case of threshold gate, any of known realizations of threshold gate<ref>V. Beiu, J. M. Quintana, M. J. Avedillo, [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.2109&rep=rep1&type=pdf "VLSI implementations of threshold logic – A comprehensive survey"], IEEE Transactions on Neural Networks, vol. 14, no. 5, pp. 1217–1243, 2003.</ref> can in principle be used for building a C-element. In the multiple-valued case, however, connecting the output of majority gate to one or several inputs may have no desirable effect. For example, using the ternary majority function defined as<ref>V. Varshavsky, B. Ovsievich, [http://www.ee.bgu.ac.il/~kushnero/asynchronous/Varshavsky%20and%20Co/Networks%20Composed%20of%20Ternary%20Majority%20Elements.pdf "Networks composed of ternary majority elements"], IEEE Transactions on Electronic Computers, vol. EC-14, no. 5, pp. 730–733, 1965.</ref>
Line 74 ⟶ 80:
-1 & \text{if}\ x_1+x_2+x_3 \leqslant -1
\end{cases}</math>
does not lead to the ternary C-element specified by the truth table, if the sum <math>x_1 + x_2 + x_3</math> is not split into pairs. However, even without such a splitting two ternary majority functions are suitable for building a ternary inclusive OR gate.
▲Other technologies suitable for realizing asynchronous primitives including C-element, are: carbon nanotubes,{{Citation needed|date=December 2019|reason=removed citation to predatory publisher content}} single-electron tunneling devices,<ref>S. Safiruddin, S. D. Cotofana, [https://www.researchgate.net/profile/Sorin_Cotofana/publication/224326348_Building_Blocks_for_Delay-Insensitive_Circuits_using_Single_Electron_Tunneling_Devices/links/0c9605230deb723cac000000.pdf "Building blocks for delay-insensitive circuits using single electron tunneling devices"], IEEE Conference on Nanotechnology 2007, pp. 704–708.</ref> quantum dots,<ref>V. I. Varshavsky, [http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=494973 "Logic design and quantum challenge"], Int. Workshop on Physics and Computer Modeling of Devices Based on Low-Dimensional Structures 1995, pp. 134–146.</ref> and molecular nanotechnology.<ref>A. J. Martin, P. Prakash, [http://www.async.caltech.edu/Pubs/PDF/2008_nano.pdf "Asynchronous nano-electronics: Preliminary investigation"] {{Webarchive|url=https://web.archive.org/web/20160304122447/http://www.async.caltech.edu/Pubs/PDF/2008_nano.pdf |date=2016-03-04 }}, IEEE Int. Symposium on Asynchronous Circuits and Systems (ASYNC) 2008, pp. 58–68.</ref>
==References==
| |||