Buat mesin tambah minifloat menggunakan gerbang logika NAND

15

Sebuah minifloat adalah representasi biner dari angka floating-point yang memiliki sangat sedikit bit.

Minifloat dalam pertanyaan ini akan didefinisikan sebagai angka 6-bit m, yang memiliki representasi berikut:

  • 1 bit untuk merepresentasikan tanda nomor. Bit ini akan menjadi 0jika jumlahnya positif, dan 1jika jumlahnya negatif.

  • 3 bit untuk mewakili eksponen angka, diimbangi oleh 3(yaitu eksponen 110sebenarnya mewakili faktor 2 3 , bukan 2 6 ).

    • Eksponen 000mengacu pada angka subnormal. Mantera mengacu pada bagian fraksional dari bilangan dengan bagian bilangan bulat 0dikalikan dengan faktor eksponen serendah mungkin (dalam hal ini, 2 -2 ).

  • 2 bit untuk mewakili mantissa nomor tersebut. Jika eksponen adalah selain dari 000atau 111, 2 bit mewakili bagian pecahan setelah a 1.

    • Eksponen 111mewakili infinityjika mantissa adalah 0, dan NaN(bukan angka) sebaliknya.

Dalam artikel Wikipedia, ini akan disebut sebagai minifloat (1.3.2.3).

Beberapa contoh representasi minifloat ini:

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

Tugas Anda adalah membangun jaringan gerbang NAND dua input yang mengambil 6 input mewakili minifloat adan 6 input mewakili minifloat b, dan mengembalikan 6 output yang mewakili minifloat a + b.

  • Jaringan Anda harus menambahkan subnormal dengan benar. Misalnya, 000001+ 000010harus sama 000011, dan 001001+ 000010= 001010.

  • Jaringan Anda harus menambah dan mengurangi infinitas dengan benar. Hingga apa pun yang ditambahkan ke tak terhingga adalah tak terhingga yang sama. Tak terhingga positif plus tak terhingga negatif NaN.

  • Nilai NaNtambah apa pun harus sama dengan NaN, meskipun NaNsama dengan Anda.

  • Bagaimana Anda menangani penambahan nol positif dan nol negatif satu sama lain terserah Anda, meskipun nol plus nol harus sama dengan nol.

Jaringan Anda dapat menerapkan aturan pembulatan berikut yang tergantung pada kenyamanan:

  • Round down (menuju infinity negatif)
  • Mengumpulkan (menuju infinity positif)
  • Bulat menuju nol
  • Membulatkan dari nol
  • Bulat ke terdekat, dengan setengah dibulatkan sesuai dengan salah satu aturan di atas

Untuk menyederhanakan hal-hal, Anda dapat menggunakan gerbang AND, ATAU, TIDAK, dan XOR dalam diagram Anda, dengan skor terkait berikut:

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

Masing-masing skor ini sesuai dengan jumlah gerbang NAND yang diperlukan untuk membangun gerbang yang sesuai.

Sirkuit logika yang menggunakan gerbang NAND paling sedikit untuk mengimplementasikan semua persyaratan di atas dengan benar akan menang.

atomic-code-golf logic-gates Joe Z.
sumber
2
Tantangan yang bagus - Saya harus serius memikirkan ini untuk mengimplementasikannya dalam kode, apalagi gerbang NAND.
Digital Trauma

Jawaban:

10

830 NANDs

Ini menggunakan 24 TIDAK, 145 AND, 128 OR, 33 XOR. Itu selalu membulat ke nol, mungkin mengembalikan -0 atau +0 untuk nilai nol, dan saya percaya itu memperlakukan Infinities dan NaNs dengan benar:

  • ± INF ± INF = ± INF
  • ± INF + NaN = ± INF
  • ± INF ∓ INF = NaN
  • ± INF + angka = ± INF
  • NaN + NaN = NaN
  • NaN + number = NaN

Di bawah ini saya memiliki representasi kode dari sirkuit. Saya memiliki sedikit pengalaman dalam menjelaskan hal-hal semacam ini, jadi saya tidak benar-benar tahu apa cara khas untuk melakukan ini, tetapi setiap variabel adalah Boolean sehingga jelas untuk melihat bahwa itu menggambarkan sebuah rangkaian. Hal lain, saya tidak memiliki pengetahuan atau keuletan untuk mencoba dan membuat diagram ini, tetapi jika ada perangkat lunak yang mudah digunakan di luar sana, ada yang ingin menunjukkan, saya akan tertarik untuk melihatnya.

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
sumber
Ketika sudah selesai, akankah ia membulatkan "ke bawah" ke nol atau ke arah infinity negatif? Hanya penasaran.
Joe Z.
@ Joz. Saya pasti akan mencoba untuk membuatnya mendekati nol, dan saya pikir melakukan itu seharusnya tidak menjadi masalah, meskipun saya tidak bisa memastikan tanpa menuliskannya. Jelas sepele untuk membuat ini menambahkan dua angka negatif (memiliki mereka membulatkan ke nol) jadi saya pikir mungkin akan lebih mudah untuk tetap dengan itu.
KSab
1
Dilakukan dengan baik untuk menghasilkan solusi lengkap. Ada beberapa optimisasi mudah. OR(AND(w,x),AND(y,z))adalah NAND(NAND(w,x),NAND(y,z))tabungan 4, dan Anda telah menggunakan konstruksi pertama beberapa kali; dan pengobatan NaN Anda sedikit salah karena Inf + NaNseharusnya NaN.
Peter Taylor