Logic in Hardware: Gate Logic

Logic in Hardware: Gate Logic Electronic gates are digital devices that involve binary voltages, either high or low. A low voltage is usually a "0"; a high voltages is a "1". The logical properties are identical to those of logic, where value 0 is true, and value 1 is false. and a b c & a b --0 0 0 1 1 0 1 1 or p q r | p q --0 0 0 1 1 0 1 1 c 0 0 0 1 not x r 0 1 1 1 ! x -0 1 y y 1 0 Notation of gates in engineering is often done with different shapes, as in the following, but usually without the operator symbol in the middle. a b & c p q | r x ! y 1 Logic Levels Binary waveforms are sequences of 0s and 1s arranged in time as shown below. The top waveforms represent inputs and the bottom waveform is the output. and a b c & a b --0 0 0 1 1 0 1 1 or p q a 1 0 b 1 0 q c 1 0 r p r | p q --0 0 0 1 1 0 1 1 c 0 0 0 1 not x ! r 0 1 1 1 x -0 1 x y y 1 0 0 1 y 2 Mechanical Logic Gates can be constructed using mechanical components, as in the following Not gate. The two positions of the movable rods can be labeled 0 at the left and 1 at the right. 0 1 0 1 NOT x x y x -0 1 y 0 1 y 1 0 0 1 Or gates are similar; the output is at the right when either input is at the right. 0 1 0 1 0 1 0 1 p p r r q q 0 1 0 1 0 1 0 1 3 And gates of this mechanical kind are slightly more complex than Or gates, with a middle element rotating when just one input is to the right. The output c is to the right only when both a and b are to the right. 0 1 0 1 0 1 0 1 a a c c b b 0 1 a b --0 0 0 1 1 0 1 1 c 0 0 0 1 0 1 0 1 0 1 The truth table for this mechanical gate shows that it does indeed behave as an And gate. Note that a spring should be included to pull back to the left the circular point of rotation when both inputs are not at the right. 4 Building with Gates The three main gates (And, Or and Not) can be used to build any binary system. For example the exclusive-Or can be created directly from its given truth table. For each output value of 1 there is created and And of the input combinations which would produce that 1. For example in the second row, (!a & b) or the third row (a & !b) both produce a 1, so are combined with an Or to produce x. exclusive-Or in a b 0 0 1 1 0 1 0 1 out x 0 1 1 0 a a b ! b & | a b ! x & Another way to build an exclusiveOr follows; it has fewer components (4 vs 5). exclusive-Or a a b b | & a b & x ! 5 maj3: Majority of 3 binary values (0,1) Majority elements are useful for increasing reliability by "triplicating" a result and then selecting the majority of the outputs. Output is 1 when 2 or 3 inputs are 1 Output is 0 when 2 or 3 inputs are 0 maj3 = (a & b) | (b & c) | (a & c) a b c m maj3: Majority of 3 0 0 0 0 a 0 0 1 0 b 0 1 0 0 a 0 1 1 1 b | b c 1 0 0 0 1 0 1 1 a 1 1 0 1 c 1 1 1 1 c & & | m & 6 Simplifying Majority (optional) The boolean formula for maj3 can be algebraically factored (using the previously proven distribution property) yielding a shorter simple formula. maj3 = (a & b) | (b & c) | (a & c) = (a & b) | (a & c) | (b & c) = a & (b | c) | (b & c) // original // commute // factor The gate system corresponding to this new majority is shown at the right. This new system is simpler than the previous old one, which is repeated at the left. The new system has four components compared to the old one with five components. old maj3 new maj3 a b a & | & b c b & a c | c | | a & c & 7 Synthesis of Logic circuits Truth tables can be used to create logical formulas. This is shown in the following example, involving three logical variables, a, b, c. The output z is the majority of these 3 values. Minterms are expressions at the right of each row. Each minterm is created so that it has the value of 1 only for the a, b, c values that correspond to that row. For example, the last minterm (which is a & b & c) has value 1 only when all three of a, b, c are 1. n 0 a b c 0 0 0 z minTerm 0 !a & !b & !c 1 2 0 0 1 0 1 0 0 !a & !b & c 0 !a & b & !c 3 4 0 1 1 1 0 0 1 !a & b & !c 0 a & !b & !c 5 6 1 0 1 1 1 0 1 1 a & !b & c a & b & !c 7 1 1 1 1 a & b & c Also the first minterm (which is !a & !b & !c) has value 1 only when all three values are zero. The resulting formula has value 1 in either of the four cases corresponding to minterms 3,5,6,and 7. z = (!a & !b & !c) | (!a & !b & !c) | (!a & !b & !c) | (!a & !b & !c) This expression can be simplified slightly if necessary. 8 More Gates: Nor and Nand (Optional) Nor is an interesting gate, which is just the Not of an Or, as shown. Nand is another gate, which is just the Not of an And, as shown. P q P Nor p q r ----- --0 0 1 0 1 0 1 0 0 1 1 0 | ! nor r P r q & ! r q Nand p q r ----- --0 0 1 0 1 1 1 0 1 1 1 0 P q nand r 9 Nors can be used as components or building blocks of other systems. P x q nor a b ! ! nor y x ! y p q ! nor r c | r a b & c Notice that a Not has been built from joining the two inputs together. The Or is built from Noting the Nor; where the Not is built from another Nor. The And is built from a Nor, along with two Nots (which are built from Nors again). So Nors have been used to build Nots, Ors, and Ands! The Nor is the only component necessary to build any boolean system. 10 MultiValued Logic (optional) Binary values (0 or1, true or false, high or low, etc) are most common, but more values are possible. For example, a three valued system could have values 0, 1, and 2. Operators on these values include maximum and minimum and inversion (similar to And, Or and Not) as follows. a b min a b --0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 c 0 0 0 0 1 0 0 1 2 c p q max p q --0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 r 0 1 2 1 1 2 2 2 2 r x inv x -0 1 2 y y 2 1 0 11 Proofs involving multi values (optional) Proofs involving 3 values are done similar to the previous two valued ones. For example, the DeMorgan's law in two values is !(p && q) == !p || !q which in three values has the form inv (p min q) == (inv p) max (inv q) To Prove this law in three-valued logic requires a long truth table of 9 rows as shown below. p q --0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2 inv (p min q) == (inv p) max (inv q) ---2 2 2 2 1 1 2 1 0 ---0 0 0 0 1 1 0 1 2 --2 2 2 1 1 1 0 0 0 --2 2 2 2 1 1 2 1 0 --2 1 0 2 1 0 2 1 0 12 Binary Addition To add the ten decimal digits requires a table of 10*10 = 100 entries; but if the digits are binary a table of only 2*2 = 4 rows is needed. The binary add definition follows: 0+0=0 0+1=1 1+0=1 1 + 1 = 2 = 10 = 0 with carry of 1 A table of such a simple adder (half adder) follows, showing the output of a sum s and a carry c. A logical gate diagram shows that the carry is simply the And of a, b. The sum is actually the exclusive-Or, which is formed in detail below. HA = Half Adder in a b 0 0 1 1 0 1 0 1 out s c 0 1 1 0 0 0 0 1 a a b b | ! & s a b & carry c 13 Problems on Logic Gates 1.Describe For the given logical formula d = (!a | b) & c draw a diagram of the gates, and draw a truth table 2. Synthesize In a given process, high temperature with high pressure could destroy it. Also, low temperature with high flow rate results in a defective product. And low rate with high viscosity and high pressure yields a burned product. Design a system to sound an alarm when at least 2 of these situations arise. 3. Optimize, Simplify For the given formuli, minimize the logical gate network: a. !a &(!b | b&!c) b. !a & !b | c & (a | b) 4. Design a Binary Subtracter Write a truth table for a binary subtractor having a minuend, subtrahend, borrow and difference. 14