Eine Boolesche Schaltung in TCS ist im Grunde eine DAG, die aus And, Or, Not-Gattern besteht, und mit der Funktion "Funktionsvollständigkeit" können sie alle möglichen Funktionen berechnen. Dies ist zB das Grundprinzip einer ALU .

Herausforderung: Erstellen Sie eine Schaltung, um zu bestimmen, ob eine 8-stellige Zahl durch 3 teilbar ist, und visualisieren Sie Ihr Ergebnis irgendwie (dh in irgendeiner Art von Bild).

Das Beurteilungskriterium für Wähler basiert darauf, ob der Code zum Erzeugen der Schaltung gut auf Zahlen beliebiger Größe verallgemeinert wird und ob die algorithmisch erstellte Visualisierung kompakt / ausgewogen, aber dennoch für den Menschen lesbar ist (dh eine Visualisierung von Hand ist nicht zulässig). dh die Visualisierung ist nur für n = 8, aber der Code funktioniert idealerweise für alle 'n'. der siegreiche Beitrag wird nur von den Besten bewertet.

Etwas ähnliche Frage: Erstellen Sie eine Multiplikationsmaschine mit NAND-Logikgattern

Das Diagramm enthält 3 Boolesche Werte auf jeder Ebene i. Sie repräsentieren die Tatsache, dass die höherwertigen i-Bits der Zahl gleich 0, 1 oder 2 mod 3 sind. Auf jeder Ebene berechnen wir die nächsten drei Bits basierend auf den vorherigen drei Bits und dem nächsten Eingabebit.

Hier ist der Python-Code, der das Diagramm generiert hat. Ändern Sie einfach N, um eine andere Anzahl von Bits zu erhalten, oder K, um einen anderen Modul zu erhalten. Führen Sie die Ausgabe des Python-Programms über dot aus , um das Image zu generieren.

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

Tiefe: 7 (logarithmisch), 18x AND, 6x OR, 7x XOR, 31 Gatter (linear)

Lassen Sie mich die Ziffernsumme in Basis vier, Modulo drei berechnen:

_{Schaltung in Logisim gezeichnet}

Verallgemeinerung, formal (hoffentlich etwas lesbar):

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

jetzt auf englisch:

Wenn die Zahl mehr als zwei Bits enthält, nehmen Sie zwei niedrigste Bitpaare und addieren Sie sie mit Modulo 3, hängen Sie das Ergebnis an die Rückseite der Zahl an und geben Sie dann zurück, wenn das letzte Paar Null mit Modulo 3 ist. Wenn eine ungerade Zahl vorliegt Anzahl der Bits in der Zahl, fügen Sie ein zusätzliches Nullbit oben hinzu und polieren Sie dann mit konstanter Werteausbreitung.

Das Anhängen an die Rückseite anstatt an die Vorderseite stellt sicher, dass der Additionsbaum ein ausgeglichener Baum und keine verknüpfte Liste ist. Dies sichert wiederum die logarithmische Tiefe der Anzahl der Bits: fünf Gatter und drei Ebenen für die Paarlöschung und ein zusätzliches Gatter am Ende.

Wenn eine ungefähre Planarität gewünscht wird, übergeben Sie das obere Paar natürlich unverändert an die nächste Ebene, anstatt es nach vorne zu wickeln. Dies ist jedoch einfacher gesagt als implementiert (auch im Pseudocode). Wenn die Anzahl der Bits in einer Zahl eine Zweierpotenz ist (wie es in jedem modernen Computersystem ab März 2014 der Fall ist), treten jedoch keine Einzelpaare auf.

Wenn der Layouter die Lokalität beibehält / eine Minimierung der Routenlänge durchführt, sollte die Schaltung lesbar bleiben.

Dieser Ruby-Code generiert ein Schaltbild für eine beliebige Anzahl von Bits (sogar eines). Zum Drucken in Logisim öffnen und als Bild exportieren:

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"

Auf die Aufforderung hin, eine Ausgabe für 32 Bit zu erstellen, generiert mein Layouter diese. Zugegebenermaßen ist es für sehr breite Eingaben nicht sehr kompakt:

2 × 24 NICHT, 2 × 10 + 5 UND, 2 × 2 + 5 ODER, 2 × 2 NOR

Das skaliert total nicht. Wie überhaupt nicht. Vielleicht versuche ich es zu verbessern.

Ich habe dies für Zahlen bis zu 30 getestet und es hat gut funktioniert.

Diese 2 großen Schaltkreise zählen die Anzahl der aktiven Eingänge:

• Die obere rechte zählt die Anzahl der Bits mit gerader Potenz (Null bis 4)
• Die untere linke zählt die Anzahl der Bits mit einer ungeraden Potenz (Null bis 4)

Ist der Unterschied dieser Zahlen 0oder ist 3die Zahl durch teilbar 3. Die untere rechte Schaltung im Grunde ordnet jede gültige Kombination ( 4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1,0, 0 ) in eine oder.

Der kleine Kreis in der Mitte ist eine LED, die an ist, wenn die Zahl durch 3 teilbar ist, und ansonsten aus ist.