CS Fall Combinational Examples - 1 Combinational Logic Design Case Studies zGeneral design procedure zExamples yCalendar subsystem yBCD to 7-segment display controller yProcess line controller yLogical function unit zArithmetic yInteger representations yAddition/subtraction yArithmetic/logic units

CS Fall Combinational Examples - 2 General Design Procedure for Combinational Logic z1. Understand the Problem yWhat is the circuit supposed to do? yWrite down inputs (data, control) and outputs yDraw block diagram or other picture z2. Formulate the Problem using a Suitable Design Representation yTruth table or waveform diagram are typical yMay require encoding of symbolic inputs and outputs z3. Choose Implementation Target yROM, PAL, PLA yMux, decoder and OR-gate yDiscrete gates z4. Follow Implementation Procedure yK-maps for two-level, multi-level yDesign tools and hardware description language (e.g., Verilog)

CS Fall Combinational Examples - 3 integer number_of_days ( month, leap_year_flag) { switch (month) { case 1: return (31); case 2: if (leap_year_flag == 1) then return (29) else return (28); case 3: return (31); case 4: return (30); case 5: return (31); case 6: return (30); case 7: return (31); case 8: return (31); case 9: return (30); case 10: return (31); case 11: return (30); case 12: return (31); default: return (0); } Calendar Subsystem zDetermine number of days in a month (to control watch display) yUsed in controlling the display of a wrist-watch LCD screen yInputs: month, leap year flag yOutputs: number of days zUse software implementation to help understand the problem

CS Fall Combinational Examples - 4 leap month monthleap ––––– 0001– – – – – – – – – – – ––––– 111–––––– Formalize the Problem zEncoding: yBinary number for month: 4 bits y4 wires for 28, 29, 30, and 31 one-hot – only one true at any time zBlock diagram:

CS Fall Combinational Examples - 5 monthleap ––––– 0001– – – – – – – – – – – ––––– 111–––––– Choose Implementation Target and Perform Mapping zDiscrete gates y28 = y29 = y30 = y31 = zCan translate to S-o-P or P-o-S m8 m4 m2 m1 leap m8 m4 m1 + m8 m1 m8 m1 + m8 m1

CS Fall Combinational Examples - 6 BCD to 7–segment control signal decoder c0 c1 c2 c3 c4 c5 c6 A B C D BCD to 7-segment display controller zUnderstanding the problem yInput is a 4 bit bcd digit (A, B, C, D) yOutput is the control signals for the display (7 outputs C0 – C6) zBlock diagram c1 c5 c2 c4 c6 c0 c3

CS Fall Combinational Examples - 7 ABCDC0C1C2C3C4C5C –––––––– 11––––––––– Formalize the problem zTruth table yShow don't cares zChoose implementation target yIf ROM, we are done yDon't cares imply PAL/PLA may be attractive zFollow implementation procedure yMinimization using K-maps

CS Fall Combinational Examples - 8 C0 = A + B D + C + B' D' C1 = C' D' + C D + B' C2 = B + C' + D C3 = B' D' + C D' + B C' D + B' C C4 = B' D' + C D' C5 = A + C' D' + B D' + B C' C6 = A + C D' + B C' + B' C Implementation as Minimized Sum-of-Products z15 unique product terms when minimized individually 1 0 X X X X 1 1 X X D A B C 1 1 X X X X 1 0 X X D A B C 0 1 X X X X 1 1 X X D A B C 1 1 X X X X 0 1 X X D A B C 1 0 X X X X 1 1 X X D A B C 1 0 X X X X 1 1 X X D A B C 1 1 X X X X 0 1 X X D A B C

CS Fall Combinational Examples - 9 C0 = B C' D + C D + B' D' + B C D' + A C1 = B' D + C' D' + C D + B' D' C2 = B' D + B C' D + C' D' + C D + B C D' C3 = B C' D + B' D + B' D' + B C D' C4 = B' D' + B C D' C5 = B C' D + C' D' + A + B C D' C6 = B' C + B C' + B C D' + A C0 = A + B D + C + B' D' C1 = C' D' + C D + B' C2 = B + C' + D C3 = B' D' + C D' + B C' D + B' C C4 = B' D' + C D' C5 = A + C' D' + B D' + B C' C6 = A + C D' + B C' + B' C C2 Implementation as Minimized S-o-P (cont'd) zCan do better y9 unique product terms (instead of 15) yShare terms among outputs yEach output not necessarily in minimized form 1 1 X X X X 0 1 X X D A B C 1 1 X X X X 0 1 X X D A B C C2

CS Fall Combinational Examples - 10 PLA implementation

CS Fall Combinational Examples - 11 C0 = C3 + A' B X' + A D Y C1 = Y + A' C5' + C' D' C6 C2 = C5 + A' B' D + A' C D C3 = C4 + B D C5 + A' B' X' C4 = D' Y + A' C D' C5 = C' C4 + A Y + A' B X C6 = A C4 + C C5 + C4' C5 + A' B' C X = C' + D' Y = B' C' C2 = B + C' + D C2 = B' D + B C' D + C' D' + C D + B C D' C2 = B' D + B C' D + C' D' + W W = C D + B C D' PAL Implementation zLimit of 4 Product Terms per Output yDecomposition of functions with larger number of terms yDo not share terms in PAL anyway (although there are some with some shared terms) yDecompose into multi-level logic (hopefully with CAD support) xFind common sub-expressions among functions need another input and another output

CS Fall Combinational Examples - 12 Production Line Control zRods of varying length (+/-10%) travel on conveyor belt yMechanical arm pushes rods within spec (+/-5%) to one side ySecond arm pushes rods too long to other side yRods that are too short stay on belt y3 light barriers (light source + photocell) as sensors yDesign combinational logic to activate the arms zUnderstanding the problem yInputs are three sensors yOutputs are two arm control signals yAssume sensor reads "1" when tripped, "0" otherwise yCall sensors A, B, C

CS Fall Combinational Examples - 13 Sketch of Problem zPosition of Sensors yA to B distance = specification – 5% yA to C distance = specification + 5% Within Spec Too Short Too Long A B C spec - 5% spec + 5%

CS Fall Combinational Examples - 14 logic implementation now straightforward just use three 3-input AND gates "too short" = AB'C' (only first sensor tripped) "in spec" = A B C' (first two sensors tripped) "too long" = A B C (all three sensors tripped) ABCFunction 000do nothing 001do nothing 010do nothing 011do nothing 100too short 101don't care 110in spec 111too long Formalize the problem zTruth Table yShow don't cares

CS Fall Combinational Examples - 15 C0C1C2FunctionComments 0001always 1 001A + Blogical OR 010(A B)'logical NAND 011A xor Blogical xor 100A xnor Blogical xnor 101A Blogical AND 110(A + B)'logical NOR 1110always 0 3 control inputs: C0, C1, C2 2 data inputs: A, B 1 output: F Logical Function Unit zMulti-purpose Function Block y3 control inputs to specify operation to perform on operands y2 data inputs for operands y1 output of the same bit-width as operands

CS Fall Combinational Examples - 16 choose implementation technology 5-variable K-map to discrete gates multiplexer implementation ABAB ABAB ABAB Formalize the Problem C0C1C2ABF C2C0C S2 8:1 MUX S1S0 F

CS Fall Combinational Examples - 17 Arithmetic Circuits zExcellent Examples of Combinational Logic Design zTime vs. Space Trade-offs yDoing things fast may require more logic and thus more space yExample: carry lookahead logic zArithmetic and Logic Units yGeneral-purpose building blocks yCritical components of processor datapaths yUsed within most computer instructions

CS Fall Combinational Examples - 18 Number Systems zRepresentation of positive numbers is the same in most systems zMajor differences are in how negative numbers are represented zRepresentation of negative numbers come in three major schemes ySign and magnitude y1s complement y2s complement zAssumptions yWe'll assume a 4 bit machine word y16 different values can be represented yRoughly half are positive, half are negative

CS Fall Combinational Examples –0 –1 –2 –3 –4 –5 –6 – = = – 4 Sign and Magnitude zOne bit dedicate to sign (positive or negative) ysign: 0 = positive (or zero), 1 = negative zRest represent the absolute value or magnitude ythree low order bits: 0 (000) thru 7 (111) zRange for n bits y+/– 2n–1 –1 (two representations for 0) zCumbersome addition/subtraction ymust compare magnitudes to determine sign of result

CS Fall Combinational Examples = = –1= = = –7 in 1s complement form 4 4 1s Complement zIf N is a positive number, then the negative of N ( its 1s complement or N' ) is N' = (2n– 1) – N yExample: 1s complement of 7 yShortcut: simply compute bit-wise complement ( > 1000 )

CS Fall Combinational Examples –7 –6 –5 –4 –3 –2 –1 – = = – 4 1s complement (cont'd) zSubtraction implemented by 1s complement and then addition zTwo representations of 0 yCauses some complexities in addition zHigh-order bit can act as sign bit

CS Fall Combinational Examples = = – –8 –7 –6 –5 –4 –3 –2 – s Complement z1s complement with negative numbers shifted one position clockwise yOnly one representation for 0 yOne more negative number than positive number yHigh-order bit can act as sign bit

CS Fall Combinational Examples = = = repr. of –7 4 2=10000 –7= = repr. of 7 4 subtract 2s complement (contd) zIf N is a positive number, then the negative of N ( its 2s complement or N* ) is N* = 2n – N yExample: 2s complement of 7 yExample: 2s complement of –7 yShortcut: 2s complement = bit-wise complement + 1 x0111 -> > 1001 (representation of -7) x1001 -> > 0111 (representation of 7)

CS Fall Combinational Examples – 4 + (– 3) – – – – s Complement Addition and Subtraction zSimple Addition and Subtraction ySimple scheme makes 2s complement the virtually unanimous choice for integer number systems in computers

CS Fall Combinational Examples - 25 Why Can the Carry-out be Ignored? zCan't ignore it completely yNeeded to check for overflow (see next two slides) zWhen there is no overflow, carry-out may be true but can be ignored – M + N when N > M: M* + N = (2n – M) + N = 2n + (N – M) ignoring carry-out is just like subtracting 2n – M + – N where N + M 2n–1 (– M) + (– N) = M* + N* = (2n– M) + (2n– N) = 2n – (M + N) + 2n ignoring the carry, it is just the 2s complement representation for – (M + N)

CS Fall Combinational Examples = –8–7 – 2 = –8 –7 –6 –5 –4 –3 –2 – –8 –7 –6 –5 –4 –3 –2 – Overflow in 2s Complement Addition/Subtraction zOverflow conditions yAdd two positive numbers to get a negative number yAdd two negative numbers to get a positive number

CS Fall Combinational Examples – – 7 – – 3 – 5 – overflow no overflow Overflow Conditions zOverflow when carry into sign bit position is not equal to carry-out

CS Fall Combinational Examples - 28 AiBiSumCout AiBiCinSumCout Circuits for Binary Addition zHalf adder (add 2 1-bit numbers) ySum = Ai' Bi + Ai Bi' = Ai xor Bi yCout = Ai Bi zFull adder (carry-in to cascade for multi-bit adders) ySum = Ci xor A xor B yCout = B Ci + A Ci + A B = Ci (A + B) + A B

CS Fall Combinational Examples - 29 Cout = A B + Cin (A xor B) = A B + B Cin + A Cin A B Cin S A A B B Cout A B A xor B Cin A xor B xor Cin Half Adder Sum Cout Cin (A xor B)A B Sum Cout Half Adder Sum Cout Full adder implementations zStandard approach y6 gates y2 XORs, 2 ANDs, 2 ORs zAlternative implementation y5 gates yhalf adder is an XOR gate and AND gate y2 XORs, 2 ANDs, 1 OR

CS Fall Combinational Examples - 30 A B Cout Sum Cin 01 Add' Subtract A0B0B0' Sel Overflow A B Cout Sum Cin A1B1B1' Sel A B Cout Sum Cin A2B2B2' Sel AB Cout Sum Cin A3B3B3' Sel S3 S2S1S0 Adder/Subtractor zUse an adder to do subtraction thanks to 2s complement representation yA – B = A + (– B) = A + B' + 1 yControl signal selects B or 2s complement of B

CS Fall Combinational Examples - 31 A A B B @N+2 late arriving signal two gate delays to compute Cout 4 stage adder A0 B0 Cin A1 B1 A2 B2 A3 B3 Ripple-Carry Adders zCritical Delay yThe propagation of carry from low to high order stages

CS Fall Combinational Examples - 32 Ripple-Carry Adders (contd) zCritical delay yThe propagation of carry from low to high order stages y is the worst case addition yCarry must propagate through all bits

CS Fall Combinational Examples - 33 Carry-Lookahead Logic zCarry generate: Gi = Ai Bi yMust generate carry when A = B = 1 zCarry propagate: Pi = Ai xor Bi yCarry-in will equal carry-out here zSum and Cout can be re-expressed in terms of generate/propagate: ySi= Ai xor Bi xor Ci = Pi xor Ci yCi+1= Ai Bi + Ai Ci + Bi Ci = Ai Bi + Ci (Ai + Bi) = Ai Bi + Ci (Ai xor Bi) = Gi + Ci Pi

CS Fall Combinational Examples - 34 Carry-Lookahead Logic (contd) zRe-express the carry logic as follows: yC1 = G0 + P0 C0 yC2 = G1 + P1 C1 = G1 + P1 G0 + P1 P0 C0 yC3 = G2 + P2 C2 = G2 + P2 G1 + P2 P1 G0 + P2 P1 P0 C0 yC4 = G3 + P3 C3 = G3 + P3 G2 + P3 P2 G1 + P3 P2 P1 G0 + P3 P2 P1 P0 C0 zEach of the carry equations can be implemented with two-level logic yAll inputs are now directly derived from data inputs and not from intermediate carries ythis allows computation of all sum outputs to proceed in parallel

CS Fall Combinational Examples gate delay Ci 2 gate delays Bi Ai 1 gate delay increasingly complex logic for carries Carry-Lookahead Implementation zAdder with propagate and generate outputs

CS Fall Combinational Examples - 36 A0 B0 Cin A1 B1 A2 B2 A3 B3 A0 B0 Cin A1 B1 A2 B2 A3 B3 Carry-Lookahead Implementation (contd) zCarry-lookahead logic generates individual carries ySums computed much more quickly in parallel yHowever, cost of carry logic increases with more stages

CS Fall Combinational Examples - 37 Lookahead Carry Unit C0 P0G0P1G1P2G2P3G3 C3 C2C1 C0 @2 C16 A[15-12]B[15-12] C12 S[15-12] A[11-8]B[11-8] C8 S[11-8] A[7-4]B[7-4] A[3-0]B[3-0] PG 4-bit Adder PG PG PG Carry-Lookahead Adder with Cascaded Carry-Lookahead Logic zCarry-lookahead adder y4 four-bit adders with internal carry lookahead ySecond level carry lookahead unit extends lookahead to 16 bits

CS Fall Combinational Examples Bit Adder [3:0] C0 C4 4-bit adder [7:4] 1 C8 0 five 2:1 mux adder low adder high 01 4-bit adder [7:4] C8S7 S6 S5S4S3S2 S1 S0 Carry-Select Adder zRedundant hardware to make carry calculation go faster yCompute two high-order sums in parallel while waiting for carry-in yOne assuming carry-in is 0 and another assuming carry-in is 1 ySelect correct result once carry-in is finally computed

CS Fall Combinational Examples - 39 logical and arithmetic operations not all operations appear useful, but "fall out" of internal logic S S Function Fi = Ai Fi = not Ai Fi = Ai xor Bi Fi = Ai xnor Bi Comment input Ai transferred to output complement of Ai transferred to output compute XOR of Ai, Bi compute XNOR of Ai, Bi M = 0, logical bitwise operations M = 1, C0 = 0, arithmetic operations F = A F = not A F = A plus B F = (not A) plus B input A passed to output complement of A passed to output sum of A and B sum of B and complement of A M = 1, C0 = 1, arithmetic operations F = A plus 1 F = (not A) plus 1 F = A plus B plus 1 F = (not A) plus B plus 1 increment A twos complement of A increment sum of A and B B minus A Arithmetic Logic Unit Design Specification

CS Fall Combinational Examples - 40 M011M011 S S Ci X X X X X X X X X X X X Ai Bi X X X X X X X X X X X X Fi Ci+1 X X X X X X X X X X X X X X X X Arithmetic Logic Unit Design (contd) zSample ALU – truth table

CS Fall Combinational Examples gates Arithmetic Logic Unit Design (contd) zSample ALU – multi-level discrete gate logic implementation

CS Fall Combinational Examples - 42 first-level gates use S0 to complement Ai S0 = 0causes gate X1 to pass Ai S0 = 1causes gate X1 to pass Ai' use S1 to block Bi S1 = 0causes gate A1 to make Bi go forward as 0 (don't want Bi for operations with just A) S1 = 1causes gate A1 to pass Bi use M to block Ci M = 0causes gate A2 to make Ci go forward as 0 (don't want Ci for logical operations) M = 1causes gate A2 to pass Ci other gates for M=0 (logical operations, Ci is ignored) Fi = S1 Bi xor (S0 xor Ai) = S1'S0' ( Ai ) + S1'S0 ( Ai' ) + S1 S0' ( Ai Bi' + Ai' Bi ) + S1 S0 ( Ai' Bi' + Ai Bi ) for M=1 (arithmetic operations) Fi = S1 Bi xor ( ( S0 xor Ai ) xor Ci ) = Ci+1 = Ci (S0 xor Ai) + S1 Bi ( (S0 xor Ai) xor Ci ) = just a full adder with inputs S0 xor Ai, S1 Bi, and Ci Arithmetic Logic Unit Design (contd) zSample ALU – clever multi-level implementation

CS Fall Combinational Examples - 43 Summary for Examples of Combinational Logic zCombinational logic design process yFormalize problem: encodings, truth-table, equations yChoose implementation tech (ROM, PAL, PLA, discrete gates) yImplement by following the design procedure for that technology zBinary number representation yPositive numbers the same yDifference is in how negative numbers are represented y2s complement easiest to handle: one representation for zero, slightly complicated complementation, simple addition zCircuits for binary addition yBasic half-adder and full-adder yCarry lookahead logic yCarry-select zALU Design ySpecification, implementation