1 00:00:01,100 --> 00:00:05,790 In this lecture you'll learn various techniques for creating combinational logic circuits 2 00:00:05,790 --> 00:00:09,420 that implement a particular functional specification. 3 00:00:09,420 --> 00:00:14,240 A functional specification is part of the static discipline we use to create the combinational 4 00:00:14,240 --> 00:00:17,020 logic abstraction of a circuit. 5 00:00:17,020 --> 00:00:21,750 One approach is to use natural language to describe the operation of a device. 6 00:00:21,750 --> 00:00:24,230 This approach has its pros and cons. 7 00:00:24,230 --> 00:00:29,750 In its favor, natural language can convey complicated concepts in surprisingly compact 8 00:00:29,750 --> 00:00:34,520 form and it is a notation that most of us know how to read and understand. 9 00:00:34,520 --> 00:00:39,129 But, unless the words are very carefully crafted, there may be ambiguities introduced by words 10 00:00:39,129 --> 00:00:43,699 with multiple interpretations or by lack of completeness since it's not always obvious 11 00:00:43,699 --> 00:00:46,379 whether all eventualities have been dealt with. 12 00:00:46,379 --> 00:00:50,999 There are good alternatives that address the shortcomings mentioned above. 13 00:00:50,999 --> 00:00:55,920 Truth tables are a straightforward tabular representation that specifies the values of 14 00:00:55,920 --> 00:01:00,610 the outputs for each possible combination of the digital inputs. 15 00:01:00,610 --> 00:01:06,640 If a device has N digital inputs, its truth table will have 2^N rows. 16 00:01:06,640 --> 00:01:12,000 In the example shown here, the device has 3 inputs, each of which can have the value 17 00:01:12,000 --> 00:01:14,850 0 or the value 1. 18 00:01:14,850 --> 00:01:21,950 There are 2*2*2 = 2^3 = 8 combinations of the three input values, so there are 8 rows 19 00:01:21,950 --> 00:01:24,020 in the truth table. 20 00:01:24,020 --> 00:01:28,800 It's straightforward to systematically enumerate the 8 combinations, which makes it easy to 21 00:01:28,800 --> 00:01:33,920 ensure that no combination is omitted when building the specification. 22 00:01:33,920 --> 00:01:38,920 And since the output values are specified explicitly, there isn't much room for misinterpreting 23 00:01:38,920 --> 00:01:41,640 the desired functionality! 24 00:01:41,640 --> 00:01:46,960 Truth tables are an excellent choice for devices with small numbers of inputs and outputs. 25 00:01:46,960 --> 00:01:51,329 Sadly, they aren't really practical when the devices have many inputs. 26 00:01:51,329 --> 00:01:57,841 If, for example, we were describing the functionality of a circuit to add two 32-bit numbers, there 27 00:01:57,841 --> 00:02:04,069 would be 64 inputs altogether and the truth table would need 2^64 rows. 28 00:02:04,069 --> 00:02:07,710 Hmm, not sure how practical that is! 29 00:02:07,710 --> 00:02:13,660 If we entered the correct output value for a row once per second, it would take 584 billion 30 00:02:13,660 --> 00:02:16,730 years to fill in the table! 31 00:02:16,730 --> 00:02:21,560 Another alternative specification is to use Boolean equations to describe how to compute 32 00:02:21,560 --> 00:02:25,810 the output values from the input values using Boolean algebra. 33 00:02:25,810 --> 00:02:31,360 The operations we use are the logical operations AND, OR, and XOR, each of which takes two 34 00:02:31,360 --> 00:02:37,190 Boolean operands, and NOT which takes a single Boolean operand. 35 00:02:37,190 --> 00:02:41,500 Using the truth tables that describe these logical operations, it's straightforward to 36 00:02:41,500 --> 00:02:46,320 compute an output value from a particular combination of input values using the sequence 37 00:02:46,320 --> 00:02:50,300 of operations laid out in the equation. 38 00:02:50,300 --> 00:02:55,210 Let me say a quick word about the notation used for Boolean equations. 39 00:02:55,210 --> 00:03:00,500 Input values are represented by the name of the input, in this example one of "A", "B", 40 00:03:00,500 --> 00:03:02,120 or "C". 41 00:03:02,120 --> 00:03:08,010 The digital input value 0 is equivalent to the Boolean value FALSE and the digital input 42 00:03:08,010 --> 00:03:12,170 value 1 is equivalent to the Boolean value TRUE. 43 00:03:12,170 --> 00:03:18,600 The Boolean operation NOT is indicated by a horizontal line drawn above a Boolean expression. 44 00:03:18,600 --> 00:03:24,230 In this example, the first symbol following the equal sign is a "C" with line above it, 45 00:03:24,230 --> 00:03:28,430 indicating that the value of C should be inverted before it's used in evaluating the rest of 46 00:03:28,430 --> 00:03:30,760 the expression. 47 00:03:30,760 --> 00:03:35,840 The Boolean operation AND is represented by the multiplication operation using standard 48 00:03:35,840 --> 00:03:38,480 mathematical notation. 49 00:03:38,480 --> 00:03:43,570 Sometimes we'll use an explicit multiplication operator - usually written as a dot between 50 00:03:43,570 --> 00:03:49,150 two Boolean expressions - as shown in the first term of the example equation. 51 00:03:49,150 --> 00:03:53,870 Sometimes the AND operator is implicit as shown in the remaining three terms of the 52 00:03:53,870 --> 00:03:56,400 example equation. 53 00:03:56,400 --> 00:04:01,410 The Boolean operation OR is represented by the addition operation, always shown as a 54 00:04:01,410 --> 00:04:03,720 "+" sign. 55 00:04:03,720 --> 00:04:06,900 Boolean equations are useful when the device has many inputs. 56 00:04:06,900 --> 00:04:14,550 And, as we'll see, it's easy to convert a Boolean equation into a circuit schematic. 57 00:04:14,550 --> 00:04:17,500 Truth tables and Boolean equations are interchangeable. 58 00:04:17,500 --> 00:04:22,130 If we have a Boolean equation for each output, we can fill in the output columns for a row 59 00:04:22,130 --> 00:04:27,760 of the truth table by evaluating the Boolean equations using the particular combination 60 00:04:27,760 --> 00:04:30,470 of input values for that row. 61 00:04:30,470 --> 00:04:35,530 For example, to determine the value for Y in the first row of the truth table, we'd 62 00:04:35,530 --> 00:04:40,850 substitute the Boolean value FALSE for the symbols A, B, and C in the equation and then 63 00:04:40,850 --> 00:04:44,250 use Boolean algebra to compute the result. 64 00:04:44,250 --> 00:04:46,060 We can go the other way too. 65 00:04:46,060 --> 00:04:50,810 We can always convert a truth table into a particular form of Boolean equation called 66 00:04:50,810 --> 00:04:52,150 a sum-of-products. 67 00:04:52,150 --> 00:04:54,940 Let's see how… 68 00:04:54,940 --> 00:05:01,260 Start by looking at the truth table and answering the question "When does Y have the value 1?" 69 00:05:01,260 --> 00:05:06,020 Or, in the language of Boolean algebra: "When is Y TRUE?". 70 00:05:06,020 --> 00:05:13,750 Well, Y is TRUE when the inputs correspond to row 2 of the truth table, OR to row 4, 71 00:05:13,750 --> 00:05:16,930 OR to rows 7 OR 8. 72 00:05:16,930 --> 00:05:20,970 Altogether there are 4 combinations of inputs for which Y is TRUE. 73 00:05:20,970 --> 00:05:26,370 The corresponding Boolean equation thus is the OR for four terms, where each term is 74 00:05:26,370 --> 00:05:32,510 a boolean expression which evaluates to TRUE for a particular combination of inputs. 75 00:05:32,510 --> 00:05:39,020 Row 2 of the truth table corresponds to C=0, B=0, and A=1. 76 00:05:39,020 --> 00:05:43,780 The corresponding Boolean expression is (NOT C) AND (NOT B) 77 00:05:43,780 --> 00:05:52,260 AND A, an expression that evaluates to TRUE if and only if C is 0, B is 0, and A is 1. 78 00:05:52,260 --> 00:05:59,169 The boolean expression corresponding to row 4 is (NOT C) AND B AND A. 79 00:05:59,169 --> 00:06:03,070 And so on for rows 7 and 8. 80 00:06:03,070 --> 00:06:07,590 The approach will always give us an expression in the form of a sum-of-products. 81 00:06:07,590 --> 00:06:14,030 "Sum" refers to the OR operations and "products" refers to the groups of AND operations. 82 00:06:14,030 --> 00:06:18,680 In this example we have the sum of four product terms. 83 00:06:18,680 --> 00:06:24,310 Our next step is to use the Boolean expression as a recipe for constructing a circuit implementation 84 00:06:24,310 --> 00:06:27,620 using combinational logic gates. 85 00:06:27,620 --> 00:06:32,390 As circuit designers we'll be working with a library of combinational logic gates, which 86 00:06:32,390 --> 00:06:38,200 either is given to us by the integrated circuit manufacturer, or which we've designed ourselves 87 00:06:38,200 --> 00:06:42,900 as CMOS gates using NFET and PFET switches. 88 00:06:42,900 --> 00:06:48,139 One of the simplest gates is the inverter, which has the schematic symbol shown here. 89 00:06:48,139 --> 00:06:53,240 The small circle on the output wire indicates an inversion, a common convention used in 90 00:06:53,240 --> 00:06:55,040 schematics. 91 00:06:55,040 --> 00:07:01,620 We can see from its truth table that the inverter implements the Boolean NOT function. 92 00:07:01,620 --> 00:07:08,710 The AND gate outputs 1 if and only if the A input is 1 *and* the B input is 1, hence 93 00:07:08,710 --> 00:07:10,430 the name "AND". 94 00:07:10,430 --> 00:07:16,340 The library will usually include AND gates with 3 inputs, 4 inputs, etc., which produce 95 00:07:16,340 --> 00:07:22,060 a 1 output if and only if all of their inputs are 1. 96 00:07:22,060 --> 00:07:28,840 The OR gate outputs 1 if the A input is 1 *or* if the B input is 1, hence the name "OR". 97 00:07:28,840 --> 00:07:34,500 Again, the library will usually include OR gates with 3 inputs, 4 inputs, etc., which 98 00:07:34,500 --> 00:07:39,040 produce a 1 output when at least one of their inputs is 1. 99 00:07:39,040 --> 00:07:42,820 These are the standard schematic symbols for AND and OR gates. 100 00:07:42,820 --> 00:07:47,370 Note that the AND symbol is straight on the input side, while the OR symbol is curved. 101 00:07:47,370 --> 00:07:53,370 With a little practice, you'll find it easy to remember which schematic symbols are which. 102 00:07:53,370 --> 00:07:57,949 Now let's use these building blocks to build a circuit that implements a sum-of-products 103 00:07:57,949 --> 00:07:58,949 equation. 104 00:07:58,949 --> 00:08:04,340 The structure of the circuit exactly follows the structure of the Boolean equation. 105 00:08:04,340 --> 00:08:08,710 We use inverters to perform the necessary Boolean NOT operations. 106 00:08:08,710 --> 00:08:13,430 In a sum-of-products equation the inverters are operating on particular input values, 107 00:08:13,430 --> 00:08:18,800 in this case A, B and C. To keep the schematic easy to read we've used 108 00:08:18,800 --> 00:08:23,590 a separate inverter for each of the four NOT operations in the Boolean equation, but in 109 00:08:23,590 --> 00:08:29,419 real life we might invert the C input once to produce a NOT-C signal, then use that signal 110 00:08:29,419 --> 00:08:33,179 whenever a NOT-C value is needed. 111 00:08:33,179 --> 00:08:37,588 Each of the four product terms is built using a 3-input AND gate. 112 00:08:37,588 --> 00:08:42,409 And the product terms are ORed together using a 4-input OR gate. 113 00:08:42,409 --> 00:08:47,569 The final circuit has a layer of inverters, a layer of AND gates and final OR gate. 114 00:08:47,569 --> 00:08:52,129 In the next section we'll talk about how to build AND or OR gates with many inputs from 115 00:08:52,129 --> 00:08:56,149 library components with fewer inputs. 116 00:08:56,149 --> 00:09:01,449 The propagation delay for a sum-of-products circuit looks pretty short: the longest path 117 00:09:01,449 --> 00:09:07,490 from inputs to outputs includes an inverter, an AND gate and an OR gate. 118 00:09:07,490 --> 00:09:14,420 Can we really implement any Boolean equation in a circuit with a tPD of three gate delays? 119 00:09:14,420 --> 00:09:19,189 Actually not, since building ANDs and ORs with many inputs will require additional layers 120 00:09:19,189 --> 00:09:23,459 of components, which will increase the propagation delay. 121 00:09:23,459 --> 00:09:26,749 We'll learn about this in the next section. 122 00:09:26,749 --> 00:09:31,490 The good news is that we now have straightforward techniques for converting a truth table to 123 00:09:31,490 --> 00:09:35,949 its corresponding sum-of-products Boolean equation, and for building a circuit that 124 00:09:35,949 --> 00:09:37,109 implements that equation.