# Get number of set bits in digital logic

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.

-

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.

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.

-
+1 just because your answer is not "Use a microcontroller". That seems to be the default mode around here. –  Connor Wolf Jun 25 '12 at 11:23
@FakeName: The first reference is to software solutions. Of course you don't have to implement them on a microcontroller, you can also use a supercomputer :) –  Federico Russo Jun 25 '12 at 12:34
@FedericoRusso - I gave those references to software solutions which give some insight as to how he might implement it in hardware. –  Rocketmagnet Jun 25 '12 at 13:15
I love the idea of doing it in analog. My only issue is that I need to be able to differentiate between 2 and 3 bits set. –  CMP Jun 25 '12 at 13:40
Perhaps: Add a 9th "summing resistor" of 20 kOhm from the current state of the central cell to the op-amp "+" summing point in Rocketmagnet's circuit -- i.e., give the central cell a weight of 1 and the 8 neighboring cells a weight of 2. Then tweak the voltage divider so "birth" (central dead cell with 3 live neighbors; sum = 6) and "stay alive" (central dead cell alive with 2 or 3 live neighbors, sum = 5 or 7) gives outputs of "01"; and all other cases (where the central cell dies or stays dead) give outputs of "00" or "11". Then an XOR gate gives the next state of the central cell. –  davidcary Jun 25 '12 at 14:24

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.

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

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.