Information about 2.digital design - sequential circuits

Sequential circuits Circuits with feedback – Outputs = f(inputs, past inputs, past outputs) – Basis for building "memory" into logic circuits – Door combination lock is an example of a sequential circuit • State is memory • State is an "output" and an "input" to combinational logic • Combination storage elements are also memory new value C1 C2 C3 multiplexer mux control equal comb. logic state comparator equal reset open/closed clock

Circuits with feedback How to control feedback? – What stops values from cycling around endlessly X1 X2 • • • Xn switching network Z1 Z2 • • • Zn

Simplest circuits with feedback Two inverters form a static memory cell – Will hold value as long as it has power applied "1" "stored value" "0" How to get a new value into the memory cell? – Selectively break feedback path – Load new value into cell "remember" "data" "load" "stored value"

Memory with cross-coupled gates Cross-coupled NOR gates – Similar to inverter pair, with capability to force output to 0 (reset=1) or 1 (set=1) R Q S Q' Q R S Cross-coupled NAND gates – Similar to inverter pair, with capability to force output to 0 (reset=0) or 1 (set=0) S' R' Q S' R' Q Q'

Timing behavior R S Reset R S Q Q Hold Q Q' Set Reset Set 100 Race

State behavior of R-S latch Truth table of R-S latch behavior Q Q' 0 1 S 0 0 1 1 R 0 1 0 1 Q hold 0 1 unstable Q Q' 1 0 Q Q' 0 0 Q Q' 1 1

Theoretical R-S latch behavior SR=10 SR=00 SR=01 Q Q' 0 1 SR=01 SR=01 SR=10 Q Q' 1 0 SR=11 State diagram – States: possible values – Transitions: changes based on inputs SR=11 SR=01 possible oscillation between states 00 and 11 Q Q' 0 0 SR=11 SR=00 SR=11 SR=00 SR=10 Q Q' 1 1 SR=00 SR=10

Observed R-S latch behavior Very difficult to observe R-S latch in the 1-1 state – One of R or S usually changes first Ambiguously returns to state 0-1 or 1-0 – A so-called "race condition" – Or non-deterministic transition SR=10 SR=00 SR=01 Q Q' 0 1 SR=01 SR=01 SR=10 Q Q' 1 0 SR=11 SR=11 SR=00 Q Q' 0 0 SR=11 SR=00 SR=00 SR=10

R-S latch analysis Break feedback path R Q Q' S S 0 0 0 0 1 1 1 1 R 0 0 1 1 0 0 1 1 Q(t) 0 1 0 1 0 1 0 1 Q(t+) 0 hold 1 0 reset 0 1 set 1 X not allowed X Q(t) Q(t+) S R S 0 Q(t) 0 X 1 1 0 X 1 R characteristic equation Q(t+) = S + R’ Q(t)

Gated R-S latch Control when R and S inputs matter – Otherwise, the slightest glitch on R or S while enable is low could cause change in value stored Set S' R' enable' Q Q' R R' Q enable' Q' S' S 100 Reset

Clocks Used to keep time – Wait long enough for inputs (R' and S') to settle – Then allow to have effect on value stored Clocks are regular periodic signals – Period (time between ticks) – Duty-cycle (time clock is high between ticks - expressed as % of period) duty cycle (in this case, 50%) period

Clocks(Cont.) Controlling an R-S latch with a clock – Can't let R and S change while clock is active (allowing R and S to pass) – Only have half of clock period for signal changes to propagate – Signals must be stable for the other half of clock period R' R Q R' and S' clock' S' stable changing stable changing stable Q' S clock

Cascading latches Connect output of one latch to input of another How to stop changes from racing through chain? – Need to control flow of data from one latch to the next – Advance from one latch per clock period – Worry about logic between latches (arrows) that is too fast R Q' R Q' S clock R S Q S Q

Master-Slave structure Break flow by alternating clocks (like an air-lock) – Use positive clock to latch inputs into one R-S latch – Use negative clock to change outputs with another R-S latch View pair as one basic unit – master-slave flip-flop – twice as much logic – output changes a few gate delays after the falling edge of clock but does not affect any cascaded flip-flops slave stage master stage R Q' S clock R S Q P' P R Q' S Q

The 1s catching problem In first R-S stage of master-slave FF – 0-1-0 glitch on R or S while clock is high "caught" by master stage – Leads to constraints on logic to be hazard-free Set S R CLK P P' Q Q' Reset slave stage master stage 1s catch R Master Outputs Slave Outputs Q' P' R Q' S clock R S Q S Q P

D flip-flop Make S and R complements of each other – Eliminates 1s catching problem – Can't just hold previous value (must have new value ready every clock period) – Value of D just before clock goes low is what is stored in flip-flop – Can make R-S flip-flop by adding logic to make D = S + R' Q slave stage master stage R S D clock Q' Q P' P R Q' Q' S Q Q 10 gates

Edge-triggered flip-flops More efficient solution: only 6 gates – sensitive to inputs only near edge of clock signal (not while high) D’ D holds D' when clock goes low 0 R negative edge-triggered D flip-flop (D-FF) 4-5 gate delays Q clock=1 must respect setup and hold time constraints to successfully capture input Q’ S 0 D D’ holds D when clock goes low characteristic equation Q(t+1) = D

Edge-triggered flip-flops(Cont.) Step-by-step analysis D’ D’ D D D’ R D’ R Q Clk=0 Clk=0 S S D D Q D’ when clock goes high-to-low data is latched D new D new D old D D’ when clock is low data is held

Edge-triggered flip-flops(Cont.) 0 1 0 1 0 1 0 The edge of the clock is used to sample the "D" input & send it to "Q” (positive edge triggering). – At all other times the output Q is independent of the input D (just stores previously sampled value). – The input must be stable for a short time before the clock edge.

Edge-triggered flip-flops(Cont.) Positive edge-triggered – Inputs sampled on rising edge; outputs change after rising edge Negative edge-triggered flip-flops – Inputs sampled on falling edge; outputs change after falling edge 100 D CLK Qpos Qpos' Qneg Qneg' positive edge-triggered FF negative edge-triggered FF

Comparison of latches and flip-flops D Q CLK positive edge-triggered flip-flop D CLK Qedge D Q G Qlatch CLK transparent (level-sensitive) latch behavior is the same unless input changes while the clock is high

Comparison of latches and flip-flops(Cont.) Type When inputs are sampled When output is valid unclocked latch always propagation delay from input change level-sensitive latch clock high (Tsu/Th around falling edge of clock) propagation delay from input change or clock edge (whichever is later) master-slave flip-flop clock high (Tsu/Th around falling edge of clock) propagation delay from falling edge of clock negative clock hi-to-lo transition propagation delay from falling edge edge-triggered (Tsu/Th around falling of clock flip-flop edge of clock)

Clock skew The problem – Correct behavior assumes next state of all storage elements determined by all storage elements at the same time – This is difficult in high-performance systems because time for clock to arrive at flip-flop is comparable to delays through logic – Effect of skew on cascaded flip-flops: 100 In Q0 Q1 CLK1 is a delayed version of CLK0 CLK0 CLK1 original state: IN = 0, Q0 = 1, Q1 = 1 due to skew, next state becomes: Q0 = 0, Q1 = 0, and not Q0 = 0, Q1 = 1

Meta-stability and asynchronous inputs Clocked synchronous circuits – Inputs, state, and outputs sampled or changed in relation to a common reference signal (called the clock) – E.g., master/slave, edge-triggered Asynchronous circuits – Inputs, state, and outputs sampled or changed independently of a common reference signal (glitches/hazards a major concern) – E.g., R-S latch Asynchronous inputs to synchronous circuits – Inputs can change at any time, will not meet setup/hold times – Dangerous, synchronous inputs are greatly preferred – Cannot be avoided (e.g., reset signal, memory wait, user input)

Synchronization failure Occurs when FF input changes close to clock edge – FF may enter a meta-stable state – neither a logic 0 nor 1 – – May stay in this state an indefinite amount of time – Is not likely in practice but has some probability logic 1 logic 0 logic 1 small, but non-zero probability that the FF output will get stuck in an in-between state logic 0 oscilloscope traces demonstrating synchronizer failure and eventual decay to steady state

