Documents

21 views

Chapter #8: Finite State Machine Design 8.1 - 8.2 Finite State Machine Design

Chapter #8: Finite State Machine Design 8.1 - 8.2 Finite State Machine Design. Chapter Overview. Concept of the State Machine • Partitioning into Datapath and Control • When Inputs are Sampled and Outputs Asserted Basic Design Approach • Six Step Design Process
of 21

Please download to get full document.

View again

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Transcript
Chapter #8: Finite State Machine Design8.1 - 8.2 Finite State Machine DesignChapter OverviewConcept of the State Machine • Partitioning into Datapath and Control • When Inputs are Sampled and Outputs AssertedBasic Design Approach • Six Step Design ProcessAlternative State Machine Representations • State Diagram, ASM Notation, VHDL, ABEL Description LanguageMoore and Mealy Machines• Definitions, Implementation ExamplesWord Problems • Case StudiesConcept of the State MachineComputer Hardware = Datapath + ControlQualifiersRegistersCombinational Functional Units (e.g., ALU)BussesFSM generating sequences of control signalsInstructs datapath what to do nextControl"Puppeteer who pulls thestrings"ControlStateControlSignalOutputsQualifiersandInputsDatapath"Puppet"Concept of the State MachineExample: Odd Parity CheckerAssert output whenever input bit stream has odd # of 1'sSymbolic State Transition TableStateDiagramEncoded State Transition Table===> One FF required because one bit is needed to represent the two statesConcept of the State MachineExample: Odd Parity CheckerLet Q = PS, Q+ = NS, X = InputUsing a D-FFDQ Q+ Q+ = DOutput X 01100 0 0 0 0 1 1 0 1 0 1 1 1101Since we have two states, we canimplement the circuit with one flip-flop.D = Q’X + QX’ = Q  XNSOutputXDQCLKQR\ResetD FF ImplementationConcept of the State MachineExample: Odd Parity CheckerLet Q = PS, Q+ = NS, X = InputUsing a T-FFTQ Q+ Q+ = T  Q==> T = Q+  QOutput X 01010 0 0 0 0 1 1 0 1 0 1 1 1101Since we have two states, we canimplement the circuit with one flip-flop.T = XXOutputTQCLKQR\ResetT FF ImplementationConcept of the State MachineTiming Behavior: Input 1 0 0 1 1 0 1 0 1 1 1 0Concept of State MachineTiming: When are inputs sampled, next state computed, outputs asserted?State Time: Time between clocking events• Clocking event causes state/outputs to transition, based on inputs• For set-up/hold time considerations: Inputs should be stable before clocking event• After propagation delay, Next State entered, Outputs are stableNOTE: Asynchronous signals take effect immediately Synchronous signals take effect at the next clocking eventE.g., tri-state enable: effective immediately sync. counter clear: effective at next clock event Concept of State MachineExample: Positive Edge Triggered Synchronous SystemOn rising edge, inputs sampled outputs, next state computedAfter propagation delay, outputs and next state are stableImmediate Outputs: affect datapath immediately could cause inputs from datapath to changeDelayed Outputs: take effect on next clock edge propagation delays must exceed hold timesConcept of the State MachineCommunicating State MachinesOne machine's output is another machine's inputMachines advance in lock stepInitial inputs/outputs: X = 0, Y = 0Basic Design ApproachSix Step Process1. Understand the statement of the Specification2. Obtain an abstract specification of the FSM(I.e. state diagram)3. Perform a state minimization4. Perform state assignment5. Choose FF types to implement FSM state register6. Implement the FSM1, 2 covered now; 3, 4, 5 covered later;4, 5 generalized from the counter design procedureBasic Design ApproachExample: Vending Machine FSMGeneral Machine Concept:deliver package of gum after 15 cents depositedsingle coin slot for dimes, nickelsno changeStep 1. Understand the problem:Draw a picture!Block DiagramVending Machine ExampleStep 2. Map into more suitable abstract representationTabulate typical input sequences:three nickels -- N,N,Nnickel, dime -- N,Ddime, nickel -- D,Ntwo dimes -- D,Dtwo nickels, dime -- N,N,DDraw state diagram:Inputs: N, D, resetOutput: openVending Machine ExampleStep 3: State MinimizationMooreMachinereuse stateswheneverpossibleSymbolic State TablePresent State Output Q Q D N Open 1 0 0 0 0 0 0 0 1 0 1 0 0 1 1 X 0 1 0 0 0 0 1 0 1 0 0 1 1 X 1 0 0 0 0 0 1 0 1 0 0 1 1 X 1 1 0 0 1 0 1 1 1 0 1 1 1 X Vending Machine ExampleStep 4: State EncodingInputs Next State Q1+ =D Q0+ =D 1 0 4 states ==>2 bits neededto represent0 0 0 1 1 0 X X 0 1 1 0 1 1 X X 1 0 1 1 1 1 X X 1 1 1 1 1 1 X X Q1 Q0 K-map for D1K-map for D0 K-map for Open Vending Machine ExampleStep 5. Choose FFs for implementationD FF easiest to useQ1 Q1 Q1 Q1 Q0 Q1 Q0 00 01 11 10 00 01 11 10 00 01 11 10 D N D N D N 00 0 0 1 1 00 0 1 1 0 00 0 0 1 0 01 0 1 1 1 01 1 0 1 1 01 0 0 1 0 N N N 11 X X X X11 X X X X 11 X X X X D D D 10 1 1 1 1 10 01 1 1 10 0 0 1 0 Q0 Q0 Q0 D1 = Q1 + D + Q0 ND0 = N Q0 + Q0 N + Q1 N + Q1 DOPEN = Q1 Q0Q 1 D Q D D Q 1 1 CLK \ Q Q Q 1 R 0 N \reset N OPEN \ Q 0 Q 0 \ N D Q D Q 0 0 Q CLK \ Q 1 Q 0 N R \reset Q 1 D Vending Machine ExampleD1 = Q1 + D + Q0 ND0 = N Q0 + Q0 N + Q1 N + Q1 DOPEN = Q1 Q08 Gates, 2 flip flopsPresent State J J K K 1 1 0 0 Q Q D N + Q Q 1 0 J K 0 0 0 X 0 X 0 0 0 0 0 X 0 X 1 X 0 1 0 1 1 X 1 X 0 X 1 0 1 0 X 1 X X X X 1 1 1 1 X 0 0 1 0 X X 0 0 0 1 X X 1 0 1 1 X X 0 1 0 X X X X 1 1 1 0 X 0 0 X 0 0 X 0 1 X 0 1 X 0 1 X 1 0 X X X X 1 1 1 1 X 0 X 0 0 0 X 0 X 0 0 1 X X 0 0 1 0 X X X X 1 1 Vending Machine ExampleStep 5. Choosing FF for ImplementationJ-K FFFlip Flop ValuesInputs Next State Q+ Q+100 0 0 1 1 0 X X 0 1 1 0 1 1 X X 1 0 1 1 1 1 X X 1 1 1 1 1 1 X X Remapped encoded state transition tableQ1 Q0 Q1 Q0 Q1 Q0 Q1 Q0 D N D N D N Vending Machine ExampleImplementation:Q1 Q1 00 01 11 10 00 01 11 10 D N 00 0 0 X X00 X X X 0 01 0 1 X X 01 X X X 0 J1 = D + Q0 NK1 = 0J0 = Q0 N + Q1 DK0 = Q1 NN N 11 XX X X 11 X X X X D D 10 1 1 X X 10 X X X 0 Q0 Q0 K-map for K1K-map for J1Q1 Q1 00 01 11 10 00 01 11 10 00 0 X X 0 00 X 0 0 X 01 1 X X 1 01 X 1 0 X N N 11 X X XX 11 X X X X Output OPEN does notchange: OPEN = Q1 Q0D D 10 0 X X 1 10 X00 X Q0 Q0 K-map for J0K-map for K0Vending Machine Example7 Gates, 2 flip flopsHW #14 -- Section 8.1 & 8.2
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks