This appendix provides a brief set of notes on Boolean algebra laws and their use. It is assumed that the reader already has knowledge of these laws. The appendix is provided as a reference only for the Boolean algebra used in this book.
The exclusive OR and exclusive NOR (Figure A.2) are well used in logic systems.
These are presented in terms of the Boolean logic equation and gate circuit.
The auxiliary law (Figure A.7) is particularly significant and much used in this book.
The answer to the first question in Figure A.7 is as follows
The answer to the second question in Figure A.7, /p + (q · p) = ?, is, of course, /p + q. Note that the auxiliary (Aux) rule is just a special case of the consensus theorem.
Consider the equation
Y = x + /x · w · z.
In the equation, if w = z = 1, then
Y = x + /x · 1 · 1 = x + /x,
which is 1.
However, it is possible under some conditions of gate delay that a logic 0 glitch can occur (this is known as a static 1 hazard). To avoid this, a cover term can be added, made up from the literals w and z, to make Y stay at logic 1:
Y = x + /x · w · z + w · z.
Thus, when w and z are both 1:
Y = x + /x + 1,
thus covering the potential terms x + /x and preventing the glitch.
Now consider the equation
Y = x + /xw.
Now add a cover term thus:
So applying the consensus theorem to Y = x + /xw results in Y = x + w as obtained using the auxiliary rule.
In effect the Aux rule is just a special case of the consensus theorem; that is, it is an auxiliary to the consensus theorem.
Another example (using the Aux rule):
since
In the following two examples the term to be removed is crossed out thus /R.
Therefore:
Y = s · t · /x + s · t · z.
Note that the reduction here is in the number of inputs. This might be relevant in some cases, but when implementing with PLD devices it may not be so relevant owing to the large number of inputs available in the AND gate array of the PLD.
Remember, however, that the application of the Aux rule eliminates a static 1 hazard and, hence, a potential glitch: in the case of P, the term r + /r; in the case of Y, /x + x.
In Chapters 3, 4 and 9, it was shown that signal delay can affect the behaviour of a circuit. The basic effect of signal delay is clearly illustrated in Figure A.8, where the points on the two input signals A and /A where an output change can occur are seen for each gate type.
In the case of AND (or NAND) gates, it is the point at which the two overlapping signals are both at logic 1.
In the case of OR (or NOR) gates, it is the point at which the two overlapping signals are both at logic 0.
The effect is to produce an unwanted glitch at the gate output. These so-called ‘glitches’ can result in maloperation in an FSM. They can occur in a logic system where two signals (they do not need to be the same signals inverted, as shown in Figure A.8) change state at the same time. This could be a change of two state variables; for example, when unit distance coding is not used in a state diagram.
This kind of behaviour can manifest itself within a logic block where two signal changes occur, due to the delays through the logic gates. Further work on this type of behaviour can be found in most textbooks on advanced digital design. These are not discussed any further, as they are beyond the scope of this book.
De Morgan's theorem (Figure A.9) is used significantly, particularly in Chapter 9.
De-Morgan's rules are often used to convert from NAND, /(a · b), to NOR, /a + /b, and from NOR, /(a + b), to NAND, /a · /b.
Z = x · y + /x · /y.
Use the De Morgan rule: /(A + B) = /A · /B, where A and B can be any product term. So, in the following example, A is replaced by x · y, and B is replaced by /x · /y:
Use the De Morgan rule:/(A · B) = /A + /B, where A and B can be any product term. So, in the following example, A is replaced by x · y and B is replaced by /x · /y:
This rule is used in the Karnaugh map method of Boolean algebra minimization and works on the idea that b + /b = 1; so, in the equation
thus eliminating the literal c (in this case).
The following example makes use of the Logical adjacency rule:
In the next example, the rule is applied twice:
The logical adjacency rule is used in most of the work on synchronous FSM design, and also in establishing correct operation in asynchronous (event) FSM design in Chapter 9.
Both the Aux rule and the logical adjacency rules are often used in the reduction of the flip-flop D, and T equations. That is, a typical equation from a state diagram could be
This is obtained from
Now:
AB + AB = AB.
Therefore:
A · d = B · st + AB + A · sp.
This appendix has looked briefly at the basic laws of Boolean algebra and discussed some of the Boolean techniques used in this book. It provides a reference source for those readers who have not used Boolean algebra for some time. Further information can be found in most books on digital logic.
3.128.200.220