Dealing with synchronization failure Probability of failure can never be reduced to 0, but it can be reduced – slow down the system clock: this gives the synchronizer more time to decay into a steady state; synchronizer failure becomes a big problem for very high speed systems – use fastest possible logic technology in the synchronizer: this makes for a very sharp "peak" upon which to balance – cascade two synchronizers: this effectively synchronizes twice (both would have to fail) asynchronous input D Q D synchronized input Q Clk synchronous system

Handling asynchronous inputs Never allow asynchronous inputs to fan-out to more than one flip-flop – Synchronize as soon as possible and then treat as synchronous signal Clocked Synchronous System Async Input D Q Synchronizer Q0 Async Input D Q D Q Clock Clock D Q Q1 Clock Q0 D Q Q1 Clock

Handling asynchronous inputs(Cont.) What can go wrong? – Input changes too close to clock edge (violating setup time constraint) In Q0 Q1 CLK In is asynchronous and fans out to D0 and D1 one FF catches the signal, one does not inconsistent state may be reached!

Flip-Flop features Reset (set state to 0) – R – Synchronous: Dnew = R' • Dold (when next clock edge arrives) – Asynchronous: doesn't wait for clock, quick but dangerous Preset or set (set state to 1) – S (or sometimes P) – Synchronous: Dnew = Dold + S (when next clock edge arrives) – Asynchronous: doesn't wait for clock, quick but dangerous Both reset and preset – Dnew = R' • Dold + S – Dnew = R' • Dold + R'S (set-dominant) (reset-dominant) Selective input capability (input enable/load) – LD or EN – Multiplexer at input: Dnew = LD' • Q + LD • Dold – Load may/may not override reset/set (usually R/S have priority) Complementary outputs – Q and Q'

Registers Collections of flip-flops with similar controls and logic – Stored values somehow related (e.g., form binary value) – Share clock, reset, and set lines – Similar logic at each stage Examples OUT1 – Shift registers "0" – Counters OUT2 R S D Q OUT3 R S D Q R S D Q OUT4 R S D Q CLK IN1 IN2 IN3 IN4

Register with selective/parallel load We often use registers to hold values for multiple clocks – Wait until needed – Used multiple times How do we modify our D flipflop so that it holds the value till we are done with it? En State Next A very simple FSM 0 1 D Q D clk enable enable clk Q Q Q Q D

Registers with clock gating Load signal is used to enable the clock signal to pass through if 1 and prevent the clock signal from passing through if 0. Example: For Positive Edge-Triggered or Negative Pulse Master-Slave Flipflop: Clock Load Gated Clock to FF What logic is needed for gating? Gated Clock = Clock + Load What is the problem? Clock Skew of gated clocks with respect to clock or each other

Register with selective/parallel load(Cont.) 1 load clock R31 0 R0

Shift register Holds samples of input – Store last 4 input values in sequence – 4-bit shift register: OUT1 IN CLK D Q D Q OUT2 D Q OUT3 D Q OUT4

Shift register with parallel load Operation: – cycle 1: load x, output x0 – cycle i: output xi Each stage: XI Q(I) Shift/load clk Q(I-1) if (shift==0 ) load FF from xi else from previous stage.

Shift register with parallel load(Cont.) shift=1 shift=0 4-bit version: X3 IN X2 X1 X0 Q(2) Q(3) Q(1) Q(0) Shift/load clk ?? ?? x3 ?? x3 x2 x3 ?? x2 x1 x2 x1 x3 x0

Shift registers with parallel load(Cont.) Parallel load shift register: X3 IN X2 Q(3) X1 Q(2) X0 Q(1) Shift/load clk “Parallel-to-serial converter” Also, works as “Serial-to-parallel converter”, if q values are connected out. Also get used as controllers (ala “ring counters”) Q(0)

Universal shift register Holds 4 values – – – – – Serial or parallel inputs Serial or parallel outputs Permits shift left or right Shift in new values from left or right output left_in left_out clear s0 s1 Universal shift register input right_out right_in clock clear sets the register contents and output to 0 s1 and s0 determine the shift function s0 0 0 1 1 s1 0 1 0 1 function hold state shift right shift left load new input

Universal shift register(Cont.) Design of universal shift register Consider one of the four flip-flops – New value at next clock cycle: Nth cell to N-1th cell clear 1 0 0 0 0 s0 – 0 0 1 1 s1 – 0 1 0 1 new value 0 output output value of FF to left (shift right) output value of FF to right (shift left) input to N+1th cell Q D CLK CLEAR 0 1 2 3 s0 and s1 control mux Q[N-1] (left) Input[N] Q[N+1] (right)

Universal shift register(Cont.) Shift register application Parallel-to-serial conversion for serial transmission parallel outputs Universal shift registeer Unversal shift reagister Universal shift register parallel inputs serial transmission Universal shift register

Register file Asel Din Bsel R0 Dsel °°° R31 ld multiplexor R2 Multiplexor 1 decoder R1 Bout Aout

Frequency divider Divide clock frequency by 4 CLK DFF Q D Q DFF Q D Q CLK CLK_4 CLK_4 Divide clock frequency by 3 DFF Q D Q DFF Q D Q CLK CLK_3 CLK_3 CLK

Pattern recognizer Combinational function of input samples – In this case, recognizing the pattern 1001 on the single input signal OUT OUT1 IN CLK D Q D Q OUT2 D Q OUT3 D Q OUT4

Counters Counters are sequential circuits which "count" through a specific state sequence. They can count up, count down, or count through other fixed sequences. Examples: – binary counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, 001, … – gray code counter: 000, 010, 110, 100, 101, 111, 011, 001, 000, 010, 110, … – one-hot counter: 0001, 0010, 0100, 1000, 0001, 0010, … – BCD counter: 0000, 0001, 0010, …, 1001, 0000, 0001 – pseudo-random sequence generators: 10, 01, 00, 11, 10, 01, 00, ... Two distinct types are in common usage: Ripple Counters – Clock is connected to the flip-flop clock input on the LSB bit flip-flop – For all other bits, a flip-flop output is connected to the clock input, thus circuit is not truly synchronous – Output change is delayed more for each bit toward the MSB. – Resurgent because of low power consumption Synchronous Counters – Clock is directly connected to the flip-flop clock inputs – Logic is used to implement the desired state sequencing

Counters(Cont.) What are they used for? Examples: – Clock divider circuits 16MHz 64 – Delays, Timing – Protocols – Counters simplify controller design… • More on this later

Ripple counter How does it work? – When there is a positive edge on the clock input of A, A complements – The clock input for flipflop B is the complemented output of flip-flop A – When flip A changes from 1 to 0, there is a positive edge on the clock input of B causing B to complement A D Clock R D B R Reset CP A B 0 1 2 3 0 1

Ripple counter(Cont.) The arrows show the CP cause-effect relationA ship from the prior slide => B The corresponding 0 1 0 1 2 3 sequence of states => (B,A) = (0,0), (0,1), (1,0), (1,1), (0,0), (0,1), … Each additional bit, C, D, …behaves like bit B, changing half as frequently as the bit before it. For 3 bits: (C,B,A) = (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1), (0,0,0), …

Ripple counter(Cont.) These circuits are called ripple counters because each edge sensitive transition (positive in the example) causes a change in the next flip-flop’s state. The changes “ripple” upward through the chain of flip-flops, i. e., each transition occurs after a clock-to-output delay from the stage before. To see this effect in detail look at the waveforms on the next slide.

Ripple counter(Cont.) Starting with C = B = A = 1, equivalent to (C,B,A) = 7 base 10, the next clock increments the count to (C,B,A) = 0 base 10. In fine timing detail: – The clock to output delay tPHL causes an increasing delay from clock edge for each stage transition. – Thus, the count “ripples” from least to most significant bit. – For n bits, total worst case delay is n tPHL. Discouraged Know it exists Don’t use it tPHL CP A tPHL tpHL B C

