Построить машину добавления минифлота с использованием логических элементов NAND

15

Minifloat является двоичным представлением числа с плавающей точкой , которая имеет очень мало бит.

Минифлоат в этом вопросе будет определен как 6-битное число m, которое имеет следующее представление:

  • 1 бит для представления знака числа. Этот бит будет, 0если число положительное, и 1если число отрицательное.

  • 3 бита для представления степени числа, смещенной на 3(т.е. показатель степени 110фактически представляет коэффициент 2 3 , а не 2 6 ).

    • Показатель 000относится к субнормальному числу. Мантисса относится к дробной части числа с целой частью, 0умноженной на коэффициент наименьшего возможного показателя степени (в данном случае 2 -2 ).

  • 2 бита для представления мантиссы числа. Если показатель степени отличается от 000или 111, 2 бита представляют дробную часть после a 1.

    • Показатель степени 111представляет, infinityесли мантисса есть 0, и NaN(не число) в противном случае.

В статье Википедии это будет упоминаться как (1.3.2.3) мини-поплавок.

Некоторые примеры представления этого минифлота:

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

Ваша задача - построить сеть из двух входных вентилей NAND, которая принимает 6 входов, представляющих мини-поплавок, aи 6 входов, представляющих мини-поплавок b, и возвращает 6 выходов, представляющих мини-поплавок a + b.

  • Ваша сеть должна правильно добавлять субнормалы. Например, 000001+ 000010должен равняться 000011, а 001001+ 000010= 001010.

  • Ваша сеть должна правильно складывать и вычитать бесконечности. Все конечное, добавленное к бесконечности, является той же бесконечностью. Положительная бесконечность плюс отрицательная бесконечность NaN.

  • NaNПлюс что - то должно равняться NaN, хотя , который NaNона равна до вас.

  • Как вы справляетесь с добавлением положительного нуля и отрицательного нуля друг к другу, зависит от вас, хотя ноль плюс ноль должны равняться нулю.

Ваша сеть может реализовать любое из следующих правил округления в зависимости от удобства:

  • Округление вниз (к отрицательной бесконечности)
  • Округление вверх (к положительной бесконечности)
  • Круглый к нулю
  • Округлить от нуля
  • Округление до ближайшего, с половинами, округленными в соответствии с любым из вышеуказанных правил

Для упрощения вы можете использовать логические элементы И, ИЛИ, НЕ и XOR на вашей диаграмме со следующими соответствующими показателями:

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

Каждый из этих баллов соответствует количеству вентилей NAND, необходимых для построения соответствующих вентилей.

Логическая схема, которая использует наименьшее количество вентилей NAND для правильной реализации всех вышеперечисленных требований, выигрывает.

atomic-code-golf logic-gates Джо З.
источник
2
Хороший вызов - мне нужно серьезно подумать об этом, чтобы реализовать его в коде, не говоря уже о NAND-шлюзах.
Цифровая травма

Ответы:

10

830 NANDS

Он использует 24 NOT, 145 AND, 128 OR, 33 XOR. Он всегда округляется до нуля, может возвращать либо -0, либо +0 для нулевых значений, и я считаю, что он правильно обрабатывает бесконечность и NaN:

  • ± INF ± INF = ± INF
  • ± INF + NaN = ± INF
  • ± INF ∓ INF = NaN
  • ± INF + число = ± INF
  • NaN + NaN = NaN
  • NaN + число = NaN

Ниже у меня есть закодированное представление схемы. У меня мало опыта в аннотировании этих типов вещей, поэтому я не знаю, каков типичный способ сделать это, но каждая переменная является булевой, поэтому ясно, что она описывает схему. Другое дело, у меня нет ни ноу-хау, ни, вероятно, упорства, чтобы попытаться составить диаграмму этого, но если есть какое-то простое в использовании программное обеспечение, кто-нибудь хочет указать, мне было бы интересно взглянуть.

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
источник
Когда это закончится, будет ли оно округлено «вниз» к нулю или к отрицательной бесконечности? Просто любопытно.
Джо З.
@JoeZ. Я определенно постараюсь сделать это до нуля, и я думаю, что это не должно быть проблемой, хотя я не могу быть уверен, не выписав это. Очевидно, тривиально, чтобы это добавило два отрицательных числа (с округлением их в сторону нуля), поэтому я думаю, что, вероятно, будет легче придерживаться этого.
KSab
1
Молодцы, что нашли полное решение. Есть несколько простых оптимизаций. OR(AND(w,x),AND(y,z))является NAND(NAND(w,x),NAND(y,z))сохранение 4, и вы использовали первую конструкцию несколько раз; и ваше лечение NaN немного неправильно, потому что Inf + NaNдолжно быть NaN.
Питер Тейлор