Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Circuit (computer science)
Résumé
In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a generalization of Boolean circuits and a mathematical model for digital logic circuits. Circuits are defined by the gates they contain and the values the gates can produce. For example, the values in a Boolean circuit are boolean values, and the circuit includes conjunction, disjunction, and negation gates. The values in an integer circuit are sets of integers and the gates compute set union, set intersection, and set complement, as well as the arithmetic operations addition and multiplication.
A circuit is a triple , where
is a set of values,
is a set of gate labels, each of which is a function from to for some non-negative integer (where represents the number of inputs to the gate), and
is a labelled directed acyclic graph with labels from .
The vertices of the graph are called gates. For each gate of in-degree , the gate can be labeled by an element of if and only if is defined on
The gates of in-degree 0 are called inputs or leaves. The gates of out-degree 0 are called outputs. If there is an edge from gate to gate in the graph then is called a child of . We suppose there is an order on the vertices of the graph, so we can speak of the th child of a gate when 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 is the length of the longest path in beginning at up to an output gate. In particular, the gates of out-degree 0 are the only gates of depth 1. The depth of a circuit is the maximum depth of any gate.
Level is the set of all gates of depth . A levelled circuit is a circuit in which the edges to gates of depth comes only from gates of depth 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.
The exact value of a gate with in-degree and label is defined recursively for all gates .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.