CSC 258 – Lab 6

Finite State Machines

1 Learning Objectives

The purpose of this lab is to learn how to create Finite State Machines and use them to perform operations

on a datapath.

2 Marking Scheme

This lab is worth 6% of your final grade, but you will be graded out of 8 marks for this lab, as follows:

• Prelab – Simulations: 3 marks

• Part I: 2 marks

• Part II: 3 marks

• Part III (bonus): 2 marks (1 for prelab, 1 for demo)

3 Preparation Before the Lab

You are required to complete Parts I and II of the lab by building and testing your circuits in Logisim

(using reasonable tests that you can justify). Part III is optional, but has a prelab component, should you

choose to do it. You must submit your prelab preparations (schematics, Logisim design, and simulation

outputs) for Parts I to II (and Part III, if you choose to do it).

You are required to implement and test all of Parts I and II of the lab (and Part III, if you choose to do

it). Your demonstration to the teaching assistants should illustrate the rigorous testing procedure you

used to verify your design.

4 Part I

Your task for this part is to implement a finite state machine (FSM) that implements a sequence recognizer. This will turn an output signal on if it recognizes two specific sequences of input signals: the

sequence 1111 or the sequence 1101.

Given an input w and an output z, the output z is set to 1 Whenever w = 1 for four consecutive clock

pulses, or when the most recent sequence on w was 1101 for the last four clock pulses. In all other cases,

z = 0. Overlapping sequences are allowed, so that if w = 1 for five consecutive clock pulses the output

z will be equal to 1 after both the fourth and fifth pulse. Figure 1 illustrates the required relationship

between w and z. A state diagram for this FSM is shown in Figure 2.

In the starter Logisim file, the two modules part1 FSM and part1 state table provide a starting point for

implementing the required state machine:

• part1 FSM is the high-level FSM circuit that has the flip-flops needed to implement the states and

a module for the state logic. A module for the output logic is omitted and must be filled in by you.

• part1 state table is the module for the state logic that you must complete.

Study and understand these modules as they provide a model for how to clearly describe a finite state

machine that will both simulate and synthesize properly.

To complete this part of the lab, you must follow the following steps:

1

!”#$%&

‘&

(&

Figure 1: Required timing for the output z.

!”#$

%”#$

&”#$

‘”

#$

(“)$

*”#$

+”

)$

,-.-/$

01)$

01)$

01)$ 01#$

01)$

01#$

01#$

01#$

01)$

01)$

01#$

01#$

01)$

01#$

Figure 2: A state diagram for the FSM.

2

1. Begin with the starter circuit provided in lab6_starter.circ. Answer the following questions in

your prelab: (PRELAB)

• Given the starter circuit, is the Reset signal a synchronous or asynchronous reset?

• Is it active high, or active low signal?

• How should the Reset signal feature in the tests that you run on your FSM?

Hint: if you’re not sure of some of the answers to the first two questions, try experimenting with

the circuit to confirm the behaviour you suspect.

2. Before modifying the Logisim starter circuit, assign flip-flop values to each of the states in Figure 2

and create a state table that illustrates the state transitions in response to the input signal w.

3. Fill in the rest of the circuit in the part1 state table module to implement the state table you derived

in Step 2. This module will implement the state logic (the combinational circuit that determines

what the new flip-flop values should be, based on the previous flip-flop values and the input w).

4. Implement the output value circuit for z in part1 FSM. (PRELAB)

5. Outline the test plan for your circuit in your prelab report and why these test cases verify the

correctness of your circuit. Use this plan to test your modules with Poke( ) to confirm its

expected behaviour. Include screenshots of your simulation output that illustrates key test cases.

(PRELAB)

Note: There are several ways to implement the state logic and output logic. There are no restrictions on

the approach that you use, but some useful suggestions will be offered during the tutorial session.

5 Part II

Processor circuits can be separated into two main components:

1. The datapath that connects data storage structures (registers) to processing units (the ALU).

2. The control path that operates the datapath signals to determine what data values flow through

the datapath and what operations are performed on this data (a finite state machine).

In previous labs, you constructed a simple ALU. In Part I of this lab you constructed a simple finite

state machine (FSM), which is the most common component used to implement the control path. To

complete this part of the lab, you will implement an FSM to control a datapath that performs a common

calculation. This is an important step towards building a microprocessor as well as any other computing

circuit.

The datapath you will be controlling is provided as part of the starter circuit. A FSM is provided as

well, which operates on this datapath to compute 2A2 + C. Your task is to create a different FSM that

controls the datapath provided to perform the following computation:

Cx2 + Bx + A

The values of x, A, B and C will be preloaded by the user on the switches before the computation begins.

Figure 3 shows the block diagram of the datapath you will be using. There are a few things to note

about this diagram:

• Reset signals are not shown to reduce clutter, but make sure to include them when building your

circuit in Logisim.

