Date: Wed, 10 Apr 2019 21:09:30 -0500
<br>
From: "Yale N. Patt" <patt@ece.utexas.edu>
<br>
To: a.deshmukh@utexas.edu, mohammadbehnia@utexas.edu, chestercai@utexas.edu
<br>
Subject: Ooops!
<br>
  After class, a student asked a question, which...
<br>
  Message-ID: <20190411020929.GG1791@ece.utexas.edu>
<br>
  MIME-Version: 1.0
<br>
  Content-Type: text/plain; charset=us-ascii
<br>
  Content-Disposition: inline
<br>
  User-Agent: Mutt/1.5.21 (2010-09-15)
<br>

<br>
  My students,
<br>

<br>
  After class, a student asked a question which made me realize that I made a
<br>
  mistake in what I told you today in explaining Boothe's algorithm.
<br>

<br>
  Ergo, this message to clear it up.  I can also talk about it on Monday if
<br>
  this email is not clear.
<br>

<br>
  The thing I messed up involved what to do if you see the two bits: 11.
<br>
  I said we subtract the mutliplicand, and then borrow 1 from the next two
<br>
  digits.
<br>

<br>
  WRONG! 
<br>

<br>
  Guess I should not sleep while I am teaching!  We do not borrow 1 from the
<br>
  next two bits, we ADD 1 to the next two bits.
<br>

<br>
  Why?
<br>

<br>
  When we see 11, we agreed that it says the multiplier bits = 3.  And we agreed
<br>
  that 3 = four minus 1.  Minus 1 means we subtract the multiplicand.  And "four"
<br>
  means we ADD 1 to the next two bits.  That is we are adding 1 AFTER shifting
<br>
  the multiplier by two bits.  "1" after shifting two bits is "4"
<br>

<br>
  Now let's look at the truth table that controls (a) the behavior of the shifter 
<br>
  before the ALU, (b) the ALU, and (c) the shifter after the ALU.
<br>

<br>
  Three inputs to the truth table: bit1, bit0 and c, where c is 1 if we need
<br>
  to add 1 from the previous two bits to what bit1 and bit0 produce.
<br>

<br>
  The state of these three inputs determine the three control fields: 
<br>

<br>
  the shift before the ALU, 
<br>
  the ALU, and 
<br>
  the shift after the ALU.  
<br>

<br>
  Also, whether or not we need to add 1 to the next two bit quantity, 
<br>
  which I have labeled c'
<br>

<br>
  Notice that the output of 010 is the same as the output of 001.  "010" says
<br>
  we need to not shift before alu, ADD in alu, and shift 2 after ALU.
<br>

<br>
  "001" says the two bits are 00, but c=1 means we need to add 1 to 00, giving
<br>
  us effectively for that input combination the same output as "010."
<br>

<br>
  Recall from above that "110" says subtract the multiplicand but set c'=1,
<br>
  so that we will add 1 to the next two bits.
<br>

<br>
  Suppose we have three pairs of 11, that is: 11 11 11.  The right most 11 is 3,
<br>
  so we subtract 1 and set c'=1 so we know to add 1 to the next pair of bits.
<br>
  Since the middle two bits are 11, adding 1 them makes 00 with setting c'=1. The 
<br>
  resulting 00 means do nothing, but set c' to 1 again.  This in turn causes the
<br>
  left two bit (which are also 11) to be 00 and sets c'=1 again.  The net effect
<br>
  of all this is 111111 subtracts the multiplican, and then adds 1 to the twobit
<br>
  pair six digits to the left.  That is correct since  111111 = 64 - 1.
<br>

<br>
  Also note, as expected that in addition to 010 and 001 causing the same outputs,
<br>
  100 and 011 cause the same outputs, 110 and 101 cause the same outputs.
<br>
  You see why that is the case?
<br>

<br>
  Anyhow, again, sorry I got it wrong in class and I am glad I was able to catch
<br>
  it quickly after class and can send you this note.
<br>

<br>
  Yale Patt