Content deleted Content added
No edit summary |
Tom.Reding (talk | contribs) |
||
Line 23:
* 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
:<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 54:
===[[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|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>[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>]]
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.{{
===Gate-level implementations===
Line 66:
[[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, [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 to Bartky
,<ref name="Kim71" />
===Generalizations and non-transistor implementations===
| |||