MIT OpenCourseWarehttp://ocw.mit.edu For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. 6.004 Computation Structures Spring 2009 L05 – Sequential Logic 1 6.004 – Spring 20092/19/09Sequential Logic: adding a littlestate Lab #1 is due tonight (checkoff meeting by next Thursday).modified 2/17/09 10:26 QUIZ #1 Tomorrow! (covers thru L4/R5) L05 – Sequential Logic 2 6.004 – Spring 20092/19/096.004: Progress so far… 01101PHYSICS: Continuous variables, Memory, Noise, f(RC) = 1 -e-t/RCCOMBINATIONAL: Discrete, memoryless, noise-free, lookup table functions 2.71354 voltsCBAY00000011010001111000101011011111What other buildingblocks do we need in order to compute? L05 – Sequential Logic 3 6.004 – Spring 20092/19/09Something We Can’t Build (Yet) What if you were given the following design specification:When the button is pushed: 1) Turn on the light if it is off2) Turn off the light if it is onThe light should change state within a second of the button pressbuttonlightWhat makes this circuit so different from those we’ve discussed before? 1. “State” – i.e. the circuit has memory 2. The output was changed by a input “event” (pushing a button) rather than an input “value” L05 – Sequential Logic 4 6.004 – Spring 20092/19/09Digital State One model of what we’d like to build Plan: Build a Sequential Circuit with stored digital STATE – •Memory stores CURRENT state, produced at output •Combinational Logic computes •NEXT state (from input, current state) •OUTPUT bit (from input, current state) •State changes on LOAD control input Combinational Logic Current State NewState InputOutput Memory Device LOAD L05 – Sequential Logic 5 6.004 – Spring 20092/19/09Needed:Storage Combinational logic is stateless:valid outputs always reflect current inputs. To build devices with state, we need components which store information (e.g., state) for subsequent access. ROMs (and other combinational logic) store information “wired in” to their truth table Read/Write memory elements are required to build devices capable of changing their contents. How can we store – and subsequently access --a bit? •Mechanics: holes in cards/tapes •Optics: Film, CDs, DVDs, … •Magnetic materials •Delay lines; moonbounce •Stored charge L05 – Sequential Logic 6 6.004 – Spring 20092/19/09Storage: Using Capacitors We’ve chosen to encode information using voltages and we know from 6.002 that we can “store” a voltage as charge on a capacitor: Pros: compact – low cost/bit (on BIG memories) Cons: complex interface stable? (noise, …) it leaks! refresh To write: Drive bit line, turn on access fet, force storage cap to new voltage To read: precharge bit line, turn on access fet, detect (small) change in bit line voltage N-channel fet serves as access switch VREFword lineBit lineSuppose we refresh CONTINUOUSLY? L05 – Sequential Logic 7 6.004 – Spring 20092/19/09Storage: Using Feedback IDEA: use positive feedback to maintain storage indefinitely. Our logic gates are built to restore marginal signal levels, so noise shouldn’t be a problem! VINVOUTResult: a bistablestorage elementFeedback constraint: VIN = VOUTVTC for inverter pair VINVOUTThree solutions: two end-points are stablemiddle point is unstable Not affected by noise We’ll get back to this! L05 – Sequential Logic 8 6.004 – Spring 20092/19/09YSBSettable Storage Element It’s easy to build a settable storage element (called a latch)using a lenient MUX: 01G0011D----01QIN01----QOUT 0101“state” signal appears as both input and outputQ follows D Q stable ADGQHere’s a feedback path, so it’s no longer a combinational circuit. L05 – Sequential Logic 9 6.004 – Spring 20092/19/09New Device: D Latch GDQDTPDV1V2V2V1TPDGQG=1:Q follows D G=0:Q holds G=1: Q Follows D, independently of Q’ G=0: Q Holds stable Q’, independently of D Y01ADGQQ’BUT… A change in D or G contaminates Q, hence Q’ … how can this possibly work? L05 – Sequential Logic 10 6.004 – Spring 20092/19/09A Plea for Lenience… Y01ADGQDTPDV1V2V2V1TPDGQAssume LENIENT Mux, propagation delay of TPDThen output valid whenQ’Does lenience guarantee a working latch? What if D and G change at about the same time… •Q’=D stable for TPD,independently of G; or •G=1, D stable for TPD,independently of Q’;or•G=0, Q’ stable for TPD,independently of D GDQ’Q10X011X1X000X1110X000X11Q(D,G) Q(D,Q’) Q(G,Q’)L05 – Sequential Logic 11 6.004 – Spring 20092/19/09Dynamic Discipline for our latch: D Stable … with a little discipline Y01ADGQTo reliably latch V2: Q’•Apply V2 to D, holding G=1 •After another TPD, Q’ & D both valid for TPD;will hold Q=V2 independently of G•Set G=0, while Q’ & D hold Q=D •After TPD,V2 appears at Q=Q’•After another TPD,G=0 and Q’ are sufficient to hold Q=V2 independently of DDGQV2V2TPDTPDTSETUPTHOLDTPDTSETUP = 2TPD: interval prior to G transition for which D must be stable & valid THOLD = TPD: interval following G transition for which D must be stable & valid L05 – Sequential Logic 12 6.004 – Spring 20092/19/09Lets try it out! Combinational Logic GDQCurrent State NewState InputOutput Plan: Build a Sequential Circuit with one bit of STATE – •Single latch holds CURRENT state •Combinational Logic computes •NEXT state (from input, current state) •OUTPUT bit (from input, current state) •State changes when G = 1 (briefly!) What happens when G=1? L05 – Sequential Logic 13 6.004 – Spring 20092/19/09Combinational Cycles Combinational Logic GDQCurrent State NewState InputOutput When G=1, latch is Transparent… … provides a combinational path from D to Q. Can’t work without tricky timing constrants on G=1 pulse: •Must fit within contamination delay of logic •Must accommodate latch setup, hold times Want to signal an INSTANT, not an INTERVAL… Looks like a stupid Approach to me… 1L05 – Sequential Logic 14 6.004 – Spring 20092/19/09Flakey Control SystemsHere’s a strategy for saving 3 bucks on the Sumner Tunnel! L05 – Sequential Logic 15 6.004 – Spring 20092/19/09Escapement Strategy The Solution: Add two gatesCartoon of a toll with series two gates. and only open one at a time. L05 – Sequential Logic 16 6.004 – Spring 20092/19/09Edge-triggered Flip Flop GDQGDQDQDCLKQDCLKQmaster slave Observations: only one latch “transparent” at any time: master closed when slave is open slave closed when master is open no combinational path through flip flop Q only changes shortly after 0 1 transition of CLK, so flip flop appears to be “triggered” by rising edge of CLK The gate of this latch is open when the clock is lowThe gate of this latch is open when the clock is highWhat does that one do? 0101SDGQ(the feedback path in one of the master or slave latches is always active) Transitions mark instants, not intervals Cartoon three cars behind closed gate.Figure by MIT OpenCourseWare. Figure by MIT OpenCourseWare.L05 – Sequential Logic 17 6.004 – Spring 20092/19/09Flip Flop Waveforms GDQGDQDQDCLKQDCLKQmaster slave DCLKQmaster closed slave openslave closed master openL05 – Sequential Logic 18 6.004 – Spring 20092/19/09Um, about that hold time… GDQGDQDQmaster slave CLKConsider HOLD TIME requirement for slave:• Negative (1 0) clock transition slave freezes data: • SHOULD be no output glitch, since master held constant data; BUT • master output contaminated by change in G input! • HOLD TIME of slave not met, UNLESS we assume sufficientcontamination delay in the path to its D input! Accumulated tCD thru inverter, G Q path of master must cover slave tHOLD for this design to work! The master’s contamination delay must meet the hold time of the slave L05 – Sequential Logic 19 6.004 – Spring 20092/19/09Flip Flop Timing -I CLKDQDQDCLKQtCDtCD: minimum contamination delay, CLK Q>tSETUPtSETUP: setup time guarantee that D has propagated through feedback path before master closes >tHOLDtHOLD: hold time guarantee master is closed and data is stable before allowing D to change L05 – Sequential Logic 20 6.004 – Spring 20092/19/09Single-clock Synchronous Circuits Single-clock Synchronous Discipline•No combinational cycles •Only care about value of register data inputs just before rising edge of clock •Period greater than every combinational delay •Change saved state after noise-inducing logic transitions have stopped! We’ll use Flip Flops and Registers – groups of FFs sharing a clock input – in a highly constrained way to build digital systems: •Single clock signal shared among all clocked devices Does that symbol register? L05 – Sequential Logic 21 6.004 – Spring 20092/19/09Flip Flop Timing -II CLKt1t1 = tCD,reg1 + tCD,1 > tHOLD,reg2 1DQDQCLKreg1reg2Questions for register-based designs: how much time for useful work (i.e. for combinational logic delay)?does it help to guarantee a minimum tCD? How ‘bout designing registers so that tCD,reg > tHOLD,reg?what happens if CLK signal doesn’t arrive at the two registers at exactly the same time (a phenomenon known as “clock skew”)? t2t2 = tPD,reg1 + tPD,1 < tCLK -tSETUP,reg2 QR1tCD,reg1 tCD, 1 tPD, 1 tPD,reg1 QR1L05 – Sequential Logic 22 6.004 – Spring 20092/19/09Model: Discrete Time Active Clock Edges punctuate time ---•Discrete Clock periods •Discrete State Variables •Discrete specifications (simple rules – eg tables – relating outputs to inputs, state variables) •ABSTRACTION: Finite State Machines (next lecture!) Combinational Logic Current State NewState InputOutput Memory Device Clock L05 – Sequential Logic 23 6.004 – Spring 20092/19/09Sequential Circuit Timing Questions: •Constraints on TCD for the logic? •Minimum clock period? •Setup, Hold times for Inputs? Combinational Logic Current State NewState InputOutput Clock tCD,L = ? tPD,L = 5ns tCD,R = 1ns tPD,R = 3ns tS,R = 2ns tH,R = 2ns > 1 ns > 10 ns (TPD,R+TPD,L+ TS,R)TS = TPD,L +TS,RTH = TH,R-TCD,LThis is a simple Finite State Machine … more next lecture!! L05 – Sequential Logic 24 6.004 – Spring 20092/19/09Summary“Sequential” Circuits (with memory): Basic memory elements: •Feedback, detailed analysis => basic level-sensitive devices (eg, latch) •2 Latches => Flop •Dynamic Discipline: constraints on input timing Synchronous 1-clock logic: •Simple rules for sequential circuits•Yields clocked circuit with TS, THconstraints on input timing Finite State Machines Next Lecture Topic! >ts>thClkQD>tcd