## 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:

• Signed Radix-2 Booth multiplication

• Signed Radix-4 Booth multiplication

• Signed Radix-16 Booth multiplication

• Multiplexer based multiplication

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

# Signed Radix-2 Booth 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.

# Signed Radix-4 Booth multiplication

Bit grouping in Radix-4:

\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

# Signed Radix-16 Booth multiplication

Bit grouping in Radix-16:

\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
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.41678348183631897, "perplexity": 174.2916948359849}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 20, "end_threshold": 15, "enable": false}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2020-16/segments/1585371799447.70/warc/CC-MAIN-20200407121105-20200407151605-00215.warc.gz"}