# Sequential Logic Design - UBC ECE ELEC 256 / Saif Zahir Sequential Logic Design Sequential Networks Simple Circuits with Feedback R-S Latch J-K Flipflop Edge -Triggered Flip-Flops Timing Methodologies Cascading Flip-Flops for Proper Operation Narrow Width Clocking vs. Multiphase Clocking Clock Skew Realizing Circuits with Flip-Flops Choosing a FF Type Characteristic Equations Conversion Among Types Self-Timed Circuits UBC / 2000 ELEC 256 / Saif Zahir Sequential Switching Networks Sequential Circuit x1 x2 x3 x4 Combinational Logic Delay = z1 z2 z3 z4 z3 = F(x1, ... ,x4,z3,z4) z3(t+) = F(x1(t), ... ,x4(t),z3(t),z4(t)) Sequential logic forms basis for building "memory" into circuits. Sequential logic is characterized by the presence of feedback paths. Observations: z3 and z4 appear as both inputs and outputs. The state of variable z3 (or z4) at time t+ depends on its value at time t, i.e. z3(t+) = F(z3(t)), hence, circuit has memory. z3(t) and z4(t) are called state variables . UBC / 2000

ELEC 256 / Saif Zahir Simple Sequential Circuits "1" "0" Cascaded Inverters: Static Memory Cell Another Example Assuming > 0 x(t) Delay= z(t) z(t+) = x(t) z(t) if x(t) = 0 then z(t)=1 (stable state) if x(t) = 1 then z(t+) = z(t) Observe that NAND gate with one input asserted acts as an inverter with respect to other input x z t When x=1, equaivalent circuit z(t) Timing Waveform: UBC / 2000 ELEC 256 / Saif Zahir Inverter Chains and Ring Oscillators Inverter Chains 1 0 1 0 0 A B

C D E X Odd # of stages leads to ring oscillator Snapshot taken just before last inverter changes Timing Waveform: tp = n n = no. inverters Output high propagating thru this stage Period of Repeating Waveform ( tp) Gate Delay ( td) A (=X) 0 B 1 C 0 D 1 E 0 1 UBC / 2000 ELEC 256 / Saif Zahir Cross-Coupled NOR Gates Simple-Latch: two-inverter loop x(t) x=1 --> z=0 x=0 --> z=1 z(t) Problem: how can we insert x in the loop? Observation NOR gate with one input=0, acts as an inverter with respect to other input.

Equivalent NOR circuit with two control inputs (R and S) to break or close the loop q R Q 0 x R q Q S S R: Reset input (R=1 --> Q=0) S: Set input (S=1 --> Q=1) X Alternative representation UBC / 2000 ELEC 256 / Saif Zahir The RS Latch if R=S=0 then Q(t+)=Q(t) (memory element) R=0 q=0 R=0 q=1 S=0 Q=1 S=0 Q=0 if R=S=1 then q = Q = 0, which violates the inverter rule (q = 0, Q = 1) if R and S chnage from 1-to-0 at precisely same moment, then RS latch will oscillate (provided the NOR gate delays are perfectly matched) R=1 R=1-->0 q=0 q=0-->1-->0-->1--

0-->1-->0-->1 S=1 Q=0 0-->1-->0-->1 Q=0-->1-->0-->1-- S=1-->0 UBC / 2000 ELEC 256 / Saif Zahir State Behavior of RS Latch The response and transient behavior of the RS latch can be described using a state-diagram: 1- Nodes represent the unique states of the circuit QQ QQ 10 2- Arcs indicate state-transition under 01 particular input combinations (arc labels). state 1 state 2 Truth Table Summary of R-S Latch Behavior S R Q 0 0 hold 0 1 0 1 0 1 1 1 unstable QQ 00 state 0 QQ 11 Because of the resulting unstable behavior the combination R=S=1 is called the forbidden input for the RS latch. state 3 UBC / 2000 ELEC 256 / Saif Zahir State-Diagrams and State Tables

A state-table expresses the same information of the state-diagram in a tabular format qQ 00 01 10 00 SR = 1 0 QQ 01 QQ 10 SR = 0 1 SR = 0 1 SR = 1 0 NS (q+, Q+) PS SR SR SR SR 00 01 10 11 11 01 10 00 01 01 01 01 10 10 10 10 PS : present state NS: next state Q+ : Q(t+) 00 00 00 00 SR = 00, 10 SR = 00, 01 SR = 11 SR = 1 1 SR = 1 1 QQ 00 SR = 0 1

