Content deleted Content added
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 |
|||
| (27 intermediate revisions by 10 users not shown) | |||
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">
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">
== Truth table and delay assumptions ==
Line 25:
==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.
Line 31:
===[[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><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|Semistatic 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>
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===
Line 41:
[[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.
===
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,<ref name="Kim69" /><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><ref>[https://glim-re.repo.nii.ac.jp/record/3834/files/thesis_O79.pdf H. Sato, Completeness on Multiple-Valued Logical Functions Realized by Asynchronous Sequential Circuits. PhD thesis, Gakushuin University, 1996.]</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
{| class="wikitable" style="text-align: center"
! <math>x_1</math> !! <math>x_2</math> !! <math>y_n</math>
|-
| −1 || −1 || −1
|-
| −1 || 0 || <math>y_{n-1}</math>
|-
| −1 || 1 || <math>y_{n-1}</math>
|-
| 0 || −1 || <math>y_{n-1}</math>
|-
| 0 || 0 || 0
|-
| 0 || 1 || <math>y_{n-1}</math>
|-
| 1 || −1 || <math>y_{n-1}</math>
|-
| 1 || 0 || <math>y_{n-1}</math>
|-
| 1 || 1 || 1
|}
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 52 ⟶ 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==
| |||