circuito de construcción para divisibilidad por 3

12

Un circuito booleano en TCS es básicamente un DAG que consiste en compuertas And, Or, Not, y por lo que se conoce como "integridad funcional", pueden calcular todas las funciones posibles. Por ejemplo, este es el principio básico en una ALU .

Desafío: cree un circuito para determinar si un número de 8 dígitos binarios es divisible por 3 y de alguna manera visualice su resultado (es decir, en algún tipo de imagen)

El criterio de evaluación para los votantes se basa en si el código para generar el circuito se generaliza bien a números de tamaño arbitrario, y si la visualización creada algorítmicamente es compacta / equilibrada pero aún legible por humanos (es decir, no se permite la visualización a mano). es decir, la visualización es solo para n = 8, pero el código idealmente funcionará para todos 'n'. la entrada ganadora es la mejor votada.

Pregunta algo similar: construir una máquina multiplicadora usando puertas lógicas NAND

vzn
fuente
2
Mucho mejor. Sin embargo, "generalizar" y "estético" no son objetivos. Todas las preguntas deben tener un criterio ganador objetivo. Si desea aplicar esas características, use el concurso de popularidad. Si desea el código más corto, use code-golf. Si desea hacer una combinación de los dos, use el desafío de código, pero especifique una fórmula. Por ejemplo 1.25 * votos - 0.25 * de longitud como lo hace esta pregunta: codegolf.stackexchange.com/questions/23581/eiffel-tower-in-3d/…
Level River St
ok hizo esas cosas que pides. Gracias por sus comentarios.
vzn
Oghh, supongo que VHDL compilado o Verilog después de todas sus optimizaciones deberían dar la respuesta más corta. Lo intentaré más tarde.
Kirill Kulakov
1
Un mejor criterio para ganar sería gate-golf
TheDoctor
@TheDoctor ??? lo que es gate-golf? esa etiqueta es inexistente. Nota para los participantes: indique qué idioma / herramienta de visualización está utilizando. si alguien más quiere ingresar un comentario por favor. de lo contrario aceptará ganador tonite. Gracias a los encuestados hasta ahora, ¡esto fue "BTE" mejor de lo esperado!
vzn

Respuestas:

7

circuito para calcular número módulo 3

El gráfico mantiene 3 booleanos en cada nivel i. Representan el hecho de que los bits de orden superior i del número son iguales a 0, 1 o 2 mod 3. En cada nivel calculamos los siguientes tres bits en función de los tres bits anteriores y el siguiente bit de entrada.

Aquí está el código de Python que generó el gráfico. Simplemente cambie N para obtener un número diferente de bits, o K para obtener un módulo diferente. Ejecute la salida del programa python a través de punto para generar la imagen.

N = 8
K = 3
v = ['0']*(K-1) + ['1']
ops = {}

ops['0'] = ['0']
ops['1'] = ['1']
v = ['0']*(K-1) + ['1']
for i in xrange(N):
  ops['bit%d'%i] = ['bit%d'%i]
  ops['not%d'%i] = ['not','bit%d'%i]
  for j in xrange(K):
    ops['a%d_%d'%(i,j)] = ['and','not%d'%i,v[(2*j)%K]]
    ops['b%d_%d'%(i,j)] = ['and','bit%d'%i,v[(2*j+1)%K]]
    ops['o%d_%d'%(i,j)] = ['or','a%d_%d'%(i,j),'b%d_%d'%(i,j)]
  v = ['o%d_%d'%(i,j) for j in xrange(K)]

for i in xrange(4):
  for n,op in ops.items():
    for j,a in enumerate(op[1:]):
      if ops[a][0]=='and' and ops[a][1]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][2]=='0': op[j+1]='0'
      if ops[a][0]=='and' and ops[a][1]=='1': op[j+1]=ops[a][2]
      if ops[a][0]=='and' and ops[a][2]=='1': op[j+1]=ops[a][1]
      if ops[a][0]=='or' and ops[a][1]=='0': op[j+1]=ops[a][2]
      if ops[a][0]=='or' and ops[a][2]=='0': op[j+1]=ops[a][1]

for i in xrange(4):
  used = set(['o%d_0'%(N-1)])|set(a for n,op in ops.items() for a in op[1:])
  for n,op in ops.items():
    if n not in used: del ops[n]

print 'digraph {'
for n,op in ops.items():
  if op[0]=='and': print '%s [shape=invhouse]' % n
  if op[0]=='or': print '%s [shape=circle]' % n
  if op[0]=='not': print '%s [shape=invtriangle]' % n
  if op[0].startswith('bit'): print '%s [color=red]' % n
  print '%s [label=%s]' % (n,op[0])
  for a in op[1:]: print '%s -> %s' % (a,n)
print '}'
Keith Randall
fuente
¡genial! también he usado graphviz ... pequeña objeción, hay AND / OR no utilizados en el diagrama. También sugiero quizás resaltar bits de entrada en diferentes colores para mostrar sus ubicaciones
vzn
@vzn: Ok, arreglado.
Keith Randall
12

Profundidad: 7 (logarítmica), 18x AND, 6x OR, 7x XOR, 31 puertas (lineal)

Permítanme calcular la suma de dígitos en la base cuatro, módulo tres:

Circuito de 7 capas con una estructura jerárquica claramente visible.

circuito dibujado en Logisim

Generalización, formalmente (con suerte algo legible):

balance (l, h) = {
  is1: l & not h,
  is2: h & not l,
}

add (a, b) = 
  let aa = balance (a.l, a.h)
      bb = balance (b.l, b.h)
  in  { l:(a.is2 & b.is2) | (a.is1 ^ b.is1),
        h:(a.is1 & b.is1) | (a.is2 ^ b.is2)}

pairs [] = []
pairs [a] = [{h:0, l:a}]
pairs [rest.., a, b] = [pairs(rest..).., {h:a, l:b}]

mod3 [p] = p
mod3 [rest.., p1, p2] = [add(p1, p2), rest..]

divisible3 number =
  let {l: l, h: h} = mod3 $ pairs number
  in  l == h

ahora en ingles:

Si bien hay más de dos bits en el número, tome los dos pares de bits más bajos y sume el módulo 3, luego agregue el resultado al final del número, luego regrese si el último par es cero módulo 3. Si hay un número impar número de bits en el número, agregue un bit cero adicional en la parte superior, luego pula con propagación de valor constante.

Agregar al reverso en lugar de al frente asegura que el árbol de adición sea un árbol equilibrado en lugar de una lista vinculada. Esto, a su vez, asegura una profundidad logarítmica en el número de bits: cinco puertas y tres niveles para la cancelación de pares, y una puerta adicional al final.

Por supuesto, si se desea una planaridad aproximada, pase el par superior sin modificar a la siguiente capa en lugar de envolverlo al frente. Sin embargo, esto es más fácil decirlo que implementarlo (incluso en pseudocódigo). Si el número de bits en un número es una potencia de dos (como es cierto en cualquier sistema informático moderno a partir de marzo de 2014), sin embargo, no se producirán pares solitarios.

Si el diagrama conserva la localidad / realiza la minimización de la longitud de la ruta, debe mantener el circuito legible.

Este código Ruby generará un diagrama de circuito para cualquier número de bits (incluso uno). Para imprimir, abra en Logisim y exporte como imagen:

require "nokogiri"

Port = Struct.new :x, :y, :out
Gate = Struct.new :x, :y, :name, :attrs
Wire = Struct.new :sx, :sy, :tx, :ty

puts "Please choose the number of bits: "
bits = gets.to_i

$ports = (1..bits).map {|x| Port.new 60*x, 40, false};
$wires = [];
$gates = [];

toMerge = $ports.reverse;

def balance a, b
y = [a.y, b.y].max
$wires.push Wire.new(a.x   , a.y , a.x   , y+20),
          Wire.new(a.x   , y+20, a.x   , y+40),
          Wire.new(a.x   , y+20, b.x-20, y+20),
          Wire.new(b.x-20, y+20, b.x-20, y+30),
          Wire.new(b.x   , b.y , b.x   , y+10),
          Wire.new(b.x   , y+10, b.x   , y+40),
          Wire.new(b.x   , y+10, a.x+20, y+10),
          Wire.new(a.x+20, y+10, a.x+20, y+30)
$gates.push Gate.new(a.x+10, y+70, "AND Gate", negate1: true),
          Gate.new(b.x-10, y+70, "AND Gate", negate0: true)
end

