Computer circuit

Computer circuit

A circuit is a triple ${\displaystyle (M,L,G)}$, where

• ${\displaystyle M}$ is a set of values,
• ${\displaystyle L}$ is a set of gate labels, each of which is a function from ${\displaystyle M^{i}}$ to ${\displaystyle M}$ for some non-negative integer ${\displaystyle i}$ (where ${\displaystyle i}$ represents the number of inputs to the gate), and
• ${\displaystyle G}$ is a labelled directed acyclic graphwith labels from ${\displaystyle L}$.

The vertices of the graph are called gates. For each gate ${\displaystyle g}$ of in-degree ${\displaystyle i}$, the gate ${\displaystyle g}$ can be labeled by an element ${\displaystyle \ell }$ of ${\displaystyle L}$ if and only if ${\displaystyle \ell }$ is defined on ${\displaystyle M^{i}}$.

TerminologyEdit

The gates of in-degree 0 are called inputs orleaves. The gates of out-degree 0 are calledoutputs. If there is an edge from gate ${\displaystyle g}$ to gate ${\displaystyle h}$ in the graph ${\displaystyle G}$ then ${\displaystyle h}$ is called a childof ${\displaystyle g}$. We suppose there is an order on the vertices of the graph, so we can speak of the ${\displaystyle k}$th child of a gate when ${\displaystyle k}$ is less than the out-degree of the gate.

The size of a circuit is the number of nodes of a circuit. The depth of a gate ${\displaystyle g}$ is the length of the longest path in ${\displaystyle G}$ beginning at ${\displaystyle g}$ up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. Thedepth of a circuit is the maximum depth of any gate.

Level ${\displaystyle i}$ is the set of all gates of depth ${\displaystyle i}$. Alevelled circuit is a circuit in which the edges to gates of depth ${\displaystyle i}$ comes only from gates of depth ${\displaystyle i+1}$ or from the inputs. In other words, edges only exist between adjacent levels of the circuit. The width of a levelled circuit is the maximum size of any level.

EvaluationEdit

The exact value ${\displaystyle V(g)}$ of a gate ${\displaystyle g}$ with in-degree ${\displaystyle i}$ and label ${\displaystyle l}$ is defined recursively for all gates ${\displaystyle g}$.

${\displaystyle V(g)={\begin{cases}l&{\text{if }}g{\text{ is an input}}\\l(V(g_{1}),\dotsc ,V(g_{i}))&{\text{otherwise,}}\end{cases}}}$

where each ${\displaystyle g_{j}}$ is a parent of ${\displaystyle g}$.

The value of the circuit is the value of each of the output gates.