- Digital System Implementation
We have learned how to specify digital systems, now let's see how we can implement it. The system implementation, means the procedure of how to build a bul, a digital system from smaller components. And these smaller components was simple components with building blocks, can be basic logical gates, can be universal gates which we are going to define later, or can be some indus, industrial technology library, we can, we can use, always use flip-flop to, to store memory. And also, nowadays when people use, reuse space of design, they're talking about using intellectual properties as the building block. Now let's see how we can implement Boolean functions using basic logical gates, by basic logical gates, we are talking about the three gates, the AND gate, which represents the Boolean AND, x and the y, which will be true if and only if both x and y are true, the logical OR, x plus y, which will be true even if any one of x and y will be true, and, the inverter, NOT gate, x prime, which will change a true to a false. And with this three basic logical gate, we can implement all kind of Boolean expressions, for example, this w based on three or four variables, x0, x1, x2, x3, it is defined, as the sum of four terms, each term is a logical end, and from here, we can easily draw the logical implementation of this function. So for example here, we have x0, and x1, so this AND gate implements this term, and then the last AND gate takes x3, and x0 so this one implements the third term. And this OR gate, implements the sum, of this, four terms. [SOUND] And besides the three basic logical gates, there are several other logi, logical gates. So for example, the NAND gate, the NOR gate, Exclusive-OR gate, and Exclusive-NOR gate. The functionality of these gates are given in this truth table, and on these first two truth columns, we list all the four combinations of two inputs, x and the y, start from 0, 0, 0, 1, go to 1, 0, then 1, 1, and then for each of these input combinations, we list, the output, for each of these four functions. So for example, so NAND gate will be 0, if and only if both x and y are 1, and the NOR gate, on the other side, will be one if and only if both x and y are 0. So with this additional gates, we can sometimes, have a much better or more efficient, implementation of the system. Consider this example. It has three input x, y, and z and then two output, S and a C, and this basically implements a which is going to add up x and y plus a carry z, and S is the new sum, and the C is the new carry. And the functionality of S is given as the Exclusive-OR of x, y and z., and then the functionality of C is given as xy plus z times, the Exclusive-OR of x and y. So from this definition, we can also draw the logical diagram of this function. So input x, y, z, output sum and a carry, and the inside, we have the basic logical gates, gate, gate, OR gate and the two Exclusive-OR gate. So for example, the first one, is the Exclusive of x and the y. It will be Exclusive-OR with z again, implement has. So this is input from z. 'Kay? And what is interesting in this example here, it also shows that, this Exclusive-OR of x and the y, also comes to this AND gate, or the AND with z here, to produce this term. So this is the concept of reuse, which we will discuss later on. Now we talk about this concept called universal gate, it is another way to implement Boolean functions. A gate or a set of gates is called universal, if it can implement all digital systems or all the Boolean functions. So this is a very, very strong statement, a gate will be able to implement all the Boolean functions, so how can we verify that, there's no way you can en, enumerate all the Boolean functions. So how we do this is, we start, from the definition of Boolean functions, we've realized that, all of the Boolean functions can be expressed as the logical AND, the logical OR, or inverters, so by putting these three gates together, we have the so called, the standard universal gate, so all the Boolean functions, should be able to implemented by these three logical gates. And now this seems becomes easier, so for us to prove, any logical gate is universal, we only need to show that this cage can be used to implement the standard universal gates which is logical AND, logical OR, and the inverter. Let's see in the example here. [SOUND] We define a logical gate as a Boolean function f of x, y, z, it is defined as, as x prime yz plus xy prime plus y prime z, and we claim this function with this gate is universal. And how do we prove this? The first one will show that, I can use this function block f or this gate to implement the inverter. And how do I do that? I set, the second and the third parameter to f as constant to 1, so if I plug in this into the definition of f, I got x prime times 1 times 1 plus x times 1 compliments plus 1 compliments times 1. And because 1 compliments equal to 0, so this last of two terms disappeared, and then 1 times anything is, that thing itself, so this give us x compliments, that is exactly the inverter. And to draw a, a diagram, I can show this, so this is my logical gate f, and how I feed into this system is I feed x and 1, 1 into f. And, but higher from outside the box, what people see is, I give it input x to the system, and then the system outputs x prime, which is equivalent to the logical AND, logical NOT gate, the inverters. So next, we show you how to implement the OR gate, and then similarly, we put the middle, parameter to 0, and then plug in to the definition of f, so we, what we get is x prime and a y 0, so this becomes 0 times z, and the z is the new y here. And plus the first variable, which is x, times the compliments of the second variable, which is zero compliments, plus the compliments of the second variable times the third variable, which is y here. And because we know that 0 complements is 1, and 0, cancel this one so the only thing left is x plus y, which is the logical OR. 'Kay? And then to show this concept, we can go the same figure, is thus the box you feed the x and the y, and internally you are taking 0 as the middle, parameter, let this function f, give you x plus y, so from outside, this looks like a OR gate. And then similarly, we can implement the AND gate, and, which is a little bit of, more, I mean, complicated than, AND, than OR gate or NOT gate. And here is the logical imp, implementation here, with two functional blocks, this one, the first one, get y complements, the second one get x times y, and from the outside you see x, y coming in, and then from outside you see x times y coming out, so, this is the logical AND. And because I can implement a logical AND, logical OR, and inverters, using this f, so I know that f is universal, and I can use f to implement any kind of Boolean functions or any kind of digital systems.
- Function Simplification and Don't Care Conditions
So we have learned how to specify Boolean systems or digital systems, and we have learned how to implement it in many, many different ways, and now we want to talk about what will be the best way to implement, which people called the function simplification of function optimization. The goal of function optimization is trying to find an equivalent function with the minimum number of literals. So, for example, I have this function f, of three variables, x, y, z. And it is the sum of four terms. And from the definition, I can implement this function using basic logical gates. The inverters give me all these complements. And then these AND gate, four AND gates create these four terms. And then finally the OR gates add them up together. However, I take a look at this. I say okay, so these four terms, they can be paired up in red and green. So for example, in the green terms, these two terms, they shared at y prime, z prime. Y prime, z prime. The difference here is the first term is x prime, the second term is x. So when you do x prime plus x, we know this is one. So that means the two green terms is equivalent to y prime, z prime. And then similarly, the, the first, the two red terms can also be simplified into yz prime. So, now we have yz prime and y prime, z prime. So applying the same strategy again, we know this is z prime. So what this simplification procedure means. Just tells us that this function is equivalent to the compliment of z. Which means that I can implement the same thing by this part. Instead of getting f from here, I can get f from here, they're equivalent. So, from here we see why people are doing simplifications. Because compared to these two designs, this one here used far less hardware. And less hardware normally means lower power consumption, faster speed and the bottom line is, they implement the same functionality. So, in some sense, we, we said this is a better design. And how do people do function simplifications? So over the past several decades. So there are a lot of CAD tools has been developed to do functions simplifications. And the don't care conditions have played essential role in most of these tools. So now let's use a small example to see how don't care's can help us simplify functions. So let's consider a design of a 3-input encoder which is going to assign a 2-bit code to each of the three different input combinations, and here is the choose table for this system. We see the three different input combinations are zero zero one, zero one zero, and one zero zero. And their codes will be zero one, one zero, and one one. So one thing we realized is so we have 3-bits which means that there is a total of two to the power three. Eight different combinations of input. But however, the system specified only three. And what happens to the other five input combinations? They are the things we call don't care conditions, because the user doesn't care what, what will be the output in these five cases. So now we'll list fill, I mean implementations of this system. So the first one is the one I do the straightforward one. To implement a, I say a is the sum of these two conditions. So a complements times y times z complements, so make a one plus the second si, situation. X times y compliments, times z compliments. And if you also simplify this a little bit, you see x prime y, plus xy prime, which means this will be true if and only if x and y have different values, which is the definition of exclusive war. And similarly we can get the expression for b. So this is one solution. And however we can find another solution here, which is much simpler here using only two inverters. X is the compliment of z and b is the compliment of y. And if you take a look up here this does meet these two requirements. Whenever z is 1, a is 0. Whenever z is 0, z will be. Whenever z is 0, a will be 1, and for b it is the same. Whenever y is 0, b will be 1. Whenever y is 1, b will be 0. So this is a much better solution in some sense. And how we come up with this solution? What happens with other cases, other five don't care cases? So for these five don't care cases, because user doesn't care the outcome. So these codes can be arbitrary. We don't care either. By using this don't care in different ways we can get actually a lot of other implementations, and later we're going to talk about vulnerabilities behind, oh this, better implementation because they may not consider don't cares properly. So other than the don't cares that are missing from the two's table in the system specification, where else can we find don't cares? So this satisfiability don't care is one of the cases. So it is a part of the system where the input pattern will never occur. So let's see this here. We consider this NOR gate by definition of the NOR gate. This is a truth table format. And the, from this input here, we see the first input and the second input to the NOR gate, they are always complement to each other. Which mean that this case will not happen, this case will not happen. That also means that these outputs of the exclude, of the NOR gates, y will always be 0. It can never be one. So with this in mind, think about the, this exclusive XOR gate. The y input is, cannot be one. Which means for the exclusive XOR GATE, input combination x equal to one, y equal to one or x equal to zero, y equal to one will never happen. And we represent these two cases by xy which means x equal to one, y equal to one and x prime y which means x equal to zero, y equal to one. So this are the two don't care conditions for this exclusive XOR gate, because this two input combination can now be satisfied by the earlier part of the circuit. So that is why we call them satisfiability don't cares. So another source of don't cares is the ones called observability don't cares. So this is the input combinations or the input patterns that will not affect the output. So let's think in this case, y will be zero. What y, zero. This NAND gate will always give a one regardless of the value of, from this link. Which means that I don't really care what is the value here, I don't care the value here. As, as long as y is zero, this is always one. The changes on this part will not be observed from outside. So in particular use case. When x, when y is zero, no matter x is zero or one, I cannot observe the difference. So this is the one called observability don't cares, or ODC. So how this satisfy ability don't care and observability don't cares to help us to simplify circuit. So consider this an example. By analysis, we know that it has SDC of x equal to one, y equal to one. x equal to zero, y equal to one. And also by, by analyze the ODCs, we know there are two ODC conditions, x equal to one, y equal to zero and x equal to zero, y equal to zero. So, now if you put all this four things together, these are all the input combinations of x and y. And that they are all don't cares. Which means that this logical gate is redundant. All the possible input accommodations they are don't cares. It is irrelevant to the output here. Which in some sense means that we can ignore this gate and then the circuit remains the same.
No comments:
Post a Comment