Cree un procesador lógico universal bidireccional con puertas lógicas NAND

8

Un procesador de lógica universal de 2 vías (2ULP) es una red de puertas lógicas que toma dos cables de entrada Ay B, así como otras cuatro entradas L_, L_a, L_b, y L_ab, y produce una única salida L(a, b)usando las cuatro Lentradas como una función de tabla de verdad:

  • El 2ULP devuelve L_si Ay Bson ambos 0.
  • Devuelve L_asi A = 1y B = 0.
  • Devuelve L_bsi A = 0y B = 1.
  • Devuelve L_absi Ay Bson ambos 1.

Por ejemplo, dadas las entradas L_ = 0, L_a = 1, L_b = 1, y L_ab = 0, a continuación, la salida L(a, b)será igual a A xor B.

Su tarea es construir un 2ULP usando solo puertas NAND, usando la menor cantidad posible de puertas NAND. Para simplificar las cosas, puede usar las compuertas AND, OR, NOT y XOR en su diagrama, con los siguientes puntajes correspondientes:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Cada uno de estos puntajes corresponde al número de puertas NAND que se necesitan para construir la puerta correspondiente.

El circuito lógico que utiliza la menor cantidad de compuertas NAND para producir una construcción correcta gana.

atomic-code-golf logic-gates Joe Z.
fuente
1
Mis habilidades de diseño de lógica digital son tan oxidadas que es ridículo, pero disfruto mucho los resultados finales de estas competiciones. +1
ProgramadorDan
Con puertas NAND de dos entradas, no hay mucho espacio para la creatividad en este diseño. Quizás, en lugar de requerir que el dispositivo tome seis entradas, diseñar un bloque con un número arbitrario de entradas y una salida, y requerir que dadas dos entradas A y B y una opción de una de las dieciséis funciones, debe ser posible conecte las entradas del bloque a alguna combinación de A, B, Alta y Baja, de modo que la salida produzca esa función. Tal dispositivo sería un procesador lógico universal de 2 vías (solo agregue cables), pero probablemente podría hacerse en mucho menos de 11 puertas.
supercat
1
Deberíamos inventar gate-golf , donde escribes en la menor cantidad de puertas.
TheDoctor
Para eso está el código atómico-golf + puertas lógicas .
Joe Z.

Respuestas:

10

11 NANDs

Defina la puerta MUX (costo 4) como

MUX(P, Q, R) = (P NAND Q) NAND (NOT P NAND R)

con tabla de verdad

P Q R    (P NAND Q)   (NOT P NAND R)    MUX
0 0 0        1               1           0
0 0 1        1               0           1
0 1 0        1               1           0
0 1 1        1               0           1
1 0 0        1               1           0
1 0 1        1               1           0
1 1 0        0               1           1
1 1 1        0               1           1

Entonces este es el operador ternario familiar MUX(P, Q, R) = P ? Q : R

Simplemente tenemos

2ULP = MUX(A, MUX(B, L_ab, L_a), MUX(B, L_b, L_))

por un costo de 12, pero hay un ahorro trivial de una puerta al reutilizar el NOT Bde los dos interiores MUX.

Peter Taylor
fuente
3
Me acabas de dar una idea de algo para probar con Redstone en Minecraft, gracias
David Wilkins
1
El mínimo absoluto es de 11 NAND. Lo busqué a fondo. Y el circuito más rápido que encontré tiene una profundidad de 5 puertas. Entonces este rompecabezas es resuelto por Peter Taylor.
KimOyhus
3

costo: 4 * 4 * 14 + 4 * (13) + 13 * 3 + 3 * 3 + 24 * 1 + 4 = 352

No soy un hombre booleano, este es mi mejor en la codificación de estas cosas (sé que esto no me dará muchos puntos de Internet inimaginables ...).

# l1 is for a=F , b=F
# l2 is for a=F , b=T
# l3 is for a=T , b=F
# l4 is for a=T , b=T

2ULP(l1,l2,l3,l4,a,b) =
 (l1&l2&l3&l4)|             # always true
 (!l1&l2&l3&l4)&(a|b)|      # a=F,b=F->F; ee in T
 (l1&!l2&l3&l4)&(!a&b)|     # a=F,b=T->F; ee in T
 (!l1&!l2&l3&l4)&(a)|       # a=F,b=F->F; a=F,b=T->F; a=T,b=F->T; a=T,b=T->T; 
 (l1&l2&!l3&l4)&(a&!b)|     # a=T,b=F->F, ee in T
 (!l1&l2&!l3&l4)&(b)|       # a=T,b=F->F, ee in T
 (!l1&!l2&!l3&l4)&(a&b)|    # a=T,b=T->T, ee in F
 (l1&l2&l3&!l4)&(!(a|b))|   # a=T,b=T->F, ee in T
 (!l1&l2&l3&!l4)&(!(avb))|  # a=T,b=F->T, a=F,b=T->T, ee in T , note v is the exor.
 (l1&!l2&l3&!l4)&(!b)|      # T when b=T
 (!l1&!l2&l3&!l4)&(a&!b)|   # T when a=T,b=F
 (l1&l2&!l3&!l4)&(!a)|      # T when a=F
 (!l1&l2&!l3&!l4)&(!a&b)|   # T when a=F,B=T
 (l1&!l2&!l3&!l4)&(!(a|b))  # T when a=F,B=F
Antonio Ragagnin
fuente
Si sigue el sistema descrito por los puntos en la pregunta, obtendrá un costo de 29, por lo que esto es impresionantemente malo.
Peter Taylor
Lo siento, Sr. Taylor, solo espero que esto no haya arruinado sus ojos.
Antonio Ragagnin
3

Al usar el lenguaje Wolfram puedo obtener una fórmula de 13 puertas :

logicfunc = Function[{a, b, Ln, La, Lb, Lab},
                   {a, b, Ln, La, Lb, Lab} -> Switch[{a, b},
                          {0, 0}, Ln, {1, 0}, La, {0, 1}, Lb, {1, 1}, Lab]
                  ];
trueRuleTable = Flatten[Outer[logicfunc, ##]] & @@ ConstantArray[{0, 1}, 6] /. {0 -> False, 1 -> True};
BooleanFunction[trueRuleTable, {a, b, Ln, La, Lb, Lab}] // BooleanMinimize[#, "NAND"] &

que salidas:

Fórmula NAND

Aquí Ln, La, Lby Labson el L_, L_a, L_by L_abpor separado en OP.

nota al margen: Los resultados de la BooleanMinimizefunción en el lenguaje Wolfram se limitan a dos niveles NANDy NOTcuando se invoca como BooleanMinimize[(*blabla*), "NAND"], por lo que no es tan bueno como la fórmula de cuatro niveles de Peter Taylor anterior .

Silvia
fuente