Home > Articles > Hardware

Digital System Design with SystemVerilog: Combinational Logic Design

  • Print
  • + Share This
Digital design is based on the processing of binary variables. In this chapter, Mark Zwolinski reviews the principles of Boolean algebra and the minimization of Boolean expressions. Hazards and basic numbering systems are also discussed.
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:

  1. NOT
  2. AND
  3. OR
  4. IMPLIES
  5. EQUIVALENCE

The last two operators are not widely used in digital design. These operators can be used to form expressions. For example:

026equ01.jpg

The symbol "+" means "OR," "." means "AND," and the overbar, for example, "a-bar.jpg," 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 (a-bar.jpg)

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 ab-bar.jpg

0

0

1

0

1

1

1

0

1

1

1

0

Table 2.5. NOR Operation

A

B

A NOR B a-plsu-b-bar.jpg

0

0

1

0

1

0

1

0

0

1

1

0

Table 2.6. XOR Operation

A

B

A XOR B (A u2295.jpg B)

0

0

0

0

1

1

1

0

1

1

1

0

The XNOR 026fig01.jpg 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.

  1. Commutativity

    A + B = B + A

    A · B = B · A

  2. Associativity

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

    A · (B · C) = (A · B) · C

  3. Distributivity

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

In addition, some basic relationships can be observed from the previous truth tables.

028equ01.jpg

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

028equ02.jpg

2.1.6 Shannon's Expansion Theorem

Shannon's expansion theorem can be used to manipulate Boolean expressions.

029equ01.jpg

F (1, B, C, D, . . .) means that all instances of A in F are replaced by a logic 1.

  • + Share This
  • 🔖 Save To Your Account