Thread by @TubeTimeUS

i've been thinking about digital counters for state machines lately. probably because of the interesting counter design that i found in the IBM CGA card (schematic below). 🧵

but back to a basic digital counter. it's simple, right? you just count up in binary. 000->001->010->011->etc. but there are some disadvantages of doing it this way.

in digital logic, be it in an FPGA or discrete TTL chips, the basic idea of a design using synchronous logic is that you have flip flops that store your "current state" and then combinational logic that take the current state and generate the "next state".

the combinational logic needs a certain propagation time for a changing signal on the input side to change the signals on the output side. this has to happen *before* the next valid clock edge or the design won't work!

if it's a problem, you can fix it two ways: 1) slow down the clock or 2) use less combinational logic

back to the counter now: a binary synchronous counter has a case where you count from all 1's back to all 0's (i.e. 1111->0000). and this requires a *carry propagation signal* to traverse the entire counter. the more bits in the counter, the slower this gets.

but there are other counter designs! a common one is a one-hot counter. it's basically a shift register. there's a gate at one end that lets you load a single logic 1 at the beginning, and then it just circulates around and around. 100->010->001->100...

the one-hot counter (only one bit is 'hot', get it?) is really fast! it does need a whole flip flop per state, but there's also less decoding logic. oh yeah and you have to add some more gates (not shown) so that 000->001, preventing the '1' from vanishing.

if we make a simple tweak and add an inverter, we have a counter that goes like (000)->001->011->111->110->100->001. this is a Johnson counter and it is a nice compromise solution. you get more states than flip flops, it's fast, but it does require logic to decode the states.

here's the Johnson counter in the IBM CGA card. it's got 8 flip flops and 15 states. you can see the inverter that takes the last bit, inverts it, and feeds it back to the input. other logic decodes various states.

the states are mostly decoded with XOR gates. i went through and manually decoded what each state looks like.

there's a rather famous design that uses a one-hot counter. that is the instruction sequencer in the 6502 microprocessor! in fact, the undocumented HALT instructions stop the CPU by *failing* to load the '1' back into the least significant bit of the one-hot counter.

on the MOnSter 6502 you can see this happen! the counter bits are the vertical column of LEDs here in the box marked "timing logic." execute HALT, and they go dark.

it's not quite an HCF (halt and catch fire) instruction. catching on fire is possible in theory if the internal logic had an invalid state with output drivers trying to drive other output drivers. but the 6502 doesn't have anything like that.

but it does point to another fundamental issue with the one-hot scheme: invalid states! if there's a bit flip, a one-hot counter can't recover -- it will continue to recirculate both bits, becoming a two-hot counter. this is bad.

you could get around it by adding extra logic to reset all the other flip flops to '0' when you detect a '1' in the first bit position. so you'll only have invalid states for a short time.

the Johnson counter has the same problem. the CGA card design doesn't do anything to address it. presumably they assumed that bit flips would be super rare and a simple system reset would fix it, returning the counter to a known state.

it's more of an issue with stuff designed to fly at high altitudes or in space, where the FPGA (or whatever) can be exposed to more high energy particles that can flip bits. so it that case, you want that extra logic to prevent bad states.