Radix 8-Multiplication is an extention of the normally implemented Radix-4 Multiplication (also known as Booth recoding).
Below is an example of Radix-4 Multiplication. The product (P), the intial A-input (A), and the last bit shifted out of A (L), can be thought of us one large shift register that is shifted right two bits (in Radix-4) on every iteration of the algorithm. For a four-bit multiplicand, we must shift right two times (4/2=2). During shifts and for generation of B-values, the product term is sign-extended to the left.
| Product | A-input | Last bit shifted out | B-input = 1011 |
| 00000 | 1001 | 0 | Multiply -7 = 1001 times -5 = 1011 |
| 11011 | Low order bits of A are 0, 1; L=0, so add B | ||
| 11011 | 1001 | 0 | |
| 11110 | 1110 | 0 | Shift right by two bits, shifring in 1s on the left. |
| 01010 | Low order bits of A are 1, 0; L=0, so add -2B | ||
| 01000 | 1110 | 0 | |
| 00010 | 0011 | 1 | Shift right by two bits. |
| Product is 35 = 0100011. |
For an 8-bit multiplicand, the above implementation of Radix-4 multiplication would take 4 full interations (we are limited by the number of bits we must shift). Radix-8 multiplication can reduce this number of iterations because each iteration shifts by 3 bits, reducing the number of iterations to 3.
Since we could not find the exact implementation of Radix-8 multiplication in the literature, we derived our own algorithm based on the descrition of lower-order Radix multiplication in Hennessy and Patterson. To this end, we were required to generate our own table of approprite B-values based on the last 3 digits of the A-input and the last bit carried out. These are:
| A_2 | A_1 | A_0 | L | Multiple of B |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 2 |
| 0 | 1 | 0 | 0 | 2 |
| 0 | 1 | 0 | 1 | 3 |
| 0 | 1 | 1 | 0 | 3 |
| 0 | 1 | 1 | 1 | 4 |
| 1 | 0 | 0 | 0 | -4 |
| 1 | 0 | 0 | 1 | -3 |
| 1 | 0 | 1 | 0 | -3 |
| 1 | 0 | 1 | 1 | -2 |
| 1 | 1 | 0 | 0 | -2 |
| 1 | 1 | 0 | 1 | -1 |
| 1 | 1 | 1 | 0 | -1 |
| 1 | 1 | 1 | 1 | 0 |
In order to verify our algorithm, Eric Johnson wrote a short C-program to check our results. The code can be found below:
Eric also decided to test the case in which we are multiplying the two greatest integers in a 9-bit by 9-bit multiplication, that is, 255 * 255, or -256 * -256. As a result of his testing, we were prompted to implement our adder as a 12-bit adder, in order to be able to handle generating 3B and -3B. This simple code can be found below: