Welcome to the next post in my series on binary numbers and binary arithmetic. In todays post we’re again going to build on what we have learnt in my previous posts on binary addition and binary subtraction and see how we can perform multiplication in binary.
Terminology
Before we dive in, I first wanted to take a moment to establish some terminology. It’s going to make it a lot easier to explain things as we go forward if we both have a common language.
An example of how we write a multiplication problem is shown below.
On the top we have the multiplicand. This is the number we want to multiply. On the bottom we have the multiplier. This is the number we will use to multiply the multiplicand. As we move through the examples later in this post, I’ll use these terms to explain the steps you need to take to perform the multiplication.
The Four Phases of Multiplication
There are a number of phases to the multiplication process:
-
The Alignment Phase: In the alignment phase the first thing we do is to align the numbers we wish to multiply so that their right-hand digits align. In cases where the numbers have a different number of digits after the radix point (remember the radix point separates the whole parts of the number from the fractional part), this means that the radix points of the two numbers will not align. Don’t worry about that. We will solve that in a later phase.
-
The Multiplication Phase: In this phase we produce a set of partial products by combining a number of single digit multiplications. Starting at the right-hand side, we take each digit of the multiplier and in turn use that digit to multiply each of the digits in the multiplicand. The results of these individual multiplications are then combined to create a partial product. Where the results of an individual multiplication has multiple digits the least significant digit is written down and the most significant digit is carried over to be added to the result of the next single digit multiplication. Once all the digits have been multiplied and the partial product has been calculated, the next digit in the multiplier is taken and the steps above are repeated. Each time a subsequent partial product is calculated the partial product is shifted one column to the left when compared to the last partial product. All spare columns to the right are then filled with zeros. (This might become a little clearer when we look at our example.) Once this is done for all digits in the multiplier and all the digits have been multiplied by all the digits in the multiplicand we should have one partial product for each of the digits in our multiplier. At this point we move on to the next phase.
-
The Addition Phase: In the addition phase, we calculate our result by adding all the partial products we calculated in phase 1.
-
Placing the Radix Point and Adding the Sign: The final step in the process is to place the radix point and calculate the sign of the number. As we’ve learnt previously, the radix point separates the whole numbers from the fractional numbers and in decimal is also known as the decimal point. The key thing to remember when placing the radix point in our final result is that our result will have the same number of digits after the radix point as there are after the radix point in each of the numbers we’re trying to multiply combined. For example if we were multiplying 23.6 x 27.564 we would have 4 digits to the right of the radix point in our answer as there is 1 digit after the radix point in our first number and another 3 after the radix point in our second number.
Multiplication in Decimal
Now that we have the basic phases clear, let’s work through an example.
To get started, lets walk through an example in decimal. It may be a refresher for you but it helps to illustrate the steps taken to perform multiplication in a number base you will be used to before we introduce the complication of performing it in binary.
In order to successfully perform multiplication of any two decimal numbers the main thing you need to remember is your multiplication tables. All decimal multiplication is based a number of simple single digit multiplications that are then added together.
For our example, imagine we were trying to work out how much it was costing us to run our computer per week and we have worked out it is consuming 23.4 units of electricity per week and each unit cost us 6.7 cents (Yeah… I know… just imagine…)
|
Stage 1: Align the Two Numbers |
|
 |
As I indicated above, the first stage of the process is to align our two numbers and write out our multiplication problem. As 23.4 (our multiplicant) and 6.7 (our multiplier) both have a single digit to the right of the decimal place, this is a pretty easy task in this case. |
|
Stage 2: Calculating the Partial Products |
|
|
Stage 2 involves calculating the partial products. As we have two digits in our multiplier we will have two partial products. |
|
|
Calculating the First Partial Product |
|
 |
Let’s start calculating our first partial product. To begin we take the right-most digit in the multiplier (the 7 of the 6.7) and multiply it by the first digit in the multiplicand (the 4 of the 23.4). 4 x 7 = 28. We put an 8 as the first digit in our partial product and then carry the 2. |
 |
Next we multiply the right-most digit in the multiplier (the 7 of the 6.7) by the second digit in the multiplicand (the 3 of the 23.4) and then add any numbers we carried. 3 x 7 = 21, add the 2 we carried from the previous step = 23. We put a 3 as the second digit in our partial product and then carry the 2. |
 |
We then multiply the right-most digit of the multiplier (the 7 of the 6.7) by the third digit in the multiplicand (the 2 of the 23.4) and again add any numbers we carried. 2 x 7 = 14, add the 2 we carried from the previous step = 16. We put 6 as the next digit of our partial product and as we have no more digits to multiply, we place the carried 1 into the next column. The result, our first partial product of 1638. |
|
Calculating the Second Partial Product |
|
 |
Having multiplied the first digit of our multiplier, we now move on to the second digit. As this second digit is an order of magnitude larger than the first digit we multiplied, we put a zero as the first digit of our second partial product. |
 |