Synchronous counters To eliminate the "ripple" effects, use a common clock for each flip-flop and a combinational circuit to generate the next state. For binary counters (most common case) incrementer circuit would work, 1 + register

Synchronous counters(Cont.) OUT1 D Q CLK "1" OUT2 D Q OUT3 D Q OUT4 D Q c 0 0 0 0 1 1 1 1 b 0 0 1 1 0 0 1 1 a 0 1 0 1 0 1 0 1 c+ b + a+ 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0

Synchronous counters(Cont.) Q 0 D Q 1 D Q 2 D 1 D Q 3 Carry Output CO Clock

counters with enable to count Count Count Enable D Q 0 D Q 1 D Q 2 D Q 3 – Forces all outputs to “hold” the state. Count Action 0 Hold stored value 1 Count up stored value Carry Output CO Clock

Counter with parallel load Load Count D 0 D Q 0 D 1 D Q 1 D 2 D Q 2 D 3 D Q 3 Add path for input data – enabled for Load = 1 Add logic to: – disable count logic for Load = 1 – disable feedback from outputs for Load = 1 – enable count logic for Load = 0 and Count = 1 The resulting function table: Load Count Action 0 0 Hold Stored Value 0 1 Count Up Stored Value 1 X Load D Carry Output CO Clock

Four-bit binary synchronous up-counter Standard component with many applications – – – – Positive edge-triggered FFs w/ sync load and clear inputs Parallel load data from D, C, B, A Enable inputs: must be asserted to enable counting RCO: ripple-carry out used for cascading counters • high when counter is in its highest state 1111 • implemented using an AND gate EN (2) RCO goes high (3) High order 4-bits are incremented (1) Low order 4-bits = 1111 D C RCO B QD A QC LOAD QB QA CLK CLR

Offset counters Starting offset counters – use of synchronous load – e.g., 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1111, 0110, . . . Ending offset counter – comparator for ending value "1" "0" "1" "1" "0" "0" EN RCO QD D QC C QB B QA A LOAD CLK CLR – e.g., 0000, 0001, 0010, ..., 1100, 1101, 0000 Combinations of the above (start and stop value) "1" "0" "0" "0" "0" EN D C B A LOAD CLK CLR RCO QD QC QB QA

Design up-down counter c b a c + b + a+ 0 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 0 0 1 1 1 0 1 1 0 0 1 1 0 1 0 1 1 Down-count 1 1 1 1 0

Other counters Sequences through a fixed set of patterns – In this case, 1000, 0100, 0010, 0001 – If one of the patterns is its initial state (by loading or set/reset) OUT1 OUT2 OUT3 OUT4 IN D Q D Q D Q D Q CLK Mobius (or Johnson) counter – In this case, 1000, 1100, 1110, 1111, 0111, 0011, OUT1 OUT2 OUT3 OUT4 0001, 0000 IN CLK D Q D Q D Q D Q

Sequential logic implementation Sequential circuits – Primitive sequential elements – Combinational logic Models for representing sequential circuits – Finite-state machines (Moore and Mealy) – Representation of memory (states) – Changes in state (transitions) Basic sequential circuits – Shift registers – Counters Design procedure Storage Elements – State diagrams – State transition table – Next state functions Outputs Inputs Combinational logic State Next State

Abstraction of state elements Divide circuit into combinational logic and state Localize feedback loops and make it easy to break cycles Implementation of storage elements leads to various forms of sequential logic Inputs Combinational Logic State Inputs Outputs State Outputs Storage Elements

Forms of sequential logic Asynchronous sequential logic – state changes occur whenever state inputs change (elements may be simple wires or delay elements) Synchronous sequential logic – state changes occur in lock step across all storage elements (using a periodic waveform - the clock) Combinational logic Combinational logic Clock

Synchronous circuit Combinational Logic clk time

Synchronous circuit(Cont.) clock input input CL reg CL reg output option feedback output Combinational Logic Blocks (CL) – Acyclic – no internal state (no feedback) – output only a function of inputs Registers (reg) – collections of flip-flops clock – distributed to all flip-flops ALL CYCLES GO THROUGH A REG!

Finite state machine representations States: determined by possible values in sequential storage elements Transitions: change of state Clock: controls when state can change by controlling storage elements 010 001 In = 0 Sequential logic In = 1 100 111 In = 0 In = 1 110 – Sequences through a series of states – Based on sequence of values on input signals – Clock period defines elements of sequence

Example : finite state machine diagram Combination lock from first slide ERR closed not equal & new S1 reset closed mux=C1 not new not equal & new S3 S2 equal & new closed mux=C2 not new not equal & new equal & new closed mux=C3 not new OPEN equal & new open

Can any sequential system be represented with a state diagram? Shift register OUT1 – Input value shown IN on transition arcs CLK – Output values shown within state node 0 000 0 001 0 0 D Q 1 1 101 0 OUT3 110 1 010 1 0 D Q 1 100 1 D Q OUT2 111 0 1 0 011 1

Counters are simple finite state machines Counters – Proceed thru well-defined state sequence in response to enable Many types of counters: binary, BCD, Gray-code – 3-bit up-counter: 000, 001, 010, 011, 100, 101, 110, 111, 000, ... – 3-bit down-counter: 111, 110, 101, 100, 011, 010, 001, 000, 111, ... 001 000 010 011 100 3-bit up-counter 111 110 101

How do we turn a state diagram into logic? Counter – Three flip-flops to hold state – Logic to compute next state – Clock signal controls when flip-flop memory can change • Wait long enough for combinational logic to compute new value • Don't wait too long as that is low performance OUT1 D Q CLK "1" OUT2 D Q OUT3 D Q

FSM design procedure Start with counters – Simple because output is just state – Simple because no choice of next state based on input State diagram to state transition table – Tabular form of state diagram – Like a truth-table State encoding – Decide on representation of states – For counters it is simple: just its value Implementation – Flip-flop for each state bit – Combinational logic based on encoding

FSM design procedure: State diagram to encoded state transition table Tabular form of state diagram Like a truth-table (specify output for all input combinations) Encoding of states: easy for counters – just use value current state next state 001 000 010 011 100 3-bit up-counter 111 110 101 0 1 2 3 4 5 6 7 000 001 010 011 100 101 110 111 001 010 011 100 101 110 111 000 1 2 3 4 5 6 7 0

Implementation D flip-flop for each state bit Combinational logic based on encoding C3 0 0 0 0 1 1 1 1 C2 0 0 1 1 0 0 1 1 C1 0 1 0 1 0 1 0 1 N3 N3 0 0 0 1 1 1 1 0 C3 N2 0 1 1 0 0 1 1 0 notation to show function represent input to D-FF N1 1 0 1 0 1 0 1 0 N1 := C1' N2 := C1C2' + C1'C2 := C1 xor C2 N3 := C1C2C3' + C1'C3 + C2'C3 := C1C2C3' + (C1' + C2')C3 := (C1C2) xor C3 N2 C3 N1 C3 0 0 1 1 0 1 1 0 1 1 1 1 C1 0 1 0 1 C1 1 0 0 1 C1 0 0 0 0 C2 C2 C2

Another example Shift register – Input determines next state In 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 C1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 C2 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 C3 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 N1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 N2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 N3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 1 1 100 0 1 0 000 0 001 N1 := In N2 := C1 N3 := C2 IN CLK 010 1 0 D Q 111 0 1 011 0 OUT1 D Q 1 1 101 0 0 110 OUT2 D Q OUT3 1

More complex counter example Complex counter – Repeats five states in sequence – Not a binary number representation Step 1: derive the state transition diagram – Count sequence: 000, 010, 011, 101, 110 Step 2: derive the state transition table from the state transition diagram Present State Next State C B A C+ B+ A+ 0 0 0 0 1 0 0 0 1 – – – 0 1 0 0 1 1 0 1 1 1 0 1 010 101 1 0 0 – – – 1 0 1 1 1 0 1 1 0 0 0 0 011 1 1 1 – – – note the don't care conditions that arise from the unused state codes 000 110

