Digital System Design with SystemVerilog: Combinational Logic Design
- 2.1 Boolean Algebra
- 2.2 Logic Gates
- 2.3 Combinational Logic Design
- 2.4 Timing
- 2.5 Number Codes
- Summary
- Further Reading
- Exercises
This chapter is from the book
This chapter is from the book
This chapter is from the book
Digital design is based on the processing of binary variables. In this chapter, we will review the principles of Boolean algebra and the minimization of Boolean expressions. Hazards and basic numbering systems will also be discussed.
2.1 Boolean Algebra
2.1.1 Values
Digital design uses a two-value algebra. Variables can take one of two values that can be represented by
- ON and OFF,
- TRUE and FALSE,
- 1 and 0.
2.1.2 Operators
The algebra of two values, known as Boolean algebra, after George Boole (1815–1864), has five basic operators. In decreasing order of precedence (i.e., in the absence of parentheses, operations at the top of the list should be evaluated first) these are:
- NOT
- AND
- OR
- IMPLIES
- EQUIVALENCE
The last two operators are not widely used in digital design. These operators can be used to form expressions. For example:
The symbol "+" means "OR," "." means "AND," and the overbar, for example, "
," means "NOT A."
2.1.3 Truth Tables
The meaning of an operator or expression can be described by listing all the possible values of the variables in that expression, together with the value of the expression in a truth table. The truth tables for the three basic operators are given in Tables 2.1, 2.2, and 2.3.
Table 2.1. NOT Operation
|
A |
NOT A ( |
|
0 |
1 |
|
1 |
0 |
Table 2.2. AND Operation
|
A |
B |
A AND B (A · B) |
|
0 |
0 |
0 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Table 2.3. OR Operation
|
A |
B |
A OR B (A + B) |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
1 |
In digital design, three further operators are commonly used: NAND (Not AND), NOR (Not OR), and XOR (eXclusive OR); see Tables 2.4, 2.5, and 2.6.
Table 2.4. NAND Operation
|
A |
B |
A NAND B |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
Table 2.5. NOR Operation
|
A |
B |
A NOR B |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
0 |
Table 2.6. XOR Operation
|
A |
B |
A XOR B (A |
|
0 |
0 |
0 |
|
0 |
1 |
1 |
|
1 |
0 |
1 |
|
1 |
1 |
0 |
B)The XNOR 
operator is also used occasionally. XNOR is the same as EQUIVALENCE.
2.1.4 Rules of Boolean Algebra
There are a number of basic rules of Boolean algebra that follow from the precedence of the operators.
- Commutativity
A + B = B + A
A · B = B · A
- Associativity
A + (B + C) = (A + B) + C
A · (B · C) = (A · B) · C
- Distributivity
A · (B + C) = A · B + A · C
In addition, some basic relationships can be observed from the previous truth tables.
The right-hand column can be derived from the left-hand column by applying the principle of duality. The principle of duality states that if eachANDis changed to an OR, each OR to an AND, each 1 to 0, and each 0 to 1, the value of the expression remains the same.
2.1.5 De Morgan's Law
There is a very important relationship that can be used to rewrite Boolean expressions in terms of NAND or NOR operations: de Morgan's Law. This is expressed as
2.1.6 Shannon's Expansion Theorem
Shannon's expansion theorem can be used to manipulate Boolean expressions.
F (1, B, C, D, . . .) means that all instances of A in F are replaced by a logic 1.