L11: Major/Minor FSMs QuizQuiz (cont.)Toward FSM ModularityThe Major/Minor FSM AbstractionInside the Major FSMInside the Minor FSMOptimizing the Minor FSMA Four-FSM ExampleFour-FSM Sample WaveformL11: 6.111 Spring 20091Introductory Digital Systems LaboratoryL11: Major/Minor FSMs Acknowledgements: Rex Min Lecture Notes prepared by Professor Anantha ChadrakasanL11: 6.111 Spring 20092Introductory Digital Systems LaboratoryQuiz Quiz will be Closed Book Tuesday, March 17, 2009, 7:30pm-9:30pm in 32-155 Covers Problem Sets 1-3, Lectures 1-9 (through Arithmetic), Labs 1-3 Some of the topics to be covered include Combinational Logic: Boolean Algebra, Karnaugh Maps, MSP, MPS, dealing with don’t cares Latches and Edge Triggered Registers/Flip-flopsz Understand the difference between latches, registers and unclockedmemory elements (e.g., SR-Flip Flop)z Different memory types: SR, D, JK, Tz Understand setup/hold/propagation delay and how they are computed System Timing (minimum clock period and hold time constraint)z Impact of Clock skew on timing Counters and simple FSMs (understand how the ‘163 and ‘393 work) FSM design (Mealy/Moore, dealing with glitches) Combinational and sequential Verilog codingz Continuous assignments, blocking vs. non-blocking, etc.L11: 6.111 Spring 20093Introductory Digital Systems LaboratoryQuiz (cont.) Tri-states basics Dealing with glitchesz When are glitches OK?z How do you deal with glitches in digital system design? (registered outputs, appropriate techniques to gate a clock, etc.) Memory Basicsz Understand differences between DRAM vs. SRAM vs. EEPROMz Understand timing and interfacing to the 6264 Arithmeticz Number representation: sign – magnitude, Ones complement, Twos complementz Adder Structures: Ripple carry, Carry Bypass Adder, Carry Lookahead Adder z False Paths and Delay Estimationz Shift/add multiplier, Baugh-Wooley Multiplier (Twos complement multiplication)L11: 6.111 Spring 20094Introductory Digital Systems LaboratoryToward FSM Modularity Consider the following abstract FSM:S0a1b1c1d1S1S2S3S4S5S6S7S8S9a2b2c2d2a3b3c3d3 Suppose that each set of states ax...dxis a “sub-FSM” that produces exactly the same outputs. Can we simplify the FSM by removing equivalent states?No! The outputs may be the same, but the next-state transitions are not. This situation closely resembles a procedure call or function callin software...how can we apply this concept to FSMs?L11: 6.111 Spring 20095Introductory Digital Systems LaboratoryThe Major/Minor FSM Abstraction Subtasks are encapsulated in minor FSMs with common reset and clock Simple communication abstraction: START: tells the minor FSM to begin operation (the call) BUSY: tells the major FSM whether the minor is done (the return) The major/minor abstraction is great for... Modular designs (always a good thing) Tasks that occur often but in different contexts Tasks that require a variable/unknown period of time Event-driven systemsMajor FSMMinor FSM AMinor FSM BSTARTASTARTBBUSYABUSYBCLKRESETRESETCLKL11: 6.111 Spring 20096Introductory Digital Systems LaboratoryInside the Major FSMS1S2STARTS3S4...BUSYBUSYBUSYBUSYBUSY BUSY1. Wait until the minor FSM is ready2. Trigger the minor FSM (and make sure it’s started)3. Wait until the minor FSM is doneSTARTBUSYMajor FSM StateS1S2S2S3S3S3S4CLKL11: 6.111 Spring 20097Introductory Digital Systems LaboratoryInside the Minor FSMT2BUSYT3BUSYT4BUSY1. Wait for a trigger from the major FSM2. Do some useful workT1BUSYSTARTSTARTSTARTBUSYMajor FSM StateS1S2S2S3S3S3S4CLKMinor FSM StateT1T1T2T3T4T1T13. Signal to the major FSM that work is donecan we speed this up?L11: 6.111 Spring 20098Introductory Digital Systems LaboratoryOptimizing the Minor FSMT2BUSYT3BUSYT4BUSYT1BUSYSTARTSTARTGood idea: de-assert BUSY one cycle earlyBad idea #1:T4may not immediately return to T1T2BUSYT3BUSYT1BUSYSTARTSTARTT4BUSYBad idea #2:BUSY never asserts!T1BUSYSTARTSTARTT2BUSYL11: 6.111 Spring 20099Introductory Digital Systems LaboratoryA Four-FSM ExampleOperating Scenario: Major FSM is triggered by TICK Minors A and B are started simultaneously Minor C is started once both A and B complete TICKs arriving before the completion of C are ignoredMajor FSMMinor FSM AMinor FSM BSTARTASTARTBBUSYABUSYBMinor FSM CSTARTCBUSYCTICKIDLESTABSTARTASTARTBWTABTICKBUSYABUSYBTICKBUSYA+BUSYBBUSYA+BUSYBSTCSTARTCBUSYABUSYBBUSYCWTCBUSYCBUSYCBUSYCAssume that BUSYAand BUSYBboth rise before either minor FSM completes. Otherwise, we loop forever!L11: 6.111 Spring 200910Introductory Digital Systems LaboratoryFour-FSM Sample WaveformIDLE IDLESTABSTABWTABWTABWTABSTCSTCWTCWTCWTCIDLE IDLE STABstatetickSTARTABUSYASTARTBBUSYBSTARTCBUSYCMajor FSMMinor FSM AMinor FSM BSTARTASTARTBBUSYABUSYBMinor FSM
View Full Document
Unlocking...