More complex counter example(Cont.) Step 3: K-maps for Next State Functions C+ B+ C 0 A 0 0 X X 1 X 1 A+ C 1 A 1 0 X X 0 X 1 B B C+ := A B+ := B' + A'C' A+ := BC' C 0 A 1 0 X X 1 X 0 B

Self-Starting counters(Cont.) Re-deriving state transition table from don't care assignmentB+ A+ C+ C C C 0 A 0 0 1 1 1 1 1 0 A B Present State Next State C B A C+ B+ A+ 0 0 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 0 1 1 0 0 0 0 1 1 1 1 0 0 1 0 1 1 0 0 0 1 A 1 0 0 0 1 0 0 B B 111 001 000 110 100 010 101 011

Self-Starting counters Start-up states – At power-up, counter may be in an unused or invalid state – Designer must guarantee it (eventually) enters a valid state Self-starting solution – Design counter so that invalid states eventually transition to a valid state – May limit exploitation of don't cares 111 111 001 000 110 implementation on previous slide 000 100 001 110 100 010 101 011 010 101 011

State machine model Values stored in registers represent the state of the circuit Combinational logic computes: – Next state • Function of current state and inputs – Outputs • Function of current state and inputs (Mealy machine) • Function of current state only (Moore machine) Inputs output logic next state logic Current State Outputs Next State

State machine model(Cont.) output logic Inputs Outputs next state logic Next State States: S1, S2, ..., Sk Inputs: I1, I2, ..., Im Current State Outputs: O1, O2, ..., On Transition function: Fs(Si, Ij) Output function: Fo(Si) or Fo(Si, Ij) Next State State Clock 0 1 2 3 4 5

Example: ant brain Sensors: L and R antennae, 1 if in touching wall Actuators: F - forward step, TL/TR - turn left/right slightly Goal: find way out of maze Strategy: keep the wall on the right

Example: ant brain(Cont.) Ant behavior A: Following wall, touching Go forward, turning left slightly C: Break in wall Go forward, turning right slightly E: Wall in front Turn left until... LOST: Forward until we touch something B: Following wall, not touching Go forward, turning right slightly D: Hit wall again Back to state A F: ...we are here, same as state B G: Turn left until...

Example: ant brain(Cont.) Designing an ant brain State diagram L+R LOST (F) L’ R’ L+R L’ R L E/G (TL) L’ R’ A (TL, F) R L’ R’ B (TR, F) R’ R C (TR, F) R’

Example: ant brain(Cont.) Synthesizing the ant brain circuit Encode states using a set of state variables – Arbitrary choice - may affect cost, speed Use transition truth table – Define next state function for each state variable – Define output function for each output Implement next state and output functions using combinational logic – 2-level logic – Multi-level logic – Next state and output functions can be optimized together

Example: ant brain(Cont.) Transition truth table Using symbolic states and outputs LOST L + R (F) L’ R’ L+R E/G (TL) L’ R’ L’ R A (TL, F) L R L’ R’ state LOST LOST LOST A A A B B ... L 0 – 1 0 0 1 – – ... R 0 1 – 0 1 – 0 1 ... next state LOST E/G E/G B A E/G C A ... outputs F F F TL, F TL, F TL, F TR, F TR, F ... B (TR, F) R’ R C (TR, F) R’

Example: ant brain(Cont.) Synthesis 5 states : at least 3 state variables required (X, Y, Z) – State assignment (in this case, arbitrarily chosen) state X,Y,Z 000 000 ... 010 010 010 010 011 011 ... L R 0 0 0 1 ... ... 0 0 0 1 1 0 1 1 0 0 0 1 ... ... next state X', Y', Z' 000 001 ... 011 010 001 001 100 010 ... outputs F TR TL 1 0 0 1 0 0 ... 1 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 ... it now remains to synthesize these 6 functions LOST E/G A B C - 000 001 010 011 100

Example: ant brain(Cont.) Synthesis of next state and output functions state X,Y,Z 000 000 000 001 001 001 010 010 010 011 011 100 100 inputs L R 0 0 - 1 1 0 0 - 1 1 0 0 0 1 1 - 0 - 1 - 0 - 1 next state X+,Y+,Z+ 000 001 001 011 010 010 011 010 001 100 010 100 010 outputs F TR TL 1 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1 0 e.g. TR = X + Y Z X+ = X R’ + Y Z R’ = R’ TR

Example: ant brain(Cont.) Circuit implementation Outputs are a function of the current state only - Moore machine F TR TL output logic L R next state logic Current State Next State X+ Y+ Z+ X Y Z

Example: ant brain(Cont.) Don’t cares in FSM synthesis What happens to the "unused" states (101, 110, 111)? Exploited as don't cares to minimize the logic – If states can't happen, then don't care what the functions do – if states do happen, we may be in trouble L’ R’ 000 (F) 101 L+R L+R 001 (TL) L’ R’ L’ R 010 (TL, F) L R L’ R’ 011 (TR, F) 110 111 Ant is in deep trouble if it gets in this state R’ R 100 (TR, F) R’

Example: ant brain(Cont.) State minimization Fewer states may mean fewer state variables High-level synthesis may generate many redundant states Two state are equivalent if they are impossible to distinguish from the outputs of the FSM, i. e., for any input sequence the outputs are the same Two conditions for two states to be equivalent: – Output must be the same in both states – Must transition to equivalent states for all input combinations

Example: ant brain(Cont.) Ant brain revisited Any equivalent states? L+R LOST (F) L’ R’ L+R L’ R L E/G (TL) L’ R’ A (TL, F) R L’ R’ B (TR, F) R’ R C (TR, F) R’

Example: ant brain(Cont.) New improved brain Merge equivalent B and C states Behavior is exactly the same as the 5-state brain We now need only 2 state variables rather L+R than 3 LOST (F) L+R L’ R’ L E/G (TL) L’ R’ A (TL, F) R L’ R’ R’ B/C (TR, F) L’ R

Example: ant brain(Cont.) New brain implementation state X,Y 00 00 00 01 01 01 10 10 10 11 11 inputs L R 0 0 - 1 1 0 0 - 1 1 0 0 0 1 1 - 0 - 1 next state outputs X',Y' F TR TL 00 1 0 0 01 1 0 0 01 1 0 0 11 0 0 1 01 0 0 1 01 0 0 1 11 1 0 1 10 1 0 1 01 1 0 1 11 1 1 0 10 1 1 0 X+ L X 0 0 0 0 1 0 0 0 1 1 1 1 Y+ 1 1 0 0 R L X 0 1 1 1 1 0 0 0 Y F L X 1 1 1 1 0 0 0 0 1 1 1 1 Y 1 1 1 1 1 0 0 1 1 0 1 1 R Y TR R L X 0 0 0 0 0 0 0 0 1 1 1 1 Y 0 0 0 0 TL R L X 0 0 0 0 1 1 1 1 0 0 0 0 Y 1 1 1 1 R

Mealy vs. Moore machines Moore: outputs depend on current state only Mealy: outputs depend on current state and inputs Ant brain is a Moore Machine – Output does not react immediately to input change We could have specified a Mealy FSM – Outputs have immediate reaction to inputs – As inputs change, so does next state, doesn’t commit until clocking event L’ R / TL, F L / TL A react right away to leaving the wall L’ R’ / TR, F

Specifying outputs for a Moore machine Output is only function of state – Specify in state bubble in state diagram – Example: sequence detector for 01 or 10 0 1 B/0 D/1 0 reset 0 1 A/0 1 1 C/0 1 0 E/1 0 reset 1 0 0 0 0 0 0 0 0 0 0 input – 0 1 0 1 0 1 0 1 0 1 current state – A A B B C C D D E E next state A B C B D E C E C B D output 0 0 0 0 0 0 1 1 1 1

Specifying outputs for a Mealy machine Output is function of state and inputs – Specify output on transition arc between states – Example: sequence detector for 01 or 10 0/0 B 0/0 reset/0 0/1 A 1/1 1/0 C 1/0 reset 1 0 0 0 0 0 0 input – 0 1 0 1 0 1 current state – A A B B C C next state A B C B C B C output 0 0 0 0 1 1 0

