Un circuito booleano en TCS es básicamente un DAG que consiste en compuertas And, Or, Not, y por lo que se conoce como "integridad funcional", pueden calcular todas las funciones posibles. Por ejemplo, este es el principio básico en una ALU .
Desafío: cree un circuito para determinar si un número de 8 dígitos binarios es divisible por 3 y de alguna manera visualice su resultado (es decir, en algún tipo de imagen)
El criterio de evaluación para los votantes se basa en si el código para generar el circuito se generaliza bien a números de tamaño arbitrario, y si la visualización creada algorítmicamente es compacta / equilibrada pero aún legible por humanos (es decir, no se permite la visualización a mano). es decir, la visualización es solo para n = 8, pero el código idealmente funcionará para todos 'n'. la entrada ganadora es la mejor votada.
Pregunta algo similar: construir una máquina multiplicadora usando puertas lógicas NAND
gate-golf
? esa etiqueta es inexistente. Nota para los participantes: indique qué idioma / herramienta de visualización está utilizando. si alguien más quiere ingresar un comentario por favor. de lo contrario aceptará ganador tonite. Gracias a los encuestados hasta ahora, ¡esto fue "BTE" mejor de lo esperado!Respuestas:
El gráfico mantiene 3 booleanos en cada nivel i. Representan el hecho de que los bits de orden superior i del número son iguales a 0, 1 o 2 mod 3. En cada nivel calculamos los siguientes tres bits en función de los tres bits anteriores y el siguiente bit de entrada.
Aquí está el código de Python que generó el gráfico. Simplemente cambie N para obtener un número diferente de bits, o K para obtener un módulo diferente. Ejecute la salida del programa python a través de punto para generar la imagen.
fuente
Profundidad: 7 (logarítmica), 18x AND, 6x OR, 7x XOR, 31 puertas (lineal)
Permítanme calcular la suma de dígitos en la base cuatro, módulo tres:
circuito dibujado en Logisim
Generalización, formalmente (con suerte algo legible):
ahora en ingles:
Si bien hay más de dos bits en el número, tome los dos pares de bits más bajos y sume el módulo 3, luego agregue el resultado al final del número, luego regrese si el último par es cero módulo 3. Si hay un número impar número de bits en el número, agregue un bit cero adicional en la parte superior, luego pula con propagación de valor constante.
Agregar al reverso en lugar de al frente asegura que el árbol de adición sea un árbol equilibrado en lugar de una lista vinculada. Esto, a su vez, asegura una profundidad logarítmica en el número de bits: cinco puertas y tres niveles para la cancelación de pares, y una puerta adicional al final.
Por supuesto, si se desea una planaridad aproximada, pase el par superior sin modificar a la siguiente capa en lugar de envolverlo al frente. Sin embargo, esto es más fácil decirlo que implementarlo (incluso en pseudocódigo). Si el número de bits en un número es una potencia de dos (como es cierto en cualquier sistema informático moderno a partir de marzo de 2014), sin embargo, no se producirán pares solitarios.
Si el diagrama conserva la localidad / realiza la minimización de la longitud de la ruta, debe mantener el circuito legible.
Este código Ruby generará un diagrama de circuito para cualquier número de bits (incluso uno). Para imprimir, abra en Logisim y exporte como imagen:
finalmente, cuando se me pide que cree una salida para 32 bits, mi layouter genera esto. Es cierto que no es muy compacto para entradas muy anchas:
fuente
2 × 24 NOT, 2 × 10 + 5 AND, 2 × 2 + 5 OR, 2 × 2 NOR
Esto no se escala totalmente. No me gusta en absoluto. Quizás intente mejorarlo.
Probé esto para números hasta el 30 y funcionó bien.
Esos 2 grandes circuitos cuentan el número de entradas activas:
Si la diferencia de esos números es
0
o3
el número es divisible por3
. El circuito inferior derecha básicamente mapea cada combinación válida (4,4
,4,1
,3,3
,3,0
,2, 2
,1, 1
,0, 0
) en una o.El pequeño círculo en el medio es un LED que está encendido si el número es divisible por 3 y apagado de lo contrario.
fuente