Erstellen Sie eine Minifloat-Addiermaschine mit NAND-Logikgattern

15

Ein Minifloat ist eine binäre Darstellung einer Gleitkommazahl mit sehr wenigen Bits.

Der Minifloat in dieser Frage wird als eine 6-Bit-Zahl mmit der folgenden Darstellung definiert:

  • 1 Bit zur Darstellung des Vorzeichens der Zahl. Dieses Bit wird angezeigt, 0wenn die Zahl positiv und 1die Zahl negativ ist.

  • 3 Bits zur Darstellung des Exponenten der Zahl, versetzt um 3(dh ein Exponent von 110repräsentiert tatsächlich einen Faktor von 2 3 , nicht 2 6 ).

    • Ein Exponent von 000bezieht sich auf eine subnormale Zahl. Die Mantisse bezieht sich auf den Bruchteil einer Zahl mit einem ganzzahligen Teil 0multipliziert mit einem Faktor des niedrigstmöglichen Exponenten (in diesem Fall 2 -2 ).

  • 2 Bits zur Darstellung der Mantisse der Zahl. Wenn der Exponent etwas anderes als 000oder ist 111, stellen die 2 Bits den Bruchteil nach a dar 1.

    • Ein Exponent von 111stellt dar, infinityob die Mantisse ist 0, und NaN(keine Zahl) sonst.

In dem Wikipedia-Artikel wird dies als (1.3.2.3) Minifloat bezeichnet.

Einige Beispiele für die Darstellung dieses Minifloats:

000000 =  0.00 = 0
000110 =  1.10 × 2^(1-3) = 0.375
001100 =  1.00 × 2^(3-3) = 1
011001 =  1.01 × 2^(6-3) = 10
011100 = infinity
011101 = NaN
100000 = -0.00 = -0
100011 = -0.11 × 2^(1-3) = -0.1875 (subnormal)
101011 = -1.11 × 2^(2-3) = -0.875
110100 = -1.00 × 2^(5-3) = -4
111100 = -infinity
111111 = NaN

Ihre Aufgabe ist es, ein Netzwerk von NAND-Gattern mit zwei Eingängen aufzubauen, das 6 Eingänge für einen Minifloat aund 6 Eingänge für einen Minifloat verwendet bund 6 Ausgänge für den Minifloat zurückgibt a + b.

  • Ihr Netzwerk muss ordnungsgemäß Subnormale hinzufügen. Zum Beispiel muss 000001+ 000010gleich 000011und 001001+ 000010= sein 001010.

  • Ihr Netzwerk muss Unendlichkeiten korrekt addieren und subtrahieren. Alles, was einer Unendlichkeit endlich hinzugefügt wird, ist dieselbe Unendlichkeit. Positive Unendlichkeit plus negative Unendlichkeit ist NaN.

  • Ein NaNPlus alles muss gleich ein NaN, obwohl NaNes gleich ist, liegt an Ihnen.

  • Wie Sie damit umgehen, positive und negative Nullen miteinander zu addieren, bleibt Ihnen überlassen, obwohl Null plus Null gleich Null sein müssen.

Ihr Netzwerk kann je nach Bedarf eine der folgenden Rundungsregeln implementieren:

  • Abrunden (gegen negative Unendlichkeit)
  • Aufrunden (gegen positive Unendlichkeit)
  • Runden Sie in Richtung Null
  • Rund weg von Null
  • Rundung auf den nächsten Wert, wobei die Hälften gemäß einer der oben genannten Regeln gerundet werden

Zur Vereinfachung können Sie in Ihrem Diagramm UND-, ODER-, NICHT- und XOR-Gatter mit den folgenden entsprechenden Ergebnissen verwenden:

  • NOT: 1
  • AND: 2
  • OR: 3
  • XOR: 4

Jede dieser Bewertungen entspricht der Anzahl der NAND-Gatter, die zum Aufbau des entsprechenden Gatters erforderlich sind.

Die Logikschaltung, die die wenigsten NAND-Gatter verwendet, um alle obigen Anforderungen korrekt zu implementieren, gewinnt.