Comparison of Mealy and Moore machines Mealy machines tend to have less states – Different outputs on arcs (n^2) rather than states (n) Moore machines are safer to use – Outputs change at clock edge (always one cycle later) – In Mealy machines, input change can cause output change as soon as logic is done – a big problem when two machines are interconnected – asynchronous feedback Mealy machines react faster to inputs – React in same cycle – don't need to wait for clock – In Moore machines, more logic may be necessary to decode state into outputs – more gate delays after inputs combinational logic for next state state feedback inputs R logic for outputs outputs logic for outputs combinational logic for next state state feedback outputs R

Mealy and Moore examples Recognize A,B = 0,1 – Mealy or Moore? A D B clock Q out Q A D Q Q B clock D Q Q out

Mealy and Moore examples(Cont.) Recognize A,B = 1,0 then 0,1 – Mealy or Moore? out A D Q Q B D Q Q clock out A D Q D Q B D Q Q clock Q Q D Q Q

Registered Mealy machine(Really Moore) Synchronous (or registered) Mealy machine – Registered state AND outputs – Avoids ‘glitchy’ outputs – Easy to implement in PLDs Moore machine with no output decoding – Outputs computed on transition to next state rather than after entering – View outputs as expanded state vector Inputs output logic next state logic Current State Outputs

Example: vending machine Release item after 15 cents are deposited Single coin slot for dimes, nickels No change Reset N Coin Sensor D Vending Machine FSM Clock Open Release Mechanism

Example: vending machine(Cont.) Suitable abstract representation Reset – Tabulate typical input sequences: • • • • 3 nickels nickel, dime dime, nickel two dimes S0 N – Draw state diagram: • Inputs: N, D, reset • Output: open chute – Assumptions: • Assume N and D asserted for one cycle • Each state has a self loop for N = D = 0 (no coin) D S1 N S3 N S7 [open] S2 D N S4 [open] S5 [open] D S6 [open]

Example: vending machine(Cont.) Minimize number of states - reuse states whenever possible present state 0¢ Reset 0¢ 5¢ N 5¢ N D D 10¢ 10¢ N+D 15¢ [open] 15¢ inputs D N 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 – – next state 0¢ 5¢ 10¢ – 5¢ 10¢ 15¢ – 10¢ 15¢ 15¢ – 15¢ symbolic state table output open 0 0 0 – 0 0 0 – 0 0 0 – 1

Example: vending machine(Cont.) Uniquely encode states present state inputs Q1 Q0 D N 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 – – next D1 0 0 1 – 0 1 1 – 1 1 1 – 1 state D0 0 1 0 – 1 0 1 – 0 1 1 – 1 output open 0 0 0 – 0 0 0 – 0 0 0 – 1

Example: vending machine(Cont.) Mapping to logic D1 Q1 D X X X X 1 1 1 1 Q0 Q1 Open 0 0 1 0 0 1 1 0 0 0 1 1 0 1 1 1 Q1 D0 1 0 1 1 N D X X X X 0 0 1 0 N 0 1 1 1 D X X X X N 0 0 1 0 Q0 Q0 D1 = Q1 + D + Q0 N D0 = Q0’ N + Q0 N’ + Q1 N + Q1 D OPEN = Q1 Q0

Example: vending machine(Cont.) One-hot encoding present state Q3 Q2 Q1 Q0 0 0 0 1 0 0 0 1 1 0 1 0 0 0 0 0 inputs D N 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 0 0 0 1 1 0 1 1 - - next state D3 D2 D1 0 0 0 0 0 1 0 1 0 - - 0 0 1 0 1 0 1 0 0 - - 0 1 0 1 0 0 1 0 0 - - 1 0 0 output D0 open 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 D0 = Q0 D’ N’ D1 = Q0 N + Q1 D’ N’ D2 = Q0 D + Q1 N + Q2 D’ N’ D3 = Q1 D + Q2 D + Q2 N + Q3 OPEN = Q3

Example: vending machine(Cont.) OPEN = Q1Q0 creates a combinational delay after Q1 and Q0 change This can be corrected by retiming, i.e., move flip-flops and logic through each other to improve delay OPEN = reset'(Q1 + D + Q0N)(Q0'N + Q0N' + Q1N + Q1D) = reset'(Q1Q0N' + Q1N + Q1D + Q0'ND + Q0N'D) Implementation now looks like a synchronous Mealy machine – Common for programmable devices to have FF at end of logic

Equivalent Mealy and Moore state diagrams Moore machine – outputs associated with state N’ D’ + Reset Reset 0¢ [0] Mealy machine outputs associated with transitions 0¢ N’ D’ N D 5¢ [0] 10¢ [0] N’ D’ D/0 5¢ N’ D’/0 10¢ N’ D’/0 15¢ Reset’/1 N/0 N’ D’ N+D 15¢ [1] N’ D’/0 N/0 N D (N’ D’ + Reset)/0 Reset/0 D/1 N+D/1 Reset’

Example: traffic light controller A busy highway is intersected by a little used farmroad Detectors C sense the presence of cars waiting on the farmroad – with no car on farmroad, light remain green in highway direction – if vehicle on farmroad, highway lights go from Green to Yellow to Red, allowing the farmroad lights to become green – these stay green only as long as a farmroad car is detected but never longer than a set interval – when these are met, farm lights transition from Green to Yellow to Red, allowing highway to return to green – even if farmroad vehicles are waiting, highway gets at least a set interval as green Assume you have an interval timer that generates: – – – – a short time pulse (TS) and a long time pulse (TL), in response to a set (ST) signal. TS is to be used for timing yellow lights and TL for green lights

Example: traffic light controller(Cont.) Highway/farm road intersection farm road car sensors highway

Example: traffic light controller(Cont.) Tabulation of inputs and outputs inputs reset C TS TL description outputs description place FSM in initial state HG, HY, HR assert green/yellow/red highway lights detect vehicle on the farm road FG, FY, FR assert green/yellow/red highway lights short time interval expired ST start timing a short or long interval long time interval expired Tabulation of unique states – some light configurations imply others state S0 S1 S2 S3 description highway green (farm road red) highway yellow (farm road red) farm road green (highway red) farm road yellow (highway red)

Example: traffic light controller(Cont.) State diagram Reset (TL•C)' S0 TL•C / ST S0: HG S1: HY TS' TS / ST S1 S3 S2: FG S3: FY TS / ST TL+C' / ST S2 (TL+C')' TS'

Example: traffic light controller(Cont.) Generate state table with symbolic states Consider state assignments output encoding – similar problem to state assignment (Green = 00, Yellow = 01, Red = 10) Inputs C TL 0 – – 0 1 1 – – – – 1 0 0 – – 1 – – – – SA1: SA2: SA3: Present State TS – – – 0 1 – – – 0 1 HG HG HG HY HY FG FG FG FY FY HG = 00 HG = 00 HG = 0001 Next State HG HG HY HY FG FG FY FY FY HG HY = 01 HY = 10 HY = 0010 FG = 11 FG = 01 FG = 0100 Outputs ST H 0 Green 0 Green 1 Green 0 Yellow 1 Yellow 0 Red 1 Red 1 Red 0 Red 1 Red FY = 10 FY = 11 FY = 1000 F Red Red Red Red Red Green Green Green Yellow Yellow (one-hot)

Example: traffic light controller(Cont.) Logic for different state assignments SA1 NS1 = C•TL'•PS1•PS0 + TS•PS1'•PS0 + TS•PS1•PS0' + C'•PS1•PS0 + TL•PS1•PS0 NS0 = C•TL•PS1'•PS0' + C•TL'•PS1•PS0 + PS1'•PS0 ST = C•TL•PS1'•PS0' + TS•PS1'•PS0 + TS•PS1•PS0' + C'•PS1•PS0 + TL•PS1•PS0 H1 = PS1 H0 = PS1'•PS0 F1 = PS1' F0 = PS1•PS0' SA2 NS1 = C•TL•PS1' + TS'•PS1 + C'•PS1'•PS0 NS0 = TS•PS1•PS0' + PS1'•PS0 + TS'•PS1•PS0 ST = C•TL•PS1' + C'•PS1'•PS0 + TS•PS1 H1 = PS0 F1 = PS0' H0 = PS1•PS0' F0 = PS1•PS0 NS3 = C'•PS2 + TL•PS2 + TS'•PS3 NS1 = C•TL•PS0 + TS'•PS1 NS2 = TS•PS1 + C•TL'•PS2 NS0 = C'•PS0 + TL'•PS0 + TS•PS3 SA3 ST = C•TL•PS0 + TS•PS1 + C'•PS2 + TL•PS2 + TS•PS3 H1 = PS3 + PS2 H0 = PS1 F1 = PS1 + PS0 F0 = PS3

