Muller C-gate

In digital computing, the Muller C-element (C-gate, hysteresis flip-flop, coincident flip-flop, or two-hand safety circuit) is a small binary logic circuit widely used in design of asynchronous circuits 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. MullerD. E. Muller
Theory of asynchronous circuits
Report no. 66, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, 1955. and first used in ILLIAC II computer. In terms of the theory of lattices, the C-element is a semimodular distributive circuit, whose operation in time is described by a Hasse diagram.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.I. Kimura,
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. The C-element is closely related to the ''rendezvous'' and ''join'' 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. Earlier techniques for implementing the C-elementW . J. Poppellbaum, N. E. Wiseman
"Circuit design for the new Illinois computer"
Report no. 90, University of Illinois at Urbana-Champaign, 1959. include Schmitt trigger, Eccles-Jordan flip-flop and last moving point flip-flop.

Truth table and delay assumptions

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

This table can be turned into a circuit using the Karnaugh map. However, the obtained implementation is naive, 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 naive implementation is correct ''only'' for slow environment.
The definition of C-element can be generalized for multiple-valued logic , or even for continuous signals:
:$\text x_1=x_2=...=x_m, \text y_n=\text(x_1,x_2,...,x_m), \text y_n=y_.$
For example, the truth table for a balanced ternary C-element with two inputs is

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 realizations of C-element. A dual-rail C-element can be realized on 2-input NANDs (NORs) only.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:
# 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. In particular, the so-called Maevsky's implementation M. Kuwako, T. Nanya
"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.J. A. Brzozowski, K. Raahemifar
"Testing C-elements is not elementary"
Working Conference on Asynchronous Design Methodologies (ASYNC) 1995, pp. 150–159. is a semimodular, but non-distributive (OR-causal) circuit loosely based on. 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. Yet another circuit with OR-causality, which operates as a Join element. A realization of C-element on two-input gates only has been proposed by Tsirlin and then synthesized by Starodoubtsev et al. using Taxogram languageN. 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. This circuit coincides with that attributed (without reference) to Bartky and can operate without the input latch. Yet another version of the C-element built on two RS latches has been synthesized by Murphy 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. Some speed-independent approaches 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.

Static and semistatic implementations

In his report 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. Generally, C-elements with different timing assumptions can be built on AND-OR-Invert (AOI)H. Zemanek
"Sequentielle asynchrone Logik"
Elektronische Rechenanlagen, vol. 4, no. 6, pp. 248–253, 1962. Also available in Russian as Г. Цеманек
"Последовательная асинхронная логика"
Mеждународный симпозиум ИФАК Теория конечных и вероятностных автоматов 1962, с. 232—245. or its dual, OR-AND-Invert (OAI) gate and inverter. Yet another option patented by Varshavsky et al.
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: $z_n = x_1 x_2 + (x_1 + x_2) \overline$. Some simple asynchronous circuits like pulse distributors can be built solely on majority gates.

Semistatic 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_\text$ 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). 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.

Generalizations and non-transistor implementations

Since the majority gate is a particular case of threshold gate, any of known realizations of threshold gate 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

:$y = \begin +1 & \text\ x_1+x_2+x_3 \geqslant +1,\\ 0 & \text\ x_1+x_2+x_3 = 0,\\ -1 & \text\ x_1+x_2+x_3 \leqslant -1 \end$

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.
Both the Maevsky and Tsirlin circuits are based actually on so-called David cell. Its fast transistor-level implementation is used in the semistatic C-element proposed. Yet another semistatic circuit using pass transistors (actually MUX 2:1) has been proposed.
Other technologies suitable for realizing asynchronous primitives including C-element, are: carbon nanotubes, single-electron tunneling devices, quantum dots, and molecular nanotechnology.A. J. Martin, P. Prakash
"Asynchronous nano-electronics: Preliminary investigation"
, IEEE Int. Symposium on Asynchronous Circuits and Systems (ASYNC) 2008, pp. 58–68.

References

{{Reflist, 30em

External links

Workcraft tool: Synthesis and verification of C-element

Logic gates
Digital electronics