Dirija um display hexadecimal de 7 segmentos usando portas lógicas NAND

9

A exibição numérica de 7 segmentos onipresente pode exibir inequivocamente todos os 16 dígitos hexadecimais, como mostra esta wikipedia .gif

As entradas para este desafio criarão um diagrama de circuitos usando portas lógicas NAND que transformam os quatro bits de um dígito hexadecimal nas entradas dos sete segmentos. As entradas para a exibição de 7 segmentos são tipicamente rotuladas da seguinte forma: (DP (ponto decimal) é ignorado para este desafio)

insira a descrição da imagem aqui

Assim, seu circuito precisará estar em conformidade com a seguinte tabela de verdade:

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

Penso que esta tabela é precisa, mas informe-me se detectar algum erro.

Sua pontuação é determinada pelo número de portas NAND de 2 entradas que você usa (1 ponto por porta). Para simplificar, você pode usar as portas AND, OR, NOT e XOR em seu diagrama, com as seguintes pontuações correspondentes:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4
Trauma Digital
fonte
esse desafio parece ser sobre o desenho de um diagrama de circuito, e não sobre a codificação. Além disso, os valores dos pontos por portão parece arbitrária (talvez intencionalmente), e utilizando E + NÃO é de 3 pontos, quando você indicar NAND é de apenas 1.
stokastic
@stokastic Existem muitos outros desafios de portas lógicas neste site, então estou assumindo essa categoria de desafio aceitável para a comunidade. Muitos usam o mesmo sistema de pontuação. Acho que a lógica NAND explica muito bem esse sistema de pontuação.
Digital Trauma
Justo. Eu não tinha visto essas tags antes. Simplesmente não parece se encaixar realmente em 'quebra-cabeças de programação' ou 'código de golfe'.
stokastic 11/09/14
O circuito pode se dividir? Em outras palavras, você pode salvar valores em variáveis ​​e recuperá-los mais tarde?
xnor
@xnor Você está falando sobre esse tipo de coisa: codegolf.stackexchange.com/a/26235/11259 ? Nesse caso, a resposta é sim.
Digital Trauma

Respostas:

17

Dominó - Pontuação total: 243 NANDs

  • RUPs utilizadas: 61 (3 NANDs cada -> 183 NANDs)

  • NOTs usados: 60 (1 NANDs cada -> 60 NANDs)

Essa solução está no dominó e exigiu uma coleção de peças de software que escrevi ao responder às duas perguntas relacionadas ao Domino de Martin Büttner para produzir ( Golfe no Domino Day e Domino Circuits ).

Ao modificar meu solucionador de circuitos do Domino , consegui produzir um circuito de dominó (esse arquivo também contém a saída e o esqueleto do circuito) consistindo em ORs e IFNOTs em que a primeira entrada é sempre VERDADEIRA (portanto, é essencialmente um NÃO). Porque não há muito que se encaixam nesta resposta, eu apresento as OR e NOT soluções para a tabela verdade:

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)))))))

Observe que as únicas operações binárias usadas são OR e IFNOT, onde conto cada IFNOT como NÃO para fins de pontuação

Eu adicionei um display de 7 segmentos ao final do circuito e o alimentei em um simulador de dominó / gerador de gif. O gif resultante (que mostra 'A' sendo exibido) levou cerca de 2 horas para ser gerado. Como o circuito final tem 1141 * 517 de tamanho, cada "célula" é representada por um único pixel. Uma célula preta está vazia, uma célula cinza tem um dominó permanente e uma célula branca tem um dominó caído. Isso significa que você não pode realmente dizer o que está acontecendo, e não ajudará se estiver sendo esmagado. Sparr gentilmente forneceu uma versão muito menor do meu gif original (650kB), então aqui está!

Animação

Abaixo está o último quadro da animação para a entrada 1010 ('A') como acima. Você pode ver as entradas na extrema esquerda, a linha de força na parte superior, o quadro de distribuição ocupando a maior parte do espaço, as 7 peças individuais de lógica (estas são representações de dominó das funções acima) à esquerda do quadro de distribuição e para a extrema direita é a própria tela de 7 segmentos. Quando isso é executado, os segmentos individuais acendem aproximadamente ao mesmo tempo, portanto, você não pode ficar olhando por muito tempo com alguns segmentos acesos esperando que outros acendam.

Último quadro de animação

Veja a animação em toda a sua glória aqui (36MB) ou aqui (650kB, cortesia de Sparr) (a cópia menor é muito menor, mas meu navegador parecia gostar de pular quadros que estragam a beleza, então deixei o original assim)

Os detalhes da tela de 7 segmentos podem ser vistos aqui ('1' é mostrado)

VisualMelon
fonte
3
+1 pela pura surrealidade de dirigir uma tela de 7 segmentos com dominós!
Digital Trauma
Isso é incrível ... Alguém deveria tentar fazer isso na vida real
Beta Decay
11

30 NANDs

Tenho certeza de que não há soluções mais simples para esse problema, exceto talvez alterando os símbolos na tela, mas esse seria outro problema diferente.

Como isso é realmente algo útil, por exemplo, ao programar um FPGA para mostrar a saída, forneço código Verilog.

Quanto ao minimalismo: é claro que era difícil de fazer. Não é compreensível, uma vez que uma tela de 7 segmentos é apenas uma maneira bastante aleatória em que os humanos mostram números, resultando em um circuito também bastante aleatório. E como é típico para esses circuitos mínimos, sua profundidade lógica é um pouco maior do que para soluções próximas. Eu acho que isso ocorre porque serial é mais simples que paralelo.

O atraso da transmissão é indicado pela posição descendente de cada porta NAND na folha.

Driver de exibição 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
fonte
Esta é uma solução realmente impressionante! Por que você está tão confiante de que não se pode fazer melhor que 30? 37 já parecia "bastante reduzido", imo.
Alex Meiburg
Obrigado. Eu procurei além dessa solução, usando muito mais tempo para isso do que para encontrar a solução em si, e não havia nada lá. A probabilidade de eu ter perdido algo melhor é muito pequena. É um argumento estatístico.
KimOyhus 30/12/19
7

Usando ~ para NOT e N para NAND, uma pesquisa por computador (sem compartilhar termos entre saídas) encontra uma solução com 82 NANDs sem compartilhar. A procura manual de termos de compartilhamento reduz para 54 NANDs e uma pesquisa no computador que inclui compartilhamento reduz ainda mais para 37 NANDs. O mínimo pode ser ainda mais baixo, pois o método certamente não é exaustivo.

Aqui está o programa que recria a tabela acima. Cada linha é rotulada com o NANDS para essa saída.

#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)))))) );
    } } } }
}

E aqui está a saída:

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

E aqui estão as equações equivalentes, compartilhando termos que o reduzem a 54 NANDs:

    /* 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)))) );

E aqui está a solução 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
fonte
2
Você deve ter um cabeçalho orgulhoso com "37 NANDs". Sua postagem é muito modesta sem isso.
21418 KimOyhus
4

197 NANDs

Uma vez que este é o meu primeiro desafio de portas lógicas. não é muito jogado e pode não ser a menor solução. Eu não estou usando circuito dividido aqui.

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 NOTs usadas, 36 NANDs
  • 41 ANDs usados, 84 NANDs
  • 19 RUPs usadas, 57 NANDs
  • 5 XORs usados, 20 NANDs

Se eu estiver certo, minha pontuação é 197 .


Durante esse desafio, criei um código JavaScript simples para testar meu portão.

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 e modifique o gate e cole-o no console do seu navegador ou no Node.js. REPL.

Lanche
fonte