Device for multiplying binary numbers

Claim 1

A device for multiplying a first number having a first plurality of m groups, by a second number having a second plurality of p groups of binary digits, each of said groups consisting of n digits, of corresponding directly successive significance levels, where m, p, and n are positive integers, comprising: a plurality of q partial product forming devices, q being a positive integer greater than or equal to m×p, each of said partial product forming devices comprising 2n inputs for simultaneously receiving a first and second group of binary digits from said first and second plurality of groups respectively, each of said groups of said first plurality being applied to p partial product forming devices, and each of said p groups of said second plurality being applied to m different ones of said partial product forming devices, so that each of said partial product forming devices receives a first group of digits from said first plurality and a second group of digits from said second plurality; each of said product forming devices further including combinatorial gating means which form a partial product consisting of 2n binary digits of successive significance levels; a sum forming device having inputs connected to said outputs of said combinatorial gating means which form a complete sum of q partial products, comprising a plurality of r partial sum forming devices, each sum forming device comprising inputs for simultaneously receiving first and second groups of binary digits, each group comprising j binary digits of directly successive significance levels, both of said groups originating from at least two partial products derived from said combinatorial gating means, where r and j are positive integers; each partial sum forming device having a further input for receiving a binary output carry signal from a partial sum forming device of next lower significance level, simultaneously with said first and second groups of binary digits; each partial sum forming device further including j outputs for outputting the partial sum of the signals received by said partial sum forming devices, and a carry output for outputting simultaneously therewith a binary output carry signal to a partial sum forming device of next higher significance level; an array of said partial sum forming devices cooperating with said partial product forming devices of lowest significance level in order to form the complete product in parallel.

Claim 2

A device for multiplying a first number having a first plurality of m groups, by a second number having a second plurality of p groups of binary digits, each of said groups consisting of n digits, of corresponding directly successive significance levels, where m, p, and n are positive integers, comprising: a plurality of q partial product forming devices, q being a positive integer greater than or equal to m×p, each of said partial product forming devices comprising 2n inputs for simultaneously receiving a first and second group of binary digits from said first and second plurality of groups respectively, each of said groups of said first plurality being applied to p partial product forming devices, and each of said p groups of said second plurality being applied to m different ones of said partial product forming devices, so that each of said partial product forming devices receives a first group of digits from said first plurality and a second group of digits from said second plurality; each of said product forming devices further including combinatorial gating means which form a partial product consisting of 2n binary digits of successive significance levels; a sum forming device having inputs connected to said outputs of said combinatorial gating means which form a complete sum of q partial products, comprising a plurality of r partial sum forming devices, each sum forming device comprising inputs for simultaneously receiving first and second groups of binary digits, each group comprising j binary digits of directly successive significance levels, both of said groups originating from at least two partial products derived from said combinatorial gating means, where r and j are positive integers; each partial sum forming device having a further input for receiving a binary output carry signal from a partial sum forming device of next lower significance level, simultaneously with said first and second groups of binary digits; each partial sum forming device further including j outputs for outputting the partial sum of the signals received by said partial sum forming devices, and a carry output for outputting simultaneously therewith a binary output carry signal to a partial sum forming device of next higher significance level; an array of said partial sum forming devices cooperating with said partial product forming devices of lowest significance level in order to form the complete product in parallel.

Claim 4

A device for multiplying a first number having a sequence of m groups of n bits each, by a second number having a sequence of p groups of n bits each, wherein p, m<3 and n<2, said device comprising: a first array of partial product forming devices, each receiving one of said m groups and one of said p groups of said first and second numbers respectively; each of m×p partial product forming devices thereby receiving a different combination of two n-bit groups; each partial product forming device having means for forming by combinatorial gating, from two bit groups received a partial product of 2n bits; said device furthermore comprising: a second array for receiving and accumulating said partial products; said second array comprising: r partial sum forming devices, each receiving within said partial products two second sequences of j bits of corresponding significance levels among said second sequences and a binary carry input signal and for thereupon generating a partial sum consisting of a third sequence of j bits and a binary carry output signal, the total complement of said second sequences encompassing all partial products formed by said first array exclusive of the least significant thereof; said second array having for each significance level of the bits received a column of at least two interconnected partial sum forming devices for generating by successive addition of said second and third sequences inclusive of any output carry signal so generated a single final product bit, the total complement of final product bits so generated together with the least significant of said partial products constituting the final product.

