mac_5x9x8-Revised.md

@@ -5,6 +5,36 @@ $$B = \lceil\log_2(K * 2^M * 2^N)\rceil = \lceil\log_2 K\rceil + M + N$$
 
 For our specialized case of a 5x9x8 MAC unit, $\lceil\log_2 5\rceil + 9 + 8 = 20$ bits.
 
+
+
+I first attempted to use the modified Baugh-Wooley form on slide 64 of
+\url{https://web.ece.ucsb.edu/~parhami/pres_folder/f31-book-arith-pres-pt3.pdf} (a more clear representation of this method is shown at \url{https://en.wikipedia.org/wiki/Binary_multiplier#Signed_integers} with the exception of a missing 1 in the MSB of the last partial sum), but the modified Baugh-Wooley method only holds for the case where `N = M`.
+
+Instead, we will just sign extend and allow the synthesis tools to perform the optimizations later as this is all combinational logic and should be optimizable.
+
+For a given multiply:
+1) Sign extend the input `a` to the number of output bits, multiply by the bit in b, and shift.
+```
+p0 = a * b[0]
+p1 = a * b[1] << 1
+p2 = a * b[2] << 2
+p3 = a * b[3] << 3
+...
+```
+2) Because the last partial sum must be subtracted, invert the last partial sum and add a constant term of `(1 << M)`, then sum all the partial sums and the constant `(1 << M)`.
+
+Since we are performing K multiplies, the constants can be pre-added and simplified to `(K << M)`. Therefore, we have an addition of N*M+1 values, each the same length as the output of the MAC unit, with the last one being the constant `(K << M)` term.
+
+
+
+
+
+
+
+
+
+# First attempt that was very wrong since Baugh-Wooley requires N and M to be equal:
+
 First, to perform a signed multiplication, we use the modified Baugh-Wooley form on slide 64 of
 \url{https://web.ece.ucsb.edu/~parhami/pres_folder/f31-book-arith-pres-pt3.pdf}. A more clear representation of this method is shown at \url{https://en.wikipedia.org/wiki/Binary_multiplier#Signed_integers} with the exception of a missing 1 in the MSB of the last partial sum.