CS/COE0447 Computer Organization & Assembly LanguageLogic DesignLayered DesignLogic GatesFunction Impl. Using GatesDescribing a FunctionTruth TableTruth Table, Cont’dCombinational vs. Sequential LogicCombinational LogicSequential LogicImplementing Combinational LogicBoolean AlgebraBoolean Algebra, cont’dSlide 15Expressive PowerMultiplexorA 32-bit MultiplexorSimplifying ExpressionsKarnaugh Map [not covered Sp 2007]Implementing Comb. Logic74LS SeriesBuilding a 1-bit ALUBuilding a 32-bit ALUImplementing “SUB”Implementing “NAND”/”NOR”Implementing “SLT”Implementing “SLT”, cont’dSupporting “BEQ”/”BNE”ALU SymbolRS LatchRS Latch, cont’dSlide 33Slide 34Slide 35Slide 36D LatchD Latch, cont’dSlide 39Slide 40D Flip-Flop (D-FF)D Flip-Flop, cont’dALU Control Logic Design we’ll return to this when we cover appendix BRegister 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 481CS/COE0447Computer Organization & Assembly LanguageLogic Design2Logic Design•Digital hardware is implemented by way of “logic design”•Digital circuits process and produce two discrete values: 0 and 1•Example: 1-bit full adder (FA)3Layered Design•Logic design is done using logic gates•Often we design desired function using high-level languages at somewhat higher level than logic gatesTransistorsLogic gatesFunction blocksMicroarchitecture4Logic GatesY=A&BY=A|BY=~(A&B)Y=~(A|B)2-input AND2-input OR2-input NAND2-input NORABAAABBBYYYY5Function Impl. Using Gatesinputs outputs……?6Describing a Function•OutputA = F(Input0, Input1, …, InputN-1)•OutputB = F’(Input0, Input1, …, InputN-1)•OutputC = F’’(Input0, Input1, …, InputN-1)•…•Methods–Truth table–Sum of products–Product of sums7Truth 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 18Truth Table, Cont’d•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 19Combinational vs. Sequential Logic•Combinational logic–A function whose outputs are dependent only on the current input–As soon as inputs are known, outputs can be computed•Sequential logic–Some memory elements (i.e., state)–Outputs are dependent on current state and current input–Next state is dependent on current state and current input10Combinational Logicinputs outputs……11Sequential Logicinputs outputs……clockcurrentstatenextstate12Implementing Combinational Logic•Any combinational logic can be implemented using sum of products or product of sums•Input-output relationship can be defined in a truth table•From a truth table, each output function can be derived•Boolean expressions can be further manipulated using various Boolean algebraic principles13Boolean 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 ()•One unary operation: NOT (~)14Boolean Algebra, cont’d•Binary operations: AND (/), OR ()–Idempotent•aa = a+a = a–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)15Boolean Algebra, cont’d•De Morgan’s laws–~(a+b) = ~a~b–~(ab) = ~a+~b•More…–a+(ab) = a–a(a+b) = a–~~a=a–a+~a = 1–a(~a) = 016Expressive Power•With AND/OR/NOT, we can express any function in Boolean algebra•Indeed, any combination logic can be implemented using AND/OR/NOT gate–Sum of products•What if we have NAND/NOR/NOT?•What if we have NAND only?•What if we have NOR only?17MultiplexorAYBSY = (S) ? B:A;0118A 32-bit Multiplexor19Simplifying Expressions•Think of Cout in our Adder–Cout = A’BCin+AB’Cin+ABCin’+ABCin–Cout = BCin+ACin+ABInput 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 120Karnaugh Map [not covered Sp 2007]ABCin0 100011110 10110001BCinABACinCout = BCin+AB+ACin21Implementing Comb. Logic•PLA (Programming Logic Array)–A direct implementation of sum of products form pla.html •(thanks to: www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/pla.html)•ROM (Read Only Memory)–Interpret the truth table as fixed values stored in memory•Using logic gate chips (74LS…)2274LS Series•Chips contain several logic gates081491225101336811SN 74LS08 Quad 2-input AND gate321491225101336811SN 74LS32 Quad 2-input OR gateSN 74LS04 Hex inverter gate04135911132468101223Building a 1-bit ALU•ALU = Arithmetic Logic Unit24Building a 32-bit ALU25Implementing “SUB”26Implementing “NAND”/”NOR”27Implementing “SLT”28Implementing “SLT”, cont’d29Supporting “BEQ”/”BNE”•Need a “zero-detector”30ALU Symbol•Note that it’s a combinational logic31RS Latch•Note that there are feedbacks!32RS Latch, cont’d•When R=0, S=101 010133RS Latch, cont’d•When R=1, S=010 101034RS Latch, cont’d•When R=0, S=0, and Q was 000 101035RS Latch, cont’d•When R=0, S=0, and Q was 100 010136RS Latch, cont’d•What happens if R=S=1?1137D Latch•Note that we have an R-S latch as a back-end38D Latch, cont’d•Note that S, R inputs always get inverted input of D when C=1•When C=0, S=R=0, remembering the previous valueSR39D Latch, cont’dSRC D Q(t)0 0 Q(t-1)0 1 Q(t-1)1 0 01 1 140D Latch, cont’dDCQQ’D Latch41D Flip-Flop (D-FF)•Two D latches are cascaded, with opposite clock42D Flip-Flop, cont’dDCQQ’D-FF43ALU Control Logic Design we’ll return to this when we cover appendix B44Register File Implementation we’ll return to this in appendix B45Reg. File Impl., cont’d we’ll return to this in appendix B10x112233440x11223344100011100046To Summarize…•In digital logic, transistors are used as simple switches•Logic gate is an abstraction of multiple transistor network•A combinational logic block has inputs and outputs that depend on the current inputs•A sequential logic block is composed of some combinational logic and memory that keeps the current state47To Summarize…, cont’d•Boolean algebra provides theory for digital logic•Combinational logic can be implemented using PLA (and many other methods)•An ALU