From Wikipedia, the free encyclopedia
Jump to: navigation, search
Delays in the naïve implementation and environment
Timing diagram of a C-element and inclusive OR gate
Majority gate realization of C-element and inclusive OR gate (a); Realizations proposed by Maevsky (b), Starodoubtsev (c) and Murphy (d)
Static implementations of two- and three input C-element [1][2][3]
Semi-static implementations of two- and multiple input C-element [3][4][5][6]
David cell (a) and its fast implementations: gate-level (b) and transistor-level (c) [7]

The Muller C-element (C-gate or sometimes, Hysteresis flip-flop) is a commonly used asynchronous logic component originally devised by David E. Muller [8][9][10] while designing ILLIAC II computer.[11] In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by Hasse diagram.[10][12][13][14] Earlier techniques for implementing the C-element include Schmidt trigger, Eccles-Jordan flip-flop, and last moving point flip-flop.[15][16]

Truth table and delay assumptions[edit]

For two input signals the C-element is defined by the equation y_n=x_1x_2+(x_1+x_2)y_{n-1}, which corresponds to the following truth table:

x_1 x_2 y_n
0 0 0
0 1 y_{n-1}
1 0 y_{n-1}
1 1 1

This table can be turned into a circuit using the Karnaugh map. However, the obtained implementation is naïve, since nothing is said about delay assumptions. To understand under what conditions the obtained circuit is workable, it is necessary to do additional analysis, which reveals that

  • delay1 is a propagation delay from node 1 via environment to node 3
  • delay2 is a propagation delay from node 1 via internal feedback to node 3
  • delay1 must be greater than delay2

Thus, the naïve implementation is correct only for slow environment.[17]

Note that the above truth table can be easily generalized to multiple-valued logic. For example, a balanced ternary C-element with two inputs is defined by

x_1 x_2 y_n
-1 -1 -1
-1 0 y_{n-1}
-1 1 y_{n-1}
0 -1 y_{n-1}
0 0 0
0 1 y_{n-1}
1 -1 y_{n-1}
1 0 y_{n-1}
1 1 1

Implementations of the C-element[edit]

Depending on the requirements to the switching speed and power consumption, the C-element can be realized as a coarse- or fine-grain circuit.

Gate-level implementations[edit]

A C-element can be built using only NAND, NOR and inverter gates. Many different implementations have been proposed.[18][19][20][21][22] The so-called Maevsky's implementation [23][24][25] is a non-distributive circuit loosely based on Varshavsky et al.,[26] which in turn, is an improved version of.[27] The 3NAND gate in this circuit can be safely replaced by two 2NAND gates. Note that sometimes it is advisable to introduce non-distributivity to increase concurrency. The C-element synthesized by Starodoubtsev et al. using Taxogram language is presented in.[28] This circuit coincides with that attributed (without reference) to Bartky in [23] and can operate without the input latch. The approach proposed in [28] is valuable by that the synthesis is done using 2NAND and 2NOR gates only. Yet another version of the C-element built on two RS latches has been synthesized by Murphy [29] using Petrify tool.

Static and semi-static implementations[edit]

The most known realization of a static C-element is a transistor circuit of majority gate [30][31] with feedback. The majority gate in turn, can be composed of AND-OR-Invert (AOI) [32][33] or its dual, OR-AND-Invert (OAI) gate [34][35] and inverter.

Note that connecting an additional majority gate to the inverted output of C-element, we obtain inclusive OR (EDLINCOR) function:[36][37] z_n=x_1x_2+(x_1+x_2)\overline{y_n}.

Note also that since the majority gate is a particular case of threshold gate, any of known realizations of threshold gate [38] 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:[39]

+1 \text { if } x_1+x_2+x_3\geqslant +1;\\
0 \text { if } x_1+x_2+x_3=0;\\ 
-1 \text { if } x_1+x_2+x_3\leqslant -1;

does not lead to the ternary C-element specified by the truth table, if the sum x_1+x_2+x_3 is not split into pairs. However, even without such a splitting two ternary majority functions are suitable for building a ternary inclusive OR gate.

Semi-static C-element stores its previous state using two cross-coupled inverters, similar to an SRAM cell. One of the inverters is weaker than the rest of the circuit, so it can be overpowered by the pull-up and pull-down networks. If both inputs are 0, then the pull-up network changes the 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 V_{dd} or ground, and so the weak inverter dominates and the latch outputs its previous state.

