Browse Prior Art Database

Fast Multiplier Circuit (MULT)

IP.com Disclosure Number: IPCOM000115245D
Original Publication Date: 1995-Apr-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 84K

Publishing Venue

IBM

Related People

Cukier, M: AUTHOR

Abstract

Disclosed is an algorithm which is used to replace the additions of several binary words used in conventional multipliers, by a single addition of two binary patterns.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Fast Multiplier Circuit (MULT)

      Disclosed is an algorithm which is used to replace the
additions of several binary words used in conventional multipliers,
by a single addition of two binary patterns.

      Multiplication Matrix - A multiplication matrix reduces the
first m patterns to be added to a fewer p patterns, such that the
decimal sum of the p patterns is the same than the decimal sum of the
initial m ones.

A four-step algorithm is applied to the initial matrix:
  o  Step 1: count for each column of the matrix the number of binary
              "1".
  o  Step 2: code the results into binary numbers and write them
              vertically, the Most Significant Bits (MSB) being at
the
              top, thus generating the MSB line.
  o  Step 3: shift to the left the MSB line to a number of columns
              corresponding to the weight of the line, and shift in a
              decremental way the remaining lines.
  o  Step 4: pad each line with binary "0".

      The algorithm is repeated until step 2 is a two bit binary
code, which leads after step 4 to a final addition of two words.

      Example - Following is an example for the addition of seven
words.  The corresponding decimal result is given on the right of the
binary matrix.
              Binary Matrix          Decimal value
          0  0  0  1  1  1  1  0             30
          0  0  1  1  1  1  0  0         +   60
          1  1  0  1  0  1  0  1         +  213
          0  1  0  1  0  0  0  0         +   80
          1  0  1  1  0  0  0  1         +  177
          0  1  0  1  0  0  0  1         +   81
          0  1  1  1  0  0  0  1         +  113
                              TOTAL      =  754
  o  Step 1: the counting of the binary "1" in each column:
     Result: 2  4  3  7  2  3  1  4
  o  Step 2: the bottom-down binary coding of the result:
             0  1  0  1  0  0  0  1     MSB line
             1  0  1  1  1  1  0  0
             0  0  1  1  0  1  1  0
  o  Step 3: the shifting of the lines according to the MSB line
              weight.  Here the weight is 4 thus the first line is
              shifted two times.
          0  1  0  1  0  0  0  1        2 columns shift
             1  0  1  1  1  1  0  0     1 column shift
        ...