Logiczna obwód w TCS jest w zasadzie DAG składający AND, OR, NOT bramy, a przez to, co jest znane to „kompletność funkcjonalna” mogą obliczyć wszystkie możliwe funkcje. np. jest to podstawowa zasada ALU .

Wyzwanie: utwórz obwód, aby ustalić, czy 8-cyfrowa liczba binarna jest podzielna przez 3 i jakoś wizualizuj swój wynik (tj. Na jakimś obrazie)

Kryteria oceniania dla wyborców są oparte na tym, czy kod generujący obwód ładnie generalizuje się do dowolnych liczb wielkości i czy wizualizacja utworzona algorytmicznie jest zwarta / zrównoważona, ale wciąż czytelna dla człowieka (tj. Wizualizacja przy pomocy układu rąk niedozwolona). tzn. wizualizacja dotyczy tylko n = 8, ale kod idealnie będzie działał dla wszystkich „n”. zwycięskie zgłoszenie jest właśnie najlepiej ocenione.

Nieco podobne pytanie: Zbuduj maszynę do mnożenia za pomocą bramek logicznych NAND

Wykres utrzymuje 3 wartości logiczne na każdym poziomie i. Reprezentują one fakt, że bity i wyższego rzędu liczby są równe 0, 1 lub 2 mod 3. Na każdym poziomie obliczamy kolejne trzy bity na podstawie poprzednich trzech bitów i następnego bitu wejściowego.

Oto kod python, który wygenerował wykres. Wystarczy zmienić N, aby uzyskać inną liczbę bitów, lub K, aby uzyskać inny moduł. Uruchom dane wyjściowe programu python przez kropkę, aby wygenerować obraz.

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

Głębokość: 7 (logarytmiczna), 18x AND, 6x OR, 7x XOR, 31 bramek (liniowy)

Pozwól mi obliczyć sumę cyfr w bazie czwartej, modulo trzy:

_{obwód narysowany w Logisim}

Uogólnienie, formalnie (mam nadzieję, że w pewnym stopniu czytelne):

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

teraz w języku angielskim:

Chociaż liczba zawiera więcej niż dwa bity, weź dwie najniższe pary bitów i zsumuj je modulo 3, a następnie dołącz wynik z tyłu liczby, a następnie zwróć, jeśli ostatnia para ma zero modulo 3. Jeśli jest nieparzysta liczbę bitów w liczbie, dodaj dodatkowy zero bitów na górę, a następnie wypoleruj ze stałą propagacją wartości.

Dołączenie do tyłu zamiast do przodu zapewnia, że ​​drzewo dodatków jest zrównoważonym drzewem, a nie połączoną listą. To z kolei zapewnia głębokość logarytmiczną w liczbie bitów: pięć bramek i trzy poziomy anulowania pary oraz dodatkowa bramka na końcu.

Oczywiście, jeśli pożądana jest przybliżona płaskość, przepuść górną parę niezmodyfikowaną do następnej warstwy zamiast owijać ją do przodu. Łatwiej to jednak powiedzieć niż zaimplementować (nawet w pseudokodzie). Jeśli liczba bitów w liczbie jest potęgą dwóch (jak to jest w każdym nowoczesnym systemie komputerowym od marca 2014 r.), Nie wystąpią jednak żadne pojedyncze pary.

Jeśli router układający zachowuje lokalizację / wykonuje minimalizację długości trasy, powinien zachować czytelność obwodu.

Ten kod Ruby wygeneruje schemat połączeń dla dowolnej liczby bitów (nawet jednego). Aby wydrukować, otwórz w Logisim i wyeksportuj jako obraz:

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"

na koniec, gdy poproszono mnie o utworzenie wyjścia dla 32 bitów, mój Layouter generuje to. Trzeba przyznać, że nie jest bardzo kompaktowy dla bardzo szerokich wejść:

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

To całkowicie się nie skaluje. Wcale nie. Może spróbuję to poprawić.

Testowałem to dla liczb do 30 i działało dobrze.

Te 2 duże obwody liczą liczbę aktywnych wejść:

• W prawym górnym rogu zliczana jest liczba bitów o parzystej mocy (od zera do 4)
• Lewy dolny zlicza liczbę bitów o nieparzystej mocy (od zera do 4)

Jeśli różnica tych liczb jest 0lub 3liczba jest podzielna przez 3. Im niższy obwód tuż zasadzie odwzorowuje każdą poprawną kombinację ( 4,4, 4,1, 3,3, 3,0, 2, 2, 1, 1, 0, 0) na OR.

Małe kółko na środku to dioda LED, która świeci się, jeśli liczba jest podzielna przez 3, a w przeciwnym razie zgaśnie.