Fast multiplication circuits

The operands are two signed 8-bit integers:

\begin{equation*} A = 77_{10} = 01001101_2 \end{equation*}
\begin{equation*} B = -92_{10} = 10100100_2 \end{equation*}

The multiplication we are looking for is signed 16-bit integer:

\begin{equation*} A \times B = 77_{10} \times -92_{10} = -7084_{10} = 1110010001010100_2 \end{equation*}

Or more verbosely:

 i 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Weight 32k 16k 8k 4k 2k 1k 512 256 128 64 32 16 8 4 2 1 A 0 1 0 0 1 1 0 1 B 1 0 1 0 0 1 0 0 A*B 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0

In the following chapters we show multiplication of the operands using various methods:

• Multiplexer based multiplication

Note that most modern processors use high-radix Booth algorithm to speed up the multiplication.

In Radix-2 Booth multiplication the bits are grouped in:

\begin{equation*} log_2{r} + 1 = log_2{2} + 1 = 1 + 1 = 2 \end{equation*}

We'll assume following selection table:

 a(i) a(i-1) D(i) 0 0 0 0 1 1 1 0 -1 1 1 0

Encoding the multiplier digits with the selection table results in high-radix multiplier:

 i 7 6 5 4 3 2 1 0 Weight 128 64 32 16 8 4 2 1 B 1 0 1 0 0 1 0 0 D(0) 0 0 D(1) 0 0 D(2) 1 0 D(3) 0 1 D(4) 0 0 D(5) 1 0 D(6) 0 1 D(7) 1 0 D -1 1 -1 0 1 -1 0 0

All possible variations of the multiplicand A can be precalculated in hardware using bit shifting and addition:

 i 7 6 5 4 3 2 1 0 Weight 128 64 32 16 8 4 2 1 D(i)=0 0 0 0 0 0 0 0 0 D(i)=1 0 1 0 0 1 1 0 1 D(i)=-1 1 0 1 1 0 0 1 1

Multiplying A with encoded values of multiplier yields in:

 i 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Weight 32k 16k 8k 4k 2k 1k 512 256 128 64 32 16 8 4 2 1 A 0 1 0 0 1 1 0 1 D -1 1 -1 0 1 -1 0 0 Expl. Z1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +0 Z2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +0 Z3 1 1 1 1 1 1 1 0 1 1 0 0 1 1 -A<<2 Z4 0 0 0 0 0 0 1 0 0 1 1 0 1 +A<<3 Z5 0 0 0 0 0 0 0 0 0 0 0 0 +0 Z6 1 1 1 1 0 1 1 0 0 1 1 -A<<5 Z7 0 0 0 1 0 0 1 1 0 1 +A<<6 Z8 1 1 0 1 1 0 0 1 1 -A<<7 Sum 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0

Steps explained:

• Z1 - Ignore, since D(0) is zero

• Z2 - Ignore, since D(1) is zero

• Z3 - Subtract A shifted left by 2 bits since D(2) is -1

• Z4 - Add A shifted left by 3 bits since D(3) is 1

• Z5 - Ignore, since D(4) is zero

• Z6 - Subtract A shifted left by 5 bits since D(5) is -1

• Z7 - Add A shifted left by 6 bits since D(6) is 1

• Z8 - Subtract A shifted left by 7 bits since D(7) is -1

The steps can also easily be verified on a Python command line:

>>> A=77
>>> B=-92
>>> A*B
-7084
>>> -(A<<2)+(A<<3)-(A<<5)+(A<<6)-(A<<7)
-7084

Thus encoding multiplicand (B) digits with Booth encoding (D) we can drastically simplify multiplication on a modern processor since bit shift is inexpensive operation which in circuit can be implemented with zero delay.

\begin{equation*} log_2{r} + 1 = log_2{4} + 1 = 2 + 1 = 3 \end{equation*}

Selector table:

 a(i+1) a(i) a(i-1) D(i) 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0

Encoding the multiplier digits yields in:

 i 7 6 5 4 3 2 1 0 Weight 128 64 32 16 8 4 2 1 B 1 0 1 0 0 1 0 0 D(0) 0 0 0 D(2) 0 1 0 D(4) 1 0 0 D(6) 1 0 1 D -1 -2 1 0

Precalculate possible variations of the multiplicand A:

 i 8 7 6 5 4 3 2 1 0 Weight 256 128 64 32 16 8 4 2 1 D(i)=0 0 0 0 0 0 0 0 0 0 D(i)=1 0 0 1 0 0 1 1 0 1 D(i)=2 0 1 0 0 1 1 0 1 0 D(i)=-1 1 1 0 1 1 0 0 1 1 D(i)=-2 1 0 1 1 0 0 1 1 0

Multiplying A with encoded values of multiplier yields in:

 i 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Weight 32k 16k 8k 4k 2k 1k 512 256 128 64 32 16 8 4 2 1 A 0 1 0 0 1 1 0 1 D -1 -2 1 0 Expl. Z1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 +0 Z2 0 0 0 0 0 0 0 1 0 0 1 1 0 1 +A<<2 Z3 1 1 1 1 0 1 1 0 0 1 1 0 -2A<<4 Z4 1 1 1 0 1 1 0 0 1 1 -A<<6 A*B 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0

