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 256×2 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.
Best Answer
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.
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.