• The datapath will operate on 8-bit unsigned values. Assume that the input values are small enough

to not cause any overflows at any point in the computation, i.e., no results will exceed 28 −1 = 255.

3

• The ALU only needs to perform addition and multiplication, but you’re welcome to use a variation

of the ALU you built in previous labs in order to have more operations available for solving other

equations (in case you wish to try some things on your own).

• There are four registers Rx, RA, RB and RC that will be loaded at the start with the values of x,

A, B and C, respectively. The registers RA and RB can be overwritten during the computation.

• There is one output register, RR, that captures the output of the ALU and displays its value both

in binary on the LEDs and in hexadecimal on the HEX displays.

• Two 8-bit-wide, 4-to-1 multiplexers at the inputs to the ALU are used to select which register

values are input to the ALU.

• All registers have enable signals to determine when they load new values. They also have an active

low asynchronous reset to clear their contents to zero.

C

X

A

B

R

alu_select_a alu_select_b

ld_c ld_b ld_a ld_b

data_result

alu_op

ld_r

data_in

ld_alu_out

ld_x

Figure 3: Block diagram of datapath.

The provided circuit should operate in the following manner:

• After an active low asynchronous reset, you will use the data in bits to load the following values

on the first four clock cycles:

– On the first clock cycle, load the value for RA.

– On the second clock cycle, load the value for RB.

– On the third clock cycle, load the value for RC .

– On the fourth clock cycle, load the value for RX.

• Computation will start after all values are loaded.

• When computation is finished, the final result will be loaded into RR.

• This final result should be displayed on LEDs in binary and HEX displays in hexadecimal.

Perform the following steps for this part:

1. Examine the provided starter circuits (all the modules for this part start with part_2), which is

available on Quercus). This is a major step in this part of the lab. You will not need to build

4

the datapath yourself, but you will need to fully understand the datapath embodied by the starter

circuit to be able to make your modifications. (PRELAB)

2. Determine a sequence of steps similar to the datapath example shown in lecture to control the

datapath to perform the required computation. You should draw a table that shows the contents

of the registers and the control signal values for each cycle of your computation. Include this table

in your prelab. (PRELAB)

3. Draw a state diagram for your controller starting with the register load states provided in the

example FSM. Include the state diagram in your prelab. (PRELAB)

4. Modify the provided FSM to implement your controller and synthesize it. You should only modify

the control module, not the datapath. Submit your modified circuit in the prelab. (PRELAB)

5. Test your modules with Poke( ) to verify its correctness. Include a few screenshots that shows

the simulation output. (PRELAB)

Again, note that there are multiple ways to implement a FSM in Logisim. Explore these and find the

approach that works best for you.

It is fine if your implementation does not use all of the modules provided, but that doesn’t mean you

should have your entire circuit in one giant module! We will start evaluating the elegance and readability

of your design in these later labs, so find ways to divide your solution into smaller modules when

possible/sensible.

6 Part III (Optional)

Note: Only start working on this part if you already completed other parts. This is an optional part

that provides a more challenging exercise for you to further test your knowledge.

Addition, subtraction and multiplication are much easier to build in hardware than division. So division

is the most complex operation in hardware. For this part, you will design a 4-bit restoring divider using

a finite state machine.

Figure 4 shows an example of how the restoring divider works. This mimics what you do when you do

long division by hand. In this specific example, number 7 (Dividend) is divided by number 3 (Divisor ).

The restoring divider starts with Register A set to 0. The Dividend is shifted left and the bit shifted

out of the left most bit of the Dividend (called the most significant bit or MSB) is shifted into the least

significant bit (LSB) of Register A as shown in Figure 5.

The Divisor is then subtracted from Register A. This is equivalent to adding the 2’s complement of the

Divisor (11101 for the example in Figure 4) to Register A. If the MSB of Register A is a 1, then we

restore Register A back to its original value by adding the Divisor back to Register A, and set the LSB

of the Dividend to 0. Else, we do not perform the restoring addition and immediately set the LSB of the

Dividend to 1.

This cycle is performed until all the bits of the Dividend have been shifted out. Once the process is

complete, the new value of the Dividend register is the Quotient, and Register A will hold the value of

the Remainder.

Structure your code in the same way as you were shown in Part II and follow these steps for this part:

1. Draw a schematic for the datapath of your circuit. It will be similar to Figure 5. You should show

how you will initialize the registers, where the outputs are connected to, and include all the control

signals that you require.

2. Draw the state diagram that controls your datapath.

3. Draw the schematic for your controller module.

5

Figure 4: An example of how a restoring divider works.

Figure 5: Block diagram of restoring divider.

6

4. Draw the top-level schematic showing how the datapath and controller are connected as well as

the inputs and outputs to your top-level circuit.

5. Build your circuit in Logisim.

6. Simulate your circuit using a variety of input settings. (PRELAB)

7

Sale!