yeolyi.comSeongyeol's CS

Sequential Logic

The registers and memory we’ve built only hold the values we put in; they don’t change on their own. Now that we have parts that remember, let’s build a machine that works on its own as long as it gets a clock. First, let’s split the circuits we’ve built so far into two kinds.

Combinational and sequential circuits

In an adder, a MUX, or a decoder, the output is decided by the current inputs alone. When the inputs change, the output changes right away, and nothing of the earlier inputs remains. Such a circuit is called a combinational logic circuit.

Latches and registers are different. Even with the same inputs, the output depends on what they remember. A circuit whose output is decided by the current inputs and a remembered value is called a sequential logic circuit, and the remembered value is called its state.

A useful sequential circuit usually has three parts: a register that holds the state, a combinational circuit that decides the next state from the current state and inputs, and a combinational circuit that decides the output from the current state. Each time the clock comes, the register takes the next state.

A counting circuit

The simplest example is a circuit that counts. The next state is the current state + 1, and the output is the state itself, so there is no separate combinational circuit for the output.

Let’s start with the combinational circuit that decides the next state. Adding 1 can be done with half adders. We add 1 to the lowest digit C0, and each half adder’s CARRY passes the carry to the next digit.

  1. Change C2, C1, and C0 to 1 so C3~C0 reads 0111. N3~N0 is 1000: the carry travels all the way to the top digit.
  2. Change C3~C0 freely. N3~N0 is always one more.

Now let’s attach a 4-bit register to hold the state. Fold the circuit above into a “Next State” box, feed the register’s outputs into the box’s C3~C0, and feed the box’s N3~N0 back into the register. When the clock comes, the register takes N, and that value goes back into the box to make the next N. A circuit that goes up by 1 each clock is called a counter. Below is a 4-bit counter.

  1. Change CLK to 1 and back to 0, over and over. C3~C0 grows one at a time: 0, 1, 10, 11, ….
  2. Watch how fast each digit changes. C0 changes every clock, C1 every two, and C2 every four.
  3. Press the play button to the right of CLK. The clock changes on its own, and the counter counts by itself.

A real computer’s clock changes on its own billions of times per second, so a counter counts that fast too.

Abstraction

From now on, we’ll draw this circuit as a single COUNTER box. Each time CLK goes from 0 to 1, the value inside goes up by 1, and it sends that value out to the right.

Wrapping up

A counter is the simplest sequential circuit: its next state is always + 1, and its output is the state itself. In the next post, let’s decide the next state and the output ourselves to build a traffic light.

Challenge

The post's 4-bit counter starts at 0. If CLK goes from 0 to 1 twenty times, what number do C3~C0 show? Answer in decimal.