Conduzca una pantalla hexadecimal de 7 segmentos utilizando puertas lógicas NAND

9

La ubicua pantalla numérica de 7 segmentos puede mostrar inequívocamente los 16 dígitos hexadecimales como se muestra en esta wikipedia .gif

Las entradas para este desafío crearán un diagrama de circuito utilizando puertas lógicas NAND que transforman los cuatro bits de un dígito hexadecimal en las entradas para los siete segmentos. Las entradas para la pantalla de 7 segmentos generalmente se etiquetan de la siguiente manera: (DP (punto decimal) se ignora para este desafío)

ingrese la descripción de la imagen aquí

Por lo tanto, su circuito deberá ajustarse a la siguiente tabla de verdad:

Hex   | Hex Input Bit | Output to Segment line:
digit |  3  2  1  0   |  A  B  C  D  E  F  G
------+---------------+-----------------------
   0  |  0  0  0  0   |  1  1  1  1  1  1  0
   1  |  0  0  0  1   |  0  1  1  0  0  0  0
   2  |  0  0  1  0   |  1  1  0  1  1  0  1
   3  |  0  0  1  1   |  1  1  1  1  0  0  1
   4  |  0  1  0  0   |  0  1  1  0  0  1  1
   5  |  0  1  0  1   |  1  0  1  1  0  1  1
   6  |  0  1  1  0   |  1  0  1  1  1  1  1
   7  |  0  1  1  1   |  1  1  1  0  0  0  0
   8  |  1  0  0  0   |  1  1  1  1  1  1  1
   9  |  1  0  0  1   |  1  1  1  1  0  1  1
   A  |  1  0  1  0   |  1  1  1  0  1  1  1
   b  |  1  0  1  1   |  0  0  1  1  1  1  1
   C  |  1  1  0  0   |  1  0  0  1  1  1  0
   d  |  1  1  0  1   |  0  1  1  1  1  0  1
   E  |  1  1  1  0   |  1  0  0  1  1  1  1
   F  |  1  1  1  1   |  1  0  0  0  1  1  1

Creo que esta tabla es precisa, pero avíseme si detecta algún error.

Su puntaje está determinado por la cantidad de compuertas NAND de 2 entradas que utiliza (1 punto por compuerta). 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
atomic-code-golf logic-gates Trauma digital
fuente
Este desafío parece tratarse de dibujar un diagrama de circuito y no de codificar. Además, los valores de puntos por puerta parecen arbitrarios (tal vez intencionalmente), y el uso de AND + NOT es de 3 puntos, cuando
declara
@stokastic Hay muchos otros desafíos de puertas lógicas en este sitio, por lo que supongo que esta categoría de desafío es aceptable para la comunidad. Muchos usan el mismo sistema de puntuación. La lógica NAND creo que explica bastante bien este sistema de puntuación.
Trauma digital
Lo suficientemente justo. No había visto esas etiquetas antes. Simplemente no parece encajar realmente en 'rompecabezas de programación' o 'golf de código'.
estokástico
¿Se puede dividir el circuito? En otras palabras, ¿puede guardar valores en variables y recuperarlos más tarde?
xnor
@xnor ¿Estás hablando de este tipo de cosas: codegolf.stackexchange.com/a/26235/11259 ? Si es así, la respuesta es sí.
Trauma digital

Respuestas:

17

Dominó - Puntaje total: 243 NANDs

  • OR utilizados: 61 (3 NAND cada uno -> 183 NAND)

  • NO utilizados: 60 (1 NAND cada uno -> 60 NAND)

Esta solución está en fichas de dominó y requería una colección de piezas de software que escribí al responder las dos preguntas relacionadas con Domino de Martin Büttner para producir ( Golfing for Domino Day y Domino Circuits ).

Al modificar mi solucionador Domino Circuit , pude producir un circuito domino (este archivo también contiene la salida del solucionador y el esqueleto del circuito) que consta de OR e IFNOT donde la primera entrada siempre es VERDADERA (por lo que es esencialmente un NO). Debido a que no hay mucho que va a encajar en esta respuesta, presento las soluciones OR y NOT a la tabla de verdad:

