Report

1 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Reading Assignment: - Chapter 5 in Logic and Computer Design Fundamentals, 4th Edition by Mano Recall an earlier slide describing two types of state diagrams. 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. We will primarily use Mealy models X X/Y A B X/Y A/Y B/Y X C/Y C Moore Model 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 • 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 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 2 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. Moore Model: Mealy Model: 0 0/0 A/0 A 0/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 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. Chapter 5B 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 3 EGR 270 – Fundamentals of Computer Engineering Chapter 5B 4 Sequence Detector: An example of a circuit whose output sequence is critical and the numeric value of the states is unimportant is a “sequence detector”. Such a circuit might be used to detect a certain bit pattern (such as in synchronizing two signals) or for a digital lock – where the lock is unlocked when a correct combination (sequence) is entered. Input, X Sequence Detector Output, Y Example: Detect the sequence 101, including overlapping sequences. Define the output, Y, as follows: 0 Inputsequence not detected Y 1 Input sequence detected Fill out the values for Y in the table below: X Y 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 EGR 270 – Fundamentals of Computer Engineering Chapter 5B Example: Design a sequence detector to detect the sequence 1010. The sequence detector should also detect overlapping sequences. The circuit should output a binary 1 when a valid sequence is detected. Use a Moore model. 5 One strategy is to use 5 states: A - 0 correct values in sequence B - 1 correct value in sequence C - 2 correct values in sequence D - 3 correct values in sequence E - 4 correct values in sequence Test the state diagram with the input sequence 0101011001010100 State A Input 0 Output 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 EGR 270 – Fundamentals of Computer Engineering Chapter 5B Example: Repeat the previous example using a Mealy model. Note that only 4 states are required. 6 One strategy is to use 4 states: A - 0 correct values in sequence B - 1 correct value in sequence C - 2 correct values in sequence D - 3 correct values in sequence Test the state diagram with the input sequence 0101011001010100 Is the output identical to the output from the previous example? State A Input 0 Output 1 0 1 0 1 1 0 0 1 0 1 0 1 0 0 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) • How many flip-flops are required using the Moore model? • How many flip-flops are required using the Mealy model? • Complete the excitation table for the Mealy model circuit. 7 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) Draw the logic diagram. Clearly label the input sequence, x, and the output sequence, y. 8 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: Serial 2’s Complementer Circuit Design a one input, one output serial 2’s complementer using a Mealy Model. The circuit accepts a string of bits from the input and generates the 2’s complement at the output. The circuit can be reset asynchronously to start and stop the operation. Implement the circuit using JK flip-flop(s). Input Sequence, x Serial 2’s Complementer 2’s complement of Input Sequence, y Design: Recall that one method for finding a 2’s complement is to start with the LSB and proceed until the first 1 is encountered and then take the 1’s complement of all bits. complement Input, x: Output, y: 1001100 0110100 State B (output = 1’s complement of input) State A (output = input) 9 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) • Draw the state diagram using states A and B as defined on the previous slide 10 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) • How many flip-flops are needed for 2 states? • Fill out the excitation table. Input/ Present State x Q 0 0 0 1 1 0 1 1 Next State Q Flip-flop inputs J K Output y • Use K-maps to find expressions for J, K, and y 11 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) • Draw the logic diagram 12 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 13 Recall that three methods for designing sequential circuits will be covered: 1) Excitation table method (already covered) 2) State equation method 3) “One-Hot” method Designing Sequential Circuits using State Equations Before the state equation method is covered, two related topics must be covered: • state equations • flip-flop characteristic equations State Equations A state equation is an equation for the next state of a sequential logic circuit. It has the form: Q(t + 1) = (Boolean expression involving present states and inputs) The state equations are simply formed using the “Next State” shown in the state table. EGR 270 – Fundamentals of Computer Engineering Chapter 5B Example: Find the state equations for the state diagram shown below. 0 1 0 0 1 4 1 0 1 1 2 3 1 0 0 14 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 15 Flip-flop characteristic equations Flip-flop behavior has been expressed so far using truth tables or excitation tables. The next state (output) of a flip-flop can also be described algebraically using a flip-flop state equation or flip-flop characteristic equation. Example: Develop the flip-flop characteristic equation for a JK flip-flop. Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: Develop flip-flop characteristic equations for SR, D, and T flipflops. 16 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Designing Sequential Circuits using State Equations – Procedure 1. Form the state table. 2. Develop the state equations from the state table. 3. Determine the type of flip-flop to be used. 4. Manipulate the state equation into the form of the characteristic equation for each flip-flop. This will yield the flip-flop input expressions. Notes: • It is easiest to design by state equations using D flip-flops. • Many programmable devices only support D flip-flop designs, so state equations are very useful. • JK flip-flop designs will yield the simplest circuits in general. • Designing circuits by the excitation table method and by the state equation method should yield the same results. 17 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: Design a modulo-7 counter by the state equation method using D flip-flops a) Create the state table Present State Next State A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 A(t+1) B(t+1) C(t+1) 18 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) b) Form the state equations 00 01 11 10 00 01 11 10 00 01 11 10 0 0 0 1 1 1 c) Determine the D flip-flop inputs (trivial!) 19 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) d) Draw the logic diagram using D flip-flops 20 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 21 Example: Repeat the last example using JK flip-flops. a) Create the state table – same as before b) Form the state equations – same as before c) Determine the JK flip-flop inputs (much harder than with D flip-flops) State Equation A(t+1) A(t 1) A B BC P ut in theformof thechar.equation for a JK flip - flop: Q(t 1) J Q K Q or A(t 1) JA A KA A (i.e.,each termmust haveA or A) So A(t 1) A B BC A(t 1) A B BC A A A(t 1) A B ABC ABC A(t 1) AB C ABC A(t 1) A B BC ABC - T heorem7A So JA = BC So KA B C KA B C KA BC Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) - Repeat for the next two state equations State Equation B(t+1) State Equation C(t+1) 22 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: (continued) d) Draw the logic diagram using JK flip-flops 23 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Three methods for designing synchronous sequential circuits: 1) Excitation table method (already covered) 2) State equation method (already covered) 3) “One-Hot” method “One-Hot” Method for designing synchronous sequential circuits The “one-hot” method is based on the idea that N flip-flops will be used to represent N states and that at any given time only one of the states is “hot” or HIGH – the current state. 24 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 25 Example: A state diagram with 4 states would require 4 flip-flops and the outputs would be as follows: Q Other connections and circuitry 1 State A is “hot” Q 0 Other connections and circuitry Q 0 Q 1 State B is “hot” Q 0 Q 0 Q 0 Q 0 (Similar diagrams for states C and D are not shown.) Chapter 5B EGR 270 – Fundamentals of Computer Engineering 26 “One-Hot” Method - Advantage The design process is simple for the “one-hot” method. The connections for D flip-flop designs can be seen easily from an ASM (Algorithmic State Machine) Chart, which is similar to a flowchart. Also note that this method can allow for a simple way to describe sequential circuits in VHDL. Algorithmic State Machine (ASM) Chart symbols ASM Charts are covered in more detail in Chapter 8 of the text. For now, we will just introduce two ASM chart symbols (elements). Entry State 0 Exit State box Entry N X = 1? Exit 0 Y Exit 1 Decision box Chapter 5B EGR 270 – Fundamentals of Computer Engineering 27 “One-Hot” Method - Disadvantage The “one-hot method requires a potentially large number of flip-flops. Since the states are not encoded as with other methods (i.e., one flip-flop is required for each state), designs may require a large number of flip-flops. Examples are provided below to illustrate this problem. # flip-flops using encoded states (state equations or excitation table method) # flip-flops using the “onehot” method # flip-flops = log2(# states) # flip-flops = # states 3-bit (mod-8) counter 3 8 8-bit counter 8 256 Circuit with 20 states 5 20 Sequential Circuit Note: When implementing sequential circuits using Aldec Active-HDL , the software gives the user a choice of implementing a “one-hot” design or using encoded states (the default) . Using encoded states saves many flip-flops. Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example: Use the “one-hot” method to design a mod-5 counter. Note that each state box essentially acts like a D flip-flop where the entry to the box is D and the exit from the box is Q. ASM Chart State Equations D0 State 0 So Q0(t+1) = D0 = Q4 Q0 D1 State 1 So Q1(t+1) = D1 = Q0 Q1 State diagram D2 State 2 0 So Q2(t+1) = D2 = Q1 Q2 D3 4 1 State 3 So Q3(t+1) = D3 = Q2 Q3 D4 3 2 State 4 Q4 So Q4(t+1) = D4 = Q3 28 Chapter 5B EGR 270 – Fundamentals of Computer Engineering 29 Example (mod-5 counter continued): State Equations: Q0(t+1) = D0 = Q4 Q1(t+1) = D1 = Q0 Q2(t+1) = D2 = Q1 Q3(t+1) = D3 = Q2 Q4(t+1) = D4 = Q3 Logic Diagram: D0 Q0 Q0 D1 Q1 Q1 D2 Q2 Q2 D3 Q3 Q3 D4 Q4 Q4 CK Recall that the outputs above are not encoded. An encoder can be used to create encoded outputs if they are needed (for example, to send the outputs to a BCD-to-7 segment decoder). This is illustrated on the following slide. Chapter 5B EGR 270 – Fundamentals of Computer Engineering 30 Example (mod-5 counter continued): CK D0 Q0 Logic Diagram with encoder added Q0 D1 Q1 Q1 D2 Q2 0 0 0 0 1 2 3 4 5 6 7 8x3 Encoder (MSB) A B C Q2 D3 Q3 0 Q3 D4 Q4 Q4 A BCD-to 7-segment B decoder C D (LSB) Exercise: Add binary values to the logic diagram if the counter is in state 3 Chapter 5B 31 EGR 270 Example: Use the “one-hot” method to design a mod-5 counter UP/DOWN. Let x be an input control where if: • x = 0 the counter counts down • x = 1 the counter counts up State 0 0 0 1 x = 0 or 1? Q2(t+1) = D2 = 1 1 0 0 1 State 2 0 4 x = 0 or 1? Q1(t+1) = D1 = ASM Chart: 1 0 1 1 State 1 0 State diagram x = 0 or 1? Q0(t+1) = D0 = State 3 0 Q3(t+1) = D3 = 1 0 0 x = 0 or 1? 1 2 3 State 4 1 • Label D and Q next to each state box • Find the state equations 0 x = 0 or 1? Q4(t+1) = D4 = 1 Chapter 5B EGR 270 – Fundamentals of Computer Engineering Example (mod-5 UP/DOWN counter continued) : Draw the logic diagram 32