Finite state machine optimization State minimization – Fewer states require fewer state bits – Fewer bits require fewer logic equations Encodings: state, inputs, outputs – State encoding with fewer bits has fewer equations to implement • However, each may be more complex – State encoding with more bits (e.g., one-hot) has simpler equations • Complexity directly related to complexity of state diagram – Input/output encoding may or may not be under designer control

State minimization Algorithmic approach Goal – identify and combine states that have equivalent behavior Equivalent states: – Same output – For all input combinations, states transition to same or equivalent states Algorithm sketch – 1. Place all states in one set – 2. Initially partition set based on output behavior – 3. Successively partition resulting subsets based on next state transitions – 4. Repeat (3) until no further partitioning is required • states left in the same set are equivalent – Polynomial time procedure

State minimization(Cont.) State minimization example Sequence detector for 010 or 110 Input Sequence 0/0 S1 0/0 Output X=0 X=1 Reset 0 1 00 01 10 11 S0 Next State Present State X=0 X=1 S0 S1 S2 S3 S4 S5 S6 0 0 0 0 1 0 1 1/0 S2 1/0 0/0 S3 S4 S5 S6 0/0 0/1 0/0 0/1 1/0 1/0 1/0 1/0 1/0 S1 S3 S5 S0 S0 S0 S0 S2 S4 S6 S0 S0 S0 S0 0 0 0 0 0 0 0

State minimization(Cont.) Method of successive partitions Input Sequence Next State Present State X=0 X=1 Output X=0 X=1 Reset 0 1 00 01 10 11 S0 S1 S2 S3 S4 S5 S6 0 0 0 0 1 0 1 S1 S3 S5 S0 S0 S0 S0 ( S0 S1 S2 S3 S4 S5 S6 ) ( S0 S1 S2 S3 S5 ) ( S4 S6 ) ( S0 S3 S5 ) ( S1 S2 ) ( S4 S6 ) ( S0 ) ( S3 S5 ) ( S1 S2 ) ( S4 S6 ) S2 S4 S6 S0 S0 S0 S0 0 0 0 0 0 0 0 S1 is equivalent to S2 S3 is equivalent to S5 S4 is equivalent to S6

State minimization(Cont.) Minimized FSM State minimized sequence detector for 010 or Input Next State Output 110 Sequence Present State X=0 X=1 X=0 X=1 Reset 0+1 X0 X1 S0 X/0 0/0 S1’ 1/0 S4’ S3’ X/0 0/1 1/0 S0 S1' S3' S4' S1' S3' S0 S0 S1' S4' S0 S0 0 0 0 1 0 0 0 0

State minimization(Cont.) More complex state minimization Multiple input example inputs here 00 10 00 S0 [1] 01 10 S2 [1] 11 01 10 01 S4 [1] S3 [0] 11 10 10 00 present state S0 S1 S2 S3 S4 S5 11 00 01 01 11 00 10 S1 [0] 11 S5 [0] 01 00 11 00 S0 S0 S1 S1 S0 S1 next state 01 10 11 S1 S2 S3 S3 S1 S4 S3 S2 S4 S0 S4 S5 S1 S2 S5 S4 S0 S5 symbolic state transition table output 1 0 1 0 1 0

State minimization(Cont.) Minimized FSM Implication chart method – Cross out incompatible states based on outputs – Then cross out more cells if indexed chart entries are already crossed out present state S0' S1 S2 S3' S1 S2 S0-S1 S1-S3 S2-S2 S3-S4 S3 S4 S0-S0 S1-S1 S2-S2 S3-S5 S5 S0 S0-S1 S3-S0 S1-S4 S4-S5 S0-S1 S3-S4 S1-S0 S4-S5 S1 S1-S0 S3-S1 S2-S2 S4-S5 S2 next state 00 01 10 11 S0' S1 S2 S3' S0' S3' S1 S3' S1 S3' S2 S0' S1 S0' S0' S3' minimized state table (S0==S4) (S3==S5) S1-S1 S0-S4 S4-S0 S5-S5 S3 S4 output 1 0 1 0

State minimization(Cont.) Minimizing incompletely specified FSMs Equivalence of states is transitive when machine is fully specified But its not transitive when don't cares are present e.g., state output S0 S1 S2 –0 1– –1 S1 is compatible with both S0 and S2 but S0 and S2 are incompatible No polynomial time algorithm exists for determining best grouping of states into equivalent sets that will yield the smallest number of final states

State minimization(Cont.) Minimizing states may not yield best circuit Example: edge detector - outputs 1 when last two input changes from 0X toQ1 Q Q Q X’ 00 [0] X’ 01 [1] X X’ 11 [0] X 0 0 0 1 1 1 – 0 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 1 1 0 1 + X Q1+ = X (Q1 xor Q0) Q0+ = X Q1’ Q0’ 0 0 0 1 1 1 0 0 +

Another implementation of edge detector "Ad hoc" solution - not minimal but cheap and X’ fast X’ 10 [0] X’ 00 [0] X X’ 11 [0] X X 01 [1] X

State assignment Choose bit vectors to assign to each “symbolic” state – With n state bits for m states there are 2n! / (2n – m)! [log n <= m <= 2n] – 2n codes possible for 1st state, 2n–1 for 2nd, 2n–2 for 3rd, … – Huge number even for small values of n and m • Intractable for state machines of any size • Heuristics are necessary for practical solutions – Optimize some metric for the combinational logic • Size (amount of logic and number of FFs) • Speed (depth of logic and fanout) • Dependencies (decomposition)

State assignment(Cont.) State assignment strategies Possible strategies – Sequential – just number states as they appear in the state table – Random – pick random codes – One-hot – use as many state bits as there are states (bit=1 –> state) – Output – use outputs to help encode states – Heuristic – rules of thumb that seem to work in most cases No guarantee of optimality – another intractable problem

State assignment(Cont.) One-hot state assignment Simple – Easy to encode, debug Small logic functions – Each state function requires only predecessor state bits as input Good for programmable devices – Lots of flip-flops readily available – Simple functions with small support (signals its dependent upon) Impractical for large machines – Too many states require too many flip-flops – Decompose FSMs into smaller pieces that can be one-hot encoded Many slight variations to One-hot – One-hot + all-0

State assignment(Cont.) Heuristics for state assignment Adjacent codes to states that share a common next state – Group 1's in next state map I i i Q a b Q+ c c O j k a i/j c=i*a + i*b i/k c Adjacent codes to states that share a common ancestor state – Group 1's in next state map I i k b Q a a Q+ b c O j l a i/j b=i *a c=k*a k/l b c Adjacent codes to states that have a common output behavior – Group 1's in Q+ O map output I Q i i a c b d j j j=i *a+ i *c b=i*a d=i*c a c i/j i/j b d

State assignment(Cont.) General approach to heuristic state assignment All current methods are variants of this – 1) Determine which states “attract” each other (weighted pairs) – 2) Generate constraints on codes (which should be in same cube) – 3) Place codes on Boolean cube so as to maximize constraints satisfied (weighted sum) Different weights make sense depending on whether we are optimizing for two-level or multi-level forms Can't consider all possible embeddings of state clusters in Boolean cube – Heuristics for ordering embedding – To prune search for best embedding – Expand cube (more state bits) to satisfy more constraints

