Zbuduj maszynę dodającą minifloat za pomocą bramek logicznych NAND

15

Minifloat jest binarna reprezentacja liczby zmiennoprzecinkowej, że ma bardzo mało bitów.

Minifloat w tym pytaniu zostanie zdefiniowany jako liczba 6-bitowa m, która ma następującą reprezentację:

  • 1 bit, aby powtórzyć znak liczby. Ten bit będzie, 0jeśli liczba jest dodatnia, a 1jeśli liczba jest ujemna.

  • 3 bity reprezentujące wykładnik liczby, przesunięty o 3(tzn. Wykładnik 110faktycznie reprezentuje współczynnik 2 3 , a nie 2 6 ).

    • Wykładnik liczby 000odnosi się do liczby nienormalnej. Mantysa odnosi się do części ułamkowej liczby z częścią całkowitą 0pomnożoną przez współczynnik najniższego możliwego wykładnika (w tym przypadku 2 -2 ).
  • 2 bity reprezentujące mantysę liczby. Jeśli wykładnik jest inny niż 000lub 111, 2 bity reprezentują część ułamkową po a 1.

    • Wykładnik 111reprezentuje, infinityczy mantysa jest 0, i NaN(nie jest liczbą) inaczej.

W artykule w Wikipedii byłoby to określane jako minifloat (1.3.2.3).

Kilka przykładów tego minifloata:

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

Twoim zadaniem jest zbudowanie sieci dwuwejściowych bramek NAND, która pobiera 6 danych wejściowych reprezentujących minifloat ai 6 danych wejściowych minifloat bi zwraca 6 wyników reprezentujących minifloat a + b.

  • Twoja sieć musi poprawnie dodawać subnormalne. Na przykład 000001+ 000010musi być równy 000011, a 001001+ 000010= 001010.

  • Twoja sieć musi poprawnie dodawać i odejmować nieskończoności. Wszystko, co dodane do nieskończoności, jest tą samą nieskończonością. Dodatnia nieskończoność plus ujemna nieskończoność to NaN.

  • NaNCokolwiek Plus musi być równa NaN, chociaż który NaNto równa jest do ciebie.

  • To, jak sobie poradzisz, dodając do siebie dodatnie zero i ujemne zero, zależy od ciebie, chociaż zero plus zero musi być równe zero.

Twoja sieć może wdrożyć dowolną z następujących zasad zaokrąglania w zależności od wygody:

  • Zaokrąglaj w dół (w kierunku ujemnej nieskończoności)
  • Zaokrąglaj w górę (w kierunku dodatniej nieskończoności)
  • Zaokrąglić w kierunku zera
  • Zaokrąglić od zera
  • Zaokrąglaj do najbliższego, z połówkami zaokrąglonymi zgodnie z dowolną z powyższych zasad

Aby uprościć rzeczy, możesz użyć bramek AND, OR, NOT i XOR na diagramie z następującymi odpowiednimi wynikami:

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

Każda z tych ocen odpowiada liczbie bramek NAND potrzebnych do zbudowania odpowiedniej bramki.

Wygrywa obwód logiczny, który używa najmniejszej liczby bramek NAND do prawidłowego wdrożenia wszystkich powyższych wymagań.

Joe Z.
źródło
2
Niezłe wyzwanie - musiałbym poważnie się nad tym zastanowić, aby zaimplementować go w kodzie, nie mówiąc już o bramkach NAND.
Cyfrowa trauma

Odpowiedzi:

10

830 NAND

Wykorzystuje 24 NOT, 145 AND, 128 OR, 33 XOR. Zawsze zaokrągla się do zera, może zwrócić albo 0, albo 0 dla wartości zerowych i uważam, że poprawnie traktuje Infinities i NaN:

  • ± INF ± INF = ± INF
  • ± INF + NaN = ± INF
  • ± INF ∓ INF = NaN
  • ± INF + liczba = ± INF
  • NaN + NaN = NaN
  • NaN + liczba = NaN

Poniżej mam zakodowaną reprezentację obwodu. Mam niewielkie doświadczenie w opisywaniu tego typu rzeczy, więc tak naprawdę nie wiem, jaki jest typowy sposób, aby to zrobić, ale każda zmienna jest wartością logiczną, więc widać, że opisuje ona obwód. Inna sprawa, nie mam ani wiedzy, ani prawdopodobnie nieustępliwości, aby spróbować sporządzić schemat tego, ale jeśli istnieje jakieś łatwe w użyciu oprogramowanie, ktoś chciałby zwrócić uwagę, że byłbym zainteresowany.

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
źródło
Czy po zakończeniu będzie zaokrąglać „w dół” w kierunku zera lub w kierunku ujemnej nieskończoności? Po prostu ciekawy.
Joe Z.
@JoeZ. Na pewno postaram się zbliżyć do zera i uważam, że nie powinno to stanowić problemu, choć nie jestem pewien, czy nie wypiszę tego. Dodanie dwóch liczb ujemnych (zaokrąglenie ich do zera) jest oczywiście trywialne, więc myślę, że łatwiej będzie się z tym trzymać.
KSab
1
Dobra robota, jeśli chodzi o opracowanie kompletnego rozwiązania. Istnieje kilka łatwych optymalizacji. OR(AND(w,x),AND(y,z))jest NAND(NAND(w,x),NAND(y,z))oszczędność 4 i użyłeś pierwsza konstrukcja kilka razy; a twoje leczenie NaN jest nieco niewłaściwe, ponieważ Inf + NaNpowinno być NaN.
Peter Taylor,