C element

Truth table and delay assumptions

For two input signals the C-element is defined by the equation y n = x 1 x 2 + ( x 1 + x 2 ) y n − 1 , which corresponds to the following truth table:

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

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

Note that the definition of C-element can be easily generalized for multiple-valued logic or even for continuous signals  if  x 1 = x 2 = . . . = x m  then  y n = a n y ( x 1 , x 2 , . . . , x m )  else  y n = y n − 1 . 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.

Gate-level implementations

A C-element can be built using only NAND, NOR and inverter gates. Many different implementations have been proposed. The so-called Maevsky's implementation is a speed-independent (internally non-distributive) circuit loosely based on Varshavsky et al., which in turn, is an improved version of. 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. This circuit coincides with that attributed (without reference) to Bartky in and can operate without the input latch. The approach proposed in 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 using Petrify tool.

Static and semi-static implementations

In his report Muller proposed to realize C-element as a majority gate with feedback. However, to alleviate hazards, which are 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) or its dual, OR-AND-Invert (OAI) gate and inverter.

Note that 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 ) y n ¯ . Note also that some simple asynchronous circuits like pulse distributors can be built solely on majority gates.

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 = { + 1  if  x 1 + x 2 + x 3 ⩾ + 1 ; 0  if  x 1 + x 2 + x 3 = 0 ; − 1  if  x 1 + x 2 + x 3 ⩽ − 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 d d 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. Yet another semi-static circuit using pass transistors has been proposed in.

There are also versions of semi-static C-element built on devices with negative differential resistance (NDR). 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, single electron tunneling devices, quantum dots and molecular nanotechnology.

Advanced topics

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 can be found.