A: 1011011111101011
((-1 ifnot (2 or (1 or (-1 ifnot 0)))) or ((-1 ifnot ((-1 ifnot 1) or (-1 ifnot 2))) or ((-1 ifnot (3 or (-1 ifnot (0 or (-1 ifnot 1))))) or (-1 ifnot (0 or ((-1 ifnot 3) or (-1 ifnot (2 or 1))))))))
B: 1111100111100100
((-1 ifnot (3 or 1)) or ((-1 ifnot (3 or (2 or 0))) or (-1 ifnot ((-1 ifnot 3) or ((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot 2))))))))
C: 1101111111110100
((-1 ifnot (2 or (-1 ifnot 3))) or ((-1 ifnot (1 or (-1 ifnot 0))) or (-1 ifnot (0 or (-1 ifnot (3 or (1 or (-1 ifnot 2))))))))
D: 1011011011011110
((-1 ifnot (3 or (1 or 0))) or ((-1 ifnot (2 or ((-1 ifnot (3 or 0)) or (-1 ifnot (1 or 0))))) or (-1 ifnot ((-1 ifnot 2) or ((-1 ifnot (3 or 1)) or (-1 ifnot ((-1 ifnot 1) or (-1 ifnot 3))))))))
E: 1010001010111111
((-1 ifnot (3 or (-1 ifnot (2 or (-1 ifnot 1))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or 1)))))
F: 1000111011111011
((-1 ifnot (3 or (-1 ifnot 1))) or ((-1 ifnot (2 or (0 or (-1 ifnot (1 or (-1 ifnot 3)))))) or (-1 ifnot ((-1 ifnot 0) or (-1 ifnot (2 or (-1 ifnot 1)))))))
G: 0011111011110111
((-1 ifnot (2 or (0 or (-1 ifnot 1)))) or ((-1 ifnot (1 or (-1 ifnot (2 or 0)))) or (-1 ifnot ((-1 ifnot (3 or 2)) or (-1 ifnot (0 or (-1 ifnot 3)))))))

Tenga en cuenta que las únicas operaciones binarias utilizadas son OR e IFNOT, donde cuento cada IFNOT como NOT para fines de puntuación

Agregué una pantalla de 7 segmentos al final del circuito y la introduje en un simulador de dominó / generador de gif. El gif resultante (que muestra la visualización de 'A') tardó aproximadamente 2 horas en generarse. Como el circuito final tiene un tamaño de 1141 * 517, cada "celda" está representada por un solo píxel. Una celda negra está vacía, una celda gris tiene un dominó de pie y una celda blanca tiene un dominó caído. Esto significa que realmente no se puede saber lo que está sucediendo, y no ayudará si se está aplastando en absoluto. Sparr amablemente proporcionó una versión mucho más pequeña de mi gif original (650kB), ¡así que aquí está!

Animación

A continuación se muestra el último cuadro de la animación para la entrada 1010 ('A') como arriba. Puede ver las entradas en el extremo izquierdo, la línea eléctrica en la parte superior, la centralita ocupando la mayor parte del espacio, las 7 piezas lógicas individuales (estas son representaciones de dominó de las funciones anteriores) a la izquierda de la centralita y el extremo derecho es la pantalla de 7 segmentos en sí. Cuando esto se ejecuta, los segmentos individuales se iluminan aproximadamente al mismo tiempo, por lo que no se puede mirar durante demasiado tiempo con algunos segmentos iluminados esperando que otros se iluminen.

Último cuadro de animación

Vea la animación en toda su gloria aquí (36MB) o aquí (650kB, cortesía de Sparr) (la copia más pequeña es mucho más pequeña, pero a mi navegador le gustaba saltar cuadros que estropeaban la belleza, así que dejé el original así)

El detalle de la pantalla de 7 segmentos se puede ver aquí (se muestra '1')

VisualMelon
fuente
3
¡+1 por la pura surrealidad de conducir una pantalla de 7 segmentos con dominó!
Trauma digital
Eso es increíble ... Alguien debería probar esto en la vida real
Beta Decay
11

30 NANDs

Estoy bastante seguro de que no hay soluciones más simples para este problema, excepto quizás cambiando los símbolos en la pantalla, pero ese sería otro problema diferente.

Dado que esto es realmente algo útil que hacer, por ejemplo, al programar un FPGA para mostrar la salida, proporciono el código Verilog.

En cuanto al minimalismo: por supuesto, fue difícil de hacer. No es comprensible, ya que una pantalla de 7 segmentos es solo una forma bastante aleatoria de que los humanos muestren números, lo que resulta en un circuito que también es bastante aleatorio. Y como es típico en estos circuitos mínimos, su profundidad lógica es algo mayor que para soluciones cercanas. Supongo que esto se debe a que el serial es más simple que el paralelo.

El retraso de la transmisión se indica mediante la posición hacia abajo de cada compuerta NAND en la hoja.

Controlador de pantalla hexadecimal mínimo de 7 segmentos

