1ECE 274 - Digital LogicLecture 21 Lecture 21 – Optimization Mealy vs. Moore Carry-Lookahead Adders2ECE 274 - Digital LogicAnnouncementsUpdated Regrade Policy All requests for regrades must be submitted in writing within one week of the distribution of graded material Problems requested to be regraded will be regraded in their entiretyThis could possibly result in a lower score for the requested problem Other problems within the same assignment mightalso be regradedBut, such regrades will not negatively impact your scoreI.e., regrades for problems not specifically requested will NOT lower your score3Moore vs. Mealy FSMs FSM implementation architecture State register and logic More detailed view Next state logic – function of present state and FSM inputs Output logic If function of present state only –Moore FSM If function of present state and FSM inputs –Mealy FSMclkIOState registerCombinationallogicSNclkIOSt a t e r e g i s t e rNext-statelogicOut putlogicFSMoutputsFSMinputsNS(a)clkIOSt a t e r e g i s t e rNext-statelogicOutputlogicFSMoutputsFSMinputsNS(b)Mealy FSM a dds thi sMooreMealy/x=0b/x=1b’/x=0Inputs: b; Outputs: xS1S0Graphically: show outputs with arcs, not with statesa4Mealy FSMs May Have Fewer States Soda dispenser example: Initialize, wait until enough, dispense Moore: 3 states; Mealy: 2 statesMooreMealyInputs: enough (bit)Outputs: d, clear (bit)WaitDispInitenough’enoughd=0clear=1d=1Inputs: enough (bit)Outputs: d, clear (bit)WaitInitenough’enough/d=1clkInputs: enoughState:Outputs: cleardIIWWD(a)clkInputs: enoughState:Outputs: cleardIIWW(b)/d=0, clear=15Mealy vs. Moore Q: Which is Moore, and which is Mealy?Inputs: b; Outputs: s1, s0, pTimeAlarmDateStpwchb’/s1s0=00, p=0b/s1s0=00, p=1b/s1s0=01, p=1b/s1s0=10, p=1b/s1s0=11, p=1b’/s1s0=01, p=0b’/s1s0=10, p=0b’/s1s0=11, p=0Inputs: b; Outputs: s1, s0, pTimeS2Alarmbbbbbbbs1s0=00, p=0s1s0=00, p=1s1s0=01, p=0s1s0=01, p=1s1s0=10, p=0s1s0=10, p=1s1s0=11, p=0s1s0=11, p=1S4DateS6StpwchS8b’b’b’b’MealyMoore• A: Mealy on left, Moore on right– Mealy outputs on arcs, meaning outputs are function of state AND INPUTS– Moore outputs in states, meaning outputs are function of state only 6Mealy vs. Moore Example: Beeping Wristwatch Button b  Sequences mux select lines s1s0through 00, 01, 10, and 11 Each value displays different internal register Each unique button press should cause 1-cycle beep, with p=1 being beep Must wait for button to be released (b’) and pushed again (b) before sequencing Note that Moore requires unique state to pulse p, while Mealy pulses pon arc Tradeoff: Mealy’s pulse on pmay not last one full cycleMealyMooreInputs: b; Outputs: s1, s0, pTimeAlarmDateStpwchb’/s1s0=00, p=0b/s1s0=00, p=1b/s1s0=01, p=1b/s1s0=10, p=1b/s1s0=11, p=1b’/s1s0=01, p=0b’/s1s0=10, p=0b’/s1s0=11, p=0Inputs: b; Outputs: s1, s0, pTimeS2Alarmbbbbbbbs1s0=00, p=0s1s0=00, p=1s1s0=01, p=0s1s0=01, p=1s1s0=10, p=0s1s0=10, p=1s1s0=11, p=0s1s0=11, p=1S4DateS6StpwchS8b’b’b’b’7Mealy vs. Moore Tradeoff Mealy outputs change mid-cycle if input changes Note earlier soda dispenser example Mealy had fewer states, but output dnot 1 for full cycle Represents a type of tradeoffMooreMealyInputs: enough (bit)Outputs: d, clear (bit)WaitDispInitenough’enoughd=0clear=1d=1Inputs: enough (bit)Outputs: d, clear (bit)WaitInitenough’enough/d=1clkInputs: enoughState:Outputs: cleardIIWWD(a)clkInputs: enoughState:Outputs: cleardIIWW(b)/d=0, clear=18Implementing a Mealy FSM Straightforward Convert to state table Derive equations for each output Key difference from Moore: External outputs (d, clear) may have different value in same state, depending on input values Inputs: enough (bit)Outputs: d, clear (bit)WaitInitenough’/d=0enough/d=1/ d=0, clear=19Mealy and Moore can be Combined Final note on Mealy/Moore May be combined in same FSMInputs: b; Outputs: s1, s0, pTimeAlarmDateStpwchb’/p=0b/p=1s1s0=00s1s0=01b/p=1b/p=1s1s0=10b/p=1s1s0=11b’/p=0b’/p=0b’/p=0Combined Moore/Mealy FSM for beeping wristwatch example10Datapath Component Tradeoffs Can make some components faster (but bigger), or smaller (but slower), than the straightforward components we previously built We’ll build A faster (but bigger) adder than the carry-ripple adder Could also do for the other datapath components6.411Faster Adder Built carry-ripple adder in Ch 4 Similar to adding by hand, column by column Con: Slow Output is not correct until the carries have rippled to the left 4-bit carry-ripple adder has 4*2 = 8 gate delays Pro: Small  4-bit carry-ripple adder has just 4*5 = 20 gatesFAa3co s3b3FAa0b0 ciFAa2s2s1 s0b2FAa1b1c3carries:b3a3s3c2b2a2s2c1b1a1s1cinb0a0s0+coutA:B:a3 b3 a2 b2 a1 b1 a0 b0 cins3 s2 s1 s0cout4-bit adderaa12Faster Adder Faster adder – Use two-level combinational logic design process Recall that 4-bit two-level adder was big Pro: Fast  2 gate delays Con: Large Truth table would have 2(4+4)=256 rows Plot shows 4-bit adder would use about 500 gates Is there a compromise design? Between 2 and 8 gate delays Between 20 and 500 gates100008000600040002000012345N678Transistorsa3cos3b3a0 b0 cia2s2s1s0b2a1b1Two-level: AND level followed by ORs13FAa3co s3b3FAa0 b0 ciFAa2s2s1 s0b2FAa1b1aFaster Adder – (Bad) Attempt at “Lookahead” Idea Modify carry-ripple adder – For a stage’s carry-in, don’t wait for carry to ripple, but rather directly computefrom inputs of earlier stages Called “lookahead” because current stage “looks ahead” at previous stages rather than waiting for carry to ripple to current stageFAc4c3 c2s3 s2stage 3 stage 2c1s1stage 1c0s0c0b0b1b2b3 a0a1a2a3stage 0coutlookaheadlookaheadlookaheadNotice – no rippling of carry14FAa3co s3b3FAa0b0 c0FAa2s2s1 s0b2FAa1b1aFaster Adder – (Bad) Attempt at “Lookahead”Stage 0: Carry-in is already an external input: c0co0c1Stage 1: c1=co0co0= b0c0 + a0c0 + a0b0c1 = b0c0 + a0c0 + a0b0co1c2Stage 2: c2=co1co1 = b1c1 + a1c1 + a1b1c2 = b1c1 + a1c1 + a1b1 Recall full-adder equations:  s = a xor b c = ab + ac + bc• Want each stage’s carry-in bit to be function of external inputs only (a’s, b’s, or c0)c2 = b1(b0c0 + a0c0 + a0b0) + a1(b0c0 + a0c0 + a0b0) +a1b1c2 = b1b0c0 + b1a0c0 + b1a0b0 + a1b0c0 + a1a0c0 + a1a0b0 + a1b1FAc4c3 c2s3 s2stage 3 stage 2c1s1stage 1c0s0c0b0b1b2b3