Lab 12: Finite State Machines

Released: 23:59 Wedneday, April 16th, 2025.

Due: 20:59 Wednesday, April 23rd, 2025.

Using simple finite state machines to detect a bit sequence.

Download the start-up materials

For this lab, we will use Logisim to implement a bitstream detection finite state machine.

A bitstream is an unstructured sequence of bits commonly used for transmitting or storing digital data. In some applications or devices, it is useful to detect a particular sequence of bits in the stream, for example to recognize the start of a data packet or file (e.g., a particular pattern of bits represents the start of an important piece of data.) The following figure shows an example:

In the example above, a 1 is first sent to the bitstream analyzer (the bitstream “flows” from right to left into the analyzer.) In the next clock cycle, a 0 is sent, and so on. To be clear (it is a little confusing): the bitstream, as depicted, is being consumed right-to-left, which is the traditional way of visualizing such bitstreams. Once the bitstream analyzer has detected that it has seen 10101010, it outputs a 1. An application or device might need to know when the sequence 10101010 has been seen in the input, for instance, in this case, this bit sequence is used as a preamble for ethernet packets. That is, you search for this bit sequence to know when such a packet starts.

One possible way to detect such an input pattern is to use a large \(n\)-bit register, where \(n\) is the size of the bit sequence we wish to detect. This sequence might be very large, requiring a large amount of memory. For example, in ethernet frames, the preamble is eight bytes (256 bits!) long.

Another solution, one which you will use in this lab, is to use an advanced sequential logic called a finite state machine (FSM). The finite state machine, depending on the sequence being detected, may require less memory than simply storing all of the previously seen bits. FSMs also allow for very powerful pattern matching beyond just detecting whether a sequence of bits matches a particular known pattern. (For example, regular expressions for string matching.)

A FSM consists of a few components, which you will first (a) design and then (b) implement in Logisim. Your design will preferably be done electronically (e.g., in PowerPoint or Word or Inkscape, pdf, etc), though you may draw it with a pen-and-paper and submit a scanned copy. Your circuit must be submitted as a Logisim file.

Example FSM Diagram and Design

FSM design first requires the drawing of a finite state machine diagram. The diagram is a visual representation of the entire FSM: its initial state, how it changes state (transitions) based on the input, and its output for each state. As humans, we might prefer to look at the diagram, because it is a visual representation. Building a FSM in Logisim, however, will require a more formal representation (truth tables) which will soon be discussed.

As mentioned, the FSM diagram completely describes how the FSM works. When an input arrives, the arrows show what new state the FSM will be in. A FSM can only be in one state at any time. Depending on the state of the FSM, the FSM will output different values. The way that the FSM moves between states and outputs its values is dependent on the purpose of the FSM: No two FSMs will be alike.

The example FSM shown above will output 111 when the FSM has been given as input an odd number of 0s, followed by a single 1 (optionally followed by an infinite number of 0s.) If the FSM has been given as input a run of an odd number of 0s, it will output 010. The FSM also outputs 111 for other bit sequences (e.g. 1, 111.)

Because the example FSM has three states in total, we can use two bits to describe which state the FSM is in. Herein, state “A” will be state 00, “B” will be 01, and “C” will be 10. (It doesn’t have to be inclusive… we don’t need a state 11, for instance.) Other encodings are certainly possible (e.g., we could refer to state “C” as 11, but in this example, we shall not.)

The two bits of state could be, for example, implemented using two D flip-flops (aka, a 2-bit register.) The diagram shows that on each clock cycle, the input to the FSM is a single bit. In this lab, your FSMs will only process a single bit of input at a time. Each FSM state has three bits of output. The number of bits of output is not related to how many bits of state there are, or how large the input is. Instead, remember that the number of bits of output depends on what you need the FSM to do.

Now that each state has a number assigned to it (e.g., “A” is 00), we can use truth tables to describe (a) how the FSM moves between states given an input (the next state function), and (b) what a particular state’s output should be (the output function.) Presented next are the example FSM’s next-state and output functions. The outputs (generated values) are in bold.

Detecting a Simple Sequence

You will go through several steps to construct a small circuit that detects when a 0 arrives after two adjacent ones arrived in a bitstream (e.g., …00010011 which reads right to left: a 1 followed by a 1 followed by a 0). The circuit outputs a ‘0’ unless it detects the sequence. If the circuit detects the sequence, it outputs a ‘1’ upon seeing that 0.

A.: Draw the state diagram for a finite state machine (FSM) that detects the sequence described above as an image, Word document, PDF, or PowerPoint file.

Remember: encode the states of the FSM by numbering each state starting with zero. (For example, state “A” is 00.) Include this encoding on your diagram, as shown by the example.

Hint: When you detect the sequence, think about how to transition from that state to one that would detect the sequence if it would occur immediately again! (…011011…)

Example: Here’s my FSM diagram for the much more complex Ethernet example: pdf, pptx

B.: Write the truth tables for the next state and output functions (as seen above) as an image, text file, Word document, PDF, or PowerPoint file.

Remember: The output function is going to be simply a single bit. A ‘1’ if the sequence is detected, and a ‘0’ if not. It will depend on the current state.

Example: Here’s my FSM truth tables for the much more complex Ethernet example: pdf, docx

C.: Implement the circuit in Logisim incorporating the details listed below.

You may use the combinational analysis tool to generate and simplify your circuit. Be sure that you use a clock, a button to let you test different inputs, and a register of appropriate width to store the state. The button serves to let you simulate a ‘1’ being the next bit of input. Just hold it down as your clock ticks (CTRL+K) when you want a ‘1’ to be seen next. Release and let the clock tick for a ‘0’. See my example for the Ethernet case below.

The above shows the generic circuit for FSM sequential logic. The Next State Function and Output Function represent subcircuits which are represented by your truth tables.

Example: Here’s my Logisim circuit for the much more complex Ethernet example: circuit

Submission

Save your FSM diagram file as lab12A.pdf (or whatever file extension is appropriate).

Save your FSM truth tables as lab12B.docx (or whatever file extension is appropriate).

Save your Logisim circuit file as lab12C.circ. Only this file will be tested, the other files will be used by humans, if you don’t manage to pass the tests.

Collaboration Policy

You may work with one other person on your lab. They may be from the other recitation, but must be from my CS447 lecture section. You both must add a note to your written submission (at the top, very legibly) indicating who you are working with. You both must submit your own individual lab submission, but may collaborate directly on the answer.

Final Submission

You should submit the files named lab12A.pdf, lab12B.docx, and lab12C.circ (no folders!). Upload all files into the Gradescope assignment. You can submit as many times as you want until the deadline! Your Box folder (you have 50GB!) is accessible through http://my.pitt.edu. When you see your file within the shared folder, you know you have uploaded it successfully. If you would like to resubmit, you can copy the file in again. Let me know immediately if there are any problems submitting your work.