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

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
...