Circuit Theory: Formal Definitions and Structural Evaluation
In computational theory, a circuit is more than just a physical arrangement of wires and transistors; it is a mathematical construct used to model the flow of information and the execution of functions. By defining a circuit as a structured graph, we can precisely analyze its complexity, size, and the efficiency with which it processes data.
The Formal Definition of a Circuit
Mathematically, a circuit is defined as a triplet (M, L, G). This triplet consists of three fundamental components that dictate how the circuit operates:
- M: A set of values that the circuit can process.
- L: A set of gate labels. Each label is a function that maps a specific number of inputs (represented by a non-negative integer i) from the set Mi to a single value in M.
- G: A labelled directed acyclic graph (DAG). A DAG is a graph where edges have a direction and there are no cycles, ensuring that the flow of information moves forward without looping back.
The vertices within this graph are known as gates. For any gate g with an in-degree of i (meaning it has i incoming edges), it can be assigned a label from L if and only if that label is defined for Mi.
[ไม่มีภาพประกอบ]Circuit Terminology and Structure
To analyze the behavior of a circuit, we use specific terminology to describe the roles and relationships of the gates within the graph G.
Gate Roles and Relationships
Gates are categorized based on their connectivity:
- Inputs (Leaves): Gates with an in-degree of 0. These are the starting points of the circuit.
- Outputs: Gates with an out-degree of 0. These represent the final results of the computation.
- Children: If an edge exists from gate g to gate h, then h is considered a child of g. Because vertices are ordered, we can identify the k-th child of a gate, provided k does not exceed the gate's out-degree.
Measuring Circuit Complexity
The efficiency and scale of a circuit are measured by its size, depth, and width:
- Size: The total number of nodes (gates) in the circuit.
- Depth: The length of the longest path in the graph starting from a specific gate g and ending at an output gate. Output gates themselves have a depth of 1. The overall depth of the circuit is the maximum depth among all its gates.
- Level: Level i consists of all gates that have a depth of i.
Levelled Circuits
A levelled circuit is a specialized structure where edges to gates of depth i originate only from gates of depth i + 1 or directly from the inputs. In these circuits, edges only exist between adjacent levels. The width of a levelled circuit is defined as the maximum size of any single level.
[ไม่มีภาพประกอบ]Evaluating Circuit Values
The evaluation of a circuit is the process of determining the output values based on the input values. This is done recursively. For a gate g with in-degree i and label l, the exact value V(g) is determined as follows:
- If g is an input, its value is simply the label l.
- If g is not an input, its value is the result of the function l applied to the values of its parents: V(g) = l(V(g1), ..., V(gi)).
The final value of the entire circuit is the value produced by each of its output gates.
Key Facts
- A circuit is formally defined as a triplet consisting of values (M), gate labels (L), and a directed acyclic graph (G).
- Inputs have an in-degree of 0; outputs have an out-degree of 0.
- Circuit size is the total count of nodes.
- Circuit depth is the longest path from any gate to an output.
- Levelled circuits restrict edges to adjacent levels or inputs.
- Circuit width is the maximum number of gates at any single level in a levelled circuit.
| Property | Definition | Key Metric |
|---|---|---|
| Size | Total number of nodes in the graph | Node Count |
| Depth | Longest path from a gate to an output | Path Length |
| Width | Maximum size of any level (levelled circuits only) | Max Level Size |
| Input | Gate with no incoming edges | In-degree = 0 |
| Output | Gate with no outgoing edges | Out-degree = 0 |
Frequently Asked Questions
What is a directed acyclic graph (DAG) in the context of circuits?
A DAG is a graph where edges have a specific direction and no path starts and ends at the same node. In circuits, this ensures that data flows from inputs to outputs without creating infinite loops.
How is the depth of a circuit calculated?
The depth of a single gate is the length of the longest path from that gate to an output. The depth of the entire circuit is the maximum depth value found among all its gates.
What distinguishes a levelled circuit from a standard circuit?
In a levelled circuit, edges are restricted; they can only connect gates in adjacent levels (from level i+1 to i) or connect inputs to a specific level.
How does the recursive evaluation of a gate work?
If a gate is an input, it takes a base value. If it is not an input, it takes the values of its parent gates and processes them through its assigned label function to produce a new value.
What is the difference between in-degree and out-degree?
In-degree refers to the number of edges entering a gate (inputs to the gate), while out-degree refers to the number of edges leaving a gate (outputs from the gate).