atomic-code-golf logic-gates Joe Z.
quelle
2
Nette Herausforderung - ich müsste ernsthaft darüber nachdenken, um es in Code zu implementieren, geschweige denn NAND-Gatter.
Digital Trauma

Antworten:

10

830 NANDs

Es werden 24 NOTs, 145 ANDs, 128 ORs, 33 XORs verwendet. Es rundet immer in Richtung Null, es kann entweder -0 oder +0 für Nullwerte zurückgeben, und ich glaube, es behandelt Unendlichkeiten und NaNs korrekt:

  • ± INF ± INF = ± INF
  • ± INF + NaN = ± INF
  • ± INF ∓ INF = NaN
  • ± INF + Zahl = ± INF
  • NaN + NaN = NaN
  • NaN + Zahl = NaN

Unten habe ich eine codierte Darstellung der Schaltung. Ich habe wenig Erfahrung damit, diese Art von Dingen zu kommentieren, daher weiß ich nicht genau, wie das normalerweise gemacht wird, aber jede Variable ist ein Boolescher Wert. Es ist also klar, dass er eine Schaltung beschreibt. Eine andere Sache, ich habe weder das Know-how noch wahrscheinlich die Hartnäckigkeit, um zu versuchen, ein Diagramm davon zu erstellen, aber wenn es eine einfach zu verwendende Software gibt, auf die jemand hinweisen möchte, wäre ich daran interessiert, einen Blick darauf zu werfen.

a0,a1,a2,a3,a4,a5 = mini0
b0,b1,b2,b3,b4,b5 = mini1

neg = XOR(a0,b0)
nneg = NOT(neg)

na1 = NOT(a1)
na2 = NOT(a2)
na3 = NOT(a3)

a2_a3 = AND(a2,a3)
a2_na3 = AND(a2,na3)
na2_a3 = AND(na2,a3)
na2_na3 = AND(na2,na3)

a123 = AND(a1,a2_a3)
l0 = AND(a1,a2_na3)
l1 = AND(a1,na2_a3)
l2 = AND(a1,na2_na3)
l3 = AND(na1,a2_a3)
l4 = AND(na1,a2_na3)
l5 = AND(na1,na2_a3)
l6 = AND(na1,na2_na3)

a45 = OR(a4,a5)
a_nan = AND(a123,a45)
a_inf = AND(a123,NOT(a45))

m0 = l0
m1 = OR(l1,AND(l0,a4))
m2 = OR(l2,OR(AND(l1,a4),AND(l0,a5)))
m3 = OR(l3,OR(AND(l2,a4),AND(l1,a5)))
m4 = OR(l4,OR(AND(l3,a4),AND(l2,a5)))
m5 = OR(l5,OR(AND(l4,a4),AND(l3,a5)))
l5_l6 = OR(l5,l6)
m6 = OR(AND(l4,a5),AND(l5_l6,a4))
m7 = AND(l5_l6,a5)

nb1 = NOT(b1)
nb2 = NOT(b2)
nb3 = NOT(b3)

b2_b3 = AND(b2,b3)
b2_nb3 = AND(b2,nb3)
nb2_b3 = AND(nb2,b3)
nb2_nb3 = AND(nb2,nb3)

b123 = AND(b1,b2_b3)
k0 = AND(b1,b2_nb3)
k1 = AND(b1,nb2_b3)
k2 = AND(b1,nb2_nb3)
k3 = AND(nb1,b2_b3)
k4 = AND(nb1,b2_nb3)
k5 = AND(nb1,nb2_b3)
k6 = AND(nb1,nb2_nb3)

b45 = OR(b4,b5)
b_nan = AND(b123,b45)
b_inf = AND(b123,NOT(b45))  

n0 = k0
n1 = OR(k1,AND(k0,b4))
n2 = OR(k2,OR(AND(k1,b4),AND(k0,b5)))
n3 = OR(k3,OR(AND(k2,b4),AND(k1,b5)))
n4 = OR(k4,OR(AND(k3,b4),AND(k2,b5)))
n5 = OR(k5,OR(AND(k4,b4),AND(k3,b5)))
k5_k6 = OR(k5,k6)
n6 = OR(AND(k4,b5),AND(k5_k6,b4))
n7 = AND(k5_k6,b5)

