In a model of computation taking errors into account, the natural assumption is that errors occur everywhere. The most familiar kind of computer, which is separated into a single processor and memory, seems extremely vulnerable under such conditions: while the processor is not “looking”, noise may cause irreparable damage in the memory. Let us therefore rather consider computation models that are parallel: information is being processed everywhere in the system, not only in some distinguished places. Then error correction can be built into the work of every part of the system. We will concentrate on the best known parallel computation model: Boolean circuits.
Let us look inside a computer, (actually inside an integrated circuit, with a microscope). Discouraged by a lot of physical detail irrelevant to abstract notions of computation, we will decide to look at the blueprints of the circuit designer, at the stage when it shows the smallest elements of the circuit still according to their computational functions. We will see a network of lines that can be in two states (of electric potential), “high” or “low”, or in other words “true” or “false”, or, as we will write, 1 or 0. The points connected by these lines are the familiar logic components: at the lowest level of computation, a typical computer processes bits. Integers, floating-point numbers, characters are all represented as strings of bits, and the usual arithmetical operations can be composed of bit operations.
The variables in are sometimes called Boolean variables, Boolean variables or bits.
Example 4.2 Given an undirected graph with nodes, suppose we want to study the question whether it has a Hamiltonian cycle (a sequence listing all vertices of such that is an edge for each and also is an edge). This question is described by a Boolean function as follows. The graph can be described with Boolean variables (): is 1 if and only if there is an edge between nodes and . We define if there is a Hamiltonian cycle in and 0 otherwise.
There are only four one-variable Boolean functions: the identically 0, identically 1, the identity and the negation: . We mention only the following two-variable Boolean functions: the operation of conjunction (logical AND):
this is the same as multiplication. The operation of disjunction, or logical OR:
It is easy to see that : in other words, disjunction can be expressed using the functions and the operation of composition. The following two-argument Boolean functions are also frequently used:
A finite number of Boolean functions is sufficent to express all others: thus, arbitrarily complex Boolean functions can be “computed” by “elementary” operations. In some sense, this is what happens inside computers.
The proof can be found in all elementary introductions to propositional logic. Note that since can be expressed using , this latter set is also a complete basis (and so is ).
From now on, under a Boolean expression (formula), we mean an expression built up from elements of some given complete basis. If we do not mention the basis then the complete basis will be meant.
In general, one and the same Boolean function can be expressed in many ways as a Boolean expression. Given such an expression, it is easy to compute the value of the function. However, most Boolean functions can still be expressed only by very large Boolean expression (see Exercise 4.2-4).
A Boolean expression is sometimes large since when writing it, there is no possibility for reusing partial results. (For example, in the expression
the part occurs twice.) This deficiency is corrected by the following more general formalism.
A Boolean circuit is essentially an acyclic directed graph, each of whose nodes computes a Boolean function (from some complete basis) of the bits coming into it on its input edges, and sends out the result on its output edges (see Figure 4.2). Let us give a formal definition.
Figure 4.2. The assignment (values on nodes, configuration) gets propagated through all the gates. This is the “computation”.
For every node there is a natural number showing its number of inputs. The sources, nodes with , are called input nodes: we will denote them, in increasing order, as
To each non-input node a Boolean function
from the complete basis is assigned: it is called the gate of node . It has as many arguments as the number of entering edges. The sinks of the graph, nodes without outgoing edges, will be called output nodes: they can be denoted by
(Our Boolean circuits will mostly have just a single output node.) To every non-input node and every belongs a node (the node sending the value of input variable of the gate of ). The circuit defines a graph whose set of edges is
We require for each (we identified the with the natural numbers ): this implies that the graph is acyclic. The size
of the circuit is the number of nodes. The depth of a node is the maximal length of directed paths leading from an input node to . The depth of a circuit is the maximum depth of its output nodes.
for , . The function can be extended to a unique configuration on all other nodes of the circuit as follows. If gate has arguments then
For example, if , and () are the input nodes to then . The process of extending the configuration by the above equation is also called the computation of the circuit. The vector of the values for is the result of the computation. We say that the Boolean circuit computes the vector function
The assignment procedure can be performed in stages: in stage , all nodes of depth receive their values.
We assign values to the edges as well: the value assigned to an edge is the one assigned to its start node.
The depth of a Boolean circuit can be viewed as the shortest time it takes to compute the output vector from the input vector by this circuit. Az an example application of Boolean circuits, let us develop a circuit that computes the sum of its input bits very fast. We will need this result later in the present chapter for error-correcting purposes.
The depth of our circuit is clearly , since the output must have a path to the majority of inputs. In order to compute the majority, we will also solve the task of summing the input bits.
(a) Over the complete basis consisting of the set of all 3-argument Boolean functions, for each there is a Boolean circuit of input size and depth whose output vector represents the sum of the input bits as a binary number.
(b) Over this same complete basis, for each there is a Boolean circuit of input size and depth computing a near-majority.
Proof. First we prove (a). For simplicity, assume : if is not of this form, we may add some fake inputs. The naive approach would be proceed according to Figure 4.3: to first compute . Then, to compute , and so on. Then will indeed be computed in stages.
It is somewhat troublesome that here is a number, not a bit, and therefore must be represented by a bit vector, that is by group of nodes in the circuit, not just by a single node. However, the general addition operation
when performed in the naive way, will typically take more than a constant number of steps: the numbers have length up to and therefore the addition may add to the depth, bringing the total depth to .
The following observation helps to decrease the depth. Let be three numbers in binary notation: for example, . There are simple parallel formulas to represent the sum of these three numbers as the sum of two others, that is to compute where are numbers also in binary notation
Since both formulas are computed by a single 3-argument gate, 3 numbers can be reduced to 2 (while preserving the sum) in a single parallel computation step. Two such steps reduce 4 numbers to 2. In steps therefore they reduce a sum of terms to a sum of 2 numbers of length . Adding these two numbers in the regular way increases the depth by : we found that bits can be be added in steps.
To prove (b), construct the circuit as in the proof of (a), but without the last addition: the output is two -bit numbers whose sum we are interested in. The highest-order nonzero bit of these numbers is at some position . If the sum is more than then one these numbers has a nonzero bit at position or . We can determine this in two applications of 3-input gates.
4.2-1 Show that is a complete basis.
4.2-3 Let us fix the complete basis . Prove Proposition 4.6 (or look up its proof in a textbook). Use it to give an upper bound for an arbitrary Boolean function of variables, on:
(a) the smallest size of a Boolean expression for ;
(b) the smallest size of a Boolean circuit for ;
(c) the smallest depth of a Boolean circuit for ;
Hint. For a constant , upperbound the number of Boolean circuits with at most nodes and compare it with the number of Boolean functions over variables.]
4.2-5 Consider a circuit with inputs, whose single output bit is computed from the inputs by levels of 3-input majority gates. Show that there is an input vector which is 1 in only positions but with which outputs 1. Thus a small minority of the inputs, when cleverly arranged, can command the result of this circuit.