Close

Fixing the Multiplication Algorithm

A project log for BREDSAC

Electronic Dynamic Storage Breadboard Computer

gregewinggreg.ewing 11/11/2018 at 03:031 Comment

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.

Discussions

Yann Guidon / YGDES wrote 11/11/2018 at 03:19 point

Wow
That's quite a schematic !

  Are you sure? yes | no