Construya un probador de conectividad de 4 vértices usando puertas NAND

12

Un gráfico conectado es un gráfico que contiene una ruta entre dos vértices.

Desafío

Cree un circuito [compuerta NAND de 2 entradas] que determine si un gráfico de 4 vértices está conectado.
(Las 2 entradas de una compuerta pueden ser el mismo bit de entrada u otra compuerta).
Salida Verdadero si el gráfico está conectado y falso en caso contrario.

Entrada

Los seis bordes posibles de un gráfico simple con 4 vértices:

[ 0 e 1 , 0 e 2 , 1 e 2 , 0 e 3 , 1 e 3 , 2 e 3 ]

donde a e b representa si hay un borde entre los vértices a y b

La conectividad es equivalente a las siguientes condiciones:

  • Si menos de 3 entradas son verdaderas, entonces la salida es falsa.

  • Si más de 3 entradas son verdaderas, entonces la salida es verdadera.

  • Si exactamente 3 entradas son Verdaderas y forman un triángulo, entonces salen Falso.

  • De lo contrario, salida True.

La respuesta que usa la menor cantidad de puertas gana. Los empates se romperán por
la profundidad de circuito más baja (longitud de la ruta más larga desde la entrada a la salida).


fuente
¿Podría especificar más el formato de entrada?
LegionMammal978
iej es Verdadero o Falso según si hay o no una arista desde el vértice i hasta el vértice j.
¿Se puede tomar la entrada como 0y 1? ¿Qué hay de salida?
TheCoffeeCup
3
@TheCoffeeCup Este es un problema de diseño de circuito lógico, no code-golf .
lirtosiast
@ThomasKwa Whoops, no se dio cuenta.
TheCoffeeCup

Respuestas:

4

30 NANDS

En lugar de preguntar cuándo obtenemos un 1, hice la pregunta de cuándo obtenemos un 0. Es mejor preguntarlo de esta manera porque hay menos 0 que 1.

Aquí está la distribución según el número de aristas (sexta fila del triángulo de Pascal)

Edges     0  1  2  3  4  5  6
Frequency 1  6 15 20 15  6  1 (total 64)
Output    0  0  0  *  1  1  1
* = 0 if triangle (4 possibilities) 1 if claw (4 possibilities) 
1 if two opposite edges and one other (12 possibilities)

Al hacer la pregunta de esta manera, obtenemos el siguiente diagrama y expresión

 ___D___
|\     /|
| E   F |
|  \ /  |
A   X   C
|  / \  |
| /   \ |
|/__B__\|

(A|C|D|B)&(A|D|E)&(D|B|E|F)&(C|B|E)&(A|C|E|F)&(D|F|C)&(A|F|B) 

Suponemos que la salida será predeterminada a 1, pero cambiará a 0 en cualquiera de las siguientes condiciones

1.A 0 para tres bordes adyacentes (prueba 3 entradas)

2.A 0 para dos pares de bordes opuestos (prueba 4 entradas)

Los términos anteriores ya están ordenados de la manera que les permitirá agruparse de la siguiente manera. (Por cierto, esta versión de la expresión es rotacionalmente simétrica respecto al vértice AFB).

((A|D)|((C|B)&E))&((B|E)|((D|F)&C))&((C|F)|((A|E)&D))&(A|F|B)    =6 inverters
   1      1  1       1      1  1       1      1  1      1        =10 (7 OR with both inputs inverted, 3 NAND)
      2                 2                 2               2      =8  (4 OR with one input inverted)
                 2                 2                 2           =6  (3 AND) 
                                                        Total    =30

La puntuación para cada &o |se coloca debajo del símbolo y se justifica de la siguiente manera:

Nivel 0: Invertimos en un inversor para cada entrada: 6 NANDS

Nivel 1: Podemos construir un OR a partir de una puerta NAND colocando un inversor en la entrada (un total de 3 NANDS) pero como ya invertimos en 6 NANDS en el paso anterior, podemos hacer 7 puertas OR a partir de 7 puertas NAND. También necesitamos 3 puertas Y. Para estos, solo usaremos NAND y dejaremos la salida invertida. 10 NANDS

