Binary multiplier

Binary multiplier is a device to multiply binary numbers. Multiplication is more challenging operation than addition, while still not as challenging as division. It simple to build a multiplier for the single bit binary numbers, as this operation is performed by the single AND element (1*1 = 1, 0*any=0). However it does not scale as easily as adder or subtractor, as we also need shift and addition to multiply bigger numbers.

Binary multiplication is similar to the decimal multiplication you have learned at school. For instance, to multiply A=3 and B=2:


       11   (this is 3 in binary, A)
     x 10   (this is 2 in binary, B)
     ====
       00   (this is 11 x 0)
      11    (this is 11 x 1, shifted one position to the left)
     ====
      110   (this is 6 in binary, A*B)

One obvious simplification is that multiplying by each bit of B we can only get A (if multiplied by 1) or 0 (if multiplied by 0). Hence all rows in the sum part are either zero rows or rows containing value A shifted to the left by the proper number of positions (the logic should be obvious from the table below). To make this more clear, let's now multiply 3 by 26 (101010):


           11   (this is 3 in binary, A)
     x  11010   (this is 26 in binary, B)
     ========
           00   (this is 11 x 0)
          11    (this is 11 x 1, shifted one position to the left)
         00     (this is 11 x 0)
        11      (this is 11 x 1, shifted three position to the left)
       11       (this is 11 x 1, shifted four position to the left)
     ========
      1001110   (this is 78 in binary, A*B)

In this table, the multiplication is represented as a combination of binary shift, logical AND and addition. Many older computers used the similarly implemented multiplication subroutine, and later or more advanced processors contained not much different microcode sequence. For the smaller number of bits it is also possible to assemble the circuit directly as done in the diagram below. However while correct, such multiplier is relatively slow. Recent circuits use more advanced solutions, such as Baugh–Wooley algorithm, Wallace tree, or Dadda multiplier[1].

2*2 binary multiplier[2]. Multiplying by 1 (say set as input A) means repeating the value. Multiplying by 2 is a shift operation: if 10, binary 2, is set as the input A, the circuit repeats the value B, shifted forward by one position. The biggest result this circuit can produce is 9 (binary 1001). On the left side, AND elements implement the logic of the first stage of addition (shift and zeroing where required). The two binary adders (each made from one XOR and one AND element) add these values, producing the output.

References

  1. 1 Wikipedia article on binary multiplier
  2. 2 Binary multiplier diagram in Wikipedia, by User:Supuhstar