def sum (a, b, c, d)
y = [a.y, b.y, c.y, d.y].max
$wires.push Wire.new(a.x   , a.y , a.x   , y+40),
          Wire.new(a.x   , y+40, a.x   , y+50),
          Wire.new(a.x   , y+40, c.x-20, y+40),
          Wire.new(c.x-20, y+40, c.x-20, y+50),
          Wire.new(b.x   , b.y , b.x   , y+30),
          Wire.new(b.x   , y+30, b.x   , y+50),
          Wire.new(b.x   , y+30, d.x-20, y+30),
          Wire.new(d.x-20, y+30, d.x-20, y+50),
          Wire.new(c.x   , c.y , c.x   , y+20),
          Wire.new(c.x   , y+20, c.x   , y+50),
          Wire.new(c.x   , y+20, a.x+20, y+20),
          Wire.new(a.x+20, y+20, a.x+20, y+50),
          Wire.new(d.x   , d.y , d.x   , y+10),
          Wire.new(d.x   , y+10, d.x   , y+50),
          Wire.new(d.x   , y+10, b.x+20, y+10),
          Wire.new(b.x+20, y+10, b.x+20, y+50)
$gates.push Gate.new(a.x+10, y+90, "XOR Gate"),
          Gate.new(b.x+10, y+80, "AND Gate"),
          Gate.new(c.x-10, y+80, "AND Gate"),
          Gate.new(d.x-10, y+90, "XOR Gate")
$wires.push Wire.new(a.x+10, y+90, a.x+10, y+100),
          Wire.new(b.x+10, y+80, b.x+10, y+90 ),
          Wire.new(b.x+10, y+90, a.x+30, y+90 ),
          Wire.new(a.x+30, y+90, a.x+30, y+100),
          Wire.new(d.x-10, y+90, d.x-10, y+100),
          Wire.new(c.x-10, y+80, c.x-10, y+90 ),
          Wire.new(c.x-10, y+90, d.x-30, y+90 ),
          Wire.new(d.x-30, y+90, d.x-30, y+100)
$gates.push Gate.new(d.x-20, y+130, "OR Gate"),
          Gate.new(a.x+20, y+130, "OR Gate")
end

def sum3 (b, c, d)
y = [b.y, c.y, d.y].max
$wires.push Wire.new(b.x   , b.y , b.x   , y+20),
          Wire.new(b.x   , y+20, b.x   , y+30),
          Wire.new(b.x   , y+20, d.x-20, y+20),
          Wire.new(d.x-20, y+20, d.x-20, y+30),
          Wire.new(c.x   , c.y , c.x   , y+60),
          Wire.new(c.x   , y+60, b.x+30, y+60),
          Wire.new(b.x+30, y+60, b.x+30, y+70),
          Wire.new(d.x   , d.y , d.x   , y+10),
          Wire.new(d.x   , y+10, d.x   , y+30),
          Wire.new(d.x   , y+10, b.x+20, y+10),
          Wire.new(b.x+20, y+10, b.x+20, y+30),
          Wire.new(b.x+10, y+60, b.x+10, y+70)
$gates.push Gate.new(b.x+10, y+60 , "AND Gate"),
          Gate.new(d.x-10, y+70 , "XOR Gate"),
          Gate.new(b.x+20, y+100, "OR Gate" )
end

while toMerge.count > 2  
puts "#{toMerge.count} left to merge"
nextToMerge = []
while toMerge.count > 3
 puts "merging four"
 d, c, b, a, *toMerge = toMerge
 balance a, b
 balance c, d
 sum *$gates[-4..-1]
 nextToMerge.push *$gates[-2..-1] 
end
if toMerge.count == 3
 puts "merging three"
 c, b, a, *toMerge = toMerge
 balance b, c
 sum3 a, *$gates[-2..-1]
 nextToMerge.push *$gates[-2..-1]
end
nextToMerge.push *toMerge
toMerge = nextToMerge
puts "layer done"
end

if toMerge.count == 2
b, a = toMerge
x = (a.x + b.x)/2
x -= x % 10
y = [a.y, b.y].max
$wires.push Wire.new(a.x , a.y , a.x , y+10),
          Wire.new(a.x , y+10, x-10, y+10),
          Wire.new(x-10, y+10, x-10, y+20),
          Wire.new(b.x , b.y , b.x , y+10),
          Wire.new(b.x , y+10, x+10, y+10),
          Wire.new(x+10, y+10, x+10, y+20)
$gates.push Gate.new(x, y+70, "XNOR Gate")
toMerge = [$gates[-1]]
end

a = toMerge[0]
$wires.push Wire.new(a.x, a.y, a.x, a.y+10)
$ports.push Port.new(a.x, a.y+10, true)