SR = 1 0 SR = 0 0 SR = 0 0, 11 QQ 11 Note the unstable behavior is now obvious from the continuous transition states 00 and 11 when SR changes from 11 to 00. UBC / 2000 ELEC 256 / Saif Zahir The D-Latch enabled when C=1 if C=1 then Q=D if C=0 then Q(t+)=Q(t) D Q q C Clk Enable Realization using an RS latch if C=0, then R=S=0 and Q(t+)=Q(t) If C=1 and D=0 then R=1, S=0, and Q=0 if C=1 and D=1 then R=0, S=1, and Q=1 D q R q RS Latch S C Note that input R=S=1 can not occur UBC / 2000 Q ELEC 256 / Saif Zahir Steup and Hold Times

Clock: Periodic Event, causes state of memory element to change. Setup Time (Tsu): Minimum time before the clocking event by which the input must be stable Tsu Th Input Clock Hold Time (Th) Minimum time after the clocking event during which the input must remain stable There is a timing "window" around the clocking event during which the input must remain stable and unchanged in order to be recognized Primitive Memory Elements: Latches: Continuously sample their inputs. Any change in the level of the inputs is propagated through to the outputs (level sensitive). Flip-Flops: Outputs change only with respect to the clock, normally the rising edge or the falling edges of the clock. UBC / 2000 ELEC 256 / Saif Zahir Level Sensitive Latches RS latch with active-low inputs and active-low Enable \S Truth Table \enb S R 1 0 0 0 0 x 0 0 1 1 x 0 1 0 1 \Q Q+ Q Q

0 1 Unstable Timing Diagram: \R Q \enb Reset Set UBC / 2000 ELEC 256 / Saif Zahir Flip-Flops and Latches 7474 D Q Clk Positive edge-triggered flip-flop Edge triggered devices sample inputs on the rising or falling edge of the Clock or the Enable. Transparent latches sample inputs as long as the clock is asserted output changes with input (after certain delay). Timing Diagram: 7476 D D Q C Clk Level-sensitive latch Bubble here for negative edge triggered device Clk Q Q 7474 7476 Behavior is the same unless input changes occur while the clock is high UBC / 2000

ELEC 256 / Saif Zahir Flip-Flops vs. Latches Input/Output Behavior of Latches and Flipflops Type unclocked latch level sensitive latch When Inputs are Sampled always When Outputs are Valid propagation delay from input change clock high (Tsu, Th around falling clock edge) propagation delay from input change positive edge flipflop clock lo-to-hi transition (Tsu, Th around rising clock edge) propagation delay from rising edge of clock negative edge flipflop clock hi-to-lo transition (Tsu, Th around falling clock edge) propagation delay from falling edge of clock master/slave flipflop clock hi-to-lo transition (Tsu, Th around falling clock edge) propagation delay from falling edge of clock UBC / 2000 ELEC 256 / Saif Zahir

Flip-Flops: Typical Timing Specifications 74LS74 Positive Edge Triggered D Flipflop D Setup time Hold time Minimum clock width Propagation delays (low to high, high to low, max and typical) Clk Q Tsu 20 ns Th 5 ns T su 20 ns Th 5 ns Tw 25 ns Tplh 25 ns 13 ns T phl 40 ns 25 ns All measurements are made from the clocking event that is, the rising edge of the clock UBC / 2000 ELEC 256 / Saif Zahir Latches: Typical Timing Specifications 74LS76 Transparent Latch D Setup time

Hold time Minimum Clock Width Propagation Delays: high to low, low to high, maximum, typical data to output clock to output Clk Q T su Th 20 5 ns ns Tw 20 ns Tplh C Q 27 ns 15 ns T plh DQ 27 ns 15 ns Tsu 20 ns T phl C Q 25 ns 14 ns T phl DQ 16 ns 7 ns Measurements from falling clock edge or rising or falling data edge UBC / 2000 Th 5 ns ELEC 256 / Saif Zahir Designing Latches RS Latch Derived K-Map: Truth Table: Next State = F(S, R, Current State) SR