first = n0,n1,n2,n3,n4,n5,n6,n7

i7 = n7
i6 = XOR(n6,n7)
carry_6 = OR(n6,n7)
i5 = XOR(n5,carry_6)
carry_5 = OR(n5,carry_6)
i4 = XOR(n4,carry_5)
carry_4 = OR(n4,carry_5)
i3 = XOR(n3,carry_4)
carry_3 = OR(n3,carry_4)
i2 = XOR(n2,carry_3)
carry_2 = OR(n2,carry_3)
i1 = XOR(n1,carry_2)
carry_1 = OR(n1,carry_2)
i0 = XOR(n0,carry_1)
i_sign = OR(n0,carry_1)

n7 = OR(AND(nneg,n7),AND(neg,i7))
n6 = OR(AND(nneg,n6),AND(neg,i6))
n5 = OR(AND(nneg,n5),AND(neg,i5))
n4 = OR(AND(nneg,n4),AND(neg,i4))
n3 = OR(AND(nneg,n3),AND(neg,i3))
n2 = OR(AND(nneg,n2),AND(neg,i2))
n1 = OR(AND(nneg,n1),AND(neg,i1))
n0 = OR(AND(nneg,n0),AND(neg,i0))
n_sign = AND(neg,i_sign)

r7 = XOR(m7,n7)
carry_7 = AND(m7,n7)
hr6 = XOR(m6,n6)
hcarry_6 = AND(m6,n6)
r6 = XOR(hr6,carry_7)
carry_6 = OR(hcarry_6,AND(hr6,carry_7))
hr5 = XOR(m5,n5)
hcarry_5 = AND(m5,n5)
r5 = XOR(hr5,carry_6)
carry_5 = OR(hcarry_5,AND(hr5,carry_6))
hr4 = XOR(m4,n4)
hcarry_4 = AND(m4,n4)
r4 = XOR(hr4,carry_5)
carry_4 = OR(hcarry_4,AND(hr4,carry_5))
hr3 = XOR(m3,n3)
hcarry_3 = AND(m3,n3)
r3 = XOR(hr3,carry_4)
carry_3 = OR(hcarry_3,AND(hr3,carry_4))
hr2 = XOR(m2,n2)
hcarry_2 = AND(m2,n2)
r2 = XOR(hr2,carry_3)
carry_2 = OR(hcarry_2,AND(hr2,carry_3))
hr1 = XOR(m1,n1)
hcarry_1 = AND(m1,n1)
r1 = XOR(hr1,carry_2)
carry_1 = OR(hcarry_1,AND(hr1,carry_2))
hr0 = XOR(m0,n0)
hcarry_0 = AND(m0,n0)
r0 = XOR(hr0,carry_1)
carry_0 = OR(hcarry_0,AND(hr0,carry_1))
r_sign = XOR(n_sign,carry_0)

s7 = r7
s6 = XOR(r6,r7)
carry_6 = OR(r6,r7)
s5 = XOR(r5,carry_6)
carry_5 = OR(r5,carry_6)
s4 = XOR(r4,carry_5)
carry_4 = OR(r4,carry_5)
s3 = XOR(r3,carry_4)
carry_3 = OR(r3,carry_4)
s2 = XOR(r2,carry_3)
carry_2 = OR(r2,carry_3)
s1 = XOR(r1,carry_2)
carry_1 = OR(r1,carry_2)
s0 = XOR(r0,carry_1)

n_r_sign = NOT(r_sign)
r0 = OR(AND(n_r_sign,r0),AND(r_sign,s0))
r1 = OR(AND(n_r_sign,r1),AND(r_sign,s1))
r2 = OR(AND(n_r_sign,r2),AND(r_sign,s2))
r3 = OR(AND(n_r_sign,r3),AND(r_sign,s3))
r4 = OR(AND(n_r_sign,r4),AND(r_sign,s4))
r5 = OR(AND(n_r_sign,r5),AND(r_sign,s5))
r6 = OR(AND(n_r_sign,r6),AND(r_sign,s6))
r7 = OR(AND(n_r_sign,r7),AND(r_sign,s7))

