Obtenga el número de bits establecidos en lógica digital

Como ejercicio, estoy tratando de diseñar una implementación del Juego de la vida de Conway en lógica digital simple. Podría hacer todo esto minimizando una función de 9 variables, pero imagino que seguirá siendo bastante grande. Uno de los elementos centrales del algoritmo es determinar cuántos de sus 8 vecinos están 'vivos'.

Dadas 8 entradas, ¿cuál es la forma más fácil de determinar cuántas se configuran? Particularmente necesito una salida que sea alta cuando se establecen 2, y una salida que sea alta cuando se establecen 3.

Mi idea principal ahora consiste en un registro de desplazamiento PISO, un contador y un decodificador 3: 8, pero prácticamente necesito un microcontrolador para manejar todo eso. No parece tan complicado de una función. Tal vez una ROM de 256x2 también funcionaría, pero mis búsquedas no han aparecido en ese tipo de partes.

Sé que cualquier foto con 10 IO podría hacer esto trivialmente, pero quiero implementarlo de la manera más mínima posible.

Puede encontrar los diversos algoritmos en la iluminación de conteo rápido de bits . Los dos últimos: Nifty Parallel Count y MIT HAKMEM Count podrían ser fáciles de convertir en puertas. Consulte esta página para obtener una buena explicación de cómo funciona.

Podrías hacer esto usando puertas de hardware. Use cuatro sumadores de 1 bit para agregar pares de bits. Esto te da cuatro números de 3 bits. Agregue estos en pares usando dos sumadores de 3 bits. Esto le da dos números de 4 bits para agregar usando un solo sumador de 4 bits. Esto te deja con un valor de 5 bits, pero puedes ignorar el bit superior. Luego use dos comparadores de 4 bits para probar los valores 2 y 3.

Para un recuento mínimo de piezas, ¿por qué no hacerlo analógico?

Cree un divisor de voltaje con una resistencia en la parte superior y sus 8 entradas conectadas a la parte inferior por 8 resistencias en paralelo. Luego, simplemente use dos comparadores configurados para detectar los niveles de voltaje que producirán 2 o 3 bits. Eso es solo 6 partes:

La red de 8 resistencias producirá un voltaje entre 0v (para conjuntos de 0 bits) a 5v (para conjuntos de 8 bits). 2 bits producirán 0.5v. 3 bits producirán 1.56v.

• Con 0 o 1 bits, la salida será 00.
• Con 2 o 3 bits, la salida será 01.
• Con 4 o más bits, la salida será 11.

Adicional:

Gracias a DavidCary por una excelente sugerencia. Después de muchos cálculos, creo que he encontrado un conjunto de resistencias que funcionan, pero primero debes verificar cuidadosamente mis cálculos. Aquí estoy usando comparadores con salidas de drenaje abierto y creo que he logrado que tenga una sola salida. Bajo significa muerto la próxima ronda, Alto significa vivo la próxima ronda.

Lo bueno es que este circuito solo tiene dos componentes más que el otro circuito. Todas son resistencias de la serie E8, por lo que debería ser posible obtenerlas. Además, R6 debería haber sido un valor más alto, como 4.7k o algo así.

$\mu$

La tabla de búsqueda también tiene solo 1 parte y es más rápida que el microcontrolador. Olvídate de las EEPROM paralelas, son caras. Use un Flash paralelo de bytes . Este es de 512 kByte, eso es 2000 veces más de lo que necesita, pero es la solución más barata (1 dólar). Y puede agregar 6 funciones más de 1 bit por el mismo precio.

También puede usar un CPLD . Escriba la función en VHDL o Verilog como una declaración larga de SOP (Suma de productos) y deje que el sintetizador cree la lógica.

El registro de desplazamiento está bien si puede esperar el resultado; Esta es la solución más lenta.

Finalmente, puede hacerlo con puertas lógicas , pero pasará mucho tiempo para reducir el SOP a su forma mínima si desea que todo sea básico. Rocketmagnet tiene la idea correcta de usar sumadores, pero sus números están apagados: un medio sumador de 1 bit da 2 bits, no 3. Por lo tanto, agregar las salidas de los medios sumadores de dos en dos requiere dos medios sumadores de 2 bits, dando dos 3- Resultados poco. Use un medio sumador de 3 bits para obtener el resultado de 4 bits. Usando sumadores completos de 1 bit solo necesitará un sumador de 2 bits.

La circuitería secuencial paralela híbrida puede ser mucho más compacta que la circuitería puramente paralela. Por ejemplo, si ajusta las reglas para que un cuadro de 3x3 convierta la celda en el centro muerta si hay menos de tres celdas vivas o más de cuatro, y la activa si hay exactamente tres celdas vivas (el comportamiento bajo estas las nuevas reglas coincidirán con el original), se puede simplificar la lógica haciendo una secuencia de dos pasos:

tempVal [x, y] = orig [x-1, y] + orig [x, y] + orig [x + 1, y] 'Suma de dos bits de tres números de un bit
orig [x, y] = LiveDeadFunc (orig [x, y], tempval [x, y-1] + tempVal [x, y] + tempVal [x, y + 1])

La matriz tempVal[x,y]tiene dos bits por celda; la última operación suma tres de estos números para producir un valor de 0-9 (aunque todos los valores superiores a cuatro son equivalentes), que luego se pueden usar para calcular un estado vivo / muerto de un solo bit para la próxima generación.

Por cierto, una alternativa a hacer una suma aritmética en la segunda etapa y examinar el valor sería convertir tempVal [x, y] en una representación única, y luego verificar explícitamente una de las nueve combinaciones de valores que producirían tres células, o una de las doce que produciría cuatro.