S 00 01 11 10 0 0 0 X 1 1 1 0 X 1 Q( t ) R Characteristic Equation: q(t+)=s(t)+R(t)q(t) or q+=s + Rq Compare to previous NOR implementation q q R Q R S S UBC / 2000 q ELEC 256 / Saif Zahir The JK Latch The JK latch eliminates the forbidden state of the RS latch Basic principle: use output feedback to guarantee

that R=S=1 never occurs K R R-S latch J=K=1 yields toggle (q+ = Q) J S J Q+ = Q K + Q J Q D K Characteristic Equation: \Q \Q Q Q D-Latch C enb UBC / 2000 ELEC 256 / Saif Zahir JK Latches Simplified State-Tables NS (q+, Q+) PS NS (q+, Q+) PS q SR SR SR SR 00 01 10 11 q JK JK JK JK 00 01 10 11

0 1 0 1 0 0 1 1 x x 0 1 0 1 0 0 1 1 1 0 Q Q 0 1 x Q Q 0 1 Q JK=00 , 10 J K Q+ 0 0 1

1 0 1 0 1 Q 0 1 Q JK=01 , 11 Q=1 Q=0 JK=10 , 11 UBC / 2000 JK=00, 01 From JK Latch to JK FlipFlop JK Latch: Race Condition Set ELEC 256 / Saif Zahir Reset 100 Toggle J K Q \Q Race Condition Ideally, the Latch should toggle only once when JK=11. Because of latch transparency, race conditions cause continuous toggrling. Toggle Correctness: Single State change per clocking event Solution: Master-Slave Flipflop UBC / 2000 ELEC 256 / Saif Zahir Master-Slave JK FlipFlop Break feedback path, by dividing operation in two time periods (clock-high and clock-low) Master Stage Slave Stage K \Q R

\P R S \Q R-S Latch R-S Latch J \Q Q S P Q Q Clk Sample inputs while clock high Set Reset 1's Catch Toggle Sample inputs while clock low 100 J K Clk P \P Q \Q Master outputs Slave outputs UBC / 2000 Correct Toggle Operation ELEC 256 / Saif Zahir

The Toggle (T) FlipFlop State table T Q Q+ 0 0 1 1 0 1 0 1 0 1 1 0 T or T Q+ 0 1 Q Q C Q T flipflop T-FF can be realized using a JK-FF q+ = tQ+Tq Verification: J=K=T T-FF can be realized using a D-FF D T C D flipflop Q T

J K Q+ 0 1 0 1 0 1 q Q T J C K UBC / 2000 JK flipflop Q ELEC 256 / Saif Zahir Edge-Triggered FlipFlops Example: Negative edge-triggered D flipflop Flipflop state changes right after the falling edge of the clock 4-5 gate delays (longer than latches) Setup and Hold times are necessary for correct operation D D D Holds D when clock goes low 0 Clk R Q Clk=1

Q Q S 0 D D Holds D when clock goes low Characteristic equation Q+ = D UBC / 2000 ELEC 256 / Saif Zahir Edge-Triggered D FlipFlopk Step-by-step analysis D 0 D 4 3 D R D R Q Clk=0 6 Q 5 Q Clk=0 D Q D S

D S 2 D D D D' 1 D 0 D' D When clock goes from high-to-low data is latched When clock is low data is held UBC / 2000 Positive and Negative Edge Triggered FlipFlops ELEC 256 / Saif Zahir Timing Diagram 100 D Clk Qpos Positive edgetriggered FF \ Qpos Qneg Negative edgetriggered FF \ Qneg Positive Edge Triggered Negative Edge Triggered Inputs sampled on rising edge Outputs change after rising edge Inputs sampled on falling edge Outputs change after falling edge UBC / 2000 ELEC 256 / Saif Zahir

Comparison R-S Clocked Latch: used as storage element in narrow width clocked systems its use is not recommended! however, fundamental building block of other flipflop types J-K Flipflop: versatile building block can be used to implement D and T FFs usually requires least amount of logic to implement (In,Q,Q+) but has two inputs with increased wiring complexity because of 1's catching, never use master/slave J-K FFs Use edge-triggered varieties D Flipflop: minimizes wires, much preferred in VLSI technologies simplest design technique best choice for storage registers T Flipflops: don't really exist, constructed from J-K FFs usually best choice for implementing counters Asynchronous Preset and Clear inputs are highly desirable! UBC / 2000 ELEC 256 / Saif Zahir FlipFlop Excitation Tables Useful Design Tool: For each state-transition, the excitation table lists the required input combination(s) 1. D FlipFlop D Q+ 0 0 1 1 Transition Table Q Q+ D 0 0 0 0 1 1 1 0 0 1 1 1 Excitation Table D Q D

