Have an Android phone?

Try our new game!

C gate

C gate (C element, Muller C-gate) is a memory-capable logic gate where all inputs vote for the element state, and then element keeps the current state until the inputs vote to change it[1].

C-gate, assembled from AND or OR gates.

If the number of inputs having logical one is equal to the number of inputs having logical zero, the element keeps the current state. In other words, the gate is capable for hysteresis. It is similar to the small parlament where the members need majority to accept some decision but once the decision is accepted they stick to it if the votes are equal and need majority again to agree on the opposite.

For the element with the two inputs, this means that the input combination 11 turns the element into state 1, combination 00 into state 0 and combinations 10 or 01 leave it in the same state where it has been before.

Truth table

The truth table of this gate is unusual, as it includes the "no change" cases. For these cases, the element keeps the state as it has been before the change of the input combination. If "no change" combination is the first combination since the element exists, the element obtains and keeps some random state:

First input Second input Output
0 0 0
0 1 no change
1 0 no change
1 1 1

C gate is not an universal logic gate: it needs some other element(s) in addition to build a functionally complete logic system.

Implementation

The two input C gate can be assembled from AND and OR logic gates (invertors are not required). It can also be made more simply if assembled directly from discrete elements as it is possible to use the positive feedback loop inside the OR gate rather than closing it through the AND elements. Such OR element must have the hysteresis similar to the hysteresis of the Schmitt trigger, with voting inputs pulling toward one of the two stable states.

The gate can also be built with more than two inputs. If the number of inputs is odd, there is no "equal number of inputs" case but some "big majority rule" (for instance, only the same value on all three inputs changes the state) can still be used to obtain the hysteresis[2]. This element can also be extended to the Asymmetric C-element where some inputs only have effect the operation in one of the transitions (positive or negative)[3].

Asymmetric C-element

Asymmetric C element (P - plus input, M - minus input, C - shared input).

Asymmetric C-elements have inputs which only effect the transitioning in one of the directions (0 to 1 or 1 to 0). Depending on the affected transition, they are called either plus input (P or +) or minus inputs (M or -). It still may have C inputs that affect both transitions.

For the element, shown in the example, signal in the inputs C and P is sufficient to bring the element in the active (logical 1) state: M does not count. However when the element is in the active state, the M input can keep it in this state regardless of the level in other inputs: as P does not count, C alone cannot make a majority.

Use

This type of element, proposed by David E. Muller, was first used on ILLIAC II supercomputer, built in 1962. It is usually used in asynchronous logic where the parts are largely autonomous and not governed by a clock circuit or global clock signal. Its typical role is to synchronize several independent processes, making the output independent on the delay differences between various parts of the system. C gate can also be used as a majority gate or as a toggle switch.

Theoretical biology

Theoretical biologists are also interested in these elements[4] as they may be used to describe the pairwise gene interaction[5], reconstructing the gene interaction network in the cell. This method uses the gene-expression data from microarray experiments as input.

References

  1. 1 Muller D.E.,Bartky W.S. (1959). A Theory of Asynchronous Circuits. Proc. Int'l Symp. Theory of Switching, Part 1, Harvard University Press, 1959, pages 204–243.
  2. 2 tams-www.informatik.uni-hamburg.de - C gate with 3 inputs that changes state when all inputs pass the same value
  3. 3 C element article in Wikipedia
  4. 4 Nguyen NP, Myers C, Kuwahara H, Winstead C, Keener J. (2010). Design and analysis of a robust genetic Muller C-element. J Theor Biol. 21;264(2):174-87. Epub 2009 Nov 13.
  5. 5 Gowda T, Vrudhula S, Kim S. (2009). Prediction of pairwise gene interaction using threshold logic. Ann N Y Acad Sci. 2009 Mar;1158:276-86.