Steps explained:

• Z1 - Ignore, since D(0) is zero

• Z2 - Add A shifted left by 2 bits

• Z3 - Subtract 2 times A shifted left by 4 bits

• Z4 - Subtract A shifted left by 6 bits

Again we can easily verify that the steps used were correct:

>>> A=77
>>> B=-92
>>> A*B
-7084
>>> (A<<2) -((2*A)<<4) - (A<<6)
-7084

\begin{equation*} log_2{r} + 1 = log_2{16} + 1 = 4 + 1 = 5 \end{equation*}

Selector table:

 a(i+3) a(i+2) a(i+1) a(i) a(i-1) D(i) 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 1 0 0 0 1 1 2 0 0 1 0 0 2 0 0 1 0 1 3 0 0 1 1 0 3 0 0 1 1 1 4 0 1 0 0 0 4 0 1 0 0 1 5 0 1 0 1 0 5 0 1 0 1 1 6 0 1 1 0 0 6 0 1 1 0 1 7 0 1 1 1 0 7 0 1 1 1 1 8 1 0 0 0 0 -8 1 0 0 0 1 -7 1 0 0 1 0 -7 1 0 0 1 1 -6 1 0 1 0 0 -6 1 0 1 0 1 -5 1 0 1 1 0 -5 1 0 1 1 1 -4 1 1 0 0 0 -4 1 1 0 0 1 -3 1 1 0 1 0 -3 1 1 0 1 1 -2 1 1 1 0 0 -2 1 1 1 0 1 -1 1 1 1 1 0 -1 1 1 1 1 1 0

Encoding the multiplier digits yields in:

 i 7 6 5 4 3 2 1 0 Weight 128 64 32 16 8 4 2 1 B 1 0 1 0 0 1 0 0 D(0) 0 1 0 0 0 D(4) 1 0 1 0 0 D -6 4

Precalculate only interesting variations of the multiplicand A:

 i 9 8 7 6 5 4 3 2 1 0 Weight 512 256 128 64 32 16 8 4 2 1 D(i)=4 0 1 0 0 1 1 0 1 0 0 D(i)=-6 1 0 0 0 1 1 0 0 1 0

Multiplying A with encoded values of multiplier yields in:

 i 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Weight 32k 16k 8k 4k 2k 1k 512 256 128 64 32 16 8 4 2 1 A 0 1 0 0 1 1 0 1 D -6 4 Expl. Z1 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 0 +4A Z1 1 1 1 0 0 0 1 1 0 0 1 0 -6A<<4 A*B 1 1 1 0 0 1 0 0 0 1 0 1 0 1 0 0

Steps explained:

• Z1 - Add 4 times A

• Z2 - Subtract 6 times A shifted left by 4 bits

Again we can easily verify that the steps used were correct:

>>> A=77
>>> B=-92
>>> A*B
-7084
>>> (4*A)-((6*A)<<4)
-7084

Multiplexer based multiplication

In following multiplexer based solution signed integers are not supported, therefore we have to substitute the variables used earlier.

The operands are two unsigned 8-bit integers:

\begin{equation*} A = 77_{10} = 01001101_2 \end{equation*}
\begin{equation*} B = 164_{10} = 10100100_2 \end{equation*}

The multiplication we are looking for is unsigned 16-bit integer:

\begin{equation*} A \times B = 77_{10} \times 164_{10} = 12628_{10} = 0011000101010100_2 \end{equation*}

Multiplexer approach uses muxers to select either one of the operands and bit shift them on each step:

 i 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 Weight 32k 16k 8k 4k 2k 1k 512 256 128 64 32 16 8 4 2 1 A(i) 0 1 0 0 1 1 0 1 B(i) 1 0 1 0 0 1 0 0 A(i/2)&B(i/2) 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 Z1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Z2 0 0 0 0 0 0 0 0 0 0 0 0 0 1 Z3 0 0 0 0 0 0 0 0 0 0 1 0 0 Z4 0 0 0 0 0 0 0 0 0 0 0 0 Z5 0 0 0 0 0 0 0 1 1 0 1 Z6 0 0 0 0 1 0 0 1 0 0 Z7 0 0 1 0 0 1 1 0 1 Sum 0 0 1 1 0 0 0 1 0 1 0 1 0 1 0 0

Steps explained:

• A(i/2)&B(i/2) - Spread conjunction bits

• Z1 - Fill with zeroes, because A(1) = B(1) = 0

• Z2 - Sum bits of A and B ignoring carry bits, because A(2) = B(2) = 1

• Z3 - Use bits from B, because A(3) = 1 and B(3) = 0

• Z4 - Fill with zeroes, because A(4) = B(4) = 0

• Z5 - Sum bits of A and B ignoring carry bits, because A(5) = B(5) = 1

• Z6 - Use bits from B, because A(6) = 1 and B(6) = 0

• Z7 - Use bits from A, because A(7) = 0 and B(7) = 1

computer arithmetic TU Berlin