Lab: FSMs
Log in and create a new project in CircuitVerse.
Whenever you want to save your work, click on Project -> Save Online.
Save often! Your work is not saved automatically.
Exercise 0: New Toys
Connect a Button element (from the Input bin) to an Output element as follows. What does pressing the button do?
Replace the Button element with a Clock element (from the Sequential Elements bin). What does this circuit do?
Use a DFlipFlop element (from the Sequential Elements bin) to build the following circuit. (Make sure you have a DFlipFlop and not a TFlipFlop. We will only be using DFlipFlop elements.) What does this circuit do?
Replace the Button element with a Clock element (from the Sequential Elements bin). What does this circuit do?
Exercise 1: Baby's First Finite State Machine
Build the following finite state machine. What does this circuit do?
Replace the Button element with a Clock element (from the Sequential Elements bin). What does this machine do now?
Exercise 2: Baby's Second Finite State Machine
Build the following finite state machine. What does it do?
Background: How To Design a Finite State Machine
1. Draw a state transition diagram. Associate input values with each arrow and output values with each state.
2. Assign binary names to each state. The starting state's name should use only 0s . Meaningful binary names can help simplify your circuit.
3. Write two truth tables. One table maps from the current state to the output values. The other table maps from the current state and input to the next state. Each row of this second table corrresponds to one arrow in the state transition diagram. Indicate which states are invalid.
4. Draw a Karnaugh map for each output bit and next state bit. Fill in bits for invalid states that will result in the simplest circuit.
5. Draw combinational logic circuits.
6. Add one flip-flop for each state bit. The flip-flops' inputs correspond to the next state and their outputs correspond to the current state.
7. Build and test!
Exercise 3: Even Machine
Follow the steps listed above to build a finite state machine with one input and one output. The machine outputs a 1 if and only if it has been given an input of 1 an even number times (since the last time it was reset), as illustrated by the following examples:
Input History Output
0001000 0 (1 is odd)
010010 1 (2 is even)
11001 0 (3 is odd)
000 1 (0 is even)
nothing yet 1 (0 is even)
Exercise 4: Counter
Follow the steps listed above to build a 2-bit binary counter. This finite state machine has zero inputs and two outputs. The machine outputs 00, then 01, then 10, then 11, then 00 again, and so on.
Additional Challenges
To earn more than 90%, go ahead and build any of the following, or build FSMs of your own design!
010 Machine
This FSM has one input and one output. It outputs a 1 if and only if it has EVER seen the input sequence 010. (Once it has seen 010, the machine outputs 1 forever, no matter what other bits it sees afterward.)
Input History Output
10 0
001011011 1
011011011 0
nothing yet 0
First Bit Memorizer
This FSM has one input and one output. If the first input it sees is 0, then it will only output a 1 in the future when it has just seen a 0. On the other hand, if the first input it sees is 1, then it will only output a 1 in the future when it has just seen a 1.
Input History Output
01110 1
00001 0
10 0
1 1
nothing yet 0
3x Machine
This FSM has one input and one output. It outputs a 1 only if the arbitrarily long stream of 0s and 1s it has read encode for a multiple of 3 in binary. For example, if your machine has seen 1, then 1, then 0, then it has seen 110, which is 6 in binary. Because 6 is a multiple of 3 in binary, the output will be 1. If it then sees a 1, it will have seen 1101, which is 13 in binary, so the output will now be 0.
Register
This FSM has two inputs (In and Load) and one output. This machine stores one bit and outputs it at all times. When Load is 0, In is ignored, and the machine outputs whatever bit was already stored. When Load is 1, the value of In is now stored, and this bit is output at all times until a new value is stored.
Challenge: Make a 4-bit register, so that In and Out consist of 4 bits each, and Load is still 1 bit.
Counter With Load
Make an 4-bit binary counter with 5 inputs (In3, In2, In1, In0, and Load) and 4 outputs (Out3, Out2, Out1, Out0). The counter stores and outputs a 4-bit value. If the Load input is 0, the counter will increment that stored value when the clock ticks. On the other hand, if the Load input is 1, the counter will replace the stored value with the value of In3/In2/In1/In0 when the clock ticks.
RAM
Make a 2-bit RAM with 3 inputs (Address, In, and Write), and 1 output (Out). The RAM stores two bits--one at address 0 and one at address 1. The RAM always outputs the value of the bit stored at the given Address. If the Write input is 0, the RAM will ignore In. If the Write input is 1, the RAM will replace the value at the given Address with the value of In when the clock ticks.
Your Original Idea
Propose and build your own FSM.