circuito de construção para divisibilidade por 3

12

Um circuito booleano no TCS é basicamente um DAG que consiste nos portões And, Or, Not e, pelo que se sabe, é "integridade funcional", eles podem calcular todas as funções possíveis. por exemplo, este é o princípio básico em uma ULA .

Desafio: crie um circuito para determinar se um número de 8 dígitos binários é divisível por 3 e visualize de alguma forma o resultado (ou seja, em algum tipo de figura)

O critério de julgamento para os eleitores é baseado em se o código para gerar o circuito generaliza bem para números arbitrários de tamanho e se a visualização criada por algoritmos é compacta / balanceada, mas ainda assim legível por humanos (ou seja, visualização por arranjo manual não é permitida). isto é, a visualização é apenas para n = 8, mas o código funcionará idealmente para todos os 'n'. a entrada vencedora é apenas a mais votada.

Pergunta um pouco semelhante: Construa uma máquina multiplicadora usando portas lógicas NAND

vzn
fonte
2
Muito melhor. No entanto, "generalizar" e "estético" não são objetivos. Todas as perguntas devem ter um critério de vitória objetivo. Se você deseja aplicar essas características, use o concurso de popularidade. Se você deseja um código mais curto, use o code-golf. Se você quiser fazer uma combinação dos dois, use desafio de código, mas especifique uma fórmula. Por exemplo, 1,25 * votos - 0,25 *, como esta pergunta: codegolf.stackexchange.com/questions/23581/eiffel-tower-in-3d/…
Level River St
ok fez as chgs que você pede. thx para feedback.
vzn 25/03
Acho que compilamos VHDL ou Verilog depois que todas as suas otimizações deveriam dar a resposta mais curta. Vou tentar mais tarde.
precisa
1
Um critério de vitória melhor seria o golfe do portão
TheDoctor 25/03
@O médico ??? o que é gate-golf? essa tag é inexistente. observação para os participantes: indique qual ferramenta de idioma / visualização você está usando. se alguém quiser inserir um comentário. caso contrário, aceitará o vencedor esta noite. thx muito para os entrevistados até agora isso foi "BTE" melhor do que o esperado!
vzn

Respostas:

7

circuito para calcular o módulo número 3

O gráfico mantém 3 booleanos em cada nível i. Eles representam o fato de que os bits i de alta ordem do número são iguais a 0, 1 ou 2 mod 3. Em cada nível, calculamos os próximos três bits com base nos três bits anteriores e no próximo bit de entrada.

Aqui está o código python que gerou o gráfico. Basta alterar N para obter um número diferente de bits ou K para obter um módulo diferente. Execute a saída do programa python através do ponto para gerar a imagem.

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
fonte
ótimo! também usei o graphviz ... pequenos detalhes, existem ANDs / ORs não utilizados no diagrama. também sugerem talvez destacando bits de entrada na cor diferente para mostrar suas localizações
vzn
@ vzn: Ok, fixo.
Keith Randall
12

Profundidade: 7 (logarítmica), 18x AND, 6x OR, 7x XOR, 31 portas (lineares)

Deixe-me calcular a soma dos dígitos na base quatro, módulo três:

Circuito de 7 camadas com uma estrutura hierárquica claramente visível

circuito desenhado no Logisim

Generalização, formalmente (espero que um tanto legível):

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

agora em inglês:

Embora haja mais de dois bits no número, pegue dois pares de bits mais baixos e some-os no módulo 3, depois acrescente o resultado à parte de trás do número e retorne se o último par for zero no módulo 3. Se houver um número ímpar número de bits no número, adicione um zero zero extra ao topo e depois faça o polimento com propagação constante do valor.

Anexar na parte de trás em vez de na frente garante que a árvore de adição seja uma árvore equilibrada em vez de uma lista vinculada. Isso, por sua vez, garante profundidade logarítmica no número de bits: cinco portas e três níveis para cancelamento de pares e um portão extra no final.

Obviamente, se a planaridade aproximada for desejada, passe o par superior não modificado para a próxima camada em vez de envolvê-lo para a frente. Isso é mais fácil dizer do que implementado (mesmo em pseudocódigo), no entanto. Se o número de bits em um número for uma potência de dois (como é verdade em qualquer sistema de computador moderno a partir de março de 2014), nenhum par isolado ocorrerá.

Se o layouter preservar a localidade / executar a minimização do comprimento da rota, deverá manter o circuito legível.

Este código Ruby irá gerar um diagrama de circuito para qualquer número de bits (mesmo um). Para imprimir, abra no Logisim e exporte como imagem:

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, quando solicitado a criar uma saída para 32 bits, meu layouter gera isso. É certo que não é muito compacto para entradas muito amplas:

Monstruosidade de 13 camadas com muito espaço desperdiçado

John Dvorak
fonte
parece realmente ótimo e melhor circuito / layout até agora. em que idioma está o código? que layouter você usou, se houver? o layouter foi solicitado para ser um algoritmo, e tenho que assumir que o algoritmo não foi utilizado (layout de mão), salvo indicação ...
vzn
@vzn o layouter também teve que ser implementado? Entendi essa restrição como significando que poderíamos desenhar o diagrama manualmente, mas a legibilidade não deve depender da maneira como o diagrama é desenhado. O circuito do TimWolla é definitivamente gerado à mão. O pseudocódigo é baseado principalmente em Haskell com objetos Javascripty adicionados.
John Dvorak
a visualização criada por algoritmos significava basicamente um layout algorítmico, mas agora admite que isso poderia ser interpretado de forma ambígua. desculpe pela falta de clareza de cristal. você conhece algum layout automático que pode obter resultados quase semelhantes ao layout da sua mão?
vzn 25/03
Infelizmente não. O yEd possui ótimos layouts, mas ignora a orientação. Eu nunca me familiarizei com o ponto nem considero sua saída exatamente agradável. Eu acho que eu poderia traduzir esse pseudocódigo para Ruby (fácil) e escrever meu próprio layout especializado (não muito difícil, mas complexo) que exportaria um circuito logisim (é apenas um XML, e nem é compactado com zíper, é muito fácil). Devo (quero) e devo postar isso como uma resposta separada? Além disso, isso contaria como desenhado à mão?
John Dvorak
Todas as boas respostas, mas esta parece ser a mais elegante até agora
Digital Trauma
5

2 × 24 NÃO, 2 × 10 + 5 AND, 2 × 2 + 5 OU, 2 × 2 NOR

Isso totalmente não escala. Como não. Talvez eu tente melhorar.

Eu testei isso para números de até 30 e funcionou bem.

Esses 2 grandes circuitos estão contando o número de entradas ativas:

  • O canto superior direito conta o número de bits com uma potência uniforme (zero a 4)
  • O canto inferior esquerdo conta o número de bits com uma potência ímpar (zero a 4)

Se a diferença desses números é 0ou 3o número é divisível por 3. O circuito inferior direito basicamente mapeia cada combinação válida ( 4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1, 0, 0) em um ou.

O pequeno círculo no meio é um LED que acende se o número for divisível por 3 e, caso contrário, apagado.

TimWolla
fonte
uau legal / rápido! ... plz colocou um link para codificar ou incorporá-lo ... também detalha como você fez a visualização ...?
vzn 25/03
@vzn A visualização foi feita com o logisim . Foi construído minha mão, mas o algoritmo geral também pode ser feito facilmente com um programa. É parcialmente explicado na resposta.
TimVolla