# Binary Multiplication **The multiplication of binary numbers.** The results table of *binary digit multiplication* is equivalent to the truth table of [[Conjunction|logical conjunction]]. | $a\times b$ | $b=0$ | $b=1$ | |:-----------:|:-----:|:-----:| | $a=0$ | $0$ | $0$ | | $a=1$ | $0$ | $1$ | As in decimal multiplication, *partial products* are calculated then summed up for the result. In binary multiplication, partial products are either *all zero* or the same as the *multiplicand*. An $m$ digit *multiplicand* by $n$ digit *multiplier* multiplication generates *up to* an $m+n$ digit result. > [!Example]- > The following is the computation of $11\times 14=154$. > > ![[BinaryMultiplicationUnsigned.svg]] *Multiplying* a number by $2^{k}$ shifts the number to the *left* by $k$ bits. *Dividing* a number by $2^{k}$ shifts the number to the *right* by $k$ bits. ## Signed 2's complement multiplication In [[Signed Binary Number#Signed 2's complement|signed 2's complement]] multiplication, the multiplicand, multiplier, and all partial products must be [[Signed Binary Number#Sign extension|sign extended]] to the *product bit width* $m + n$. The result is also only read up to the product bit width. Multiplication by a *positive* value creates a shorter computation overall. ![[BinaryMultiplicationSignedComparison.svg]] *The computation of $-6\times-7$ without and with sign extension; under sign extension the result is only read up to $4+4=8$ bits* ## Implementation ### Unsigned multiplication #### Adder tree A simple but slow implementation of unsigned binary multiplication is an [[adder]] tree. Partial products are formed using $m\times n$ AND gates. They are then summed to form the result using adders. $n-1$ adders of $m$ bit width are required. The first adder receives an additional *zero* input since the *least significant bit* of the first partial product is taken as part of the result. It is appended to the *front* of the first partial product. Each successive adder does not receive the least significant bit of the previous partial product summation. Below is a 4-bit by 4-bit binary multiplier implemented by an adder tree. ![[BinaryMultiplicationAdderTree.svg]] #### Iterative array Binary multiplication can also be implemented as an [[Iterative Circuit|iterative array]], which is a faster method. Each *cell* of the array receives a carry-in and a single bit of the *incoming* partial product sum (PPS), the multiplicand $m$, and the multiplier $n$. It computes the *current* partial product then adds it to the *partial product sum*. ^08a9d1 The first row of the array receives a *zero* input as the *incoming* partial product. The right-most cells also receive a *zero* input as the *carry-in*. ![[BinaryMultiplicationArrayCell.svg]] ![[BinaryMultiplicationArray.svg]] *An individual cell (above) and combined iterative array (below) implementing a 4-bit by 4-bit multiplier* ### Signed 2's complement multiplication #### Baugh-Wooley algorithm Signed 2's complement multiplication can be implemented using the [[Baugh-Wooley algorithm]] in an [[Iterative Circuit|iterative array]]. There are two types of *cells* used in the array. The majority of the cells are the same as the cells used in the *previous* array circuit, whilst the remaining cells use the *complement* of the multiplication of input bits. These complement cells replace the AND gate with a NAND gate and are used when $i=n-1$ or $j=n-1$ but not both. The cells of the first column and the first row accept a *zero* for its *sum input*. The cells of the first row also accept a *zero* for its *carry-in*. The final row consists of [[Adder#Full adder|full adders]]. The full adders accept an *input* number from the cell to its *top right* and a *"carry-in"* [^1] from both the adder to its *right* and the cell *above*. Below is a 4-bit by 4-bit Baugh-Wooley multiplier implemented by an iterative array. The two types of cells are also shown. >[!Implementation from the formula]- > The product of two 4 bit numbers can be written as > $\begin{align*} P={}&a_{3}b_{3}2^{6}+\sum_{i=0}^{2}\sum_{j=0}^{2}a_{i}b_{j}2^{i+j}+ \\ &2^{3}\sum_{i=0}^{2}\overline{a_{i}b_{3}}2^{i}+2^{3}\sum_{j=0}^{2}\overline{a_{3}b_{j}}2^{j} \\ &-2^{7}+2^{4} \end{align*}$ > The first term, $a_{3}b_{3}2^{6}$, is calculated by the *non-complemented* cell in the *bottom left*. > > Each term of the double sum $\sum_{i=0}^{2}\sum_{j=0}^{2}a_{i}b_{j}2^{i+j}$ > is calculated by the non-complemented cells in the *top right*. The products corresponding to each bit position $2^{i+j}$ is found *collectively* by the cells along a *diagonal* from the *top left to the bottom right*. > > The sums > $2^{3}\sum_{i=0}^{2}\overline{a_{i}b_{3}}2^{i}\quad\quad 2^{3}\sum_{j=0}^{2}\overline{a_{3}b_{j}}2^{j}$ > are calculated by the *complemented* cells in the *second last row* and *first column*, respectively. > > The terms $2^{7}$ and $2^{4}$ are added by the *one* input to the outer full adders of the last row. ![[BaughWooleyMultiplicationArrayCells.svg]] *The two types of cells used in a Baugh-Wooley multiplier* ![[BaughWooleyMultiplicationArray.svg]] *A 4-bit by 4-bit Baugh-Wooley multiplier* [^1]: Adders are typically considered to receive two input numbers. However, two of the inputs from the circuit are technically carry-outs from previous cells.