Fixing the Multiplication Algorithm
When I tried to implement the multiplication scheme I described
earlier, I found that it didn't work properly. It turns out my
assumption that shifting the product right would be equivalent to
shifting the multiplier left is not quite true.
To see the problem, let's do this example again using the product-shifting technique:
0.75 * 0.6875 = 0.515625
The initial S-register and Multiplier values are:
17 16 15 14 13 12
S Register: 0. 1 1 0 0 0 ...
Multiplier: 0. 1 0 1 1 0 ...
The product register is zero until multiplication step 15, where the multiplier is added to it for the first time.
Product: 0. 0 0 0 0 0 ...
Multiplier: 0. 1 0 1 1 0 ...
---------------------
New Product: 0. 1 0 1 1 0 ...
The product is then shifted right and the multiplier is added to it again.
Shifted Product: 0. 0 1 0 1 1 0 ...
Multiplier: 0. 1 0 1 1 0 0 ...
------------------------
New Product: 1. 0 0 0 0 1 0 ...
Note that the sign bit of the product is now 1. However, the product is not
negative -- it can't be, since it was obtained by adding two positive
numbers! If we continue and perform the final step of the
multiplication, the product register is shifted right again with sign
extension and we obtain a negative result, which is incorrect.
Final Product: 1. 1 0 0 0 0 1 0 ... Wrong
In essence, the problem is that the product register overflows. To
avoid this, we need an extra bit of precision on the left, between the
binary point and the sign bit. Here's how that looks:
17 16 15 14 13 12 11
S Register: 0 0. 1 1 0 0 0 ...
Multiplier: 0 0. 1 0 1 1 0 ...
Product: 0 0. 0 0 0 0 0 ...
Multiplier: 0 0. 1 0 1 1 0 ...
------------------------
New Product: 0 0. 1 0 1 1 0 ...
Shifted Product: 0 0. 0 1 0 1 1 0 ...
Multiplier: 0 0. 1 0 1 1 0 0 ...
---------------------------
New Product: 0 1. 0 0 0 0 1 0 ...
Final Product: 0 0. 1 0 0 0 0 1 0 ...
Moving the Unused Bit (Again)
To provide the required extra bit of precision in the product register,
I've decided to move the unused bit back to the most significant
end. The reason I moved it before -- to get the final product aligned
correctly -- turns out not to be a problem as long as multiplication is
stopped once the sign bit (now the next-most-significant bit) of the
multiplicand (in the S-register) has been processed.
So I have undone most of the modifications I made earlier to put the
unused bit at the least significant end. However, the ALU treats it as
an ordinary bit -- I am not forcing it to be equal to the sign bit as I
did before. That shouldn't be necessary, since they will end up equal
anyway unless an overflow occurs, and I may want to implement overflow
detection later by comparing them.
Revised ALU
In the process of updating the ALU I discovered some other mistakes
that were no doubt contributing to my messed-up multiplication results.
This is the new ALU subcircuit.
Revised Multiplication Step Counter
The MSC subcircuit now signals MLAST (last multiplication step) and
wraps to zero on T16 of MMSW (most significant word of multiplicand).
On the least significant word of the multiplicand, it wraps on T17.
Changes to Microcode Encoding
I discovered that encoding MMSW
and MLSW as values of the MISC field wasn't going to work, because I
need them both at once during a single word multiplication. I could
have used yet another MISC value to represent the combination, but I
realised a couple of things. I don't really need the MASEL field,
because it's only ever used during an instruction fetch, and FETCH is
never used together with any other MISC values. So I decided to
allocate a MISC value for FETCH, and use it to control both memory
address selection and PC incrementing, freeing up two microcode bits to
use for MMSW and MLSW. This also simplified some of the other logic a
bit, because MMSW and MLSW no longer need to imply RSH.
I also shuffled some of the microcode bits around, resulting in the following version of the main circuit.