Having got ourselves set up, we now take the second digit in the multiplier (the 6 of the 6.7) and multiply it by the first digit in the multiplicand (the 4 of the 23.4). 4 x 6 = 24. We put the 4 as the second digit in the partial product and carry the 2. |
 |
Next, we multiply the second digit in the multiplier (the 6 of the 6.7) and multiply that by the second digit of the multiplicand (the 3 of the 23.4) before adding anything we carried from the previous step. 3 x 6 = 18, add the 2 we carried = 20. We put the 0 as the third digit in our partial product and again carry the 2. |
 |
Next, we multiply the second digit in the multiplier (the 6 of the 6.7) by the third of the digits in the multiplicand (the 2 of the 23.4) and again add anything we carried. 2 x 6 = 12, add the 2 we carried = 14. We put the 4 as the next digit in our partial product and as there are no more digits to multiply, put the 1 in the next column. The result is our second partial product of 14040. |
|
Stage 3: Adding the Partial Products |
|
 |
The next phase is about adding the two partial products together. Starting in the rightmost column, we add the 8 of the first partial product with the 0 of the second partial product and get 8 which we place in the first column of our result. |
 |
Next we move on to the second column, adding the 3 of the first partial product to the 4 of the second partial product to get 7. This is added as the second digit of our result. |
 |
The third column sees us adding the 6 of the first partial product to the 0 of the second partial product to get 6 which is placed as the third digit in our result. |
 |
In the fourth column we add the 1 from the first partial product to the 4 of the second partial product to get 5 which we write as the fourth digit of the result. |
 |
Finally, we take the 1 of the second partial product and move that down as the fifth digit in our result. That gives us a result of 15678. |
|
Stage 4: Locating the Radix Place |
|
 |
The next step is to place the radix or decimal place. The rule is that our result will have the same number of places as there are in all the numbers we were multiplying together. Our multiplicand 23.4 has only one place and our multiplier also has one place giving us a total of 2. Starting to the right of the rightmost digit in our result, we therefore move the decimal place 2 places to the left to get our final result of 156.78. |
Binary Multiplication
Binary Multiplication is generally simpler than decimal multiplication. Instead of needing to know your multiplication tables you only really need to know three things:
-
1 x 1 = 1
-
0 x 1 = 0
-
1 x 0 = 0
When you perform multiplication with binary you will notice that there are never any carries and the partial products will either be zero or a shifted version of the multiplicand. Let’s look at another example. Imagine we were trying to multiply the following: 1.01 x 10.10 (it’s stretching the analogy somewhat to imagine this is also your electricity bill!). Again we will follow the same stages as we did with decimal multiplication.
|
Stage 1: Alignment |
|
 |
As we know by now, stage 1 is to align our two numbers. Again, each of our numbers in this case have two digits to the right of the radix point so we align them and write our our problem. |
|
Stage 2: Calculating the Partial Products |
|
|
The first stage is to calculate the partial products. As our multiplier has four digits we will have four partial products. |
|
|
Calculate the First Partial Product |
|
 |
First we take the first digit of the multiplier (the right-hand 0 of 10.10) and multiply that by the different digits of the multiplicand. As we know, anything multiplied by 0 is zero so our first partial product is 0 (or more accurately 000). |
|
Calculate the Second Partial Product |
|
 |
As we move onto the second digit in our multiplier (the right-hand 1 of 10.10) the first thing we do is initially put a 0 in the first column of the partial product. We then multiply each individual digit in the multiplicand by the 1 of our multiplier filling in the digits of the progressively more significant columns. The result is a partial product of 1010. (Notice how the first three digits are our multiplicand shifted one place.) |
|
Calculate the Third Partial Product |
|
 |
As we move onto the third digit (the left-hand 0 of the 10.10) the first thing we do is put two zeros in the first two columns of the partial product. We then multiply the 0 from our multiplier with each of the digits in the multiplicand. As 0 multiplied by anything is 0 the third partial product is 0 (or more accurately 00000). |
|
Calculate the Fourth Partial Product |
|
 |
Moving on to the final digit in our multiplier (the left-hand 1 of the 10.10) we first put three zeros in the first three columns of the partial product to represent the increased significance of the digit we are multiplying. We then take the 1 of our multiplier and multiply it by each of the digits in the multiplicand. The result is the partial product of 101000. |
|
Stage 3: Adding the Partial Products |
|
 |
The next stage is to add all our partial products. Addition is performed using binary addition that we have learnt in my previous post. This gets us a result of 110010. |
|
Stage 4: Locating the Radix Place |
|
 |
The final stage is to locate the radix place. As with decimal, the same rule applies with the result having the same number of places are there are in all the original numbers being multiplied together. If we take a quick look back we see that our multiplicand has 2 places and our multiplier has two as well giving us a total of 4. Starting to the right of the right-most digit in our result, we therefore move the radix place four places to the left and get our final result of 11.0010. |
So there we have it. Binary Multiplication. Slightly simpler than decimal equivalent due to the reduced need to know all your different multiplication tables but still an essential building block of binary mathematics. Try it for yourself.
Image Source: http://flic.kr/p/b9KQCk