Demo 6.6: Registers, and Circuits That Walk a Chosen Sequence

The synchronous counter ended with a description of itself that never once mentioned counting: flip-flops holding a state, combinational logic working out the next one, and a clock stepping between them. A counter, it turned out, is that machine with the simplest next-state logic anybody could pick.

So what happens if you take the next-state logic away?

You get a register. Four D flip-flops side by side, one clock wire to all of them, and each D fed from somewhere. There are no gates in it at all. It computes nothing, decides nothing, and counts nothing.

It is the most useful circuit in the module.

The whole demonstration is one question

Each flip-flop has a D input, and something has to be connected to it. That is the only design decision available, and every circuit on this page is a different answer to it:

Where D comes from	What the circuit becomes
Its own input pin	A storage register. It remembers a word.
Its own Q	A register that holds. This is what a load enable really does.
The Q of the stage before it	A shift register. The word walks along, one stage per clock.
The Q of the last stage	A ring counter. The word walks in a circle for ever.
The Q̄ of the last stage	A Johnson counter. Twice as many states, one inverter.

Same four flip-flops in every row. Same single clock. One wire moved.

That is worth holding onto, because the four circuits are usually taught as four separate things with four separate diagrams, which hides the fact that they are one piece of hardware being asked a different question.

Why anyone builds the shifting one

The storage register is easy to want: you have a value, you would like to keep it, and here is a box that keeps it.

The shifting one takes more explaining, and the explanation is not about registers at all. It is about wires.

Sending an eight-bit value from one chip to another needs eight wires, and wires are expensive in a way that is easy to underestimate. Eight pins on the package at each end. Eight tracks on the board. Eight conductors in the cable, and a connector wide enough for them. Widen the value to sixteen bits and all of those costs double.

Or send it on one wire, one bit at a time, and take eight clocks over it. The pin count stops depending on the width entirely.

A shift register is the converter between those two, and it converts in whichever direction you read it. That is the trade the third tab is about, and it is the reason this circuit is in every serial link, every serial port, and every part that drives more outputs than the processor has pins to spare.

How to use it

Holding a word is the storage register. Set the four data inputs, then clock. The point of the tab is the gap between the inputs and the outputs: they are only ever forced to agree at an edge, and that gap is the entire reason a register exists.

Shifting it along moves one wire and runs the same four flip-flops as a shift register. There is a serial pattern you can edit a bit at a time, and the waveforms underneath show every output as the one above it delayed by exactly one clock.

Serial and parallel puts numbers on the trade. Pick a width and a shift clock and read the two panels against each other, then the four in/out arrangements and what each one is for.

Walking a sequence feeds the output back to the input. The register stops storing anything and starts walking a fixed loop of states, and the tab ends with all sixteen states laid out so you can see the loops nobody designed.

Registers, and Circuits That Walk a Chosen Sequence

Four flip-flops, one clock, and one wire moved: a word held, a word walked along, wires traded against time, and a sequence somebody chose.

derekmolloy.ie

A register is a row of flip-flops that share a clock and do no arithmetic whatsoever.

Every circuit in this half of the module so far has computed something. This one does not: it remembers.
Four D flip-flops side by side, one clock wire to all of them, and each D fed from its own input pin. That is the whole circuit.
The clock is not a timekeeper here. It is an instruction, and the instruction is "remember what is on the inputs, now".
Between clocks the inputs can do whatever they like and the outputs will not care, which is exactly what makes the thing useful.
Everything else on this page is the same four flip-flops with one wire moved.

The data inputs, D0 to D3

Click to change them. Nothing happens to the outputs until you clock.

The load enable

Try one of these

On the inputs

1011

Stored in the register

0000

they agreeno

load enable1

The inputs and the outputs disagree, and that is fine

The inputs are showing 1011 and the register is holding 0000.
Neither of those is wrong. The inputs are what is being offered and the outputs are what was accepted, and they are only ever forced to agree at a clock edge.
That gap is the entire reason a register exists. Whatever is producing the data can change it whenever it likes, and the register goes on presenting the last value it was told to keep.
Press "Clock once" and the two will match until you change the inputs again.

Why the enable is not a switch on the clock

The obvious way to stop a register loading is to stop the clock reaching it, and it is the wrong way.
A gated clock arrives late, because it has been through a gate, so that register is no longer in step with the rest of the system.
Worse, a gate whose inputs change at the wrong moment can emit a narrow spike, and a flip-flop cannot tell a spike from an edge.
So the clock is left alone and the data path is switched instead: a multiplexer on each D choosing between the input pin and the stage’s own Q.
Every arrangement on the other three tabs is that same multiplexer with more inputs on it.

