Reed CS 221 Fall 2020

Lab 07: sequential circuits

Here we construct sequential circuits, circuits store and modify a collection of state bits. The state bits are held within memory commponents called registers. The circuit reasons about and modifies those state bits. It does so once per tick of a system clock signal.

This repo contains five examples of sequential circuits. Two of them are complete, two can be completed within this lab session, and the fifth is a bonus exercise that can optionally be completed.

Up/Down 2-bit Counter
The circuit upDownCounter.circ is an implementation of a 2-bit counter that “wraps around.” When counting up, it cycles as 00, 01, 10, 11, etc. When counting down, it cycles as 00, 11, 10, 01, etc. To build this circuit, there is a nextStateLogic subcircuit that takes three bits of input—two state bits along with a “count down” control line—to compute the next state bits. It is is a 3-input, 2-output combinatorial circuit.

When this machine is running, the two bits of state are interpreted as a 7-segment LED display. These seven LEDs correspond to the horizontal and vertical lights displayed on the right. There are, thus, seven combinatorial circuits used to interpret the 00, 01, 10, and 11 bits as a display of 0, 1, 2, and 3 as a single digit.

Up/Down 2-bit Counter
The circuit justSaw00.circ is an implementation of a three state machine that processes a sequence of 0s and 1s, one bit at a time, and changes its state accordingly. The machine is built to recognize when two 0s occur consecutively. This task requires that it have three different states: “bored”, “alert”, and “excited”. It’s in the bored stated initially. When the in that state and it processes 1 bits, it remains bored. When instead it sees a 0 bit it becomes alert. If it sees a 1 bit it goes back to being bored. But if in the alert state it becomes excited because it has just seen two consecutive 0 bits. Again, it becomes bored with a 1 input.

The states of the machine are held as two bits q1:q0. The bored state is 0:0, the alert state is 0:1, and the excited state is 1:0. When this machine runs, the output “lights up” only when the machine is in the excited state.

Exercises

Complete the first two exercises below alone or with your lab partner. If you work in a pair, then switch roles as to who draws the circuit and who watches and helps.

The third circuit exercises is a BONUS.

I’d normally want the logic components of your circuits to use AND, OR, and NOT gates. You can also use other basic gates (XOR, NAND, NOR) as well as any combinatorial circuit that we’ve built in class, lab, or on homework (e.g. a multiplexer).

Exercise 1: 3-bit saturating counter

Build a sequential circuit saturate3Bit.circ that has 3-bits of state representing the integers from 0 to 7. When its external DOWN input is set to 0, the circuit should count from its current state up to 7, with one incrementation per clock tick. Once at 7, it should stay at 7. This is its “saturated” count up state (i.e. the state bits of 111).

When instead its external DOWN input is set to 1, the circuit should count down from its state to 0. Once at 0, it should stay at 0. This is its “unsaturated” count state. (i.e. the state bits of 000).

The circuit is like the 2-bit counter circuit except it has three registers to keep track of three bits of state. And the 7-segment LED display should display the digits for 0 thru 7. This means you’ll build a 4-input 3-output combinatorial circuit for the next state logic, and you’ll build a 3-input 7-output combinatorial circuit for the display logic.

Exercise 2: a pattern recognizer

Devise a sequential circuit justSaw011 that processes sequences of 0s and 1s, one bit per clock tick. It should have a single bit display that should be lit up whenever the machine just processed three consecutive bits 011.

This requires you to perform four tasks:

  1. Determine the states and the transition behavior of the circuit. This would be something like a finite state diagram or a state transition table.

  2. Determine a binary code for each of the states. The initial state must be all 0s.

  3. Build a combinatorial circuit that computes the next state logic. This takes as input the previous state bits, along with the current bit of the sequence being processed in that clock tick. It produces the next state bits as output.

  4. Build a combinatorial circuit that computes the display bit from the state bits.

BONUS Exercise 3: an addition checker

Build a circuit that takes three bit sequences as input, with each being the same length. It processes each of the sequences simultaneously, processing a bit from each with each tick of the clock. Call the bit input from two of the sequences x and y, and the third an input z. The circuit should display a single invalid bit indicating whether the bits, as read so far, do not correspond to three rows of a valid schoolbook addition. For example, if it has processed the bits 0111010 from input x, and the bits 0101001 from input y, and the bits 1101011 from input z, then it should have the invalid bit set to 0. This is because they form the valid schoolbook addition:

  0 1 1 1 0 1 0
+ 0 1 0 1 0 0 1
---------------
  1 1 0 1 0 1 1

You should devise the circuit so that it reads the bits from left to right (from most- to least-significant). This is a little tricky because, if you start to think about what’s involved in this verification, you’ll realize that the invalid indicator can “flicker” with each new column it reads. For example, suppose it’s processed 7 columns that give this valid addition:

  0 1 1 1 0 1 1
+ 0 1 0 1 0 0 1
---------------
  1 1 0 0 1 0 0

Then the circuit should see this as valid, and the invalid indicator should be off. But then if the next column of bits read were x of 0, y of 0, and z of 1, then the invalid light should go on because

  0 1 1 1 0 1 1 0 
+ 0 1 0 1 0 0 1 0 
-----------------
  1 1 0 0 1 0 0 1

is not valid. If the next bits read were x of 1, y of 1, and z of 0, then the invalid light should go off again because

  0 1 1 1 0 1 1 0 1
+ 0 1 0 1 0 0 1 0 1
-------------------
  1 1 0 0 1 0 0 1 0

is a valid schoolbook addition.

Modify the included file addChecker.circ so that it behaves as prescribed here.

For partial credit, you could instead make a circuit where the input is instead processed from the least-significant bit column to the most-significant bit column.