h0 = r0
rest = h0
h1 = AND(r1,NOT(rest))
rest = OR(rest,h1)
h2 = AND(r2,NOT(rest))
rest = OR(rest,h2)
h3 = AND(r3,NOT(rest))
rest = OR(rest,h3)
h4 = AND(r4,NOT(rest))
rest = OR(rest,h4)
h5 = AND(r5,NOT(rest))
rest = OR(rest,h5)
h6 = AND(r6,NOT(rest))
rest = OR(rest,h6)
h7 = AND(r7,NOT(rest))

e0 = OR(h0,OR(h1,h2))
e1 = OR(h0,OR(h3,h4))
e2 = OR(h1,OR(h3,h5))

ne0 = NOT(e0)
ne1 = NOT(e1)
ne2 = NOT(e2)

e0e1 = AND(e0,e1)
e0ne1 = AND(e0,ne1)
ne0e1 = AND(ne0,e1)
ne0ne1 = AND(ne0,ne1)

x0 = AND(e0e1,  ne2)
x1 = AND(e0ne1, e2 )
x2 = AND(e0ne1, ne2)
x3 = AND(ne0e1, e2 )
x4 = AND(ne0e1, ne2)
x5 = AND(ne0ne1,e2 )
x6 = AND(ne0ne1,ne2)

u0 = AND(x0,r1)
u1 = AND(x1,r2)
u2 = AND(x2,r3)
u3 = AND(x3,r4)
u4 = AND(x4,r5)
u5 = AND(x5,r6)
u6 = AND(x6,r6)

v0 = AND(x0,r2)
v1 = AND(x1,r3)
v2 = AND(x2,r4)
v3 = AND(x3,r5)
v4 = AND(x4,r6)
v5 = AND(x5,r7)
v6 = AND(x6,r7)

f0 = OR(u0,OR(u1,OR(u2,OR(u3,OR(u4,OR(u5,u6))))))
f1 = OR(v0,OR(v1,OR(v2,OR(v3,OR(v4,OR(v5,v6))))))
sign = XOR(a0,r_sign)

either_nan = OR(a_nan,b_nan)
either_inf = OR(a_inf,b_inf)
ans_nan = OR(AND(AND(a_inf,b_inf),XOR(a0,b0)),AND(NOT(either_inf),either_nan))
nans_nan = NOT(ans_nan)
ans_inf = AND(nans_nan,OR(either_nan,either_inf))
ans_none = AND(nans_nan,NOT(ans_inf))
nans_none = NOT(ans_none)

result0 = OR(OR(AND(a_inf,a0),AND(b_inf,b0)),AND(ans_none,sign))
result1 = OR( nans_none, AND(ans_none,e0) )
result2 = OR( nans_none, AND(ans_none,e1) )
result3 = OR( nans_none, AND(ans_none,e2) )
result4 = OR( ans_nan, AND(ans_none,f0) )
result5 = OR( ans_nan, AND(ans_none,f1) )
KSab
quelle
Wenn es fertig ist, wird es auf Null oder auf negative Unendlichkeit "abrunden"? Nur neugierig.
Joe Z.
@JoeZ. Ich werde auf jeden Fall versuchen, es auf Null zu bringen, und ich denke, dass dies kein Problem sein sollte, obwohl ich nicht sicher sein kann, ohne es aufzuschreiben. Es ist offensichtlich trivial, zwei negative Zahlen zu addieren (mit einer Rundung gegen Null), daher denke ich, dass es wahrscheinlich einfacher sein wird, sich daran zu halten.
KSab
1
Gut gemacht, um eine Komplettlösung zu finden. Es gibt einige einfache Optimierungen. OR(AND(w,x),AND(y,z))ist NAND(NAND(w,x),NAND(y,z))Spar 4, und Sie haben die erste Konstruktion ein paar Mal verwendet wird ; und Ihre NaN-Behandlung ist etwas falsch, weil Inf + NaNsollte sein NaN.
Peter Taylor