Multiplication

1. Multiplication
   • Multiplication shows how simple logic functions can be combined to make a much more complex function.
   • Method 1: partial products
     • The result of multiplying two n-bit numbers occupies up to 2×n bits.Multiplying the 4-bit numbers A and B can be written as A₃A₂A₁A0 × B₃B₂B₁B₀.  The product can then be found by adding the partial products.
     • A basic building block can be made using:
       • Forming the partial product of two binary digits is simply an AND operation.
       • Adding the partial sums can be accomplished with 1-bit full adders.
         
     • These building blocks can then be used to build a 4-bit multiplier as shown in the figure below.  (see also “Combinational multiplier“)
       
   • Method 2: quarter squares
     • ¼·(A + B)² - ¼·(A – B)² = ¼·(A² + 2·A·B + B²) – ¼·(A² – 2·A·B + B²) =A·B
       • hard wire a look-up table of squares
       • calculate A + B, and look up C = (A + B)²
       • calculate A – B, and look up D = (A – B)²
       • calculate C – D, and divide by 4.  The result is A × B^.
     • So three additions, two table look ups and divide by 4 (right shift by 2 bits).
     • The size of the look up tables scales nicely linear with the length of the operands.
       :
2.