What the word actually means

A register is any small, fast store built from flip-flops and read or written as a unit.
The registers inside a processor are exactly this: a handful of them, a few tens of bits wide, holding the values an instruction is about to work on.
Width is a design decision rather than a fact of nature. Four here, eight in a 74HC595, sixty-four in a modern processor.
The clock that loads them is the same clock that steps everything else, which is what keeps a synchronous system coherent.
This is the smallest interesting example of one, and the counters were the second smallest.

Walkthrough

Step 1: Find the gap between present and stored

Open Holding a word. The inputs are showing 1011 and the register is holding 0000.

Neither of those is wrong, and that is the point. The inputs are what is being offered; the outputs are what was accepted. A register is the device that keeps those two things apart.

Press Clock once and they match. Now change any input bit and watch the outputs: nothing moves. Change another. Still nothing.

Whatever is producing that data can change it as often as it likes, and the register goes on presenting the last value it was told to keep, until the next edge. Every clocked system in existence is built out of that one property.

Step 2: Notice what a load enable is not

Set the enable to Disabled and press the clock. Nothing happens, which is what you would expect.

Now look at how nothing happened. The clock still arrived at every flip-flop and every flip-flop was still triggered by it. What changed is where each D came from: with the load disabled, each D is fed from its own Q, so each stage reloads the value it already had.

That looks from outside exactly like doing nothing, and it is not the same thing at all.

Step 3: Move one wire

Open Shifting it along.

Each D has come off its own pin and gone to the Q of the stage before it. Nothing else about the circuit has changed: same flip-flops, same single clock, same everything.

Press Step one clock four times and watch the pattern walk in from the left, one stage per clock. After four clocks a word that arrived one bit at a time is sitting across the four outputs, side by side.

That is the conversion, and it is worth stating plainly: a value spread out in time has become a value spread out in space.

Now read those outputs carefully, because there is a trap in them. The serial input sent 1, 0, 1, 1 in that order, and the outputs read 1101 from Q₀ to Q₃. Those are not the same string, and nothing has gone wrong: the first bit sent has had four clocks to travel and is sitting in the last stage.

Which end you call the first bit is a convention rather than a fact, and it is one that both ends of a serial link have to agree on before anything works at all. Send the least significant bit first and you read the register one way round; send the most significant first and you read it the other.

Keep stepping and the word walks out the far end and is gone.

Step 4: Ask why it does not all rush through at once

This is the question worth stopping on, and most people do not think to ask it.

Every stage is clocked at the same instant. Every stage is watching the output of the stage before it. So when the edge arrives, what stops a 1 at the input travelling the whole length of the register in one go?

The answer is that a flip-flop looks at its D input at the edge, not after it. Every stage captures the value its neighbour was showing just before the edge, not the value it is about to change to. All four hand their contents on simultaneously, and each receives what its neighbour was holding.

That only works because outputs take a little time to change. The data has to stay put for a moment after the edge, which is the hold time, and here it is met by the flip-flop’s own propagation delay.

A shift register is therefore the circuit that hold time exists for. If you have wondered why that number is on a data sheet, this is the answer.

Step 5: Put numbers on the trade

Open Serial and parallel and set the width to 8 bits at 1 MHz.

Parallel: 8 wires, one clock, 1.00 µs.
Serial: 2 wires, eight clocks, 8.00 µs.

Now step the width up to 32 bits. The parallel wire count goes to 32. The serial wire count does not move at all.

That is the property being bought. The serial cost in wires is independent of the width, and the penalty is time, which is usually the resource you have plenty of. Very little in an embedded system needs a value inside a microsecond.

Where the penalty does bite is anything that must be fast and wide at once, which is why the memory bus inside a computer is still parallel and the cable to the printer is not.

The 74HC595 is a serial-in, parallel-out shift register with three control pins and eight outputs. Clock eight bits in, pulse the latch pin, and all eight outputs change together.

A microcontroller with three pins to spare can drive eight LEDs, or a seven-segment display, or eight relays. Chain the serial output of one into the serial input of the next and the same three pins drive sixteen, or eighty.

It contains both circuits from this page. The shift register takes the bits; a separate storage register holds what the pins actually show; and the latch pulse copies one into the other. Without that second register the outputs would display every intermediate pattern as the bits shuffled through, and eight LEDs would flicker through eight wrong values on the way to each right one.

The seven-segment demonstration decoded four bits into seven outputs with gates and needed seven wires to the display. Through a 595 it needs three, and the decoding moves into software. Which side of that trade you want depends on whether pins or clocks are scarcer, and the Arduino demonstration at the end of the module drives this exact part.

