How To Draw Logic Circuits Using Nand
Logic & circuits
by Carl Burch, Hendrix College, September 2022
Logic & circuits by Carl Burch is licensed under a Artistic Commons Attribution-Share Alike 3.0 Usa License.
Based on a work at www.cburch.com/books/logic/.
Contents
i. Logic circuits
2. Building logic circuits
ii.ane. Boolean expressions
2.ii. Boolean algebra laws
two.iii. Sum of products
iii. Simplifying circuits
3.1. Measuring circuit efficiency
3.2. Karnaugh maps
3.3. A more complex Karnaugh map
iv. Other logic gates and universality
To sympathize how computers work, nosotros will want to sympathise the fundamentals of digital circuits. As it turns out, digital circuits are congenital on the foundation of basic logic.
one. Logic circuits
At the most bones level, of course, a computer is an electrical circuit build using wires. We'll think of each wire in the circuit every bit carrying a single data chemical element, called a flake. The word bit comes from Binary digIT, using the term binary because a bit tin can accept either of ii possible values, 0 and ane. In electric terms, yous can think of cypher volts representing 0 and 5 volts representing 1; merely for our purposes, the specific voltages aren't of import — and indeed there are varying systems for interpreting voltage levels as 0 or ane. (People have experimented with more than two different voltage levels, but this ends upward leading to circuits that are more complex and end upward being less constructive than the binary system.)
Here is an example showing the diagram of a uncomplicated logic circuit.
Figure 1: A uncomplicated logic circuit.
This diagram consists of some peculiar shapes continued with some lines. The lines correspond wires; the shapes stand for what are called logic gates, which we'll written report soon.
We'll think of each wire as carrying a bit until it hits a gate. You tin see that some wires intersect in a small, solid circle: This circle indicates that the wires are connected, and and so values coming into the circumvolve continue downwardly all the wires continued to the circle. If two wires intersect with no circumvolve, this means that one wire goes over the other, similar an Interstate overpass, and a value on i wire has no influence on the other.
(In our circuits, we'll draw systems of wires using unlike colors, so you tin tell that two wires don't bear upon when you encounter them in different colors. Traditionally, though, circuits are drawn using blackness and white only, and these dots are crucial for agreement when wires intersect and when they overlap.)
Suppose that nosotros take our case excursion from Figure 1 and transport a 0 bit on the upper input (x) and a 1 scrap on the lower input (y). Then these inputs would travel down the wires until they hit a logic gate.
So what happens when an input reaches a logic gate? It depends on what blazon of logic gate information technology is. In that location are iii major types of logic gates, depicted using iii different shapes.
Here'southward a handy mnemonic for distinguishing the shapes for OR and AND: The symbol for the AND gate looks similar a uppercase letter D, which you can find in the word AND.
Effigy 2: Logic gate beliefs.
(a) Non gate (b) AND gate (c) OR gate 
a o 0 1 ane 0
a b o 0 0 0 0 i 0 1 0 0 one 1 one
a b o 0 0 0 0 ane one 1 0 i 1 1 1
After the values filter through the gates based on the behaviors of Figure two, the values in the circuit will be as follows.
Based on this diagram, we tin meet that when 10 is 0 and y is ane, the output o is 1.
Past doing the same sort of propagation for other combinations of input values, we can build up the following table showing how this circuit behaves for unlike combinations of inputs.
10 y o 0 0 0 0 1 ane 1 0 1 1 i 0
To interpret this tabular array, allow'southward examine the second row: information technology has a 0 in the ten column, one in the y cavalcade, and i in the o column. This indicates that if the x input is 0 and the y input is i, then the excursion'south output o volition be 1.
Such a table is called a truth tabular array. A truth table contains a row for every possible combination of input values and each row tells what the value of the excursion's output would be for that combination of inputs. In this example table, we have four rows, representing each possible combination of x and y. Our truth table would have viii rows if the circuit had iii inputs; and it would have sixteen if the excursion had four inputs.
2. Building logic circuits
In the previous section, nosotros saw how logic circuits work. This is helpful when you want to understand how a circuit behaves. But reckoner designers often face up the contrary trouble: Given a desired behavior, how can we build a excursion behaving that manner? Or to ask the same basic question: How can we convert a truth table into a logic circuit?
In this section, we await at a systematic technique for designing circuits. Starting time, though, nosotros'll take a necessary detour through the report of Boolean expressions.
2.1. Boolean expressions
In the middle of the nineteenth century, George Boole designed a organization of logic that forms the foundation of the mod estimator. He noticed that logical functions could be built from the AND, OR, and Not operations and that this ascertainment leads one to be able to reason about logic in a mathematical system.
As Boole was working in the nineteenth century, of course, he wasn't thinking about logic circuits. He was examining the field of logic, created for thinking well-nigh the validity of philosophical arguments. Philosophers have idea about this field of study since the time of Aristotle. Logicians formalized some mutual mistakes, such as the temptation to conclude that if A implies B, and if B holds, then A must hold too. ("Brilliant people wear spectacles, and I wear spectacles, so I must exist vivid.")
As a mathematician, Boole sought a manner to encode sentences like this into algebraic expressions, and he invented what we at present call Boolean expressions. An example of a Boolean expression is "y 10 + y x." A line over a variable (or a larger expression) represents a NOT; for example, the expression y corresponds to feeding y through a NOT gate. Multiplication (equally with xy) represents AND. After all, Boole reasoned, the AND truth table (Figure ii(b)) is identical to a multiplication tabular array over 0 and one. Addition (as with x +y) represents OR. The OR truth table (Figure 2(c)) doesn't lucifer an addition table over 0 and 1 exactly — one OR 1 is i, simply 1 plus one is 2 — merely, Boole decided, it's shut plenty.
In Boolean expressions, we find the regular guild of operations: Multiplication (AND) comes before addition (OR). Thus, when we write y ten + y ten, nosotros mean (y x + y x). Nosotros can utilise parentheses when this guild of operations isn't what we want. For Non, the bar over the expression indicates the extent of the expression to which it applies; thus, 10 +y represents Notten ORy), while 10 + y represents (NOTx) OR (Nony).
A alarm: Students new to Boolean expressions ofttimes endeavor to abridge ten y as xy — that is, they draw a single line over the whole expression, rather than two separate lines over the two individual pieces. This abbreviation is wrong. The first, x y , translates to (NOTten) AND (Noty) (that is, both ten and y are 0), while teny translates to Not (x ANDy) (that is, x and y aren't both i). We could draw a truth table comparing the results for these ii expressions.
x y 10 y x y xy xy 0 0 1 one 1 0 one 0 one 1 0 0 0 i 1 0 0 i 0 0 1 one i 0 0 0 ane 0
Since the fifth column ( 10 y ) and the seventh column ( xy ) aren't identical, the two expressions aren't equivalent.
Every expression straight corresponds to a circuit and vice versa. To determine the expression respective to a logic excursion, we feed expressions through the excursion just as values propagate through information technology. Suppose we do this for our circuit of Effigy 1.
The upper AND gate's inputs are y and x , and so it outputs y x . The lower AND gate outputs y x, and the OR gate combines these 2 into y 10 + y x.
2.ii. Boolean algebra laws
Boole'due south system for writing down logical expressions is called Boolean algebra. It'southward called an algebra because we tin manipulate symbols using laws similar to those of traditional algebra. For example, the commutative law applies to both OR and AND. To show that OR is commutative (that is, that A +B =B +A, nosotros can complete a truth table demonstrating that for each possible combination of A and B, the values of A +B and B +A are identical.
A B A +B B +A 0 0 0 0 0 one 1 1 1 0 one i i 1 1 i
Since the third and 4th columns match, we would conclude that A +B =B +A is a universal constabulary.
Since OR (and AND) are commutative, nosotros can freely reorder terms without changing the meaning of the expression. The commutative law of OR would allow us to transform y ten + y x into y x +y x , and the commutative law of AND (applied twice) allows united states to transform this to x y + 10 y.
Similarly, OR (and AND) has an associative police force (that is, A + (B +C) = (A +B) +C. Because of this associativity, we volition free to write A +B +C (and ABC) without parentheses — later on all, placing parentheses around the first pair (A +B) results in the same thing as parentheses around the second pair (B +C). In drawing circuits, we'll freely draw AND and OR gates that have several inputs. A 3-input AND gate would actually represent to two two-input AND gates when the circuit is actually wired. In that location are two possible ways to wire this.
Because of the associative law for AND, it doesn't affair which we choose, and so nosotros'll experience gratuitous to ambiguously draw an AND or OR gate with iii (or more) inputs.
At that place are many such laws, summarized in Figure 3. This includes analogues to all of the important algebraic laws dealing with multiplication and improver. In that location are as well many laws that don't hold with addition and multiplication; in the table, these are marked in red with an asterisk.
Figure 3: A sampler of important Boolean identities.
* Those in ruby with an asterisk don't correspond to standard algebraic identities. AND OR commutative AB =BA A +B =B +A associative A (BC) = (AB)C A + (B +C) = (A +B) +C identity A ⋅ 1 =A A + 0 =A distributive A (B +C) =AB +AC * A +BC = (A +B) (A +C)) one/zero A ⋅ 0 = 0 * A + ane = 1 idempotency * AA =A * A +A =A changed * A A = 0 * A + A = 1 DeMorgan's law * AB = A + B * A +B = A B double negation * A =A
two.iii. Sum of products
At present we can return to our problem: If we have a particular logical role we want to compute, how can we build a circuit to compute it? Nosotros'll begin with a description of the logical function as a truth table. Suppose nosotros showtime with the following function for which we want a excursion.
ten y z o 0 0 0 0 0 0 ane 1 0 1 0 1 0 ane one 0 1 0 0 0 1 0 1 0 1 1 0 1 1 i 1 1
Given such a truth table defining a office, we'll build up a Boolean expression representing the function. For each row of the table where the desired output is 1, we describe it as the AND of several factors.
10 y z o description 0 0 1 1 x y z 0 1 0 1 x y z 1 ane 0 1 xy z 1 1 ane 1 xyz
To get in at a row'southward description, we cull for each variable either that variable or its negation, depending whether the variable in that row is 1 or not; and then we take the AND of these choices. For example, looking at the first of the rows above, we include x since ten is 0 in this row, y since y is also 0, and z since z is 1; our description is the AND of these: x y z. This expression gives i for the combination of values on this row; but for other rows, its value is 0, since every other row is different in some variable, and that variable's contribution to the AND would yield 0.
Once we have the descriptions for all rows where the desired output is ane, we observe the following: The value of the desired excursion should be one if the inputs stand for to the showtime ane-row, the 2nd one-row, the third one-row, or the fourth 1-row. Thus, we'll combine the expressions describing the rows with an OR:
Note that our expression does non include descriptions for rows where the truth table signals that the desired output is 0: if we did, then that description would be one, and so the OR of all terms would exist 1, non the 0 that we want.
This expression leads immediately to the excursion of Figure 4.
Figure 4: A circuit derived from a given truth tabular array.
The final expression we get is called a sum of products expression. Information technology is called this because it is the OR (a sum, if we empathise OR to be like addition) of several ANDs (products, since AND corresponds to multiplication). We call this technique of building an expression from a truth table the sum of products technique.
This sum of products technique allows united states take any function over $.25 and build a circuit to compute that office. The existence of such a technique proves that circuits can compute whatever logical office.
To summarize: We have seen three means of describing a Boolean function: logic circuits, truth tables, and Boolean expressions. Moreover, we take seen systematic ways to convert between the three techniques, diagrammed below.
The only missing arrow is the conversion from truth tables to circuits; we can handle that, though, by converting the truth table to a Boolean expression (using the sum of products technique) and converting that into a excursion.
3. Simplifying circuits
Logic gates are concrete devices built using transistors. In practice, the efficiency of a circuit matters. We'll now plough to understanding how to measure a circuit's efficiency, and we'll encounter a technique that ofttimes results in a more than efficient excursion than the ane we arrive at through using the sum of products technique.
3.1. Measuring circuit efficiency
We tin can measure a excursion'southward efficiency in ii directions: space and speed. The space cistron relates to the fact that each transistor takes up space, and the chip containing the transistors is limited in size, then the number of transistors that fit onto a scrap is limited past electric current technology. Since CPU designers want to fit many features onto the chip, they attempt to build their circuits with as few transistors equally possible to attain the tasks needed. To reduce the number of transistors, they effort to create circuits with few logic gates. Thus nosotros can approximate the space usage of a excursion merely by counting how many logic gates the circuit includes.
The 2d factor, speed, relates to the fact that transistors take fourth dimension to operate. Since designers want circuits to piece of work as apace equally possible, they work to minimize the excursion depth, which is the maximum distance from whatsoever input through the excursion to an output. Consider, for example, the two dotted lines in the post-obit excursion, which indicate two unlike paths from an input to an output in the circuit.
The dotted path starting at x goes through three gates (an OR gate, then a Non gate, so another OR gate), while the dotted path starting at y goes through merely two gates (an AND gate and an OR gate). There are two other paths, besides, but none of the paths get through more than three gates. Thus, we would say that this circuit'due south depth is 3. This is a rough measure of the circuit's speed: Computing an output with this circuit takes virtually three times the amount of time it takes a single gate to exercise its work.
The "sum of products technique" that we saw for converting a Boolean office into a circuit isn't too bad using these criteria. The circuit resulting from this technique has a depth of just 3 — or slightly more if you lot insist (equally circuit designers volition) that each AND and OR gate has but two inputs. But it does less well than nosotros might hope in terms of space.
iii.two. Karnaugh maps
We'll now plow to investigating a technique for building circuits from a truth table, which results in smaller circuits without making whatever compromises in depth.
For Boolean functions with four or fewer inputs, the Karnaugh map is a particularly user-friendly manner to find the smallest possible sum-of-products expression. It is a simple procedure: We convert the truth tabular array to a matrix every bit we'll see afterwards, then we determine how all-time to "cover" the one's in the matrix with a set of rectangles; each rectangle will correspond to a term in our sum of products expression.
Permit's start with the truth table used in Section 2.three.
x y z o 0 0 0 0 0 0 1 1 0 1 0 i 0 1 1 0 ane 0 0 0 1 0 1 0 1 1 0 1 one i one 1
Since in that location are eight rows to this table, we will convert information technology into a 2×iv matrix. (If at that place were 4 rows, it would exist a two×2 matrix. And if there were xvi rows, it would exist a 4×4 matrix.) Ane of the variables will be represented forth the vertical axis, and the other two variables along the horizontal axis. Annotation how the variable combinations along the horizontal centrality exercise not go in the traditional order of 00-01-10-11, but instead 00-01-11-10. This is important for the Karnaugh map technique to work.
Having created that matrix, we now fill it by copying the respective output values into the appropriate jail cell. The truth table's last row, for case, maps to the cell in the matrix'south second row (since 10 is i in that row of the truth table) and third column (since y and z are both 1 in that row of the truth table). The output in the truth table'south last row is a i, so we identify a i into that cell of the matrix. Below is the completed matrix, with the 1 corresponding to the truth table's last row circled.
Now we look for the smallest prepare of rectangular regions that encompass all i's in our table but no 0'southward. The summit and width of each rectangle must be a power of 2, and so the possibilities are i×1, 1×2, 1×four, 2×1, two×2, 2×iv, 4×1, 4×2, and 4×4. In our example, we can cover all the 1'south using but three rectangles.
Each of the regions will stand for to a term in a sum of products expression that we build based on the selected regions. The pink region at far right, for case, nether the 10 column, corresponds to the term where y is one and z is 0, but x could be either 0 or ane. The corresponding term, then, would be y z . Putting together the terms from the three regions together, we make it at:
This can be translated into the excursion of Figure five. Notice how this circuit has merely 7 gates in comparison to the 10 gates of Effigy 4.
Effigy 5: A simplified circuit equivalent to Figure 4.
3.3. A more than complex Karnaugh map
Some other case will illustrate some additional features of a Karnaugh map. This time, we will work from a truth table over four inputs.
due west x y z o 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 one 0 0 one 0 1 0 one 0 0 1 1 0 1 0 1 1 1 0
w x y z o i 0 0 0 1 1 0 0 1 0 one 0 i 0 1 1 0 ane 1 one i i 0 0 0 one 1 0 1 0 1 ane 1 0 1 1 1 1 1 i
Since we accept 16 rows in this table, we'll commencement with a iv×four matrix. Each row will stand for a combination of values for the first two variables' values, and each cavalcade volition represent a combination of the last two variables' values.
In determining the rectangular regions, nosotros introduce a new dominion: Regions can wrap around the edges of the matrix. (This dominion applies for 3-input functions, too, though information technology didn't happen to come in our previous example.) Using this fact, we can cover the 1'due south using just three rectangles.
The simplest region (drawn in yellow) is in the lower right; it corresponds to the term wy. The upper 2×2 region (fatigued in pinkish) wraps from the last column effectually to first column; it corresponds to the term w z . There is another region (depict in blue) that wraps between columns and besides between rows, so it covers all four corners of the matrix; it corresponds to the term x z . Putting these three terms together, we arrive at our simplified Boolean expression:
When you draw your rectangular regions, you want to apply every bit few every bit possible: Each region will correspond to an additional AND gate. In our above example, we omitted a possible rectangle that covers the last column, because it wouldn't comprehend any 1's that weren't already covered.
Moreover, you want each rectangle to cover as many one's as possible, even if it isn't necessary, because larger rectangles atomic number 82 to terms containing fewer variables. In our earlier case, we could take fatigued the upper pink rectangle every bit a 1×ii rectangle in the 2nd row only. But then the second terms would have been w 10 z , which has ane more than variable in it than we used previously.
4. Other logic gates and universality
Until now, we've dealt only with AND, OR, and Not gates. Circuit designers ofttimes work with four other gates: NAND (not and), NOR (not or), XOR (etenclusive or), and XNOR (not e10clusive or). The XOR gate emits ane when ane or the other of its inputs is one, but non when both are; that is, the example of two 1 inputs is excluded from the situation when the gate emits a ane. The NAND, NOR, and XNOR gates work but equally an AND/OR/XOR gate with a NOT gate after it — and they are drawn as an AND/OR/XOR gate with a pocket-sized circle at its output. Figure 6 depicts the appearance of these gates and the truth table summaries.
Figure 6: More logic gates.
(a) NAND gate (b) NOR gate (c) XOR gate (d) XNOR gate 
a b o 0 0 i 0 1 1 1 0 1 1 1 0
a b o 0 0 1 0 1 0 ane 0 0 1 one 0
a b o 0 0 0 0 ane 1 one 0 i 1 one 0
a b o 0 0 1 0 1 0 1 0 0 1 1 1
Nosotros haven't looked at these gates previously because they tin can all be built using AND, OR, and NOT gates. In fact, we've seen that every truth table has a circuit of AND, OR, and Non gates that corresponds to it — we simply derive the sum of products expression (which has simply AND, OR, and NOT operations) and then build the corresponding circuit. Considering of this property, we call the combination of AND, OR, and NOT universal.
Somewhat more surprising is that the NAND gate alone is universal — that is, any truth tabular array tin be implemented past a circuit that includes only NAND gates. To convince ourselves of this, we commencement with the fact that any truth table tin exist implemented using AND, OR, and NOT gates; then we encounter how ane tin replace each AND/OR/Non gate with a organization of NAND gates to arrive at a circuit including just NAND gates. Figure 7 demonstrates the NAND-gate system corresponding to each of AND, OR, and Not.
Figure seven: Edifice NOT, AND, and OR using NAND gates.
is converted to 
is converted to 
is converted to 
Nosotros can do a similar thing to find that NOR gates by themselves are universal.
The fact that NAND is universal is often used by circuit designers. Though designers at starting time design a circuit using AND, OR, and Non gates, in practice circuits are easier to manufacture when they use only NAND gates (or just NOR gates). (Why this is so is not something we'll tackle hither.) Thus, their initial AND/OR/Not designs are converted to use only NANDs (or NORs).
In any case, by this bespeak we have seen how yous can build up a reasonably modest circuit for whatever possible logical function. This noesis forms the footing for building up full computational devices.
Source: http://cburch.com/books/logic/
Posted by: kendallmouldither1967.blogspot.com
0 Response to "How To Draw Logic Circuits Using Nand"
Post a Comment