Logic Circuits II – Lecture 11: Finite State Machines PDF

Logic Circuits II – Lecture 11 Finite State Machines  Finite State Machines A state machine is a sequential circuit having a limited (finite) number of states occurring in a prescribed order. A counter is an example of a state machine; the...

Logic Circuits II – Lecture 11 Finite State Machines  Finite State Machines A state machine is a sequential circuit having a limited (finite) number of states occurring in a prescribed order. A counter is an example of a state machine; the number of states is called the modulus. Two basic types of state machines are the Moore and the Mealy. The Moore state machine is one where the outputs depend only on the internal present state. The Mealy state machine is one where the outputs depend on both the internal present state and on the inputs. Both types have a timing input (clock) that is not considered a controlling input. Lecture 11- Logic cct II  General Models of Finite State Machines A Moore state machine consists of combinational logic that determines the sequence and memory (flip-flops), as shown in Figure (a). A Mealy state machine is shown in part (b). Lecture 11- Logic cct II  General Models of Finite State Machines In the Moore machine, the combinational logic is a gate array with outputs that determine the next state of the flip-flops in the memory. There may or may not be inputs to the combinational logic. There may also be output combinational logic, such as a decoder. If there is an input(s), it does not affect the outputs because they always correspond to and are dependent only on the present state of the memory. For the Mealy machine, the present state affects the outputs, just as in the Moore machine; but in addition, the inputs also affect the outputs. The outputs come directly from the combinational logic and not the memory. Lecture 11- Logic cct II  Example of a Moore Machine The figure shows a Moore machine (modulus-26 binary counter with states 0 through 25) that is used to control the number of tablets (25) that go into each bottle in an assembly line. When the binary number in the memory (flip-flops) reaches binary twenty-five (11001), the counter recycles to 0 and the tablet flow and clock are cut off until the next bottle is in place. Lecture 11- Logic cct II  Example of a Moore Machine The combinational logic for the state transitions sets the modulus of the counter so that it sequences from binary state 0 to binary state 25, where 0 is the reset or rest state and the output combinational logic decodes binary state 25. There is no input in this case, other than the clock, so the next state is determined only by the present state, which makes this a Moore machine. Lecture 11- Logic cct II  Example of a Moore Machine One tablet is bottled for each clock pulse. Once a bottle is in place, the first tablet is inserted at binary state 1, the second at binary state 2, and the twenty-fifth tablet when the binary state is 25. Count 25 is decoded and used to stop the flow of tablets and the clock. The counter stays in the 0 state until the next bottle is in position (indicated by a 1). Then the clock resumes, the count goes to 1, and the cycle repeats, as illustrated by the state diagram in the figure. Lecture 11- Logic cct II  Example of a Mealy Machine Let’s assume that the tablet-bottling system uses three different sizes of bottles: a 25-tablet bottle, a 50-tablet bottle, and a 100-tablet bottle. This operation requires a state machine with three different terminal counts: 25, 50, and 100. Lecture 11- Logic cct II  Example of a Mealy Machine The combinational logic sets the modulus of the counter depending on the modulus-select inputs. The output of the counter depends on both the present state and the modulus-select inputs, making this a Mealy machine. Lecture 11- Logic cct II  Example of a Mealy Machine -State diagram The red arrows in the state diagram represent the recycle paths that depend on the input number. The black dashed lines mean the interim states are not shown for simplicity. Lecture 11- Logic cct II