CS/COE0447 Computer Organization & Assembly LanguageOutlineLogic GatesMultiplexorComputers and LogicCombinational vs. Sequential LogicCombinational LogicSequential LogicSlide 9Functions Implemented Using GatesDescribing a FunctionTruth TableTruth TablesSlide 14Truth Table and EquationsTruth Tables and EquationsBoolean AlgebraLaws of Boolean AlgebraLaws of Boolean AlgebraExamplesExample equationTruth Table for EGive a Boolean Equation for DExample: boolean equation of a circuit First add the boolean equations at the output for each AND gateExample: Next add the Boolean equations at the output for the OR gate The Boolean equation for the complete logic circuit is: Y = (A•B)+(B•C)Example: Truth Table Y = (A•B)+(B•C)Example: MUXSlide 28Expressive PowerSlide 30Since we were talking about MUXs…A 32-bit wide 2-to-1 MultiplexorUse a Decoder to build a MUX with more choices Decoder n bit input value and 2^n outputs (Fig B.3, pB8) Decoder: implementation with gates Decoder n bit input value and 2^n outputs A = X • Y B = X • Y C = X • Y D = X • YN input MUX using a decoderImplementing Combinatorial Logic74LS SeriesFig 5.28 (added for reference)ALU SymbolBuilding a 1-bit ALUBuilding a 32-bit ALUImplementing “SUB”Implementing “NAND”/”NOR”Implementing “SLT”Implementing “SLT”, cont’dSupporting “BEQ”/”BNE”Slide 47Slide 48RS LatchRS Latch, cont’dSlide 51Slide 52Slide 53Slide 54D LatchD Latch, cont’dSlide 57Slide 58D Flip-Flop (D-FF)D Flip-Flop, cont’dRegister File Implementation we’ll return to this in appendix BReg. File Impl., cont’d we’ll return to this in appendix BTo Summarize…To Summarize…, cont’dSlide 651CS/COE0447Computer Organization & Assembly LanguageLogic DesignAppendix B2Outline•Example to begin: let’s implement a MUX!•Gates, Truth Tables, and Logic Equations•Combinatorial Logic•Constructing an ALU•Memory Elements: Flip-flops, Latches, and Registers (if there is time)3Logic GatesY=A&BY=A|BY=~(A&B)Y=~(A|B)2-input AND2-input OR2-input NAND2-input NORABAAABBBYYYY4MultiplexorIf S then C=B else C = AACBS01How many bits is S?1, since it is choosing between 2 valuesLet’s see how to implement a 2-input MUX using gates. Hint: the answer uses AND gates, an OR gate, and one INVERTER Answer in lecture; Figure B.3.2 shows the answer as well.5Computers and Logic•Digital electronics operate with only two voltage levels of interest: high and low voltage. –All other voltage levels are temporary and occur while transitioning between values•We’ll talk about them as signals that are –Logically true; 1; asserted–Logically false; 0, deasserted•0 and 1 are complements and inverses of each other6Combinational vs. Sequential Logic•Combinational logic–A function whose outputs depend only on the current input•Sequential logic–Memory elements, i.e., state elements–Outputs are dependent on current input and current state–Next state is also dependent on current input and current state7Combinational Logicinputs outputs……8Sequential Logicinputs outputs……clockcurrentstatenextstate9•The next set of topics [until the sequential logic picture we just saw pops up again] will only be about combinatorial logic10Functions Implemented Using Gatesinputs outputs……?Combinatorial logic blocks implement logical functions, mapping inputs to outputs11Describing a Function•OutputA = F(Input0, Input1, …, InputN-1)•OutputB = F’(Input0, Input1, …, InputN-1)•OutputC = F’’(Input0, Input1, …, InputN-1)•[each output is its own function of the inputs]•Methods–Truth table (since combinatorial logic has no memory, it can be completely specified by a truth table)–…[in a moment]12Truth TableInput OutputA BCinSCout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 113Truth Tables•In a truth table, there is one row for every possible combination of values of the inputs•Specifically, if there are N inputs, the possible combinations are the binary numbers 0 through 2EN - 1. For example:–3 bits (0-7): 000 through 111 –4 bits (0-15): 0000 through 1111–5 bits (0-31): 00000 through 11111•While we could always use a truth table, they quickly grow in size and become hard to understand and work with•Boolean logic equations are more succinct14Describing a Function•OutputA = F(Input0, Input1, …, InputN-1)•OutputB = F’(Input0, Input1, …, InputN-1)•OutputC = F’’(Input0, Input1, …, InputN-1)•[each output is its own function of the inputs]•Methods–Truth table –Boolean logic equations15Truth Table and Equations •S = A’B’Cin+A’BCin’+AB’Cin’+ABCin•Cout = A’BCin+AB’Cin+ABCin’+ABCinInput OutputA BCinSCout0 0 0 0 00 0 1 1 00 1 0 1 00 1 1 0 11 0 0 1 01 0 1 0 11 1 0 0 11 1 1 1 1Each output has its own…? Column in the truth tableAnd its own Boolean equation16Truth Tables and Equations•All functions specified by truth tables can also be specified by Boolean formulas [and vice versa]•So, let’s look more closely at Boolean algebra17Boolean Algebra•Boole, George (1815~1864): mathematician and philosopher; inventor of Boolean Algebra, the basis of all computer arithmetic•Binary values: 0, 1•Two binary operations: AND (/), OR ()–AND is also called the logical product since its result is 1 only if both operands are 1–OR is also called the logical sum since its result is 1 if either operand is 1•One unary operation: NOT (~)18Laws of Boolean Algebra •Identity, Zero, and One laws–aa = a+a = a–a1 =a; a+0 = a [“copy” operations]–a0 =0; a+1 = 1 [deassert by ANDing with 0; assert by ORing with 1]•Inverse –aa = 0; a+a = 1•Commutative–ab = ba–a+b = b+a•Associative–a(bc) = (ab)c–a+(b+c) = (a+b)+c•Distributive–a(b+c) = ab + ac –a+(bc) = (a+b)(a+c)19Laws of Boolean Algebra•De Morgan’s laws–~(a+b) = ~a ~b–~(ab) = ~a+~b•More…–a+(ab) = a–a(a+b) = a–~~a=a•You’ll see this again in CS441 and CS150220Examples•To get used to Boolean equations•To see the relationships among Truth Tables, Boolean Equations, and hardware implementations in gates•To see that a “sum of products” formula can always be derived from a truth table•To see that equations can often be simplified21Example equation•E = (A’ B C) + (A B’ C) + (A B C’) •What is the value of the equation if A