The Elements of Computing Systems: Building a Modern Computer from First Principles (4 page)

Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online

Authors: Noam Nisan,Shimon Schocken

BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
9.79Mb size Format: txt, pdf, ePub
This chapter focuses on the construction of a family of simple chips called Boolean gates. Since Boolean gates are physical implementations of Boolean functions, we start with a brief treatment of Boolean algebra. We then show how Boolean gates implementing simple Boolean functions can be interconnected to deliver the functionality of more complex chips. We conclude the background section with a description of how hardware design is actually done in practice, using software simulation tools.
1.1.1 Boolean Algebra
Boolean algebra deals with Boolean (also called binary) values that are typically labeled true/false, 1/0, yes/no, on/off, and so forth. We will use 1 and 0. A Boolean function is a function that operates on binary inputs and returns binary outputs. Since computer hardware is based on the representation and manipulation of binary values, Boolean functions play a central role in the specification, construction, and optimization of hardware architectures. Hence, the ability to formulate and analyze Boolean functions is the first step toward constructing computer architectures.
 
Truth Table Representation
The simplest way to specify a Boolean function is to enumerate all the possible values of the function’s input variables, along with the function’s output for each set of inputs. This is called the truth table representation of the function, illustrated in figure 1.1.
The first three columns of figure 1.1 enumerate all the possible binary values of the function’s variables. For each one of the 2
n
possible tuples
υ
1
...
υ
n
(here
n
= 3), the last column gives the value of
f
(
υ
1
...
υ
n
).
Boolean Expressions
In addition to the truth table specification, a Boolean function can also be specified using Boolean operations over its input variables. The basic Boolean operators that are typically used are “And” (
x
And
y
is 1 exactly when both x and
y
are 1) “Or” (
x
Or
y
is 1 exactly when either
x
or
y
or both are 1), and “Not” (Not
x
is 1 exactly when
x
is 0). We will use a common arithmetic-like notation for these operations:
x
·
y
(or xy) means
x
And
y, x
+
y
means
x
Or y, and
means Not
x
.
To illustrate, the function defined in figure 1.1 is equivalently given by the Boolean expression
. For example, let us evaluate this expression on the inputs
x
= 0,
y
= 1,
z
= 0 (third row in the table). Since
y
is 1, it follows that x +
y
= 1 and thus
. The complete verification of the equivalence between the expression and the truth table is achieved by evaluating the expression on each of the eight possible input combinations, verifying that it yields the same value listed in the table’s right column.
Figure 1.1
Truth table representation of a Boolean function (example).
 
Canonical Representation
As it turns out, every Boolean function can be expressed using at least one Boolean expression called the
canonical representation
. Starting with the function’s truth table, we focus on all the rows in which the function has value 1. For each such row, we construct a term created by And-ing together literals (variables or their negations) that fix the values of all the row’s inputs. For example, let us focus on the third row in figure 1.1, where the function’s value is 1. Since the variable values in this row are
x
= 0,
y
= 1,
z
= 0, we construct the term
. Following the same procedure, we construct the terms
and
for rows 5 and 7. Now, if we Or-together all these terms (for all the rows where the function has value 1), we get a Boolean expression that is equivalent to the given truth table. Thus the canonical representation of the Boolean function shown in figure 1.1 is
f
(
x, y, z
) =
. This construction leads to an important conclusion: Every Boolean function, no matter how complex, can be expressed using three Boolean operators only: And, Or, and Not.
 
Two-Input Boolean Functions
An inspection of figure 1.1 reveals that the number of Boolean functions that can be defined over n binary variables is
. For example, the sixteen Boolean functions spanned by two variables are listed in figure 1.2. These functions were constructed systematically, by enumerating all the possible 4-wise combinations of binary values in the four right columns. Each function has a conventional name that seeks to describe its underlying operation. Here are some examples: The name of the Nor function is shorthand for Not-Or: Take the Or of
x
and y, then negate the result. The Xor function—shorthand for “exclusive or”—returns 1 when its two variables have opposing truth-values and 0 otherwise. Conversely, the Equivalence function returns 1 when the two variables have identical truth-values. The If-
x
-then-
y
function (also known as
x
→ y, or “
x
Implies
y”
) returns 1 when
x
is 0 or when both
x
and
y
are 1. The other functions are self-explanatory.

Other books

Rebel Without a Cake by Jacklyn Brady
Dishonorable Intentions by Stuart Woods
Fortune Knocks Once by Elizabeth Delavan
The Last Run by Todd Lewan
Soron's Quest by Robyn Wideman
Bugs by Sladek, John
Windswept (The Airborne Saga) by Constance Sharper