Un circuit booléen dans TCS est fondamentalement un DAG composé de portes And, Or, Not, et par ce qui est connu comme "complétude fonctionnelle", ils peuvent calculer toutes les fonctions possibles. c'est par exemple le principe de base d'une ALU .

Défi: créer un circuit pour déterminer si un nombre à 8 chiffres binaires est divisible par 3 et visualiser en quelque sorte votre résultat (c'est-à-dire dans une sorte d'image)

Les critères de jugement pour les votants sont basés sur le fait que le code pour générer le circuit se généralise bien à des nombres de taille arbitraires, et si la visualisation créée par algorithme est compacte / équilibrée mais néanmoins lisible par l'homme (c'est-à-dire que la visualisation à la main n'est pas autorisée). c'est-à-dire que la visualisation est uniquement pour n = 8 mais le code fonctionnera idéalement pour tous les «n». l'entrée gagnante est juste votée en haut.

Question un peu similaire: construire une machine à multiplier à l'aide de portes logiques NAND

Le graphique maintient 3 booléens à chaque niveau i. Ils représentent le fait que les i bits de poids fort du nombre sont égaux à 0, 1 ou 2 mod 3. À chaque niveau, nous calculons les trois bits suivants sur la base des trois bits précédents et du bit d'entrée suivant.

Voici le code python qui a généré le graphique. Modifiez simplement N pour obtenir un nombre différent de bits, ou K pour obtenir un module différent. Exécutez la sortie du programme python via dot pour générer l'image.

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 '}'

Profondeur: 7 (logarithmique), 18x ET, 6x OU, 7x XOR, 31 portes (linéaire)

Permettez-moi de calculer la somme des chiffres en base quatre, modulo trois:

_{circuit tracé dans Logisim}

Généralisation, formellement (je l'espère quelque peu lisible):

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

maintenant en anglais:

Bien qu'il y ait plus de deux bits dans le nombre, prenez les deux paires de bits les plus basses et additionnez-les modulo 3, puis ajoutez le résultat à l'arrière du nombre, puis retournez si la dernière paire est zéro modulo 3. S'il y a un impair nombre de bits dans le nombre, ajoutez un bit zéro supplémentaire en haut, puis polissez avec une propagation de valeur constante.

L'ajout à l'arrière plutôt qu'à l'avant garantit que l'arbre d'addition est un arbre équilibré plutôt qu'une liste liée. Ceci, à son tour, garantit une profondeur logarithmique du nombre de bits: cinq portes et trois niveaux pour l'annulation de paires, et une porte supplémentaire à la fin.

Bien sûr, si une planarité approximative est souhaitée, passez la paire supérieure non modifiée à la couche suivante au lieu de l'envelopper à l'avant. Cependant, c'est plus facile à dire qu'à implémenter (même en pseudocode). Si le nombre de bits d'un nombre est une puissance de deux (comme c'est le cas dans tout système informatique moderne à partir de mars 2014), aucune paire isolée ne se produira cependant.

Si le planificateur préserve la localité / effectue une minimisation de la longueur de l'itinéraire, il doit garder le circuit lisible.

Ce code Ruby générera un schéma de circuit pour n'importe quel nombre de bits (même un). Pour imprimer, ouvrir dans Logisim et exporter en tant qu'image:

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"

enfin, lorsqu'on lui a demandé de créer une sortie pour 32 bits, mon layouter génère cela. Certes, ce n'est pas très compact pour des entrées très larges:

2 × 24 NON, 2 × 10 + 5 ET, 2 × 2 + 5 OU, 2 × 2 NOR

Cela ne change absolument pas. Comme pas du tout. J'essaierai peut-être de l'améliorer.

J'ai testé cela pour des nombres allant jusqu'à 30 et cela a bien fonctionné.

Ces 2 gros circuits comptent le nombre d'entrées actives:

• Le coin supérieur droit compte le nombre de bits avec une puissance paire (zéro à 4)
• Le coin inférieur gauche compte le nombre de bits de puissance impaire (zéro à 4)

Si la différence de ces nombres est 0ou 3le nombre est divisible par 3. Le circuit inférieur droit des cartes essentiellement chaque combinaison valide ( 4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1, 0, 0) dans un ou.

Le petit cercle au milieu est une LED qui est allumée si le nombre est divisible par 3 et éteinte sinon.