Construa um processador lógico universal de duas vias usando portas lógicas NAND

8

Um 2-maneira lógica processador universal (2ULP) é uma rede de portas lógicas que leva dois fios de entrada Ae B, bem como outros quatro entradas L_, L_a, L_b, e L_ab, e produz uma saída única L(a, b), utilizando os quatro Lentradas como uma função tabela de verdade:

  • O 2ULP retorna L_se Ae Bsão ambos 0.
  • Retorna L_ase A = 1e B = 0.
  • Retorna L_bse A = 0e B = 1.
  • Retorna L_abse Ae Bsão ambos 1.

Por exemplo, tendo em conta as entradas L_ = 0, L_a = 1, L_b = 1, e L_ab = 0, em seguida, a saída L(a, b)será igual a A xor B.

Sua tarefa é construir uma 2ULP usando apenas portas NAND, usando o menor número possível de portas NAND. 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

Cada uma dessas pontuações corresponde ao número de portas NAND necessárias para construir o portão correspondente.

O circuito lógico que usa o menor número de portas NAND para produzir uma construção correta vence.

Joe Z.
fonte
1
Minhas habilidades de design de lógica digital são tão enferrujadas que é ridículo, mas eu aprecio muito os resultados finais dessas competições. +1
ProgrammerDan
Com portas NAND de duas entradas, não há muito espaço para criatividade neste design. Talvez, em vez de exigir que o dispositivo receba seis entradas, projete um bloco com um número arbitrário de entradas e uma saída e exija que, dadas duas entradas A e B e uma opção de uma das dezesseis funções, seja possível conecte as entradas do bloco a alguma combinação de A, B, Alta e Baixa, para que a saída produza essa função. Esse dispositivo seria um processador lógico bidirecional universal (basta adicionar fios), mas provavelmente poderia ser feito em muito menos de 11 portas.
Supercat 28/03
1
Deveríamos inventar o gate-golf , onde você escreve na menor quantidade de portões.
TheDoctor
É para isso que serve o código atômico-golfe + portas lógicas .
Joe Z.

Respostas:

10

11 NANDs

Defina o portão MUX (custo 4) como

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

com tabela de verdade

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

Então este é o operador ternário familiar MUX(P, Q, R) = P ? Q : R

Nós simplesmente temos

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

por um custo de 12, mas há uma economia trivial de uma porta, reutilizando a NOT Bpartir das duas MUXes internas .

Peter Taylor
fonte
3
Você só me deu uma idéia de algo para tentar com redstone em Minecraft, graças
David Wilkins
1
O mínimo absoluto é de 11 NANDs. Eu procurei completamente. E o circuito mais rápido que encontrei tem 5 portões de profundidade. Então, esse quebra-cabeça foi resolvido por Peter Taylor.
21419 KimOyhus
3

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

Eu não sou um homem booleano, este é o meu melhor na codificação dessas coisas (eu sei que isso não vai me dar muitos pontos de internet immaginários ..).

# 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
fonte
Se você seguir o sistema descrito pelos pontos da pergunta, receberá um custo de 29, portanto isso é impressionantemente ruim.
Peter Taylor
Sinto muito, Sr. Taylor, só espero que isso não tenha arruinado seus olhos.
Antonio Ragagnin 28/03
3

Usando a linguagem Wolfram, posso obter uma fórmula de 13 portas :

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"] &

quais saídas:

Fórmula NAND

Aqui Ln, La, Lbe Labsão L_, L_a, L_be L_abseparadamente no OP.

nota de rodapé: Os resultados da BooleanMinimizefunção na linguagem Wolfram são restritos a dois níveis NANDe NOTquando invocados como BooleanMinimize[(*blabla*), "NAND"], portanto, não é tão bom quanto a fórmula de quatro níveis de Peter Taylor acima .

Silvia
fonte