Código Verilog:

// Hexadecimal 7-segment display driver
// Minimal at 30 NANDs
//
// By Kim Øyhus 2018 (c) into (CC BY-SA 3.0)
// This work is licensed under the Creative Commons Attribution 3.0
// Unported License. To view a copy of this license, visit
// https://creativecommons.org/licenses/by-sa/3.0/
//
// This is my entry to win this Programming Puzzle & Code Golf
// at Stack Exchange: 
// /codegolf/37648/drive-a-hexadecimal-7-segment-display-using-nand-logic-gates
//
// I am quite sure there are no simpler solutions to this problem,
// except perhaps by changing the symbols on the display,
// but that would be another and different problem.
//
// Since this is actually something useful to do, for instance when
// programming an FPGA to show output, I provide this Verilog code.
//
// As for the minimalism: Of course it was tricky to make.
// It is not comprehensible, since a 7-segment display is
// just a fairly random way of showing numbers, resulting
// in a circuit that is fairly random too.
// And as is typical for these minimal circuits, its logical depth
// is somewhat higher than for close solutions. I guess this is because
// serial is simpler than parallel.
//
// 4 bits of input "in_00?", and 7 bits of output,
// one bit per LED in the segment.
//   A
// F   B
//   G
// E   C
//   D

module display7 ( in_000, in_001, in_002, in_003,  G, F, E, D, C, B, A );
  input in_000, in_001, in_002, in_003;
  output G, F, E, D, C, B, A;
  wire wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017, wir018, wir019, wir020, wir021, wir022 ;

  nand gate000 ( wir000, in_000, in_002 );
  nand gate001 ( wir001, in_000, in_000 );
  nand gate002 ( wir002, wir000, in_001 );
  nand gate003 ( wir003, in_001, wir002 );
  nand gate004 ( wir004, wir000, wir002 );
  nand gate005 ( wir005, in_002, wir003 );
  nand gate006 ( wir006, in_003, wir001 );
  nand gate007 ( wir007, wir006, wir004 );
  nand gate008 ( wir008, in_003, wir005 );
  nand gate009 ( wir009, wir005, wir008 );
  nand gate010 ( wir010, in_003, wir008 );
  nand gate011 ( wir011, wir010, wir009 );
  nand gate012 ( wir012, wir010, wir007 );
  nand gate013 ( wir013, wir001, wir011 );
  nand gate014 ( wir014, wir003, wir004 );
  nand gate015 (      G, wir011, wir014 );
  nand gate016 ( wir015, in_003, wir014 );
  nand gate017 ( wir016, wir015, wir013 );
  nand gate018 (      C, wir016, wir012 );
  nand gate019 ( wir017, wir016, wir007 );
  nand gate020 ( wir018, wir003, wir012 );
  nand gate021 ( wir019, wir017, in_003 );
  nand gate022 (      F, wir011, wir017 );
  nand gate023 (      D, wir018, wir017 );
  nand gate024 (      B, wir012,      F );
  nand gate025 ( wir020, wir004, wir018 );
  nand gate026 ( wir021, wir001,      D );
  nand gate027 (      E, wir019, wir021 );
  nand gate028 ( wir022,      D, wir019 );
  nand gate029 (      A, wir020, wir022 );
endmodule

Kim Øyhus

KimOyhus
fuente
¡Esta es una solución realmente impresionante! ¿Por qué estás tan seguro de que no se puede hacer mejor que 30? 37 ya parecía "bastante reducido", en mi opinión.
Alex Meiburg
Gracias. Busqué más allá de esta solución, usando mucho más tiempo para eso que para encontrar la solución en sí, y no había nada allí. La probabilidad de que me haya perdido algo mejor es muy pequeña. Es un argumento estadístico.
KimOyhus
7

Usando ~ para NOT y N para NAND, una búsqueda por computadora (sin compartir términos entre salidas) encuentra una solución con 82 NAND sin compartir. La búsqueda manual de términos de uso compartido lo reduce a 54 NAND, y una búsqueda por computadora que incluye el uso compartido lo reduce aún más a 37 NAND. El mínimo podría ser incluso más bajo, ya que el método ciertamente no es exhaustivo.

Aquí está el programa que recrea la tabla anterior. Cada línea está etiquetada con las NANDS para esa salida.

#include <stdio.h>

int N(int x, int y) { return 1 & ~(x & y); }

