dark

Hardware Multiplication and Division

admin
2022-01-13 14:18:10
Hardware Multiplication and Division

Algorithm

The secret to implementing hardware multiplication and division is to regress -- specifically, regress back to elementary / primary school when you first learned how to perform multiplication and division with multiple digits as inputs. Stuff like this:

432 20 R 12 x 21 _________ ----- 21 / 432 432 -42 +864 -- ----- 12 9072 - 0 -- 12The exact same algorithm works in any base, including base 2 (binary). The advantage is that you only need to perform one addition operation for each digit in the input. For example:

15 = 0000 1111 7 = 0000 0111 0010 R 1 __________ 0000 1111 0000 0111 / 0000 1111 x 0000 0111 -0 ---------------- -- 0000 1111 11 + 0 0001 111 -- ---------------- -0 0 0010 1101 -- + 00 0011 11 111 ---------------- -111 00 0110 1001 = 105 --- 0001 - 0 ---- 1In short, you can multiply or divide any 8 digit binary numbers with only 8 additions -- if you are clever, of course. :)

Multiplication Psedo-Code

Given: Two inputs, A and B.

For each of the bit in A (8 bits in the LEX architecture) do the following, starting with the least significant bit (the value in the 1s place).

Convert the bit into a byte where all the bits have the same value as the input bit. For example, with 8 bit inputs, 1 = 1111 1111.

AND the mask from the previous step with B. Yes, "B" is used, without modification, 8 times.

Shift the result of the previous step to the left by one place for each bit processed. That is, the first bit (the least significant bit or LSB), doesn't change (it shifts 0 places), the next bit will be shifted left once, the third bit shifts twice, and so forth until the 8th bit is shifted 7 places.If desired, capture the bits that shift off to the left (overflow) to populate a new byte.Add this number to the running total of the previous steps.If you are accumulating the overflow bits in another byte, you'll need two adders, connected via the carry bit.

Once all bits of A have been processed the running total will contain the result of the multiplication.

Division Psedo-Code

In multiplication, the inputs are interchangeable -- A * B = B * A. This isn't true for division. Thus, the two numbers in this section will be called divisor (D) and dividend (N). Also, since we need to do subtraction, one bit of the input values must be reserved for the sign -- so, using the standard LEX architecture, we can only divide 7-bit positive numbers.

Before we do anything else, negate the divisor (D). For all of the following steps, this negated divisor will be used (and the psedo-code will reference addition rather than subtraction).

For each bit in the dividend (N), perform the following steps, starting with the most significant bit:Add D to the remainder from the previous iteration (in the first iteration, this will be zero).

If the result of this is negative, note this (it will be used later).

If the result of the addition is negative, discard the result of the addition -- instead, use the remainder from the previous iteration (one of the inputs into the addition in step #1).

Shift the result to the left by one, filling in the least significant bit with the next bit in the dividend (N). The result will be the remainder to feed into the next iteration.Note that the MSB never gets used -- the first bit that actually feeds into the circuit is the "MSB-1" bit.

That's because the MSB is used to store sign information.The negated results that you collected in step #2 above are the bits of quotient, with the MSB being the results of the first iteration, and the LSB being the result of the last iteration. The remainder output by the last iteration, after shifting right once, is the remainder of the overall division.

NotesTo accurately calculate the result using the above algorithm, you'll need to perform the above 8 times, even though the result cannot contain more than 7 bits. You can simplify the circuit a bit by eliminating steps 1-3 for the first iteration and simply fixing the MSB of the quotient as 0. The example below doesn't do this -- the advantage is that it produces some sort of result if a negative number is fed in for the dividend, but its the wrong result... :)

If you really want to divide 8 bit numbers, you could implement a hardware subtract -- it accepts in two unsigned 8 bit numbers, adds a temporary 9th bit to both, negates the second number (using the 9th bit for sign), performs the addition across all 9 bits, then returns the 8 least significant bits of the result. It should be reasonably simple to implement -- but I haven't tried it.

The last (8th) iteration won't have a bit in the dividend to use to "fill" in the empty bits after the shift left operation. That's fine -- this value will be shifted right once to produce the remainder of the overall calculation.No, you can't simply put the shift left at the beginning of the algorithm -- if the result of the addition isn't negative, you'll shift that value left rather than the remainder from the previous step.

Multiplication Circuit


Hardware Multiplication and Division image 23

Note that this uses four custom components:A shift left component.

A shift right component.

A "Bit-Byte AND", that takes a single bit as input, converts it to "1111 1111" or "0000 0000", then ANDs that value with the byte provided.

A double adder (that can add 2 bytes together).It outputs two bytes, the LSB and MSB of the result of the multiplication. For ease of implementation within the LEX architecture, you can discard the results of the MSB -- with the downside that multiplications with more than 8 bits of input (spread across both operands) will overflow and the results of the multiplication will be inaccurate.

The right shift custom operator isn't really necessary -- it could be replaced with a byte -> 8 bit component, then wiring the individual bits to the correct places.

Oddly, this circuit is very inefficient compared to the two byte multiply that the game gives you when you complete the "Multiply" level -- that multiplier is delay 292 / NAND 1168, while the shown implementation is delay 1348 / NAND 2704. Something seems stinky here -- the double adders make up the bulk of the cost (at 368 NAND / 192 delay, x7), but they consist of nothing more than two ADD components (connected via the carry bit. Maybe there is some really, really clever way to eliminate half of the adders while retaining 2 bytes of output percision, but I think the developer has the cost wrong on the built-in multiply component. :)

Division Circuit


Hardware Multiplication and Division image 31
Hardware Multiplication and Division image 32

OK, that isn't all that helpful. :)

This uses three custom components:"Is Neg" simply returns true if the MSB is set (128). I go ahead and invert it here, because it needs to be inverted to generate the quotient.

"Shift left and Fill" shifts the input (lower right hand corner) to the left by one, setting the LSB to the value provided in the upper right hand input. The lower right hand output contains the result, and the upper right hand output will be set if overflow occurred.

Interestingly, this divide component can't used to pass the level "Divide" -- the first problem that comes up when I load the level is "82 / 219", and this circuit can't handle "219" as an input. So, if you actually want to use this component on the one puzzle in the game that actually calls for division, you'll need to change it to handle unsigned 8-bit integers. :)

Source: https://steamcommunity.com/sharedfiles/filedetails/?id=2717768140

More Turing Complete guilds

⮙