New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Hertha Tremblay


Hertha Tremblay
GPA 3.59

Ian Harris

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Ian Harris
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 67 page Class Notes was uploaded by Hertha Tremblay on Saturday September 12, 2015. The Class Notes belongs to CompSci 151 at University of California - Irvine taught by Ian Harris in Fall. Since its upload, it has received 57 views. For similar materials see /class/201899/compsci-151-university-of-california-irvine in ComputerScienence at University of California - Irvine.

Similar to CompSci 151 at UCI

Popular in ComputerScienence




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15
Digital Design with RU Design VHDL anti Verilng Digital Design Chapter 3 Sequential Logic Design Controllers Slides to accompany the textbook Digital Design with RTL Design VHDL and Verilog 2nd Edition by Frank Vahid John Wiley and Sons Publishers 2010 httpwwwddvahidcom Frank Vahid f nWWileyiand39SUWquot r 39 m U 139 quot r H 1 393 y l 37 H 31 v39 IL quot m quot T hf Frin zerel eotwnizzme 2 I L 9 M w 7 x 31 Introduction p1 1 a Sequential circuit b o combinational gtF gt digital crrcult Output depends not just on present inputs as in combinational circuit but on past sequence of inputs Stores bits also known as having state a 9 O Sequential gtF Simple example a Circuit that counts up In binary bgt digital circuit This chapter will Design a new building block a flipflop to store one bit Mustknow sequence of Combine flipflops to build multibit storage register 19amans to Describe sequential behavior with finite state machines know output Convert a finite state machine to a controller sequential circuit with a register and combinational logic 7 Digital Design 2e Copyright 2010 2 Frank vahid Note Slides with animation are denoted with a small red quotaquot near the animated items 32 Storing One Bit FlipFlops Example Requiring Bit Storage bugj Bit 1 lueligt Flight attendant call buttV ab Storage Press call light turns on Stays on after button released Press cancel light turns off Call rue t Stays off after button release bumquot 32961 imh Cancel Logic gate circuit to implement thi 9 buttonlil 1 Call button pressed 7 light turns on 2 Call button released 7 light stays on Call 3 Cancel Call 0 Blue light butt 31 Doesn t work Q1 when Ca111 but mung Storlage doesn t stay 1 when Call returns to 0 button Need some form of feedback in the circuit 3 Cancel button pressedi light turns o by Digital Design 26 Copyright 2010 3 Frank Vahid First attempt at Bit Storage Need some sort of feedback 5 Q Does circuit on the right do what we want t o No Once Q becomes 1 when 81 Q stays 1 forever no value of S can bring Q back to 0 so 0Q S 0Q S 1Q S 1Q I 1Q O I I t l I x 1 t l 7 Digital Design 26 Copyright 2010 Frank Vahid Does the circuit to the right with crosscoupled NOR gates do what we want Yes How did someone come up with that circuit Maybe just trial and error a bit of insight I 50 0 Fl O O O OA Bit Storage Using an SR Latch SR latch Q R reset Recall NOR 03gt 1 0 13gt 0 x Digital Design 26 Copyright 2010 Frank Vahid storage in previous example of flightattendant call button Example Using SR Latch for Bit Storage SR latch can serve as bit Call1 sets Q to 1 Q stays 1 even after Call0 Canoel1 resets Q to O But there s a problem Digital Design 26 Copyright 2010 Frank Vahid Call button EI Ca l buggi Bit Sorage Blue ligwt jue it Problem with SR Latch Problem If 81 and R1 simultaneously we don t know what value Q will take 1 Q may oscillate Then because one path will be 1 slightly longer than the other Qwill eventually to I I I I I I I I I I settle to l or 0 but we don t know which 1 Q Known as a race COI ldlllOl l o 7 V7 Digital Design 26 Copyright 2010 7 Frank Vahid Problem with SR Latch Designer might try to avoid problem using external circuit Circuit should prevent SR from ever being 11 But 11 can occur due to different path delays External circuit Call Ca SR latch button Cancel button Cn R Assume 1 ns delay per gate The longer path from Call to R than from Call to S causes SRll for short time could be long enough to cause oscillation V7 Digital Design 26 Copyright 2010 Frank Vahid 1 I Call I 0 I Cncl 0 O 50 O I I U II 2 ns Problem with SR Latch Glitch can also cause 1 undesired set or reset Ca 0 External circuit Ca 3 SR latch 1 button CnCI O Q S 1 it R 0 SR 07 R 1 A undesired S th39 39 h 4 d I 39 uppose lS wzre as ns 6 ay 0 V gIl ch 4 ns 7 V7 Digital Design 26 Copyright 2010 9 Frank Vahid Solution LevelSensitive SR Latch Call Cncl Add enable input C Only let S and R change when CO Ensure circuit in front of SR never sets SR11 except briefly due to path delays Set C1 after time for S and R to be stable When C becomes 1 the stable S and R value passes through the two AND gates to the SR latch s S1 R1 inputs Call Levelsensitive SR latch V7 Digital Design 26 i Copyright 2010 Frank Vahid Cncl 81 R1 Levelsensitive SR latch T Levelsensitive SR latch symbol 5 Glitch on R or S doesn t affect R1 or 1 S 1 O I I orrec l I 39 values when 10 0 I I enabled LevelSensitive D Latch U I SR latch requires careful design to ensure SR11 never occurs D latch relieves designer of that c burden Inserted inverter ensures R always opposite of S R 87 R7 D latch U 0 D Q Q 2 m A O O O O OA O 7 V7 Digital Design 26 i Copyright 2010 Frank Vahid D latch symbol Problem with LevelSensitive D Latch D latch still has problem as does SR latch When C1 through how many latches will a signal travel Depends on how long C1 ClkA signal may travel through multiple latches ClkB signal may travel through fewer latches 1 1 1 1 Y D1 Q1 D2 Q2 D3 Q3 D4 1 C1 1 C2 1 C3 39 C4 Clk v v ClkA ClkB M Digital Design 26 Copyright 2010 Frank Vahid 12 Problem with LevelSensitive D Latch D latch D3 Q3 D4 Q4 C3 C4 I J D1 D1 l Q1D2 0102 Q1 doesn t change 82 32 R2 R2 02 quot2nd latch set Q2 390 c 7 V7 Digital Design 26 Copyright 2010 13 Frank Vahid D FlipFlop Can we design bit storage thatonly Flip flop Bit storage that stores on clock edge storesavalue on One design masterservant the wedge ofa Clk O master enabled loads D appears at Qm clock signal Servant disabled rising edges Clk 1 Master disabled Qm stays same Servant latch enabled loads Qm appears at 05 Thus value at D and hence at Qm when Clk changes from 0 to 1 gets stored into servlant Clk D flipflop Clk D latch D latch I DDm l D Dm Qm Ds Qs 0 l Cm I Ecm I39CS QS 2quot QmDs master servant Cs Note I Hundreds Clk of different QS E 7 Digital Design 26 l Copyright 2010 flipflop 1 4 Frank Vahid desrgns exist D FlipFlop Solves problem of not knowing through how many latches a signal travels when C1 In figure below signal travels through exactly one flipflop for ClkA or ClkB Why Because on rising edge of Clk all four flipflops are loaded simultaneously then all four no longer pay attention to their input until the next rising edge Doesn t matter how long Clk is 1 1 1 Y D1 Q1 D2 Q2 D3 Q3 D4 Q4 Two latches inside l gt each ip op V7 Digital Design 26 Copyright 2010 15 Frank Vahid D FlipFlop D Q O The triangle means edge 39gt Q triggered CIOCk iniout Symbol for risingedge triggered D flipflop rising edges Clk i V Digital Design 26 i Copyright 2010 Frank Vahid D Q 0 Internal design Just invert servant clock rather than master Symbol for fallingedge triggered D flipflop falling edges Clk 16 D Latch vs D FlipFlop Latch is levelsensitive Stores D when C1 Flipflop is edge triggered Stores D when C changes from O to 1 Saying levelsensitive latch or edgetriggered flipflop is redundant Comparing behavior of latch and flipflop Clk D DI t h Latch follows D Q a0 while Clkis Flip op only loads D Q D flipflop E 39 quot V7 DigitalDesignZe 39 5 during Clk msmg edge Copyright 2010 aquot 17 FrankVahid Flipflop Clk inputs typically connect to one clock signal Clock Signal Coming from an oscillator component Generates periodic pulsing signal Below quotPeriodquot 20 ns quotFrequencyquot 120 ns 50 MHz quotCyclequot is duration of 1 period 20 ns below shows 35 cycles 1 Clk Time00 ns 10 ns l 0 l 1 PeriodFreq shortcut Remember 1 ns 9 1 GHz 7 V7 Digital Design 2e i Copyright 2010 Frank Vahid 20 ns 0 30 ns 40 ns 0 50 ns 1 Clk 3960 ns O Freq Period 100 GHz 001 ns 10 GHz 01 ns 1 GHz 1 ns 100 MHz 10 ns 10 MHz 100 ns 18 FlightAttendant Call Button Using D FlipFlop o flipflop will store bit buifl39lil Inputs are Call Cancel and present value Cancel DAM Clout of D flipflop Q 39 Q v Truth table shown below C a l l C a H c el 0 D a o o o o Preserve value if QO make DO39 if D O 1 l Q1 make D1 O 1 O O Cancel make Ca 0 1 1 O DO button 1 o o 1 g 1 O 1 1 Call make D1 1 1 O 1 Let s give priority 1 1 1 1 to Call make Circuit derived from truth table Frank Vahid D1 using Chapter 2 combinational r logic dESign process V DigitalDesignZe a Copyright 2010 19 Bit Storage Summary SR latch Levelsensitive SR latch D latch D flipflop t 8 5e 8 S 57 D D latch Dm Qm C Cm Q Q master R reset R R Feature S1 Feature S and R only Feature SR can t be 11 Feature Only loads D value sets Q to 1 R1 have effect when C1 ProbemC1 for too long present at rising clock edge resets Q to 0 An external circuit can will propagate new values so values can39t propagate to Probem prevent SR11 when through too many latches other flipflops during same SR11 yields C1 for too short may not clock cycle Tradeo f39 uses undefined Q Probem avoiding result in the bit being more gates internally and other glitches SR11 can be a burden stored requires more external gates may setreset than SR but transistors today inadvertently are more plentiful and cheaper We considered increasingly better bit storage until we arrived at the robust D flipflop bit storage 7 Digital Design 26 Copyright 2010 20 Frank Vahid BaSIc Register Typically we store multibit items eg storing a 4bit binary number Register multiple flipflops sharing clock signal From this point we ll use registers for bit storage No need to think of latches or flipflops But now you know what s inside a register If I III IIO 39 l 39 l 4bit register I I I I D D D D I3 I2 I1 I0 Q Q Q Q gt 994 gt gt gt gt clk f f 1 03020100 I I I I I Q3 Q2 Q1 Q0 V7 Digital Design 26 Copyright 2010 21 Frank Vahid Example Using Registers Temperature Display Temperature history display Sensor outputs temperature as 5bit binary number Timer pulses C every hour Record temperature on each pulse display last three recorded values Present 1 hour ago 2 hours ago Display Display Display 24 Hill Mill Hill x4 a4 a3 a2 a1 a0 b4 b3 b2 b1 b0 c4 c3 c2 c1 c0 x3 X1 Temperatu reH istoryStorage x0 ollllll K timer V7 Digital Design 26 Copyright 2010 22 Frank Vahid Example Using Registers Temperature Display Use three 5bit registers 24 21 18 TemperatureHistoryStorage x4x0lt 15I1820212122242424252526262627272727 c a FeoX 182124252627 Note that registers Ra 0X 0X 18X21X24X25X2e X only loaded on rising R o o o 18 21 X 24 X 25 clock edges X r 7 Digital Design 26 Copyright 2010 23 Frank Vahid 33 meState Machines FSMs and Controllers Want sequential circuit with particular behavior over time Example Laser timer Pushing button causes x1 for exactly 3 clock cycles Preciselytimed laser pulse How Let s try three flipflops b1 gets stored in first D flip flop Then 2nd flipflop on next cycle then 3rd flipflop on next OR the three flipflop outputs so x should be 1 forthree cycles 7 Digital Design 26 i Copyright 2010 Frank Vahid I39I Controller clk gt laser 7 x patient Bad job what if button pressed a second time during 2 those 3 cycles 4 Need a Better Way to Design Sequential Circuits Also bad because of ad hoc design process How create other sequential circuits Need A way to capture desired sequential behavior A way to convert such behavior to a sequential circuit Step Description Create a truth table or equations whichever is capture the most natural for the given problem to describe function the desired behavior of each output ofthe we hadfor combinational logic deSlgnlng This substep is only necessary if you captured the 2A Create function using a truth table instead of equations Create comblnatlonal equations an equation for each output by ORing all the minterms circuits Convert for that output Simplify the equations if desired to circuit 251 Implement For each output create a circuit corresponding as a gate to the output s equation Sharing gates among V based CirCUit multiple outputs is OK optionally 7 Digital Design 26 Copyright 2010 25 Frank Vahid Capturing Sequential Circuit Behavior as FSM Outputs x FiniteState Machine FSM Describes desired behavior of sequential circuit Akin to Boolean equations for combinational behavior List states and transitions among states Digital Design 26 Copyright 2010 Frank Vahid Example Toggle x every clock cycle Two states Lo xO and Hi x1 Transition from L0 to Hi or Hi to L0 on rising clock edge clkquot Arrow points to initial state when circuit first starts 0 0 xO clkquot clkquot x1 I clk cycle1 cycle2 cycle3 cycle4 state lt Lo Outputs X bit or other info in a timing diagram Hi Hi I I I l I I I I I I 26 FSM Example Three Cycles High System WantO 1 1 1 O 1 1 1 For one clock cycle each Outputsx Capture as FSM xO elk x1 elk x1 elk x1 Four states 0 first 1 second 1 third 1 Transition on rising clock cm a edge to next state elk JLlLlLlLlLlLlLIL State orr0n10n20nd orr0n10n20n2l orrl Outputs I I I I X 7 V7 Di italDesi 26 Coiyright 6921010 27 FrankVahid ThreeCycles High System with Button Input lnpuz sb Outputs39x Wait in Off while b is O b Ckquot When bis 1 bCkquot L1 clkA x1 clkA transition to CM Sets x1 Next two Clock edges transition to On2 then On3 clk I L So x1 for three cycles after nputs button pressed b State Offl orrl orrl Offl Off On1On2On3 Offl x1 Outputs X i V7 Digital Design 26 Copyright 2010 28 Frank Vahid FSM Simplification Rising Clock Edges Implicit l t 39b39 O t t 39 Every edge ANDed with rising p 0 p S X clock edge What if we wanted a transition without a rising edge We don t consider such asynchronous FSMs less common and advanced topic Only consider synchronous FSMs rising edge on every XO transition Note Transition with no associated condition thus transistions to next state on next clock cycle Digital Design 26 Copyright 2010 29 Frank Vahid FSM Definition FSM conSiStS Of Inputs b Outputs x Set of states Ex Off On1 On2 On3 Set of inputs set of outputs Ex Inputs b Outputs x xO Initial state 0 Ex Off Set of transitions Each with condition We often draw FSM graphically Describes next states known as state diagram Ex Has 5 transitions Set of actions Sets outputs in each state Ex x0 x1 x1 and x1 V7 Digital Design 26 Copyright 2010 3 0 Frank Vahid Can also use table state table or textual languages FSM Example Secure Car Key Many new car keys include 5 tiny computer chip When key turned car s computer under engine hood requests identifier from key Key transmits identifier Inputs a Outputs r Wait Else computer doesn t start car r0 a a FSM Wait until computer requestsID a a 31 r1 r1 r0 r1 Transmit ID in this case 1 1 O 1 r V Digital Design 26 Copyright 2010 3 1 Frank Vahid FSM Example Secure Car Key cont Nice feature of FSM 39quotputszwutputsquot Can evaluate output behavior for different input sequence Timing diagrams show states and output values for different input waveforms Q Determine states and r value for given input waveform Inputs InPUtS a 8 State lWaitIWait K1 K2 K3 K4 IWaitIWaitl State WaitWait K1 K2 K3 K4 WaitK1 Outputs Output I a r l l r l l 7 V7 Digital Design 26 Copyright 2010 32 Frank Vahid Ex Earlier FlightAttendant Call Button Previously built using SR latch C BI r ht then Dflipflop buuinlil Bit 3399 Orae Q Capture desired bit storage iiltien39lil St 9 behavior using FSM instead Clear and precise description of desired behavior We ll later convert to a circuit Inputs Call Cnc Outputs L LO Ca L1 Call39 CnclCall3939 CnclCall39 7 V7 Digital Design 26 Copyright 2010 3 3 Frank Vahid How To Capture Desired Behavior as FSM List states Give meaningful names show initial state Optionally add some transitions if they help Create transitions For each state define all possible transitions leaving that state Refine the FSM Execute the FSM mentally and make any needed improvements 7 it Digital Design 26 i Copyright 2010 Frank Vahid 34 FSM Capture Example Code Detector Unlock door u1 only start 5 u 1 when buttons pressed gt Red r Code Door In sequence g lock Green detector start then red blue Blue green red 1 Input from each button snob Inputs srg ba Also output a Waitfor Start button Outputs u 0 S indicates that some colored button u pressed Capture as FSM List states Some transitions included S u0 u0 u0 u1 7 V7 Digital Design 26 Copyright 2010 3 5 Frank Vahid FSM Capture Example Code Detector Capture as FSM Start 8 U r R d r Door Create transrtlons a Grezn dgtggteor 39OCK Blue 7 i Inputs srgba Outputs u r V Digital Design 26 Copyright 2010 3 6 Frank Vahid FSM Capture Example Code Detector Capture as FSM Start 8 39 Red Code Door Create transrtrons a Green 9 detector 39OCK Repeat for remaining Blue states 1 Refine FSM Mentally execute Works for normal sequence Check unusual cases All colored buttons u0 pressed Door opens Change conditions other buttons NOT u0 pressed also Inputs srgba Outputs u V7 Digital Design 26 Copyright 2010 3 7 Frank Vahid FSM Capture Example Code Detector IIIIIIIIIIIIII Start 5 Red r Code a Green 9 detector BMe r 1 Inputs 3 r g ba Ouzjouz s u 7 V7 Digital Design 26 Copyright 2010 Frank Vahid Door lock 38 34 Controller Design Laser timer FSM Converting FSM to sequential circuit Circuit called controller Standard controller architecture Inputs b Outputs x State register stores encoding of current state eg Off00 On101 On210 On311 Combinational logic computes outputs and next state from inputs and current Controller for laser timer FSM state Rising clock edge takes controller to Laser timer controller next state b x FSM39 Combinational n1 FSM 39 1 Controller 0 inputs ogc ouww s G I FSM FSM S1 50 enem inputs ouzjouz s form clk gtState register m a clk Digital Design 26 3 9 Copyright 2010 Frank Vahid Controller Design Process Step Description Step 139 Capture the Create an FSM that describes the desired behavior Capture FSM of the controller behaVIor 2A S t Use state register of appropriate width and combinational 39 9 up logic The logic s inputs are the state register bits and the architecture ZBEncode the states Step 2 Convert to circuit 201 Flquot In the truth table 2D Implement combinational logic 7 V7 Digital Design 26 i Copyright 2010 Frank Vahid FSM inputs outputs are next state bits and the FSM outputs Assign unique binary number encoding to each state Usually use fewest bits assign encoding to each state by counting up in binary Translate FSM to truth table for combinational logic such that the logic will generate the outputs and next state signals for the given FSM Ordering the inputs with state bits first makes the correspondence between the table and the FSM clear Implement the combinational logic using any method 40 Controller Design Laser Timer Example Step 1 Capture the FSM Inputs b Outputsrx x0 Already done Step 2A Set up architecture 2 bit state register for 4 states nputboutputx Next state signals n1 n0 Step 28 Encode the states a 1 u E Combinational n1 Any encoding With each state logic unique will work s1 50 clk State register gtgt outputs V7 Digital Design 26 i Copyright 2010 Frank Vahid Controller Design Laser Timer Example cont Step 2C Fill in truth table Inputb0utputsx 6 Inputs 1 50 i O 0 g 0 1 1 1 1 1 1 a 150 1 1 1 1 1 1 1 1 1 1 1 1 7 V Digital Design 26 Copyright 2010 42 Frank Vahid Controller Design Laser Timer Example cont Step 2D Implement combinational logic FSM Inputs 039 X 31nd1no WS Inputs Outputs A A aeregl er s 1 so b ppm 10 gt O O O O O D Off 0 o 1 o o O 1 O 1 O 1 1 O X 81 80 note that x1 Ifs11 or 501 o 1 1 1 1 o 1 O O 1 1 1 n1 s1 sOb s1 sOb s1sO b s1sO b n1 51 50 15 0 12 1 o 1 1 1 1 0423 1 1 O 1 O 0 no s1 so b s lsO b stsO b 1 1 1 1 o o V 7 V Digital Design 26 Copyright 2010 43 Frank Vahid lt lt Controller Design Laser Timer Example cont Step 2D Implement b combinational logic cont Combinational Logic 51 50 State register xstsO Inputs Outputs 1 s0 13 x 111 110 3 8 2 a 3 2 0n 8 i 3 i i 8 03912 i 8 3 i i i 03913 i i 3 i 8 8 n1 st sO 3130 no st sO b 5130 i V Digital Design 26 i Copyright 2010 Frank Vahid 44 Understanding the Controller s Behavior x0 X0 X0 b b b b 0 Clk state00 stat e00 state01 Inputs Outputs x Digital Design 26 Copyright 2010 Frank Vahid 45 Controller Example Button Press Synchronizer dk cyde1 cycle2 cycle3 cycle4 Inputs bl l bi Button press b0 synchronizer Outputs h controller b0 Want simple sequential circuit that converts button press to single cycle duration regardless of length of time that button was actually pressed We assumed such an ideal button press signal in earlier example like the button in the laser timer controller V7 Digital Design 26 i Copyright 2010 Frank Vahid Controller Example Button Press Synchronizer cont n 59 FSM inputs bi FSM outputs bo a 3 3 5 1 Step 2A1 Set UIO arChIteCtUFe E Combinational quotquot 3 O logic n1 n1 s1 s0bi s1 sObi a n0 s1 s0 bi bo s1 s0bi s1 sObi s1s0 Combinational logic Step 1 Capture FSM b0 Combinational logic Inputs Outputs s1 50 bi n1 n0 bo FSM inputs biFSM outputs bo 0 0 0 0 0 0 O O 1 O 1 O u6uTB 001 O 1 1 1 O 1 39 1 o o o o 0 so bozo bo1 bozo 1 2 1 1 0 0 State register 1 1 O O O 0 Step ZB Encode states nusec39 1 1 1 o o o Step 2C Fill in truth table Step 2D Implement combinational logic 7 Digital Design 26 Copyright 2010 47 Frank Vahid Controller Example Sequence Generator Want generate sequence 0001 0011 1100 1000 repeat Each value for one clock cycle Common eg to create pattern in 4 lights or control magnets of a stepper motor Inputs none Outputs wxyz wxyz0001 wxyz0011 wxyz1000 wxyz1100 Step 1 Create FSM Step 2A Set up architecture Combinational logic Digital Design 26 Copyright 2010 Frank Vahid Inputs Outputs 5 1 s 0 w x y z n 1 n 0 A 0 0 0 0 0 1 0 1 B 0 1 0 0 1 1 1 0 C 1 0 1 1 0 0 1 1 D 1 1 1 0 0 0 0 0 Step 2C Fill in truth table ws1 xs1sO ys1 sO zs1 n1 s1xorsO n0sO n1 Step 2D E3 Inputs none Outputs wxyz gt z wxyz0001 wxyz1 000 39 5 1 o 0 wxyz001 1 wxyz1 100 Step 28 Encode states logic 48 Controller Example Secure Car Key from earlier example Inputs a Outputs r Inputs Outputs E a s 2 s 1 s O a r n 2 r1 1 r1 0 D r1 r1 r0 r1 Van U 0 O O O O O O 2 L D O O 1 O O D 1 g Combinational O O 1 D 1 O 1 O Q 39 9i K e e 1 1 1 0 1 e 93 I D 1 O O 1 O 1 1 K2 0 1 0 1 1 0 1 1 clk Kg 0 1 1 O O 1 O D U 1 l 1 U 1 D 0 Inputs at Outputs r K4 1 O O D 1 O 0 CI 1 O O 1 1 O D O r 1 U 1 O O O D 0 1 O l 1 O O O D Uanth i i 8 E B 8 g g 75 1 1 1 p 0 0 0 0 r1 r1 r0 r1 l l l l U 0 O U 1g1ta e51gn e 49 Copyright 2010 We ll omit Step ZD Frank Vahid Converting a Circuit to FSM Reverse Engineering 2D Circuit to eqns Step 1 FSM get from table What does this yS1 a z 3130 n1s1 xor sOx States n0s1 sO x 2C TrUth table Outputsyz Inputs Outputs states 51 SO x n1 n0 y z VF10 yz10 with A 0 0 o 0 0 1 0 outputs O O 1 O 1 1 O yz00 yzzm B O 1 O O O 1 O 0 1 1 1 0 1 O nputsx0itputsyz C 1 O O O 0 O 1 1 0 1 1 0 0 1 Work backwards D 1 1 0 0 0 0 0 1 1 1 O 0 0 O IZB Unencode states Pick any state names you want X states with outputs and r V Digital Design 26 tranSItlonS 5 0 i C 39 t 2010 Fg hid 2A Set up arch i already done Reverse Engin the Dflipflop Flight Atten Call Button Call button 39139 D Qo Blue 2C2 Inputs Outputs light Cancel 7 c button lil Clkgt Q Truth Q Call 11 1 D L m T table r3 3 3 C 3 e 1 1 r n Laght GE 0 1 n 1 1 2B 3 1 1 1 Unencode 1 1 g 1 1 2D C1rcu1t t0 eqns states 111111 1 1 1 1quot 1 L Q U 1 1 0 1 1 1 1 1 1 1 D Cncl39Q Call next state 2A Setup arch nothing Don t let the way the Circuit ZS drawn to do confuse you the combinational logic is quotPU S5 ca Onc Outputs 3 L everything outside the register Lo Ca L1 Step 1 FSM ca get from table CnCI Ca Ca39Cnc r V Digital Design 26 Copyright 2010 5 1 Frank Vahid Common Mistakes when Capturing FSMs Nonexclusive transitions o g ab 11 next state J 7 i Digital Design 26 i Copyright 2010 Frank Vahid Incomplete transitions a a b What if ab00 G a ab 52 Verifying Correct Transition Properties Can verify using Boolean algebra Answer Only one condition true AND of each condition pair for 29333 b transitions leaving a state should equal 0 9 proves pair o b can never simultaneously be true 0 K One condition true OR of all conditions of transrtlons O leaving a state should equal 1 9 proves at least one a 3b a1b a b condition must be true a ab ab Example a aa b a ab Fails Might not be 1 la aO ab bO Q For shown transitions prove whether Only one condition true AND of each pair is always 0 One condition true OR of all transitions is always 1 7 V7 Digital Design 26 Copyright 2010 5 3 Frank Vahid Verifying transition properties Recall code detector FSM We fixed a problem with the transition conditions Do the transitions obey the two required transition properties u Consider transitions of state Start and the only one true property i i 1 er a j a 3 bg ar gaitbig lntuitively press red and blue a a r O r a a r bg O r bg buttons at same time conditions aarr bg arr bg ar and ar bg will both be 0 0 arr arbarg true Which one should be O arbarg taken arb arg Q How to solve arbg A ar should be arb g likewise for ab ag ar Note As evidence the pitfall is common r DigitalDesignZe we admit the mistake was not initially intentional 54 gg ii 2010 A reviewer of an earlier edition ofthe book caught it Fails Means that two of Start s transitions could be true Simplifying Notations TY FSMs Assume unassigned output implicitly 39 assigned 0 a Sequential circuits m elk a b1 b0 c1 OO39QJ O O OO39QJ OO Assume unconnected clock inputs connected to same external clock r V Digital Design 26 Copyright 2010 5 5 Frank Vahid Mathematical Formalisms Two formalisms to capture behavior thus far Boolean equations for combinational circuit design w for sequential circuit design Not necessary But tremendously beneficial Structured methodology Correct circuits Automated design automated verification many more advantages V7 Digital Design 26 i Copyright 2010 Frank Vahid 56 35 More on FlipFlops and Controllers Nonideal flipflop behavior Can t change flipflop input too close to clock edge Setup time time D must be stable before edge Else stable value not present at internal latch Hold time time D must be held stable after edge Else new value doesn t have time to loop around and stabilize in internal latch D latch Setup time violation Digital Design 26 Copyright 2010 Frank Vahid clk I I Elt gti setup time Clk I I I I I H H hold time Leads to oscillation 57 Metastability Violating setuphold time can lead to bad situation Metastable state Any flipflop state other than stable 1 or O Eventually settles to either but we don t know which For internal circuits we can make sure to observe setup time But what if input is from external asynchronous source eg button press Partial solution Insert synchronizer flipflop for asynchronous input Special flipflop with very small setuphold time Digital Design 26 Copyright 2010 Frank Vahid ai ai l synchronizer Clk I I D i 39 i setup time violation Q metasta ble state 58 Metastability Synchronizer flipflop doesn t completely prevent metastability But reduces probability of metastability in dozenshundreds of internal flip flops storing important values Adding more synchronizer flipflops further reduces probability First ff likely stable before next clock second ff very unlikely to have setup time violated Drawback Change on input is delayed to internal flipflops By three clock cycles in below circuit Probability of flipflop being metastable is very very very incredibly low low low low ai gt gt gt gt synchronizers V7 Digital Design 26 gt Copyright 2010 5 9 Frank Vahid Example of Reducing Metastability Probability Recall earlier secure car key controller Inputs a Outputs r Adding synchronizer ip op reduces metastability probability in state register at expense of 1 cycle delay Original D a r a i o V gt p p Combinational logic State register clk gt clk V7 Digital Design 26 a Copyright 2010 60 Frank Vahid FlipFlop Set and Reset Inputs Some flipflops have D Qo D Qo DARQO additional resetset Inputs gt Q gt Q gt As Q Synchronous R AR I Synch reset Clears Q to O on next clock edge Synch set Sets Q to 1 on next clock edge Have priority over D input Asynchronous Asynch reset Clear Q to 0 independently of clock Example timing diagram shown cycle 1 cycle 2 cyole 3 cyole 4 Asynch set set Q to 1 indep of clock V7 Digital Design 26 Copyright 2010 61 Frank Vahid Initial State of a Controller All our FSMs had initial state inputs X Outputs b But our sequential circuits did not Can accomplish using flipflops with resetset inputs Shown circuit initializes flipflops to 01 Designer must ensure reset b X Combinational controller input IS 1 during power logic quot1 up of circuit n no By electronic Circuit deSIgn State register clk gtgt 0 Q0 D Q0 Controller with reset to initial 0 O gt R 0 gt S Q state assuming state reset l I was encoded as 0 controiiEr 39 7 Digital Design 26 Copyright 2010 62 Frank Vahid Glitching Glitch Temporary values on outputs that appear soon after input changes before stable new output values Designer must determine whether glitching outputs may pose a problem If so may consider adding flipflops to outputs Delays output by one clock cycle but may be OK Called registered output b x gt D xr Combinational n1 39 logic f gtlipflop s1ffs0 State register gt Laser timer controller with ip op to prevent glitches on x from unintentionally turning on laser 7 Digital Design 26 Copyright 2010 63 Frank Vahid Glitching Alternative registered output approach avoid 1 cycle delay Add extra state register bit for each output Connect output directly to its bit No logic between state register flipflop and output hence no glitches Inputs b Outputs x b 0 gt X Combination H logic l 31 sx State register 6 gt a Digitamesignk But uses more z39p ops plus more 64 g iirgiii 2010 logic to compute next state Digital Design 26 Copyright 2010 Frank Vahid Product Profile Pacemaker 65 Product Profile Pacemaker Pacemaker IOscl quot I V Inputs 3 z Outputs t p Controller lt l2 Timer counts down from 083 Basic pacemaker 7 V7 Digital Design 26 Copyright 2010 66 Frank Vahid Product Profile Pacemaker Pacemaker IOscl quot I Controller tv 2v ll TimerV V7 Digital Design 26 Copyright 2010 Frank Vahid right atrium Inputs sa za 3 ZV left atrium Outputs Pa ta pv tv ta 1 ResetTimerA left right ventricle ventricle Atrioventricular pacemaker 67


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.