Nivel 2: Nuevamente construimos 4 puertas OR a partir de puertas NAND. En cada caso tenemos 1 entrada desde una puerta OR, por lo que tenemos que invertir eso. Pero la otra entrada ya está invertida (proveniente de una de las NAND en el paso anterior que corresponde a un &símbolo en tres casos, y de un inversor en el último), por lo que solo necesitamos 2 puertas para cada funcionalidad OR. 4 * 2 = 8

Nivel 3: ahora necesitamos Y las cuatro salidas juntas. Esto requiere 3 compuertas AND, cada una construida a partir de 2 NAND, 3 * 2 = 6

Eso es un total de 30 puertas NAND, con una profundidad máxima de 2 + 2 + 4 = 8 NAND para ramas con un |nivel 1 o 3 + 1 + 4 = 8 NAND para ramas con un &nivel 1.

El siguiente script de Ruby confirma visualmente que la expresión anterior es válida.

64.times{|i|
  a=i%2
  b=i/2%2
  c=i/4%2
  d=i/8%2
  e=i/16%2 
  f=i/32%2

puts i, ((a|d)|((c|b)&e))&((b|e)|((d|f)&c))&((c|f)|((a|e)&d))&(a|f|b)

puts " ___#{d}___
|\\     /|
| #{e}   #{f} |
|  \\ /  |
#{a}   X   #{c}
|  / \\  |
| /   \\ |
|/__#{b}__\\|


"
}
Level River St
fuente
7

19 NANDs

No hay un circuito más simple que este.

Hay un código para probarlo debajo de la imagen. En cuanto a entenderlo, eso es difícil. Hay un par de puertas IF allí, y las entradas se agrupan en un triángulo con las líneas de esquina libres agregadas para el análisis una por una, pero no de una manera simple. Si alguien logra entenderlo, quedaré impresionado.

ingrese la descripción de la imagen aquí

Código Verilog con pruebas:

// 4-vertex Connectedness Tester                                                                  
// Minimal at 19 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/69912/build-a-4-vertex-connectedness-tester-using-nand-gates/                                                                                      
//                                                                                                
// I am sure there are no simpler solutions to this problem.                                      
// It has a logical depth of 11, which is deeper than                                             
// circuits using a few more NANDs.                                                               

module counting6 ( in_000, in_001, in_002, in_003, in_004, in_005, in_006, out000 );
  input  in_000, in_001, in_002, in_003, in_004, in_005, in_006;
  output out000;
  wire   wir000, wir001, wir002, wir003, wir004, wir005, wir006, wir007, wir008, wir009, wir010, wir011, wir012, wir013, wir014, wir015, wir016, wir017;

  nand gate000 ( wir000, in_000, in_000 );
  nand gate001 ( wir001, in_001, in_003 );
  nand gate002 ( wir002, wir001, wir000 );
  nand gate003 ( wir003, in_002, wir002 );
  nand gate004 ( wir004, wir002, wir002 );
  nand gate005 ( wir005, wir004, in_002 );
  nand gate006 ( wir006, wir005, wir004 );
  nand gate007 ( wir007, in_005, wir006 );
  nand gate008 ( wir008, in_003, wir006 );    
  nand gate009 ( wir009, in_004, wir003 );
  nand gate010 ( wir010, wir003, wir009 );
  nand gate011 ( wir011, wir009, wir000 );
  nand gate012 ( wir012, wir011, in_001 );
  nand gate013 ( wir013, wir008, wir012 );
  nand gate014 ( wir014, wir013, in_005 );
  nand gate015 ( wir015, wir006, wir013 );
  nand gate016 ( wir016, wir015, wir007 );
  nand gate017 ( wir017, wir016, wir010 );
  nand gate018 ( out000, wir014, wir017 );
endmodule


module connecting6_test;
   reg [5:0] X;
   wire a;

  counting6 U1 (
  .in_000 (X[0]),
  .in_001 (X[1]),
  .in_002 (X[2]),
  .in_003 (X[3]),
  .in_004 (X[4]),
  .in_005 (X[5]),
  .in_006 (X[6]),
  .out000 (a )
  );

  initial begin
    X = 0;
  end

  always
    #10  X = X+1;

 initial  begin
    $display("\t\t     \t_");
    $display("\t\ttime,\t \\db/_,\tconnected");
    $monitor("%d,\t%b,\t%d",$time, X, a );
  end

  initial
   #630  $finish;

