Get number of set bits in digital logic

Question

As an exercise, I am trying to design an implementation of Conway's Game of Life in simple digital logic. I could do the whole thing by minimizing a 9-Variable function, but I imagine that will still be fairly large. One of the core elements of the algorithm is determining how many of your 8 neighbors are 'alive'.

Given 8 inputs, what is the easiest way to determine how many are set? Particularly I need an output that is high when 2 are set, and an output that is high when 3 are set.

My main idea now consists of a PISO shift register, a counter, and a 3:8 decoder, but I pretty much need a microcontroller to drive all of that. It does not seem like that complicated of a function. Maybe a 256x2 ROM would work as well, but my searches haven't turned up any of that kind of part.

I know that any pic with 10 IO could do this trivially, but I want to implement it in as minimal a way as reasonably possible.

Answer 1

You might find the various algorithms on Fast Bit Counting enlightening. The last two: Nifty Parallel Count and MIT HAKMEM Count might well be easy to convert into gates. See this page for a good explanation of how it works.

You could do this using gates hardware. Use four 1-bit adders to add pairs of bits together. This gives you four 3-bit numbers. Add these in pairs using two 3-bit adders. This gives you two 4-bit numbers to add using a single 4-bit adder. This leaves you with a 5-bit value, but you can ignore the top bit. Then use two 4-bit comparators to test for the values 2 and 3.

For minimal parts count, why not do it Analog?

Create a voltage divider with one resistor on top, and your 8 inputs connected to the bottom by 8 resistors in parallel. Then simply use two comparators set to detect the voltage levels that 2 or 3 bits will produce. That's only 6 parts:

The 8-resistor network will produce a voltage between 0v (for 0-bits set) to 5v (for 8 bits sets). 2 bits will produce 0.5v. 3 bits will produce 1.56v.

• With 0 or 1 bits, the output will be 00.
• With 2 or 3 bits, the output will be 01.
• With 4 or more bits, the output will be 11.

---

Added:

Thanks to DavidCary for an excellent suggestion. After a lot of calculating, I think I have found a set of resistors that work, but you should carefully check my calculations first. Here I am using comparators with open-drain outputs and I think I have managed to get it to have a single output. Low means dead next round, High means alive next round.

The nice thing is that this circuit only has two more components than the other circuit. They're all E8 series resistors, so should be possible to get hold of. Also, R6 should have been a higher value, like 4.7k or something.

Answer 2

What is minimal? The microcontroller is just 1 part, and can produce the result with a minimum delay (< 1 \$\mu\$s). At 54 cent the ATTiny20 is the cheapest microcontroller with 10 I/O at Digikey.

The lookup table is also just 1 part, and is faster than the microcontroller. Forget about parallel EEPROMs, they're expensive. Use a byte-wide parallel Flash. This one is 512 kByte, that's 2000 times more than what you need, but it's the cheapest solution (1 dollar). And you can add 6 more 1-bit functions for the same price.

You can also use a CPLD. Write the function in VHDL or Verilog as one long SOP (Sum Of Products) statement, and let the synthesizer create the logic.

The shift register is OK if you can wait for the result; this is the slowest solution.

Finally, you can do it with logic gates, but you'll spend a lot of time to reduce the SOP to its minimal form if you want to go all basic. Rocketmagnet has the right idea using adders, but his numbers are off: a 1 bit half adder gives 2 bits out, not 3. So adding the outputs of the half adders two by two requires two 2-bit half adders, giving two 3-bit results. Use a 3-bit half adder to get the 4-bit result. Using 1-bit full adders you'll need only one 2-bit adder.

Answer 3

Hybrid parallel-sequential circuitry is apt to be much more compact than purely-parallel circuitry. For example, if you adjust the rules so that a 3x3 box will turn the cell in the center dead if there are fewer than three live cells or more than four, and turn it live if there are exactly three live cells (the behavior under these new rules will match the original), one can simplify the logic by doing a two-step sequence:

tempVal[x,y] = orig[x-1,y] + orig[x,y] + orig[x+1,y] ' Two-bit sum of three one-bit numbers
orig[x,y] = LiveDeadFunc(orig[x,y], tempval[x,y-1] + tempVal[x,y] + tempVal[x,y+1])

The array tempVal[x,y] has two bits per cell; the latter operation sums together three such numbers to produce a value 0-9 (though all value exceeding four are equivalent), which can then be used to compute a single-bit live/dead status for the next generation.

BTW, an alternative to doing an arithmetic sum in the second stage and examining the value would be to convert tempVal[x,y] into a one-hot representation, and then explicitly check for one of the nine combinations of values that would yield three cells, or one of the twelve that would yield four.