For the life of me I cannot understand binary multiplication or booths algorithm.
This is topic I have just been introduced to in my computer architectures class and it makes 0 sense.
In: 0
First, remember decimal multiplication. When we multiply `A*B`, we separate `B` into sum of decimal places and distribute `A` over sum. So `A*3456 = A * (3000 + 400 + 50 + 6) = A*3000 + A*400 + A*50 + A*6`. And of course, `A*400` is the same as `A*4, shift left 2`. So, we only need to know multiplication on single digits to multiply any numbers.
Binary multiplication works the same way: `A*1011 = A*1000 + A*000 + A*10 + A*1`. Again, `A*1000` is just `A*1, shift left 4`. Actually, because there are only two digits in binary – 0 and 1 – you only ever need to add either `A shift left X`, or nothing!
Now to understand Booth’s, let’s again start from decimal. Can you multiply `A*999`? You can use the usual algorithm (`999 = 900 + 90 + 9`), but you can do it simpler: `999 = 1000 – 1`, so `A * 999 = A * (1000 – 1) = A*1000 – A`! By allowing subtraction we can calculate the answer easier!
Booth’s does the same, but in binary: it detects strings of 1s and replaces them with subtraction – `1111 = 10000 – 1`, `1110 = 10000 – 10`, etc. So `A*110111 = A*(100000 – 10000 + 1000 – 1)`, which can be converted in adding either `A` or `-A`, shifted left. Booth’s algorithm reads numbers from right to left:
* each time you see `10` – you at the right end of 1s string: subtract,
* each time you see `01` – you at the left end of 1s string: add,
* `00` is the 0s – do nothing
* `11` is the middle of 1s string: do nothing
Latest Answers