Note that both the Maevsky and Starodoubtsev circuits are based actually on so-called David cell. Its fast transistor-level implementation is used in the semi-static C-element proposed in.[40] Yet another semi-static circuit using pass transistors has been proposed in.[41]

There are also versions of semi-static C-element built on devices with negative differential resistance (NDR).[42][43] It should be noted however, that 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.

Other modern technologies suitable for realizing asynchronous primitives including C-element, are carbon nanotubes,[44] single electron tunneling devices,[45] quantum dots [46] and molecular nanotechnology.[47]


  1. ^ I. E. Sutherland, "Micropipelines," Communications of the ACM, vol. 32, no. 6, pp. 720-738, 1989.
  2. ^ C. H. van Berkel, "Beware the isochronic fork," Report UR 003/91, Philips Research Laboratories, 1991.
  3. ^ a b V. B. Marakhovsky, Logic design of asynchronous circuits. Slides on the course. CS&SE Department, SPbPU.
  4. ^ V. I. Varshavsky, "β-driven threshold elements," IEEE Great Lakes Symposium on VLSI 1998, pp. 52-58.
  5. ^ V. I. Varshavsky, N. M. Kravchenko, V. B. Marakhovsky, B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1562964, Jul. 5, 1990.
  6. ^ K. J. Schultz, R. J. Francis, K. C. Smith, "Ganged CMOS: trading standby power for speed," IEEE Journal of Solid-State Circuits, vol. 25, no. 3, pp. 870-873, 1990.
  7. ^ D. Sokolov, A. Yakovlev, "Clockless circuits and system synthesis," IEE Proceedings, Computers and Digital Techniques, vol. 152, no. 3, pp. 298-316, 2005.
  8. ^ D. E. Muller, W. S. Bartky, "A theory of asynchronous circuits I," Report no. 75, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1956.
  9. ^ D. E. Muller, W. S. Bartky, "A theory of asynchronous circuits II," Report no. 78, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1957.
  10. ^ a b D. E. Muller and W. S. Bartky, "A theory of asynchronous circuits," Int. Symposium on the Switching Theory in Harvard University, pp. 204-243, 1959.
  11. ^ H. C. Breadley, "ILLIAC II — A short description and annotated bibliography," IEEE Transactions on Electronic Computers, vol. EC-14, no. 3, pp. 399-403, 1965.
  12. ^ W. J. Poppelbaum, Introduction to the Theory of Digital Machines. Math., E.E. 294 Lecture Notes, University of Illinois at Urbana-Champaign.
  13. ^ W. D. Frazer, A switching theory for bilateral nets of threshold elements. PhD thesis, University of Illinois at Urbana-Champaign, 1963, 69 p.
  14. ^ J. Gunawardena, "A generalized event structure for the Muller unfolding of a safe net," Int. Conference on Concurrency Theory (CONCUR) 1993, pp. 278-292.
  15. ^ Technical Progress Report, Jan. 1959, University of Illinois at Urbana-Champaign.
  16. ^ W . J. Poppellbaum, N. E. Wiseman, "Circuit design for the new Illinois computer," Report no. 90, University of Illinois at Urbana-Champaign, 1959.
  17. ^ J. Cortadella, M. Kishinevsky, Tutorial: Synthesis of control circuits from STG specifications. Summer school, Lyngby, 1997
  18. ^ B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1096759, Jun. 7, 1984
  19. ^ B. S. Tsirlin, "Multiple input H flip-flop," USSR author's certificate SU1162019, Jun. 15, 1985
  20. ^ G. S. Brailovsky, L. Ya. Rozenblyum, B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1277385, Jan. 15, 1986
  21. ^ B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1324108, Jul. 15, 1987
  22. ^ G. S. Brailovsky, L. Ya. Rozenblyum, B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1432733, Oct, 23, 1988
  23. ^ a b M. Kuwako, T. Nanya, "Timing-reliability evaluation of asynchronous circuits based on different delay models," IEEE International Symposium on Advanced Research in Asynchronous Circuits and Systems (ASYNC) 1994, pp.22-31.
  24. ^ J. A. Brzozowski, K. Raahemifar, "Testing C-elements is not elementary," Working Conference on Asynchronous Design Methodologies (ASYNC) 1995, pp. 150-159.
  25. ^ S. Golubcovs, A. Alekseyev, A. Mokhov, A. Yakovlev, "Asynchronous circuit development with Workcraft," Technical Report NCL-EECE-MSD-TR-2011-174, University of Newcastle upon Tyne, 2011
  26. ^ V. I. Varshavsky, O. V. Maevsky, Yu. V. Mamrukov, B. S. Tsirlin, "H flip-flop," USSR author's certificate SU1081801, Mar. 23, 1984
  27. ^ G. Brailovsky, "H flip-flop," USSR author's certificate SU945960, Jul. 23, 1982
  28. ^ a b N. A. Starodoubtsev, S. A. Bystrov, "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.
  29. ^ J. P. Murphy, "Design of latch-based C-element," Electronics Letters, vol. 48, no. 19, 2012, pp. 1190-1191
  30. ^ D. Hampel, K. Prost, and N. Scheingberg, "Threshold logic using complementary MOS device," Patent US3900742, Aug. 19, 1975.
  31. ^ D. Doman, Engineering the CMOS Library: Enhancing Digital Design Kits for Competitive Silicon. Wiley, 2012, 327p.
  32. ^ H. Zemanek, "Sequentielle asynchrone Logik," Elektronische Rechenanlagen, vol. 4, no. 6, pp. 248–253, 1962. also available in Russian as Г. Цеманек, "Последовательная асинхронная логика," Mеждународный симпозиум ИФАК Теория конечных и вероятностных автоматов 1962, стр. 232—245.
  33. ^ W. Fleischhammer, "Improvements in or relating to asynchronous bistable trigger circuits," UK patent specification GB1199698, Jul. 22, 1970
  34. ^ T.-Y. Wuu and S. B. K. Vrudhula, "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.
  35. ^ H. K. O. Berge, A. Hasanbegovic, S. Aunet, "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.
  36. ^ D. A. Pucknell, "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.
  37. ^ A. Yakovlev, M. Kishinevsky, A. Kondratyev, L. Lavagno, M. Pietkiewicz-Koutny, "On the models for asynchronous circuit behaviour with OR causality, " Formal Methods in System Design, vol. 9, no. 3, pp. 189—233. 1996.
  38. ^ V. Beiu, J. M. Quintana, M. J. Avedillo, "VLSI implementations of threshold logic - A comprehensive survey," IEEE Transactions on Neural Networks, vol. 14, no. 5, pp. 1217-1243, 2003.
  39. ^ V. Varshavsky, B. Ovsievich, "Networks composed of ternary majority elements," IEEE Transactions on Electronic Computers, vol. EC-14, no. 5, pp.730-733, 1965.
  40. ^ S. M. Fairbanks, "Two-stage Muller C-element," United States Patent US6281707, Aug. 28, 2001
  41. ^ A. Morgenshtein, M. Moreinis, R. Ginosar, "Asynchronous gate-diffusion-input (GDI) circuits," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol.12, no.8, pp. 847-856, 2004
  42. ^ C.-H. Lin, K. Yang, A. F. Gonzalez, J. R. East, P. Mazumder, G. I. Haddad, "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.
  43. ^ P. Glosekotter, C. Pacha, K. F. Goser, W. Prost, S. Kim, H. van Husen, et al., "Asynchronous circuit design based on the RTBT monostable-bistable logic transition element (MOBILE)," Symposium Integrated Circuits and Systems Design 2002, pp. 365-370.
  44. ^ B. Liu, "Nanoelectronic Design Based on a CNT Nano-Architecture," Chap. 19 in VLSI book, ed. Z. Wang, pp. 375-408, InTech, 2010.
  45. ^ S. Safiruddin, S. D. Cotofana, "Building blocks for delay-insensitive circuits using single electron tunneling devices," IEEE Conference on Nanotechnology 2007, pp. 704-708.
  46. ^ V. I. Varshavsky, "Logic design and quantum challenge," Int. Workshop on Physics and Computer Modeling of Devices Based on Low-Dimensional Structures 1995, pp. 134-146.
  47. ^ A. J. Martin, P. Prakash, "Asynchronous nano-electronics: Preliminary investigation," IEEE Int. Symposium on Asynchronous Circuits and Systems (ASYNC) 2008, pp. 58-68.

External links[edit]