void main(void)
{
    int i0, i1, i2, i3;
    for (i3 = 0; i3 <= 1; i3++) {
    for (i2 = 0; i2 <= 1; i2++) {
    for (i1 = 0; i1 <= 1; i1++) {
    for (i0 = 0; i0 <= 1; i0++) {
            printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
    /* 14 */        N(N(N(i3, N(i2, i1)), N(N(i2, i0), ~i1)), N(N(i2, N(i3, N(i3, i0))), N(i0, N(i3, N(i3, i1))))),
    /* 12 */        N(N(N(i3, i0), N(i2, N(i1, i0))), N(~i1, N(N(i3, i0), N(~i3, N(i2, i0))))),
    /* 10 */        N(N(i0, N(i3, i1)), N(N(i3, i2), N(i1, N(i1, N(~i3, ~i2))))),
    /* 16 */        N(N(N(i2, i1), N(N(i3, i0), N(i2, i0))), N(N(i0, N(i1, ~i2)), N(N(i3, i2), N(N(i3, i1), N(i2, N(i2, i1)))))),
    /*  7 */        N(N(i3, i2), N(N(i2, N(i2, i1)), N(i0, N(i3, i1)))),
    /* 11 */        N(N(i3, N(i2, N(i3, i1))), N(N(i1, N(i2, N(i2, i0))), N(i0, N(i2, ~i3)))),
    /* 12 */        N(N(i3, i0), ~N(N(i1, N(i2, i0)), N(N(i3, i2), N(~i3, N(i2, N(i2, i1)))))) );
    } } } }
}

Y aquí está el resultado:

0 0 0 0 : 1 1 1 1 1 1 0
0 0 0 1 : 0 1 1 0 0 0 0
0 0 1 0 : 1 1 0 1 1 0 1
0 0 1 1 : 1 1 1 1 0 0 1
0 1 0 0 : 0 1 1 0 0 1 1
0 1 0 1 : 1 0 1 1 0 1 1
0 1 1 0 : 1 0 1 1 1 1 1
0 1 1 1 : 1 1 1 0 0 0 0
1 0 0 0 : 1 1 1 1 1 1 1
1 0 0 1 : 1 1 1 1 0 1 1
1 0 1 0 : 1 1 1 0 1 1 1
1 0 1 1 : 0 0 1 1 1 1 1
1 1 0 0 : 1 0 0 1 1 1 0
1 1 0 1 : 0 1 1 1 1 0 1
1 1 1 0 : 1 0 0 1 1 1 1
1 1 1 1 : 1 0 0 0 1 1 1

Y aquí están las ecuaciones equivalentes, compartiendo términos que lo reducen a 54 NAND:

    /* 1 */ int z1 = 1 - i1;
    /* 1 */ int z2 = 1 - i2;
    /* 1 */ int z3 = 1 - i3;

    /* 1 */ int n_i2_i0 = N(i2, i0);
    /* 1 */ int n_i2_i1 = N(i2, i1);
    /* 1 */ int n_i3_i0 = N(i3, i0);
    /* 1 */ int n_i3_i1 = N(i3, i1);
    /* 1 */ int n_i3_i2 = N(i3, i2);

    /* 1 */ int n_i0_n_i3_i1 = N(i0, n_i3_i1);
    /* 1 */ int n_i2_n_i2_i1 = N(i2, n_i2_i1);

            printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
    /* 9 */ N(N(N(i3, n_i2_i1), N(n_i2_i0, z1)), N(N(i2, N(i3, n_i3_i0)), N(i0, N(i3, n_i3_i1)))),
    /* 7 */ N(N(n_i3_i0, N(i2, N(i1, i0))), N(z1, N(n_i3_i0, N(z3, n_i2_i0)))),
    /* 5 */ N(n_i0_n_i3_i1, N(n_i3_i2, N(i1, N(i1, N(z3, z2))))),
    /* 8 */ N(N(n_i2_i1, N(n_i3_i0, n_i2_i0)), N(N(i0, N(i1, z2)), N(n_i3_i2, N(n_i3_i1, n_i2_n_i2_i1)))),
    /* 2 */ N(n_i3_i2, N(n_i2_n_i2_i1, n_i0_n_i3_i1)),
    /* 8 */ N(N(i3, N(i2, n_i3_i1)), N(N(i1, N(i2, n_i2_i0)), N(i0, N(i2, z3)))),
    /* 6 */ N(n_i3_i0, ~N(N(i1, n_i2_i0), N(n_i3_i2, N(z3, n_i2_n_i2_i1)))) );