State assignment(Cont.) Output-Based encoding Reuse outputs as state bits - use outputs to help distinguish states – Why create new functions for state bits when output can serve as well – Fits in nicely with synchronous Mealy implementations Inputs C TL 0 – – 0 1 1 – – – – 1 0 0 – – 1 – – – – Present State TS – – – 0 1 – – – 0 1 HG HG HG HY HY FG FG FG FY FY HG = ST’ H1’ H0’ F1 F0’ + ST H1 H0’ F1’ F0 HY = ST H1’ H0’ F1 F0’ + ST’ H1’ H0 F1 F0’ FG = ST H1’ H0 F1 F0’ + ST’ H1 H0’ F1’ F0’ HY = ST H1 H0’ F1’ F0’ + ST’ H1 H0’ F1’ F0 Next State HG HG HY HY FG FG FY FY FY HG Outputs ST H 0 00 0 00 1 00 0 01 1 01 0 10 1 10 1 10 0 10 1 10 F 10 10 10 10 10 00 00 00 01 01 Output patterns are unique to states, we do not need ANY state bits – implement 5 functions (one for each output) instead of 7 (outputs plus 2 state bits)

State assignment(Cont.) Current state assignment approaches For tight encodings using close to the minimum number of state bits – Best of 10 random seems to be adequate (averages as well as heuristics) – Heuristic approaches are not even close to optimality – Used in custom chip design One-hot encoding – Easy for small state machines – Generates small equations with easy to estimate complexity – Common in FPGAs and other programmable logic Output-based encoding – Ad hoc - no tools – Most common approach taken by human designers – Yields very small circuits for most FSMs

Sequential logic examples Finite state machine concept – FSMs are the decision making logic of digital designs – Partitioning designs into data-path and control elements – When inputs are sampled and outputs asserted Basic design approach: 4-step design process Implementation examples and case studies – – – – Finite-string pattern recognizer Complex counter Traffic light controller Door combination lock

General FSM design procedure Determine inputs and outputs Determine possible states of machine – State minimization Encode states and outputs into a binary code – State assignment or state encoding – Output encoding – Possibly input encoding (if under our control) Realize logic to implement functions for states and outputs – Combinational logic implementation and optimization – Choices in steps 2 and 3 have large effect on resulting logic

Finite string pattern recognizer (Step 1) Finite string pattern recognizer – One input (X) and one output (Z) – Output is asserted whenever the input sequence …010… has been observed, as long as the sequence 100 has never been seen Step 1: understanding the problem statement – Sample input/output behavior: X: 0 0 1 0 1 0 1 0 0 1 0 … Z: 0 0 0 1 0 1 0 1 0 0 0 … X: 1 1 0 1 1 0 1 0 0 1 0 … Z: 0 0 0 0 0 0 0 1 0 0 0 …

Finite string pattern recognizer(Cont.) Step 2: draw state diagram – For the strings that must be recognized, i.e., 010 and 100 reset S0 [0] 0 1 – Moore implementation S1 [0] 1 S2 [0] 0 S3 [1] S4 [0] 0 S5 [0] 0 S6 [0] 0 or 1

Finite string pattern recognizer(Cont.) Exit conditions from state S3: have recognized …010 – If next input is 0 then have …0100 = ...100 (state S6) – If next input is 1 then have …0101 = …01 (state S2) reset Exit conditions from S1: recognizes strings of form …0 (no 1 seen); loop back to S1 if input is 0 Exit conditions from S4: recognizes strings of form …1 (no 0 seen); loop back to S4 if input is 1 0 0 S1 [0] ...0 S0 [0] 1 ...1 1 ...01 0 ...010 1 0 S2 [0] S5 [0] 1 S3 [1] S4 [0] 0 ...100 S6 [0] 0 or 1

Finite string pattern recognizer(Cont.) S2 and S5 still have incomplete transitions – S2 = …01; If next input is 1, then string could be prefix of (01)1(00) S4 handles just this case – S5 = …10; If next input is 1, then string could be prefix of (10)1(0) S2 handles just this case reset Reuse states as much as possible – Look for same meaning – State minimization leads to smaller number of bits to represent states Once all states have complete set of transitions we have final state diagram S0 [0] 0 0 S1 [0] ...0 1 ...01 0 ...010 1 ...1 1 1 S3 [1] 1 0 1 S2 [0] S4 [0] S5 [0] ...10 0 ...100 S6 [0] 0 or 1

Finite string pattern recognizer(Cont.) Review of process – Understanding problem • Write down sample inputs and outputs to understand specification – Derive a state diagram • Write down sequences of states and transitions for sequences to be recognized – Minimize number of states • Add missing transitions; reuse states as much as possible – State assignment or encoding • Encode states with unique patterns – Simulate realization • Verify I/O behavior of your state diagram to ensure it matches specification

Complex counter Synchronous 3-bit counter has a mode control M – When M = 0, the counter counts up in the binary sequence – When M = 1, the counter advances through the Gray code sequence binary: 000, 001, 010, 011, 100, 101, 110, 111 Gray: 000, 001, 011, 010, 110, 111, 101, 100 Valid I/O behavior (partial) Mode Input M 0 0 1 1 1 0 0 Current State 000 001 010 110 111 101 110 Next State 001 010 110 111 101 110 111

Complex counter(Cont.) Deriving state diagram – One state for each output combination – Add appropriate arcs for the mode control 0 reset S0 [000] 0 S1 [001] 1 0 S2 [010] 1 1 0 1 S3 [011] 0 0 S4 [100] S5 [101] 0 1 1 1 0 S6 [110] 1 S7 [111]

Traffic light controller as two communicating FSMs Without separate timer – – – – – – TS' S0 would require 7 states S1 would require 3 states S1 S2 would require 7 states S3 would require 3 states S1 and S3 have simple transformation S0 and S2 would require many more arcs S1a TS/ST S1b S1c • C could change in any of seven states By factoring out timer – Greatly reduce number of states • 4 instead of 20 – Counter only requires seven or eight states • 12 total instead of 20 traffic light controller ST TS TL timer –/ST

Communicating finite state machines One machine's output is another machine's input X FSM 1 Y FSM 2 CLK FSM1 A A B C D D X Y==0 Y==0 A [1] X==0 C [0] Y X==1 Y==1 B [0] X==0 FSM2 D [1] X==1 X==0 machines advance in lock step initial inputs/outputs: X = 0, Y = 0

Data path and control Digital hardware systems = data-path + control – Data-path: registers, counters, combinational functional units (e.g., ALU), communication (e.g., busses) – Control: FSM generating sequences of control signals that instructs data-path what to do next "puppeteer who pulls the strings" control status info and inputs state data-path control signal outputs "puppet"

Digital combinational lock Door combination lock: – Punch in 3 values in sequence and the door opens; if there is an error the lock must be reset; once the door opens the lock must be reset – Inputs: sequence of input values, reset – Outputs: door open/close – Memory: must remember combination or always have it available – Open questions: how do you set the internal combination? • Stored in registers (how loaded?) • Hardwired via switches set by user

Digital combinational lock(Cont.) Implementation in software integer combination_lock ( ) { integer v1, v2, v3; integer error = 0; static integer c[3] = 3, 4, 2; while (!new_value( )); v1 = read_value( ); if (v1 != c[1]) then error = 1; while (!new_value( )); v2 = read_value( ); if (v2 != c[2]) then error = 1; while (!new_value( )); v3 = read_value( ); if (v2 != c[3]) then error = 1; if (error == 1) then return(0); else return (1); }

Digital combinational lock(Cont.) Determining details of the specification How many bits per input value? How many values in sequence? How do we know a new input value is entered? What are the states and state transitions of the system? new value reset clock open/closed

Digital Combinational Lock(Cont.) Digital combination lock state diagram States: 5 states – Represent point in execution of machine – Each state has outputs Transitions: 6 from state to state, 5 self transitions, 1 global – Changes of state occur when clock says its ok – Based on value of inputs Inputs: reset, new, results of comparisons Output: open/closed C1!=value & new S1 reset closed not new C1=value & new S2 closed not new C2=value & new ERR closed C2!=value & new S3 closed not new C3!=value & new C3=value & new OPEN open

