Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

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 ...