2.1   COMBINATIONAL CIRCUIT DESIGN

Combinational logic circuits have outputs that are strictly functions of their inputs, and have no memory, that is, state. The sequence of steps in synthesizing a design is as follows:

Problem definition: The required circuit may be described informally, in English sentences, or as an actual schematic diagram, as a truth table, or formally by a high-level definition language.

Boolean equations: The description is converted into a set of equations in terms of Boolean variables.

Simplification: The set of equations may often be simplified, for example, removing redundant terms.

Minimization: The equations may be manipulated further, depending on the eventual implementation technology, and the aims of minimization, such as maximum speed or minimum resource use.

Technology mapping: The equations are implemented in a particular technology. The set of primitive elements will vary between technologies, and for FPGAs, from one architecture to another. A complex equation might require several basic elements, while a simple one might share a basic element with another equation.

2.1.1   Boolean Algebra

Boolean algebra is concerned with variables that only have two states—true or false—and with expressions formed from such variables. While computer aids are often available, it is useful to be fluent in manipulating Boolean equations, usually to simplify them.

A number of alternative notations are in use for functions of Boolean variables, of which we will use the first given in each instance:

Negation, for example, Ā, ~A, A′, NOT(A)

Disjunction, for example, A.B, A ∩ B, A * B, AND(A, B)

Conjunction, for example, A + B, A ∪ B, OR(A, B)

There are a number of useful theorems including the following:

commutativity: the order of terms in a logical sum or product is of no consequence

A + B = B + A

A.B = B.A

associativity: the order of evaluation of the same function is of no consequence

(A + B) + C = A + (B + C)

(A.B).C = A.(B.C)

distributivity:

A.(B + C) = A.B + A.C

A + B.C = (A + B).(A + C)

DeMorgan:

Example   The following equation is in sum-of-products form. Simplify it and convert to product-of-sums form:

F = X.Y.Z + X. + X.Z + Y.

It can be expanded to the canonical form:

The last four terms include all combinations of Y and Z, so the expression can be simplified and reordered:

F = X + .Y.

Applying the second distributivity theorem, we obtain:

F = (X + ).(X + Y.)

The first term is always true, so we can eliminate it. Applying the theorem a second time, we obtain the product-of-sums form:

F = (X + Y).(X + )

For the most part, equation manipulation can be left to CAD programs. FPGAs vary considerably in the basic blocks that are used to implement combinational logic. The technology mapping process is discussed later, and depends on the number of signals that may fan-in to a block, and the generality or specificity of the function generated.

2.1.2   Multiplexers and Boolean Function Evaluation

Some circuit technologies, such as complementary metal-oxide semiconductor (CMOS), provide excellent electrically controlled switches. These can be easily connected to form multiplexers (MUX), which allow the selection of one from 2ⁿ inputs. For example, with a 4:1 MUX, controlled by two variables A and B, we can implement any of the 16 possible Boolean functions of them, as shown in Figure 2–1, by choosing appropriate Boolean values for the inputs C₀, C₁, C₂, C₃.

For example, the values 0, 1, 1, 0 provide the exclusive-OR function. By linking these inputs to FPGA configuration memory, we obtain a space-efficient and flexible means of evaluating Boolean functions. As the size of the multiplexer increases, the number of possible functions increases extremely rapidly. With a 32:1 MUX, which has five control inputs, we can generate any function of five-variables, of which there are 2²⁵ possibilities, that is, over 4 billion.

Figure 2–1. 4:1 MUX for Boolean function of two inputs.