Digital combinational lock(Cont.) Data-path and control structure Data-path – Storage registers for combination values – Multiplexer – Comparator Control – Finite-state machine controller – Control for data-path (which value to compare) C1 4 C2 4 new C3 4 multiplexer mux control 4 value 4 comparator reset controller clock equal open/closed

Digital combinational lock(Cont.) State table for combination lock Finite-State machine – Refine state diagram to take internal structure into account – State table ready for encoding reset 1 0 0 0 ... 0 ... new – 0 1 1 equal – – 0 1 state – S1 S1 S1 next state S1 S1 ERR S2 mux C1 C1 – C2 open/closed closed closed closed closed 1 1 S3 OPEN – open

Digital combinational lock(Cont.) Encodings for combination lock Encode state table – State can be: S1, S2, S3, OPEN, or ERR • Needs at least 3 bits to encode: 000, 001, 010, 011, 100 • And as many as 5: 00001, 00010, 00100, 01000, 10000 • Choose 4 bits: 0001, 0010, 0100, 1000, 0000 – Output mux can be: C1, C2, or C3 controller – Output open/closed can be: open or closed • Needs 1 or 2 bits to encode • Choose 1 bit: 1, 0 reset 1 0 0 0 ... 0 new – 0 1 1 equal – – 0 1 state – 0001 0001 0001 1 1 0100 1000 reset mux control • Needs 2 to 3 bits to encode • Choose 3 bits: 001, 010, 100 next state 0001 0001 0000 0010 new equal clock open/closed mux 001 001 – 010 open/closed 0 mux is identical to last 3 bits of state 0 open/closed is identical to first bit of state 0 therefore, we do not even need to implement 0 FFs to hold state, just use outputs – 1

Design register with set/reset S R D Q Set forces state to 1 Reset forces state to 0 What might be a useful fourth option?

Design A single input X single output Z synchronous sequential circuit will give a 1 output when the input sequence starting from reset up to present time includes odd number of 1s, otherwise the circuit will give a 0 output. Design a clock synchronous sequential circuit with two inputs A, B and a single output Z that is 1 if: – A had the same value at each of the two previous clock ticks, or – B has been 1 since the last time that the first condition was true. – Otherwise, output should be 0.

Digital design Other flip-flop types

Other flip-flop types J-K and T flip-flops – Behavior – Implementation Basic descriptors for understanding and using different flip-flop types – Characteristic tables – Characteristic equations – Excitation tables For actual use, see Reading Supplement Design and Analysis Using J-K and T Flip-Flops

J-K flip-flop Behavior – – – – – Same as S-R flip-flop with J analogous to S and K analogous to R Except that J = K = 1 is allowed, and For J = K = 1, the flip-flop changes to the opposite state As a master-slave, has same “1s catching” behavior as S-R flip-flop If the master changes to the wrong state, that state will be passed to the slave • E.g., if master falsely set by J = 1, K = 1 cannot reset it during the current clock cycle

J-K flip-flop(Cont.) Symbol Implementation – To avoid 1s catching behavior, one solution used is to use an edge-triggered D as the core of the flip-flop J K J K D Q Q

T flip-flop Behavior – Has a single input T • For T = 0, no change to state • For T = 1, changes to opposite state Same as a J-K flip-flop with J = K = T As a master-slave, has same “1s catching” behavior as J-K flip-flop Cannot be initialized to a known state using the T input – Reset (asynchronous or synchronous) essential

T flip-flop(Cont.) Implementation – To avoid 1s catching behavior, one solution used is to use an edge-triggered D as the core of the flip-flop T D Q Symbol T Q

Basic flip-flop descriptors Used in analysis – Characteristic table - defines the next state of the flip-flop in terms of flip-flop inputs and current state – Characteristic equation - defines the next state of the flip-flop as a Boolean function of the flip-flop inputs and the current state Used in design – Excitation table - defines the flip-flop input variable values as function of the current state and next state

D flip-flop descriptors Characteristic Table D Q(t + 1) 0 1 0 1 Operation Reset Set Characteristic Equation Q(t+1) = D Excitation Table Q(t +1) D Operation 0 1 0 1 Reset Set

T flip-flop descriptors Characteristic Table T Q(t + 1) Operation 0 Q ( t) No change 1 Q ( t) Complement Characteristic Equation Q(t+1) = T Q Excitation Table Q(t +1) T Operation Q ( t) 0 No change Q ( t) 1 Complement

S-R flip-flop descriptors Characteristic Table S R Q(t + 1) Operation 0 0 0 1 1 0 Q ( t) 0 1 No change Reset Set 1 1 ? Undefined Characteristic Equation Q(t+1) = S + R Q, S.R = 0 Excitation Table Q(t) Q(t+ 1) S R Operation 0 0 1 0 1 0 0 X 1 0 0 1 No change Set Reset 1 1 X 0 No change

J-K flip-flop descriptors Characteristic Table J K Characteristic Equation Q(t+1) = J Q + K Q Excitation Table Q(t) 0 0 1 1 0 0 1 1 0 1 0 1 Q(t + 1) Q ( t) 0 1 Q ( t) Q(t + 1) J K 0 1 0 1 0 1 X X X X 1 0 Operation No change Reset Set Complement Operation No change Set Reset No Change

Flip-flop behavior Use the characteristic tables to find the output waveforms for the flipflops shown: Clock D,T D Q T Q

Flip-flop behavior(Cont.) Use the characteristic tables to find the output waveforms for the flipflops shown: Clock S,J R,K S QSR R J QJK K ?

Implement D Flip-flop by T Flip-flop Q 0 1 0 0 0 1 1 1 D Q 0 1 0 0 1 1 1 0 T T = D Q’ + D’ Q D D’ T Q Q’

Implement JK Flip-flop by D Flip-flop Q JK 0 Q 1 0 1 Q+ 00 0 1 JK 00 01 0 0 01 0 0 0 0 11 1 0 11 1 0 1 1 10 1 1 10 1 1 D 0 1 D = J Q’ + K’ Q J D K Q Q’

Implement JK Flip-flop by T Flip-flop Q+ Q JK 0 1 Q 0 1 00 0 1 JK 00 01 0 0 01 0 1 11 1 0 11 1 10 1 1 10 1 JK 0 Q+ 00 Q 01 0 0 Q 1 10 1 1 Q’ 0 11 Q’ T = J Q’ + K Q J T K Q+ T 0 Q Q’

Implement T Flip-flop by JK Flip-flop Q T J K 0 1 Q Q+ 0 0 1 00 0 X 1 1 0 01 1 X 10 X 1 11 X 0 Q T 0 1 0 0 X 1 1 X J=T Q T 0 1 0 X 0 1 X 1 K=T

Sequential circuit analysis

thanks digital design

fifa coin | 26/02/15

Omg, That's a nice post!
Love you, Thank you!
Excuse me, Please look at my username! Cheap Fifa Coins.
fifa coin http://www.fifacoing.com/

Elec 326 22 Sequential Circuit Design 3. Sequential Circuit State Reduction This section presents a technique for reducing the

Read more

... sequential logic is a type of logic circuit whose output ... Asynchronous sequential circuits are typically ... processing circuits. The design of ...

Read more

Sequential Circuits Inc. ... Sequential pioneered technologies and design principles that have served as a foundation for the development of modern music ...

Read more

Digital Logic Design CHAPTER 5 Sequential Logic. 2 Sequential Circuits Combinational circuits ... 2 Sequential Circuits Combinational circuits ...

Read more

Elec 326 4 Sequential Circuit Analysis Sequential Circuit Canonical Form

Read more

PART OF CHAPTER 5 Combinational & Sequential ... • For the design of Combinational digital circuits Basic ... Combinational & Sequential Circuits

Read more

A sequential circuit uses flip flops. Unlike combinational logic, sequential circuits have state, which means basically, sequential circuits have memory.

Read more

This Synchronous Sequential Logic ... Tutorial Part 2 - Digital Logic and Design ... DESIGN OF SYNCHRONOUS SEQUENTIAL CIRCUITS ...

Read more

This Synchronous Sequential Logic Tutorial ... Tutorial Part 2 - Digital Logic and Design ... Sequential Circuit Design ...

Read more

## Add a comment