This lab will be worked using Logisim. Start Logisim by opening a terminal window under Linux and entering the command:

**logisim &**

In last week's lab we built a sequential logic component called a *flip-flop*, and we observed that
this component can store its state. It is a primitive memory element; 8 flip-flops can be used to form one 8-bit
register. In this lab, we will delve further into sequential logic circuits by constructing a
*Finite State Machine* (*FSM*) that uses flip-flops to store its state. It is a bit too ambitious to
breadboard even a simple FSM in a little over one hour, so we'll build our FSM in Logisim.

A finite state machine is not a "real" machine. It is a mathematical abstraction of a machine
that could be built from combinatorial and sequential logic components. We'll begin the task of
creating a finite state machine by reading
*How To Design A Finite
State Machine* developed at Princeton University. Read that
tutorial and answer the
questions below before proceeding.

**Questions**

- Is a FSM a sequential or combinatorial logic device?
- What digital logic elements are used to represent the "states" in the finite state machine?
- Is there any information in the finite state diagram that is not represented in the state transition table (i.e., the truth table)?
- Where do the numbers assigned to the states in the finite state diagram appear in the state transition table (i.e., the truth table)?
- How is the state transition table (i.e., the truth table) used to develop the
*next state*and*output*sub-circuits? - Are the
*next state*and*output*sub-circuits sequential or combinatorial logic circuits?

Verify your answers to the questions above with your instructor, if you are uncertain of the correct answer. |

Your task is to build a Moore state machine that recognizes a sequence of three ones in a stream of binary input. Whenever three consecutive ones are detected in the input stream, a 1 is output; a zero is output for all other inputs.

001011011101011010011101111110 <-- INPUT 000000000100000000000100011110 <-- OUTPUT

The first step is to create the state transistion diagram that will become the basis for your sequence recognizing state machine.

Draw your state transition diagram and show it to your instructor. |

Your next job is to fill in the state transition truth table show below. The state transition table contains the same information as your state transition diagram but expresses it in table form. Note:

**CS**is**C**urrent**S**tate and**NS**is**N**ext**S**tate.- Because there are four states, two binary digits are required to identify each state: the first state is 00 which means CS0=0 and CS1=0, etc.

CS1 | CS0 | Input | NS1 | NS0 | Output |
---|---|---|---|---|---|

Show your truth table to your instructor. |

There are two steps remaining to complete your FSM:

- Develop the boolean expressions that describe the "next state" and "output" logic from the truth table.
- Implement the FSM in Logisim.

This section focuses on the first step. For each subcircuits, you should write a Boolean expression that states its output as a function of its inputs; these are combinatorial circuits. You should derive these boolean expressions from the truth table formulated in Part 2. Use the Sum of Products (SOP) method used in Lab 2. The SOP method (although it is not called that) is also illustrated in the FSM tutorial, provided as part of this lab. You do not need to simplify these expressions.

Show your Boolean expressions to your instructor. |

We will build the FSM in three parts: (1) the next-state subcircuit, (2) the output subcircuit, and (3)
the flip-flops that will store the "state" of the FSM. All three should be built in Logisim. Remember
from Lab 2, that a Logisim
project can contain subcircuits. Create next-state and output subcircuits
in your Logisim project using the `Project->Add Circuit`

option on the tool bar.

Although you are not required to do so, it is recommended that you implement the two combinatorial logic subcircuits (the next-state logic and the output logic) using the features provided in the "Combinational Analysis" window. Specifically, you can enter either the boolean expressions or the truth table that define each of these subcircuits in the "Combinational Analysis" window, and, using that information, Logisim will build the subcircuit for you.

Note: Be sure to enter the input and output variable names before entering either the boolean expressions or the truth table for each combinational logic subcircuit.

Show your next-state and output subcircuits, implemented in Logisim, to your instructor. |

We will use *synchronous D flip-flops* to store the state of the FSM. Please read the short information panel
on synchronous D flip-flops before proceeding.

*Synchronous* means that the flip-flop is concerned with time. Digital circuits can have a concept of time
by using a clock signal. The clock signal simply goes from low-to-high and high-to-low in a short period of time.

A D flip-flop is a slight variation of the synchronous flip-flop shown above. The figure below shows a sketch of a D flip-flop similar to the one we will be using. This is a high level triggered D flip flop. In addition to the clock input, it has a data input D. It holds a single bit of state, which is visible on its output Q. During the high level of the clock it captures D and stores it internally. The schematic symbol for the D flip-flop is also shown below.

Select the `main`

window of your Logisim project. Open the Memory folder in the Explorer window and
you will see a D Flip-Flop. Add one to your empty schematic. In the Properties List on the left of the window, set
the `Trigger`

to `Rising Edge`

. Mouse over the flip-flop's pins so you can see its connections.
You can read about it under Help. Connect an input pin to D and an output pin to Q. In the `Wiring`

folder you will find a special pin called `Clock`

. Drop it in and connect the flip-flop to the clock.
It should look something like the image below.

`Poke`

D and see that nothing changes. You can `poke`

the clock to cause it to cycle and that's
fine for testing your circuits in this lab. *Optionally*, you can use the `Logging`

as follows: Pull down the
Simulate menu and select `Logging...`

. Begin by selecting the components that you want to monitor. Move to
the `Table`

tab under the Simulate menu and select `Reset Simulation.`

Now, set the tick frequency
to 4 Hz and select `Ticks Enabled,`

both located on the `Simulate`

menu. If you use
`Logging`

, make sure that you understand the output displayed under the `Table`

tab, and note
that you will still need to `poke`

the input to D to change it's value.

Now that you understand how to work with flip-flops in Logisim, build your complete FSM by linking the next-state and output subcircuits to D flip-flops. Be sure to test your FSM.

Demonstrate your FSM (or display your logging window) for your instructor. |

Before quitting, try one last thing. Modify both of your D flip-flops by making them high level trigger instead of edge triggered. Test your FSM again. Can you explain the difference in the FSM performance?

Explain why a level triggered flip-flop does not perform adequately in this circuit. |