Step 6: Choose a sequence

Open Walking a sequence.

The serial input has come off its pin and gone to the last stage’s output. Nothing now enters the register and nothing leaves it. Whatever pattern is inside goes round and round, one place per clock, for as long as the clock runs.

Start it from One bit set and press play. The pattern is 1000, 0100, 0010, 0001, and back to the beginning.

Look at that sequence and try to find the arithmetic in it. There is none. It is not counting up, it is not counting down, and the four states are not four consecutive anythings. Somebody wanted that order and wired the feedback to produce it.

This is the first circuit in the module whose behaviour is a design decision rather than a consequence of arithmetic, and that is why it is here.

Then switch to Johnson and watch what one inverter buys: eight states from the same four flip-flops instead of four, because the pattern fills with ones from the left and then empties from the left.

Step 7: Find the states nobody designed

Still on the last tab, press Two bits set.

The register is now walking 1010, 0101, 1010, 0101, for ever. Two states, not four. No clock edge will ever get it out.

Be precise about what has gone wrong here, because it is easy to get this wrong: the circuit is not broken. No component has failed, nothing is out of specification, and the feedback is doing exactly what it was built to do. It was simply never asked what should happen from this state.

Now look at the panel at the bottom of the tab, which walks all sixteen states and shows every loop the wiring produces.

Loop	States	Is it the design?
`1000 → 0100 → 0010 → 0001`	4	Yes
`1100 → 0110 → 0011 → 1001`	4	No
`1110 → 0111 → 1011 → 1101`	4	No
`1010 → 0101`	2	No
`0000`	1	No
`1111`	1	No

Six separate loops, and no way between them. A four-bit ring counter has sixteen states, of which the design uses four and says nothing whatsoever about the other twelve, and a circuit that has powered up into one of them will stay there until someone cuts the power.

Try All zeros as well. With no bits set there is nothing to circulate, so the counter produces zeros for ever, which is the failure a real ring counter is most likely to suffer.

Switch to Johnson and the picture is different but no better: sixteen states split into two loops of eight. The parasitic loop is the same length as the intended one, so a Johnson counter in the wrong loop looks entirely healthy on a scope. It is simply producing the wrong phases.

Check your understanding

Quiz

Select 0/1

A four-bit storage register is holding 0110. Its data inputs are changed to 1011 and no clock edge occurs. What do the outputs show?

derekmolloy.ie

Quiz

Select 0/1

In a shift register, every stage is clocked at the same instant and every stage is watching the output of the stage before it. What stops a bit travelling the whole length of the register on one edge?

derekmolloy.ie

Quiz

Select 0/1

A four-bit ring counter is switched on and comes up holding 1010. What happens?

derekmolloy.ie

Concept Match

Match each item to what it is

derekmolloy.ie

Quiz

Select 0/4

Which statements about shift registers and ring counters are true? Select all that apply.

derekmolloy.ie

Wrap-up

Five things to take away.

A register is flip-flops with no logic between them. It computes nothing. The clock is not a timekeeper but an instruction, and the instruction is “remember what is on the inputs, now”.
Every circuit here is the same hardware with one wire moved. Where D comes from is the only decision, and it turns the same four flip-flops into a store, a shifter, a delay line or a counter.
A shift register converts between time and wires. Bits arriving one at a time leave as a word, and a word leaves one bit at a time. The serial cost in wires does not depend on the width, and that is what is being bought.
Hold time is why it works. Each stage captures what its neighbour was showing just before the edge, so the contents advance exactly one place per clock instead of racing the length of the register.
Feed the output back and the sequence becomes a choice. A ring counter walks four states because somebody decided it should, and the twelve states it says nothing about are still there.

That last point is the one this demonstration exists for.

Every sequential circuit in the module so far has done something arithmetic. A counter counts because addition says it must; the AND chain in the synchronous counter is the carry chain from binary arithmetic and could not have been anything else. The ring counter is the first circuit whose sequence was specified rather than derived, and the moment a sequence can be specified, two new questions arrive with it: what should the next state be from every state, including the ones you did not plan to visit, and what logic produces that?

Those two questions are the whole of finite state machine design, and you already have the tools for both. A state table says what follows what. Karnaugh maps turn a state table into gates. Flip-flops hold the state and a clock steps between them, exactly as they have done since the latch.

A counter is that construction with the simplest sequence anyone could pick. A ring counter is that construction with a sequence somebody chose. What comes next is that construction with a sequence chosen to do a job, and inputs that change which way it goes, which is what a processor is made of and where this material has been heading since the first latch held its state.