def xy (x, y)
"(#{x},#{y})"
end
circ = Nokogiri::XML::Builder.new encoding: "UTF-8" do |xml|
xml.project version: "1.0" do
xml.lib name: "0", desc: "#Base"
xml.lib name: "1", desc: "#Wiring"
xml.lib name: "2", desc: "#Gates"
xml.options
xml.mappings
xml.toolbar do
  xml.tool lib:'0', name: "Poke Tool"
  xml.tool lib:'0', name: "Edit Tool"
end #toolbar
xml.main name: "main"
xml.circuit name: "main" do
  $wires.each do |wire|
    xml.wire from: xy(wire.sx, wire.sy), to: xy(wire.tx, wire.ty)
  end #each 
  $gates.each do |gate|
    xml.comp lib: "2", name: gate.name, loc: xy(gate.x, gate.y) do
      xml.a name: "facing", val: "south"
      xml.a name: "size", val: "30"
      xml.a name: "inputs", val: "2"
      if gate.attrs
        gate.attrs.each do |name, value|
          xml.a name: name, val: value 
        end #each
      end #if
    end #comp
  end #each
  $ports.each.with_index do |port, index|
    xml.comp lib: "1", name: "Pin", loc: xy(port.x, port.y) do
      xml.a name: "tristate", val: "false"
      xml.a name: "output",   val: port.out.to_s
      xml.a name: "facing",   val: port.out ? "north" : "south"
      xml.a name: "labelloc", val: port.out ? "south" : "north"
      xml.a name: "label",    val: port.out ? "out" : "B#{index}"
    end #port
  end #each
end #circuit
end #project
end #builder

File.open "divisibility3.circ", ?w do |file|
file << circ.to_xml
end

puts "done"

finalmente, cuando se me pide que cree una salida para 32 bits, mi layouter genera esto. Es cierto que no es muy compacto para entradas muy anchas:

Monstruosidad de 13 capas con mucho espacio perdido

John Dvorak
fuente
se ve realmente genial y el mejor circuito / diseño hasta ahora. ¿En qué idioma está el código? ¿Qué layouter usaste? se solicitó que el layouter fuera un algoritmo, y debe asumir que el algoritmo no se usó (diseño manual) a menos que se indique ...
vzn
@vzn, ¿también se tuvo que implementar el diseño? Entendí que restricción significa que podríamos dibujar el diagrama manualmente, pero la legibilidad no debe depender de la forma en que se dibuja el diagrama. El circuito de TimWolla es definitivamente generado a mano. El pseudocódigo se basa principalmente en Haskell con objetos Javascripty agregados.
John Dvorak
La visualización creada algorítmicamente significaba básicamente un diseño algorítmico, pero ahora admite que podría interpretarse de manera ambigua. perdón por falta de claridad cristalina. ¿Conoces algún diseño automático que pueda obtener resultados casi similares al diseño de tu mano?
vzn
Lamentablemente no. yEd tiene excelentes diseños pero ignora la orientación. Nunca me he familiarizado con dot ni encuentro que su salida sea exactamente buena. Supongo que podría traducir este pseudocódigo a Ruby (fácil) y escribir mi propio diseño especializado (no demasiado difícil, pero complejo) que exportaría un circuito logisim (es solo un XML, y ni siquiera está comprimido, tan fácil). ¿Debo (quiero) y debo publicar eso como una respuesta separada? Además, ¿eso contaría como diseñado a mano?
John Dvorak
Todas son buenas respuestas, pero este parece el más elegante hasta ahora
Digital Trauma
5

2 × 24 NOT, 2 × 10 + 5 AND, 2 × 2 + 5 OR, 2 × 2 NOR

Esto no se escala totalmente. No me gusta en absoluto. Quizás intente mejorarlo.

Probé esto para números hasta el 30 y funcionó bien.

Esos 2 grandes circuitos cuentan el número de entradas activas:

  • El superior derecho cuenta el número de bits con una potencia par (cero a 4)
  • El inferior izquierdo cuenta el número de bits con una potencia impar (cero a 4)

Si la diferencia de esos números es 0o 3el número es divisible por 3. El circuito inferior derecha básicamente mapea cada combinación válida ( 4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1, 0, 0) en una o.

El pequeño círculo en el medio es un LED que está encendido si el número es divisible por 3 y apagado de lo contrario.

TimWolla
fuente
wow bonito / rápido! ... por favor ponga un enlace al código o en línea ... también detalle cómo hizo la visualización ...?
vzn
@vzn La visualización se realizó con logisim . Fue construido de mi mano, pero el algoritmo general también se puede hacer fácilmente con un programa. Se explica en parte en la respuesta.
TimWolla