Y aquí está la solución 37 NAND:

    x0fff =  N(i3, i2);
    x33ff =  N(i3, i1);
    x55ff =  N(i3, i0);
    x0f0f =  not(i2);
    x3f3f =  N(i2, i1);
    x5f5f =  N(i2, i0);
    xcfcf =  N(i2, x3f3f);
    xf3f3 =  N(i1, x0f0f);
    x5d5d =  N(i0, xf3f3);
    xaaa0 =  N(x55ff, x5f5f);
    xfc30 =  N(x33ff, xcfcf);
    xd5df =  N(x3f3f, xaaa0);
    xf3cf =  N(x0fff, xfc30);
    xaeb2 =  N(x5d5d, xf3cf);
    x7b6d =  N(xd5df, xaeb2);
    xb7b3 =  N(i1, x7b6d);
    xf55f =  N(x0fff, xaaa0);
    xcea0 =  N(x33ff, xf55f);
    x795f =  N(xb7b3, xcea0);
    xd7ed =  N(xaeb2, x795f);
    xfaf0 =  N(x55ff, x0f0f);
    xae92 =  N(x55ff, x7b6d);
    xdd6d =  N(x33ff, xae92);
    x279f =  N(xfaf0, xdd6d);
    xaf0f =  N(i2, x55ff);
    x50ff =  N(i3, xaf0f);
    xef4c =  N(xb7b3, x50ff);
    x1cb3 =  N(xf3cf, xef4c);
    xef7c =  N(xf3cf, x1cb3);
    xfb73 =  N(i1, x279f);
    x2c9e =  N(xd7ed, xfb73);
    xdf71 =  N(xf3cf, x2c9e);
    xdd55 =  N(i0, x33ff);
    xf08e =  N(x0fff, xdf71);
    x2ffb =  N(xdd55, xf08e);
    x32ba =  N(xcfcf, xdd55);
    xfd45 =  N(x0fff, x32ba);

    printf("%d %d %d %d : %d %d %d %d %d %d %d\n", i3, i2, i1, i0,
            xd7ed, x279f, x2ffb, x7b6d, xfd45, xdf71, xef7c);
    } } } }
AoneOne
fuente
2
Deberías tener un encabezado orgulloso con "37 NANDs". Tu publicación es demasiado modesta sin eso.
KimOyhus
4

197 NANDs

Dado que este es mi primer desafío de puertas lógicas. no se juega mucho al golf y puede que no sea la solución más pequeña. No estoy usando circuito dividido aquí.

A = OR(AND(d, NOT(AND(a, XOR(c, b)))), AND(NOT(d), NOT(AND(NOT(b), XOR(a, c)))))
B = AND(OR(OR(NOT(c), AND(NOT(d), NOT(XOR(b, a)))), AND(d, a)), NOT(AND(AND(d, b), a)))
C = OR(AND(NOT(c), NOT(AND(AND(NOT(d), b), NOT(a)))), AND(c, OR(NOT(d), AND(AND(d, NOT(b)), a))))
D = AND(OR(OR(OR(a, c), AND(AND(NOT(d), NOT(c)), NOT(a))), AND(AND(d, NOT(c)), NOT(b))), NOT(OR(AND(AND(NOT(d), NOT(b)), XOR(c, a)), AND(AND(c, b), a))))
E = OR(AND(NOT(a), NOT(AND(AND(NOT(d), c), NOT(b)))), AND(d, NOT(AND(AND(NOT(c), NOT(b)), a))))
F = AND(OR(OR(d, c), AND(NOT(b), NOT(a))), NOT(AND(AND(c, a), XOR(d, b))))
G = AND(OR(OR(d, c), b), NOT(OR(AND(AND(NOT(d), c), AND(b, a)), AND(AND(d, c), AND(NOT(b), NOT(a))))))
  • 36 NO utilizados, 36 NAND
  • 41 AND usados, 84 NAND
  • 19 OR utilizados, 57 NAND
  • 5 XOR utilizados, 20 NAND

Si tengo razón, mi puntaje es 197 .

Durante este desafío, hice un código JavaScript simple para probar mi puerta.

function NOT(a){return !a}function AND(a,b){return a&b}function OR(a,b){return a|b}function XOR(a,b){return a^b}
for(d=0;d<=1;d++){for(c=0;c<=1;c++){for(b=0;b<=1;b++){for(a=0;a<=1;a++){console.log(""+d+c+b+a,
    // Enter your gate here
    // OR(AND(d, NOT(AND(a, XOR(c, b)))), AND(NOT(d), NOT(AND(NOT(b), XOR(a, c)))))
)}}}}

Copie y modifique gate, y péguelo en la consola de su navegador o Node.js REPL.

Bocadillo
fuente