endmodule

// iverilog -o hello hello.v                                                                      
// vvp hello                                                                                      

Kim Øyhus

KimOyhus
fuente
¿Probaste esto mínimo, y si es así, cómo?
lirtosiast el
Utilicé pruebas estadísticas para obtener evidencia de que es mínimo. Para circuitos relativamente simples, como este, las pruebas son bastante seguras.
KimOyhus
1

Mathematica, 17 puertas

Simplemente enumeramos todas las reglas, construimos la función booleana y la minimizamos en NANDforma.

#->If[Total@#<3||
       MemberQ[{{1,1,1,0,0,0},{1,0,0,1,1,0},{0,1,0,1,0,1},{0,0,1,0,1,1}},#]
       ,0,1] /.{1->True,0->False}& /@
     Tuples[{0,1},6];
BooleanMinimize[BooleanFunction[rule], "NAND"]

Resultado :

(#1⊼#2⊼#4)⊼(#1⊼#2⊼#5)⊼(#1⊼#2⊼#6)⊼(#1⊼#3⊼#4)⊼ \
(#1⊼#3⊼#5)⊼(#1⊼#3⊼#6)⊼(#1⊼#4⊼#6)⊼(#1⊼#5⊼#6)⊼ \
(#2⊼#3⊼#4)⊼(#2⊼#3⊼#5)⊼(#2⊼#3⊼#6)⊼(#2⊼#4⊼#5)⊼ \
(#2⊼#5⊼#6)⊼(#3⊼#4⊼#5)⊼(#3⊼#4⊼#6)⊼(#4⊼#5⊼#6)&

, donde #1...#6hay 6 espacios para argumentos.


Casos de prueba :

f=%; (* assign the function to symbol f *)

f[True, True, True, True, False, False]
(* True *)

f[True, True, False, True, False, False]
(* True *) (*, three Trues do not form a triangle *)

f[True, True, True, False, False, False]
(* False *) (*, three Trues form a triangle *)
njpipeorgan
fuente
¿P⊼q⊼r significa not (p&q&r)? ¿Qué significa el resultado final y final?
@RickyDemer Sí, p⊼q⊼rsignifica (p⊼q)⊼r, que es equivalente a !(p&&q&&r).
njpipeorgan
Conectar False, False, True parece mostrar que (p⊼q)⊼rno es equivalente a !(p&&q&&r).
@RickyDemer Eso es un problema ... Lo di por sentado.
njpipeorgan
Además, al menos la versión wolframalpha de BooleanMinimize [expr, "NAND"] no necesariamente minimiza el número de NANDS. (Pruebe BooleanMinimize [(((a NAND b) NAND (c NAND d)) NAND ((e NAND f) NAND (g NAND h))), "NAND"].) Ejecutar eso en Mathematica da una salida con a lo sumo 7 NANDS?
1

64 NANDs

Los seis bordes se pueden dividir en tres pares de bordes opuestos. Para que se conecte un gráfico, debe haber dos bordes opuestos, así como un tercer borde, o tres bordes conectados al mismo vértice.

       •
       U

   Z   •   Y  
    V     W 
 •     X     •

Los pares opuestos son UX, VY, WZ, entonces:

A = U+V   ;3 gates
B = W+X
C = Y+Z

D = UV(B+C)  ;2+2+3=7 gates
E = WX(A+C)
F = YZ(C+A)

Result = D+E+F+UVW+UYZ+XVZ+XWY ; 18 + 16 = 34 gates

Construyendo puertas AND y OR de la manera usual, el número total de puertas utilizadas es 3*3+7*3+34= 64.

lirtosiast
fuente
[Verdadero, verdadero, falso, verdadero, falso, falso] proporciona un gráfico conectado sin bordes opuestos.
@RickyDemer Creo que esto funciona ahora ...
lirtosiast