Claim 5

A device for multiplying a first number having a sequence of m groups of n bits each, by a second number having a sequence of p groups of n bits each, wherein p, m<3 and n<2, said device comprising: a first array of partial product forming devices, each receiving one of said m groups and one of said p groups of said first and second numbers respectively; each of m×p partial product forming devices thereby receiving a different combination of two n-bit groups; each partial product forming device having means for forming by combinatorial gating, from two bit groups received a partial product of 2n bits; said device furthermore comprising: a second array for receiving and accumulating said partial products; said second array comprising: r partial sum forming devices, each receiving within said partial products two second sequences of j bits of corresponding significance levels among said second sequences and a binary carry input signal and for thereupon generating a partial sum consisting of a third sequence of j bits and a binary carry output signal, the total complement of said second sequences encompassing all partial products formed by said first array exclusive of the least significant thereof; said second array having for each significance level of the bits received a column of at least two interconnected partial sum forming devices for generating by successive addition of said second and third sequences inclusive of any output carry signal so generated a single final product bit, the total complement of final product bits so generated together with the least significant of said partial products constituting the final product.

Claim 11

A device for multiplying a first number in binary two's complement representation including a first sign bit and a sequence of m groups of n bits each having a fractional value, by a second number in binary two's complement representation including a second sign bit and a sequence of p groups of n digits each having a fractional value, wherein p,m, n>2, said device comprising: a first array of partial product forming devices, each receiving one of said m groups and one of said n groups of said first and second numbers, respectively; each of m×p partial product forming devices thereby receiving a different combination of two n-bit groups; each partial product forming device having means for forming by combinatorial gating from two bit groups received a partial product of 2n bits; said device furthermore comprising: a second array for receiving and accumulating said partial products; said second array comprising r partial sum forming devices for each receiving within said partial products two second sequences of j bits of corresponding significance levels among said second sequences and a binary carry input signal, and thereupon generating a partial sum consisting of a third sequence of j bits and a binary carry output signal, the total complement of said second sequences encompassing all partial products formed by the first array exclusive of the least significant thereof; said second array having for each significance level of the bits received a column of at least two interconnected partial sum forming devices for generating, by successive addition of said second and third sequences inclusive of any output carry signals so generated, a single preliminary product bit, the total complement of preliminary product bits so generated together with the least significant of said partial products constituting a preliminary product; means for multiplying the first sign bit with the bitwise inverted contents of said p groups of n bits to form a first correction bit sequence; means for multiplying the second sign bit with the bitwise inverted contents of said m groups of n bits to form a second correction bit sequence; further adding means for adding said preliminary product and said first and second correction bit sequences to form a final product; and sign bit determining means being provided for multiplying said first and second sign bits.

Claim 12

A device for multiplying a first number in binary two's complement representation including a first sign bit and a sequence of m groups of n bits each having a fractional value, by a second number in binary two's complement representation including a second sign bit and a sequence of p groups of n digits each having a fractional value, wherein p,m, n>2, said device comprising: a first array of partial product forming devices, each receiving one of said m groups and one of said n groups of said first and second numbers, respectively; each of m×p partial product forming devices thereby receiving a different combination of two n-bit groups; each partial product forming device having means for forming by combinatorial gating from two bit groups received a partial product of 2n bits; said device furthermore comprising: a second array for receiving and accumulating said partial products; said second array comprising r partial sum forming devices for each receiving within said partial products two second sequences of j bits of corresponding significance levels among said second sequences and a binary carry input signal, and thereupon generating a partial sum consisting of a third sequence of j bits and a binary carry output signal, the total complement of said second sequences encompassing all partial products formed by the first array exclusive of the least significant thereof; said second array having for each significance level of the bits received a column of at least two interconnected partial sum forming devices for generating, by successive addition of said second and third sequences inclusive of any output carry signals so generated, a single preliminary product bit, the total complement of preliminary product bits so generated together with the least significant of said partial products constituting a preliminary product; means for multiplying the first sign bit with the bitwise inverted contents of said p groups of n bits to form a first correction bit sequence; means for multiplying the second sign bit with the bitwise inverted contents of said m groups of n bits to form a second correction bit sequence; further adding means for adding said preliminary product and said first and second correction bit sequences to form a final product; and sign bit determining means being provided for multiplying said first and second sign bits.