Lecture 12 EGR 270 Fundamentals of Computer Engineering Reading Assignment Chapter 5 in Logic and Computer Design Fundamentals 4th Edition by Mano Online supplement to text Design and Analysis using JK and T Flip Flops www prenhall com mano Synchronous Logic Circuits versus Combinational Logic Circuits Let s begin by comparing how we describe each type of circuit Descriptions of Combinational Logic Circuits Recall that there are numerous ways to describe a combinational logic circuit including truth tables Karnaugh maps minterms maxterms Boolean expressions SOP expressions POS expressions Logic diagrams VHDL descriptions 1 Note Given any one of the descriptions above we could determine all of the others Lecture 12 EGR 270 Fundamentals of Computer Engineering Descriptions of Sequential Logic Circuits Similarly there are numerous ways to describe a sequential logic circuit including State diagrams State tables State equations and output equations Input equations flip flop input functions and output Equations Logic diagrams VHDL descriptions Note Given any one of the descriptions above we could determine all of the others Some of these ways to describe sequential circuits will now be introduced Finite State Machines FSM Sequential circuits are also referred to as finite state machines The circuit operates by moving between a finite number of pre determined states 2 Lecture 12 EGR 270 Fundamentals of Computer Engineering State Diagrams This is the most common way to describe a sequential circuit A state diagram is somewhat like a flowchart that describes the sequence to states through which the circuit might progress State a distinct event that is to occur one event in a sequence Example A state might be a single count in a counter If a counter counts 0 1 2 9 and then repeats then it has 10 unique states If four flip flops were used to store the count then the flip flops would store the values 1001 corresponding to state 9 Example A state might be one step in a machining operation there might be 5 states corresponding to the operations drill ream counterbore countersink and polish Example A traffic light controller might have three states Green Yellow and Red Under certain input conditions or at certain times the controller will change state 3 Lecture 12 EGR 270 Fundamentals of Computer Engineering Encoding states Show how a binary code can be stored in a set of flip flops In most cases Number of flip flops needed log2 Number of states Example Determine the number of states needed in each case below Description of circuit Number of flip flops required Circuit with 20 states Traffic light controller 3 bit UP DOWN counter Decade counter 4 Lecture 12 5 EGR 270 Fundamentals of Computer Engineering There are two primary types of state diagrams state machines Mealy state machine Mealy model the output depends on the present state and the inputs applied Moore state machine Moore model the output only depends on the present state X X Y We will primarily use Mealy models A B A Y B Y X X Y C Mealy Model Transition from one state to another depends on the Input X Output Y is specified with the transition Output Y depends on both the Present State and the Input X C Y Moore Model Transition from one state to another depends on the Input X Output Y is specified with the Present State Output Y depends only on the Present State Lecture 12 6 EGR 270 Fundamentals of Computer Engineering Example Both a Mealy Model and a Moore Model are used below to specify state machines that will detect the occurrence of two 1 s in a row Mealy Model 0 0 A 0 0 A 0 1 0 0 0 B 1 1 State A Zero 1 s received State B One 1 received Two states one flip flop Output of 1 indicates that two inputs of 1 occurred in a row Output is not associated with a state but with the transition 1 B 0 0 Moore Model State A Zero 1 s received State B One 1 received State C Two 1 s received 1 C 1 1 Three states two flip flops Output of 1 indicates that two inputs of 1 occurred in a row Output is associated with state C Lecture 12 EGR 270 Fundamentals of Computer Engineering Comparison of Mealy models and Moore models Mealy Model Moore Model Output depends on both the Present State and the Inputs Output depends only on the Present State Specify output in transition Specify output in Present State Generally requires fewer states Generally requires more states Output may change immediately when input changes so may change in the same clock cycle Output does not respond immediately to input change but is synchronized with the clock Reacts faster to inputs Safer Most of our textbook examples and class examples will use Mealy models 7 Lecture 12 EGR 270 Fundamentals of Computer Engineering Examples of state diagrams A Modulo 5 mod 5 counter B 3 bit Up Down counter C Traffic Light Controller 8 Lecture 12 EGR 270 Fundamentals of Computer Engineering State Table A state table provides the same information as the state diagram but in tabular form Example Determine the state table for the state diagram shown below 0 0 1 0 0 1 Is this a Mealy machine or a Moore machine 1 0 A D B 1 0 C 1 1 0 0 0 1 9 Lecture 12 EGR 270 Fundamentals of Computer Engineering State Assignment Some state diagrams have states indicated by letters or names because there is no numeric value assigned to the states As an example there are no natural numeric values for the states in a circuit that controls a traffic light states RED YELLOW and GREEN In such cases numeric values must be assigned to each state In the case of the traffic light 2 bits are needed to encode the three states but various possible codes could be used For example RED 00 YELLOW 01 and GREEN 10 There are many other possible state assignments Which is the best assignment to use We don t know This is a current research topic Example List possible state assignments for the last problem and repeat the state table using one of the state assignments 10 Lecture 12 EGR 270 Fundamentals of Computer Engineering Determining the State Diagram from a Logic Diagram The state diagram or state table can be found from the logic diagram by assuming an initial state determining the corresponding flip flop input values and then using the truth table for the flip flop to find the next state This information can be easily tabulated as in the example below 11 Lecture 12 EGR 270 Fundamentals of Computer Engineering Example Determine the state diagram for the logic diagram shown below 1 16 J Q 15 A M S B U 5A C LK K C LR 4 PR E 2 U 1A 1