AMAZON multi-meters discounts AMAZON oscilloscope discounts
Before you begin this journey into digital design, it is important that you understand the philosophy that will guide your study. If you have not read the Preface, do so now before you go on. There we discuss the issues that give rise to the need for good style and structure in digital design. Also, the Preface contains an outline of the guide, which will give you a view of where you are heading and how you will get there. It is particularly important that you understand our approach to the details of digital hardware. The overriding emphasis is to let the problem solution dictate the hardware, rather than allowing premature commitments to hardware to coerce the solution. This conscious suppression of hardware detail during most ,of the design pays big dividends. Chips and wires and power supplies are still important-they are vital to success, and you will need a good background in many areas of digital technology in order to become an accomplished designer-but too often in digital design the hardware has dominated the solution to the problem. To head off this common malady, we have deferred to the end of the guide almost all of the technology needed for your introduction to digital design. This information, in Part IV, does not depend on the material in Parts I through III. Read the topics in Part IV as you require or desire them while you are progressing through the first three parts of the text.
THE NEED FOR ABSTRACTION, FORMALISM, AND STYLE
Style
The human mind needs help when it tackles complex tasks. As we use the term, style is a method of partitioning a large problem into manageable subunits in a systematic and understandable way. The need for good style is more apparent as problems become larger. The most complex projects ever attempted by human beings have been computer programs; some, exceeding 500,000 lines of code, are so large that no one person is able to encompass the entire program, or even a significant part of it. The study of programming style was forced upon practitioners of the art as a way of gaining control over their projects. Programming style has blossomed into a rather well-defined set of techniques, bearing such names as "top-down" and "structured." The hardware of a large computer involves complexity on the same scale as these giant computer programs. The study of style in digital system design is not as well developed as its programming counterpart but is nonetheless essential to success. In this guide, we emphasize style.
Here are some rules of good style in digital design: (a) Design from the top down. The design starts with the specification of the complete system in a form compact enough that one person can readily comprehend it. The design proceeds by sectioning the digital system into subunits such as memory, arithmetic elements, and control, with well defined interrelationships. You may then describe each unit in more detail and still retain the ability to comprehend both the whole structure and the details of the units. This process continues until you have completely specified the system in detail, at which time construction may begin.
(b) Use only foolproof techniques that will keep you on the narrow path of safety in the design process. Digital hardware allows a high degree of flexibility in design-so much flexibility that designers can bury themselves in clever and unusual circuits. Uncontrolled use of such flexibility promotes undisciplined, unintelligible, and incorrect design of products. This phenomenon has its counterpart (to a less severe degree) in computer software because assembly language programming offers access to the full power of a digital computer. Experience in the solution of hardware and software problems has shown that we must restrict our design tools and techniques to those that can be shown to work reliably and understandably under a variety of circumstances.
(c) Use documentation techniques, at both the system level and the detailed circuit level, that clearly portray what you, the designer, were thinking when you reduced your problem first to an abstract solution and then to hardware. This often-violated precept boils down to common courtesy.
Put yourself in the position of a user or a maintainer of your hardware design; in such a position you would be grateful for clear, complete documentation.
Abstraction
In our context, abstraction means dealing with digital design at the conceptual level. The concept of a memory, a central theme in every computer, is an abstraction. When starting a design we need to deal with conceptual elements and their interrelationships: it is only later in the design process that we need to worry about the realization of the concepts in hardware. This freedom from concern about the details of various hardware devices is absolutely essential if we are to get a good start on a new design of any complexity. Start at the top and begin reducing the problem to its natural conceptual elements. For example, a computer will need a memory, an input-output system, an arithmetic unit, and so on. We ordinarily begin a design at this highly abstract level, and carry the conceptual process down, level by level. Thus, at the next level we draw a block diagram of an arithmetic unit by interconnecting functional units such as registers, control units, and data paths. The initial abstraction is a critical part of any design, since bad early planning will inevitably lead to bad implementations. There is no way to rescue a bad design with clever tricks of Boolean algebra or exotic integrated circuits.
Formalism
Formalism is the theory of the behavior of a system. In a digital design, formalisms help us to establish systematic rules and procedures with known characteristics.
Formalisms are important at all levels of design. In the traditional study of digital systems, one of the principal formalisms is Boolean algebra, the theory of binary logic, named after George Boole, who studied it long before the advent of digital computers. Boolean algebra is an essential tool for describing and simplifying the detailed logical processes at the root of digital design. Powerful and well developed as Boolean algebra is, it nevertheless becomes of less benefit as our level of abstraction increases. For instance, at the top ("systems") level of abstraction, where we are thinking in terms of the movement, storage, and manipulation of data, Boolean algebra is of little use. As we move closer to the detailed implementation-as our design becomes less abstract and more concrete Boolean algebra begins to be a useful tool.
At the systems level, the formalisms are less well developed, appearing as structures and rules rather than mathematical constructs. High-level formalisms are nevertheless of great importance to good design, for only by adopting systematic methods at all levels can we hope to transform correct concepts reliably into correct hardware.
LOGIC IN DIGITAL DESIGN
Imagine trying to speak without the words and, or, and not. Discarding these little words would severely handicap our ability to express complex thoughts.
Although and, or, and not each have several meanings in English, the most profound uses describe logical combinations of thoughts: "I have money for gas and my car is running"; "There is a paper jam or the printer is out of paper"; "She will not fail." Our thought processes are molded by our language, and when we design digital systems we will use and, or, and not in the same sense as above. In this guide, we denote the specific logical uses of and, or, and not by the symbols AND, OR, and NOT.
It is nearly always useful to formalize heavily used concepts; by so doing we achieve compactness and are able to handle more complexity than if we wrestle with informal concepts such as the normal English language uses of and, or, and not. To pave the way for a Boolean algebraic treatment of digital logic, we will formalize the concepts of logical constants, variables, and operators.
Logical Constants
The statement "There is a photodiode error" is either true or false. The operators AND, OR, and NOT are likewise concerned with two logical values, true and false.
We will concern ourselves only with logic systems that can be formalized with a binary set of logical constants, TRUE and FALSE. Since we use these concepts so heavily, it is worthwhile seeking abbreviations. We will represent TRUE by T or 1, and FALSE by F or 0. In this context 1 and 0 are not decimal numerical values; they are abbreviations for TRUE and FALSE, and nothing more. We will use 1 and T, 0 and F interchangeably in the text. Each abbreviation has its value, and both are widely used in digital design. In the study of hardware implementation of logic in Section 2, we will show a strong bias toward the T ,F notation, to avoid a common point of confusion. On the other hand, in much of this section the 1,0 form for TRUE and FALSE is convenient. Be prepared to accept and use either form.
Logical Variables
Consider the declaration
A = photodiode error
We use the logical variable A as an abbreviation for the cumbersome phrase "photodiode error" to achieve compactness. The variable A can have two values, T or F. If we do not have a photodiode error, then A = F; if we do, then A = T. Although it is possible to use single letters to represent logical elements, as we have above, it is usually better to use a more recognizable abbreviation, such as
PDE = photodiode error
In general, the abbreviations should be a compromise between clarity and brevity. It is not really necessary to abbreviate at all. We could use PHOTODIODE.ERROR as the name of the logical variable, but it is too long to be convenient. A is short but conveys no meaning; PDE is a good compromise.
We often use numbers in logical variables to indicate a particular member of a set of variables. A common unit of computer information is the 8-bit byte. If we needed to examine the individual bits of the byte, we might choose to assign distinct names to the bit values:
B0 = 1 in leftmost bit
B7 = 1 in rightmost bit
Other notations for sets of variables will suggest themselves. Instead of the distinct names for bits in the byte, we might choose to use a subscripted variable B0 ... B7 , with equivalent meanings.
In this guide we will capitalize the letters in the names of logical variables and will always start each name with a letter. To preserve the mnemonic value, names of variables may include periods as separators; GO.ON is an example.
Truth Tables
Consider a set of logical variables, each variable of which may have one of two values, Tor F. In digital design we are interested in combining logical variables (e.g., using AND, OR, and NOT) to produce new variables that again have only two possible values, T or F, for any combination of given variable values. In other words, we wish to study binary functions of binary variables.
For a set of logical variables, we may define any desired function by giving the function value for each possible set of variable values. A tabular form with input variables on the left and the function on the right is useful for this display.
For example, here is a logical function X of three variables A, B, and C, shown in both the 1,0 and the T , F notations.
Such a display is called a truth table. Having chosen an ordering of the input variables (A, C, B in this case), we list all possible combinations of the variables' values, in binary numeric order. A tabulation in this standard form is called a canonical truth table. "Canonical" means standard. For three variables, the canonical truth table has 2^3 = 8 rows, arranged from binary 000 through binary 111. Since each binary bit pattern corresponds to a decimal number, we may describe a row of a canonical truth table by its decimal number equivalent.
For example, the row corresponding to the variable values 0110 for a four-variable function may be called row 6. When convenient, you may write the row numbers on the left of the canonical truth table.
For canonical truth tables, we may compactly describe the function by a vector of function values. For example, the three-variable truth table for X above yields an eight-element vector X(A,C,B) = (0,1,1,0,1,0,0,0) Although we usually choose to list the values of variables in canonical order, any other order of rows displays the same information. The following two truth tables are equivalent, but the right-hand table lacks the useful uniformity of the canonical form on the left:
Logical Operators and Truth Tables
We will now give a precise definition of the three logical operators AND, OR, and NOT. NOT. We represent logical NOT by the overscore. Thus, if PDE is a logical variable, then
NOT PDE = PDE
In words, we would describe the notation PDE as "PDE not." We may define NOT by listing in a truth table all possible values for an arbitrary logical variable, and the corresponding values of the logical NOT of that variable. Since a logical variable A can have only two values, 1 and 0, the following list is exhaustive:
ili
A o 1 1 0
We regard the formal definition of logical NOT to be given by its truth table. Remember that 1 and ° represent TRUE and FALSE.
AND. We represent logical AND by a dot separating two logical variables we write BAND C as B·C. We shall faithfully use the "." symbol to represent the AND operator even though some authors omit it when dealing with single letter logical variables. Thus, if you insist upon single-letter names, you might interpret BC as B·C. This is dangerous because we may want to name a single logical variable with the two-letter name BC. In real-world logic design, single letter names are not descriptive enough to be of use. There are only 26 possible single-letter names and a typical design may require many more than 26 names.
We therefore give up the dubious advantage of having an implied AND for the real advantage of multiletter names for logical variables.
We will define AND with a truth table. There are two independent variables in the logical AND, each of which can assume either of the two values, 1 and O. Therefore, specifying the function value for each of the four combinations of inputs completely defines AND:
The table corresponds to our intuitive notion of AND in that B·C is true only if both Band C are simultaneously true.
Just as we may generalize the English use of and to encompass more than two variables, we can do so for the formal logical AND. The truth table for
For more than three variables, the truth table becomes unwieldy, and we revert to a verbal definition of the logical AND: The logical AND of several variables is true only when all the variables are simultaneously true.
OR. The symbol for logical OR is the + sign. Do not confuse this with the use of + in other contexts to represent arithmetic addition. Since in logic design the uses of logical OR will vastly outnumber the uses of an arithmetic plus, we choose a convenient single symbol for the OR operator and we use the more cumbersome word "plus" or the symbol "( +)" for an arithmetic plus.
Here are two word statements translated into their corresponding logic design notations
A is true if B OR C is true
2 added to 3 is 5
A = B+C
5 = 2 plus 3, or 5 = 2 ( + ) 3
The defining truth table for a two-input logical OR is:
As with the AND operator, we may generalize the definition of the logical OR to more than two input variables. In words, the output is true if at least one of the inputs is true. For instance,
AY PDE X AY + PDE + X
This completes our definition of AND, OR, and NOT. These logical operators operate on input variables to yield a single output. The NOT operates only on single variables, while AND and OR fundamentally operate on two inputs. For our convenience we may also think of AND and OR as multi-input operators.
Truth tables are useful in many designs, but we need a more compact and powerful tool for representing logical manipulations. An algebra of logical operators, called Boolean algebra in honor of George Boole, who first explored the properties of the logical operators, is analogous to the familiar algebra of arithmetic operators.
In the next section, we present some simple but important Boolean algebraic results.
ELEMENTS OF BOOLEAN ALGEBRA
Basic Manipulations
Boolean algebra is important to hardware designers because it allows the compact specification and simplification of logic formulas. Physical devices can perform the AND and OR functions, and it is this fact that raises Boolean algebra from the realm of interesting theory to the role of a vital design tool. The algebra may be developed from any of several starting points. Modern mathematicians derive Boolean algebra from a compact set of abstract postulates, producing an elegant and rigorous theory; however, in building a useful tool to assist structured digital design, we best achieve our goals by emphasizing the relationship of truth tables to logic equations. Truth tables and allied tabular displays play an important role in digital design and implementation. Therefore, we will assume as our starting point the existence of the two binary values TRUE (T or 1) and FALSE (F or 0), and the three operators AND, OR, and NOT, with behavior described by their truth tables.
Boolean algebraic formulas follow certain conventions. Our intuition tells us that we want the operators AND and OR to commute (e.g., A + B == B + A) and associate [e.g., A + (B + C) == (A + B) + e]. The operators also distribute according to the relations
A-(B + e) == (A-B) + (A-C)
A + (B-e) == (A + B)-(A + e)
The conventional hierarchy of operator action in complex expressions is First: NOT
then: AND
last: OR
Our notation for logical NOT (the overscore) explicitly shows the scope of action of the NOT operation, so the only possible confusion in evaluating expressions would occur with AND and OR. As the hierarchy shows, AND takes precedence.
As an example, consider
x = A + B-e
Evaluation is in the order specified below by the parentheses, innermost parenthesized expressions being evaluated first. Thus
x = (A + (B-( e))))
Parentheses are useful in Boolean equations to override the normal hierarchy, just as we use them for similar purposes in conventional algebra.
Below are some fundamental relations of Boolean algebra; memorize these results.
Each identity involving AND or OR operators comes in two forms, one emphasizing AND, the other emphasizing OR. This principle of duality is a characteristic of Boolean algebra, and it has important applications in the study of logic and in the implementation of logic functions with physical devices. The dual identities are related by this rule: Change each AND to OR, and each OR to AND, and change each T to F, and each F to T. Equation (eqn. 6) is the well-known De Morgan's law. It is of special importance because it allows us to convert Boolean operators from AND to OR, and vice versa.
You may prove each of the foregoing identities by using the truth-table definitions of the logical operators. To illustrate the art of proving theorems with truth tables, we will prove the validity of De Morgan's law. Start with the form A ° B = A + B. Develop truth tables for the left -hand side and for the right-hand side of the identity. (When convenient, we may show several functions [outputs] in the same table: we write two or more truth tables in one package.)
A truth table is an exhaustive list of function values for each possible combination of inputs; therefore, if two truth tables have identical rows, the functions behave identically. You see that the truth table for A OR B is the same as that for A + B; this proves Eq. (eqn. 6).
De Morgan's law extends to more than two variables. For example, the following identities are valid.
A+B+C=A o B o C
Several other Boolean identities find frequent use in our design work. You may demonstrate each relationship using truth tables or using the previous Boolean identities.
The left-hand form of Eq. (eqn. 8) is not immediately obvious, but it is of great help in reducing the complexity of commonly occurring Boolean expressions.
After De Morgan's law, Eq. (eqn. 9) is perhaps the most widely used relation. It is the basis for several systematic Boolean simplification procedures. Presently, we will develop the one simplification method, Karnaugh maps, that will be of most benefit to our design work.
Truth tables serve as an easy means of verifying the validity of small Boolean equations, whereas the Boolean identities presented above are useful in manipulating both large and small Boolean equations. Here is an example of Boolean algebraic manipulations.
Equations from Truth Tables
If the truth table and logic equation are to work hand in hand as design aids, we must be able to derive a logic equation for a function from its truth table.
Consider this example:
In words, W is true only if A is true and B is false (from row 2). More formally, W = A-B. Another example is:
Here, our intuitive understanding of the truth table is that Y is true whenever A is false and B is false (row 0), or whenever A is true and B is false (row 2), or whenever A is true and B is true (row 3). Thus Incidentally, we may simplify this equation:
Y = A·Jj + A·Jj + A·B (eqn. 10)
= Jj + A·B
= lJ +A
[by Eq. (eqn. 9)]
[by Eq. (eqn. 8)] (eqn. 11)
Viewing this truth table another way, we may say that Y is false only when A is false and B is true (row 1):
y = A·B (eqn. 12)
We have two equations for Y derived from the same truth table--Eqs. (eqn. 10) and (eqn. 12). Can you show that the expressions for Yare equivalent? Which way is best for writing equations from truth tables-reading true conditions for the function, or reading false conditions? Both ways result in equivalent expressions, usually in somewhat different form. For equations of more than two variables, when there are many rows in the truth table, you will usually wish to use the method that involves the fewer AND terms. In this example, Eq. (eqn. 12), derived from the false function values, yields the more direct and simple result.
Sum-of-products form. Equation (eqn. 10) (and also Eq. [1-11]) expresses the function Y in the sum-of-products form. This is the most common form for deriving Boolean equations from truth tables, and in this context the form fits nicely with our thought processes. The name "sum of products" comes from an analogy of the Boolean operator symbols with those of arithmetic: the expression is a sum (OR) of product (AND) terms.
In sum-of-products form, a product term consists of the logical AND of a set of operands, each operand being a logic variable or its negation. (A trivial form of product term consists of a single variable or its negation.) A variable's name must appear at most once in a product term. For example, A, A·Jj, and A ·B·e are valid product terms, whereas A·A and A ·B·B·e, although valid Boolean expressions, are not proper product terms.
A product term containing exactly one occurrence of every variable (either asserted or negated) is called a minterm or a canonical product term. A function expressed as a logical OR of distinct minterms is in canonical sum-of-products form or disjunctive normal form. Our intuitive method for deriving equations from truth tables yields the canonical sum-of-products form, as in Eq. (eqn. 10). An expression may be in sum-of-products form yet not be canonical. Equation (eqn. 11) is a non-canonical sum-of-products expression.
We may now state formal prescriptions for deriving sum-of-products logic equations from canonical truth tables: To derive a sum-of-products form for a function from a canonical truth table, write the OR (sum) of the minterms for which the function is true.
Similarly, to derive a sum-of-products form for the complement of a function from a canonical truth table, write the OR of the minterms for which the function is false.
Applying these rules to the previous truth table yields Eqs. (eqn. 10) and (eqn. 12). For n-variable functions, there are 2n possible minterms. A minterm is sometimes designated by mj , where i is the number of the single canonical truth table row for which the minterm yields truth. For example, m4 = A o B o e yields truth only for variable values A = 1, B = 0, e = 0; this corresponds to row 4, since binary 100 is decimal 4. Again, m2 = A o B o C produces truth only for row 2 (binary 010). (The name minterm denotes that the term is true for only one row of the table.) With this notation, we may describe canonical sum-of products equations as sums of minterms. Equation (eqn. 10) becomes Y = mo + m2 + m3' Although this notation is important in certain developments of Boolean algebra, we will not use it frequently in this guide.
Equation (eqn. 12) is a canonical sum-of-products equation for Y, albeit a somewhat trivial form containing only one term. We may use the minterm notation for this form also:
Y=m1
Product-of-sums form. There is another formulation of logic expressions from truth tables: the product-o/-sums form. This form consists of the AND (the product) of a set of OR terms (the sums), such as (A + B)o(A + B)o(B). In a product-of-sums expression, a sum term consists of the logical OR of a set of operands, each operand being a logic variable or its negation, and each variable appearing at most once.
A sum term that contains exactly one occurrence of every variable (either asserted or negated) is called a maxterm or canonical sum term. A function expressed as a logical AND of distinct maxterms is in canonical product-of-sums form or conjunctive normal form. The product-of-sums notation is not much used in practical design, since it lacks the sum-of-products' easy kinship with our thought processes. An expression may be in product-of-sums form yet not be canonical, if one or more of the sum terms is not a maxterm. For a three variable function, A + B + e is a maxterm; B + e is not. W = (P + Q + R)o (P + Q + R) is in canonical product-of-sums form; W = (P + Q)o(P + Q + R) is not canonical.
The prescriptions for forming product-of-sums logic equations from truth tables are:
To derive a product-of-sums form of a function from a canonical truth table, write the AND (product) of each maxterm for which the function is false.
Similarly, to derive a product-of-sums form for the complement of a function, write the AND of each maxterm for which the function is true.
Applying these rules to the previous truth table, we have
Y = (A + B)
Y = (A + B)e(A + B)e(A + B) (eqn. 13)
The first equation agrees with Eq. (eqn. 11), obtained by simplifying the sum-of products form in Eq. (eqn. 10). With the aid of the distributive law, we may simplify Eq. (eqn. 13) to yield in agreement with Eq. (eqn. 12).
A maxterm is true for every row of the canonical truth table except one; we sometimes specify the maxterm by Mj , where i is the row number for which the maxterm is false. For example, (A + B + C) is true for every combination of values of variable except A = 1, B = 0, C = 1, which designates row 5 (binary 101 = decimal 5). Maxterm Mo is (A + B + C), since only for variable values 000 does the term produce a false value. The name maxterm connotes that the term is true for all but one set of variable values. We occasionally write canonical product-of-sums expressions, analogous to the sum-of-products formalism, as products of maxterms. For instance, the products of sums above become
Y = (A + B) = M1
Y = (A + B) (A + B) (A + B) = M0 M2 M3
To illustrate the four rules for producing canonical equations, we derive the equations for a function W of three variables:
Sum of products on true outputs:
W = JeKeL + JeKer + JeKeL (eqn. 14)
Sum of products on false outputs:
w = J o K o L + J o K o L + J o K o L + J o K o L + J o K o L
Product of sums on false outputs:
W = (J + K + L) o O + K + L) o O + K + L) 0( + K + L) o (J + K + L)
Product of sums on true outputs:
W = (J + K + L) o (J + K + L) o (J + K + L)
You should simplify each equation, using algebraic identities, and verify that the equations are equivalent. NEXT>>
Related Articles -- Top of Page -- Home