flipflop C q+ = d 2. T FlipFlop T Q + 0 q 1 Q Transition Table Q Q+ T 0 0 0 0 1 1 1 0 1 1 1 0 Excitation Table T Q T flipflop C q+ = tQ+Tq UBC / 2000 ELEC 256 / Saif Zahir FlipFlop Excitation Tables RS= 01 1. SR FlipFlop q+ = s + Rq R S Q+ 0 0

Q 0 1 1 1 0 0 1 1 forbid Transition Table Q Q=0 Q+ R S Q+ 0 0 X 0 0 1 0 1 1 0 1 0 1 1 0 X Excitation Table 0 0 q 0 1 1 1 0 0 1 1 Q Transition Table Q Q+ Q=1 RS=10 S R Q SR flipflop Clk S JK=00,10 JK=00,01

1. JK FlipFlop q+ = jQ + Kq R RS=00,01 RS=00,10 JK= 10, 11 Q=0 J K 0 0 0 X 0 1 1 X 1 0 X 1 1 1 X 0 Excitation Table Q=1 JK= 01, 11 J Clk K UBC / 2000 Q JK flipflop ELEC 256 / Saif Zahir Conversion Between FlipFlop Types Procedure uses excitation tables Method: to realize a type A flipflop using a type B flipflop: 1. Start with the K-map or state-table for the A-flipflop. 2. Express B-flipflop inputs as a function of the inputs and present state of A-flipflop such that the required state transitions of A-flipflop are reallized. x Q y g h CL

x CL y Type B Type A 1. Find Q+ = f(g,h,Q) for type A (using type A state-table) 2. Compute x = f1(g,h,Q) and y=f2(g,h,Q) to realize Q+. UBC / 2000 Q ELEC 256 / Saif Zahir Conversion Between FlipFlop Types Example: Use JK-FF to realize D-FF 1) Start transition table for D-FF 2) Create K-maps to express J and K as functions of inputs (D, Q) 3) Fill in K-maps with appropriate values for J and K to cause the same state transition as in the D-FF transition table D Q Q 0 0 0 0 1 0 1 0 1 1 1 1 State-Table + J K 0 X 1 X X 1 X 0 e.g. when D=Q=0, then Q+= 0

the same transition Q-->Q+ is realize with J=0, K=X Q Q+ 0 0 0 1 1 0 1 1 R X 0 1 0 D S 0 1 0 X 0 1 0 0 1 1 X X Q J= D UBC / 2000 J 0 1 X X K X X 1 0 D T 0 1 1 0

D 0 1 0 1 0 1 0 X X 1 1 0 Q K =D ELEC 256 / Saif Zahir Conversion Between FlipFlops Another Example: Implement JK-FF using a D-FF J K Q Q+ D T 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1

0 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 0 0 1 1 0 1 1 J D K DFF C Clk J Q T K T-FF C Clk JK

J JK Q 0 00 01 11 10 0 0 1 1 Q 0 1 1 0 0 1 1 J 00 01 11 10 0 0 1 1 0 1 1

0 K d= jQ + Kq Q K t= jQ + kq UBC / 2000 ELEC 256 / Saif Zahir Asynchronous Inputs PRESET PRESET and CLEAR: asynchronous, level-sensitive inputs used to initialize a flipflop. T Q Clk PRESET, CLEAR: active low inputs CLEAR PRESET = 0 --> Q = 1 CLEAR = 0 --> Q = 0 SET 1 0 1 0 D T LogicWorks Simulation Clk 1 0 200 400 Clk CLR SET T

Q UBC / 2000 S Q CRQ CLR Q ELEC 256 / Saif Zahir Proper Cascading of Flipflops Serial connection of positive edge-trigerred flipflops 1. on rising efge of CLK, FF1 reads Q0, and FF0 reads IN 2. during clock period FF1 performs Q1 <-- Q0, and FF0 performs Q0 <-- IN FF0 IN Shift-register D Q FF1 Q0 C Q D C Q CLK 100 In Correct Operation, assuming positive edge triggered FF Q Q0 Q1 Clk UBC / 2000 Q1