Flip Flops Lecture 10 CAP 3103 06-18-2014 Uses for State Elements 1. As a place to store values for some indeterminate amount of time: Register files (like $1-$31 on the MIPS)

Memory (caches, and main memory) 2. Help control the flow of information between combinational logic blocks. State elements are used to hold up the movement of information at the inputs to combinational logic blocks and Dr Dan Garcia Accumulator Example Why do we need to control the flow of information? Want :

S=0; for (i=0;i

Reason #1 What is there to control the next iteration of the for loop? Reason #2 How do we say: S=0? Dr Dan Garcia Second tryHow about this? Rough timing T i m e Dr Dan Garcia Register DetailsWhats inside?

n instances of a Flip-Flop Flip-flop name because the output flips and flops between and 0,1 D is data, Q is output Also called d-type Flip-Flop Dr Dan Garcia Whats the timing of a Flip-flop? (1/2) Edge-triggered d-type flip-flop This one is positive edge-triggered On the rising edge of the clock, the input d is sampled and transferred to the output. At all other times, the input d is ignored. Example waveforms:

Dr Dan Garcia Whats the timing of a Flip-flop? (2/2) Edge-triggered d-type flip-flop This one is positive edge-triggered On the rising edge of the clock, the input d is sampled and transferred to the output. At all other times, the input d is ignored. Example waveforms (more detail): MetaStability? Dr Dan Garcia Accumulator Revisited (proper timing 1/2) Reset input to register is used to force it to all zeros (takes priority over

D input). Si-1 holds the result of the ith-1 iteration. Analyze circuit timing starting at the output of the register. Dr Dan Garcia Accumulator Revisited (proper timing 2/2) reset signal shown. Also, in practice X might not arrive to the adder at the same time as Si-1 Si temporarily is wrong, but register always captures correct value.

In good circuits, instability never happens around rising edge of clk. Dr Dan Garcia Maximum Clock Frequency Hint Frequency = 1/Period What is the maximum frequency of this circuit? Max Delay = Setup Time + CLK-to-Q Delay + CL Delay Dr Dan Garcia

Pipelining to improve performance (1/2) Extra Register are often added to help speed up the clock rate. Timing Note: delay of 1 clock cycle from input to output. Clock period limited by propagation delay of adder/shifter. Dr Dan Garcia Pipelining to improve performance (2/2) Insertion of register allows higher clock frequency. More outputs per second.

Timing Dr Dan Garcia Recap of Timing Terms Clock (CLK) - steady square wave that synchronizes system Setup Time - when the input must be stable before the rising edge of the CLK Hold Time - when the input must be stable after the rising edge of the CLK CLK-to-Q Delay - how long it takes the output to change, measured from the rising edge of the CLK Flip-flop - one bit of state that samples every rising edge of the CLK (positive edge-triggered) Register - several bits of state that samples on rising edge of CLK or on LOAD (positive edgetriggered)

Dr Dan Garcia Finite State Machines (FSM) Introduction You have seen FSMs in other classes. Same basic idea. The function can be represented with a state transition diagram. With combinational logic and registers, any FSM can be implemented in hardware. Dr Dan Garcia

Finite State Machine Example: 3 ones FSM to detect the occurrence of 3 consecutive 1s in the input. Draw the FSM Assume state transitions are controlled by the clock: on each clock cycle the machine checks the inputs and moves to a new state and produces a new output Dr Dan Garcia Hardware Implementation of FSM Therefore a register is needed to hold the a representation of which state the machine is in. Use a unique bit pattern for each state. +

= Combinational logic circuit is used to implement a function maps from present state and input to next state and output. ? Dr Dan Garcia Hardware for FSM: Combinational Logic To do: Draw FSM from the truth table Truth table PS Input 00 0

00 NS Output 00 0 1 01 0 01 0 00 Dr Dan Garcia General Model for Synchronous Systems

Collection of CL blocks separated by registers. Registers may be back-to-back and CL blocks may be backto- back. Feedback is optional. Clock signal(s) connects only to clock input of registers. Dr Dan Garcia Peer Instruction 1) HW feedback akin to SW recursion 2) The minimum period of a usable synchronous circuit is at least the CLK-to-Q delay can build a FSM to signal 3) You

when an equal number of 0s and 1s has appeared in the input. CS61C L24 State Elements : Circuits that Remember (22) a: a: b: b: c: c: d: e: 123 FFF FFT FTF

FTT TFF TFT TTF TTT Dr Dan Garcia Peer Instruction Answer 1) It needs base case (reg reset), way to step True i to i+1 (use register + clock). from ! 2) If not, will loose True !

data! 3) many states would it have? How Say its n. How does it know when n+1 bits have been seen? False! 1) HW feedback akin to SW recursion 2) The minimum period of a usable synchronous circuit is at least the CLK-to-Q delay can build a FSM to signal 3) You when an equal number of 0s and

1s has appeared in the input. CS61C L24 State Elements : Circuits that Remember (23) a: a: b: b: c: c: d: e: 123 FFF FFT FTF FTT

TFF TFT TTF TTT Dr Dan Garcia Design Hierarchy syste m contro l datapat h code

register s multiplexe comparato r r state register s register switchin g network s

combination al logic logi c Dr Dan Garcia And In conclusion State elements are used to: Build memories Control the flow of information between other state elements and combinational logic D-flip-flops used to build registers Clocks tell us when D-flip-flops change Setup and Hold times important We pipeline long-delay CL for faster clock

Finite State Machines extremely useful Youll see them again 150, 152, 164, 172, Dr Dan Garcia