Parallel adder with distributed control to add a plurality of binary numbers

Claim 3

A method as defined in claim 1 wherein said binary ones are grouped together asynchronously in said binary memory elements of said column for said given order in accordance with the following equation: bi bi.bi 1 where bi represents the future state of the i-th memory element of said column and i is one of a series of integers 1, 2, . . . k . . . M.

Claim 4

A method as defined in claim 2 wherein said number k is detected in accordance with the following equations:

Claim 5

A method as defined in claim 1 wherein said last step of adding binary digits of equal weight from said groups is carried out in a manner strictly analogous to steps defined in claim 1 utilizing a second plurality of networks cascaded with said first plurality of networks such that the binary digits of numbers to be added by each of said first plurality of networks are digits of binary-coded groups produced by said second plurality of networks, whereby 2M-1 numbers stored in memory elements of said first plurality of networks may be added in parallel.

Claim 6

A method as defined in claim 1 wherein M is equal to 7, whereby each of said first plurality of networks provides a binary-coded group of three binary digits R, S and T weighted 2i, 2i 1 and 2i 2, respectively, and wherein binary digits R, S and T of equal weight from said groups are combined in a full adder to provide a pseudosum digit pi for a given order when any one, but not two, or all three binary digits are equal to one and an assimilated carry digit qi 1 when any two binary digits are equal to one. 7,

Claim 7

A method as defined in claim 5 wherein said last step said sum and carry digits pi and qi of a given order i are combined to provide a sum digit pi and a carry digit Qi 1 in response to said digits pi and qi and a carry Qi from the order i-1.

Claim 8

A method as defined in claim 6 wherein pi and qi signals are combined in a full parallel binary adder to provide a sum in the form PN 1 2N 1+ . . . P2 .2 2+P1.21+Po by generating the binary digits signals Pi in accordance with the following equation:

Claim 9

A method as defined in claim 7 wherein said full parallel binary adder end-around carry is provided by selecting for the pseudosum full adder of the least significant order, the triadic signals R, S and T from the least significant order, most significant order, and next to most significant order, respectively.

Claim 10

A method as defined in claim 6 wherein end-around carry is provided by selecting for the psuedosum full adder of the least significant order of the triadic signals R, S and T from said networks of least significant order, most significant order, and next to most significant order, respectively, and for the sum full adder of the lest significant order the inputs Po, qN 1, and QN 1 where the subscript N-1 is equal to the integer i which defines the weight 2i for the most significant order of numbers to be added.

Claim 11

Apparatus for simultaneously adding a number M of binary numbers having N digits of weights 20, 21, 22 . . . 2N 1 in successively increasing orders 1, 2, 3 . . . N, comprising: a first plurality of registers, one for each order of said binary numbers, a given register having a plurality of binary memory elements b1 to bM, each memory element being adapted to store a digit of a different binary number, but of the same binary order as other memory elements of the same register; a first means connected to each of said first plurality of registers for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register and, in response thereof, generating a binary-coded group of n signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N-1 corresponding to one of said orders 1, 2, 3 . . . N and j is an integer from 0 to n-1 corresponding to the orders from 1 to n of said binary-coded group ofn signals; and means connected to all of said first means for adding in parallel signals of binary-coded groups generated by all of said first means, said parallel adding means being connected for signals of equal weight to be added together to provide the sum of said binary numbers being added together.

Claim 12

Apparatus for simultaneously adding a number M of binary numbers having N digits of weights 20, 21, 22 . . . 2N 1 in successively increasing orders 1, 2, 3 . . . N, comprising: a first plurality of registers, one for each order of said binary numbers, a given register having a plurality of binary memory elements b1 to bM, each memory element being adapted to store a digit of a different binary number, but of the same binary order as other memory elements of the same register; a first means connected to each of said first plurality of registers for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register and, in response thereof, generating a binary-coded group of n signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N-1 corresponding to one of said orders 1, 2, 3 . . . N and j is an integer from 0 to n-1 corresponding to the orders from 1 to n of said binary-coded group ofn signals; and means connected to all of said first means for adding in parallel signals of binary-coded groups generated by all of said first means, said parallel adding means being connected for signals of equal weight to be added together to provide the sum of said binary numbers being added together.

Claim 13

Apparatus as defined in claim 10 wherein said binary ones are grouped together in a given register in memory elements b1 to bk, where k is the number of binary ones in said given register, by means for shifting binary ones toward said memory element b1 in accordance with the following control function: bi bibi+1 where bi represents the future state of the i-th memory element and i is one of a series of integers 1, 2, . . . k, . . . M.

Claim 14

Apparatus as defined in claim 11 wherein said binary-coded group of n signals is generated by means for converting k to a binary number of n digits.

Claim 15

Apparatus as defined in claim 12 wherein n is equal to three and said means for adding in parallel signals of said binary-coded groups comprises a first group of binary full adders, a different one being associated with each order of binary numbers to be added, a given binary full adder being connected to receive signals of equal weight commensurate with the order of binary numbers to be added with which it is associated, and transmitting a pseudosum signal and a carry signal.

Claim 16

Apparatus as defined in claim 13 wherein said parallel adding means further includes a second group of binary full adders, a different one associated with each full adder of said first group, a given binary full adder of said second group being connected to receive a pseudosum signal from its associated one of said first group of full adders, a carry signal from the full adder of next lower order of said first group and a carry signal from the full adder of next lower order of said second group.

Claim 17

Apparatus as defined in claim 10 wherein end-around carry is provided by means for adding binary-coded group signals having weights 2N 1.2j with binary-coded group signals having weights 20.2j 1, but only when the sum (N-1)+jN.

Claim 18

Apparatus as defined in claim 15 wherein n is equal to three and said means for adding in parallel signals of said binary-coded groups comprises a first group of binary full adders, a different one associated with each order of binary numbers to be added, a given binary full adder receiving being connected to receive signals of equal weight commensurate with the order of binary numbers to be added with which it is associated, and transmitting a psuedosum signal and a carry signal.

Claim 19

Apparatus as defined in claim 16 wherein a second group of binary full adders is provided, a different one associated with each full adder of said first group, a given binary full adder of said second group being connected to receive a pseudosum signal from its associated one of said first group of full adders, a carry signal from the full adder of next lower order of said first group and a carry signal from the full adder of next lower order of said second group, and end-around carry is provided by adding a carry signal from the full adder of said first group associated with the most significant order of said binary numbers to be added, and a carry signal from the full adder of said second group associated with the most significant order, with a pseudosum signal from the full adder of said first group associated with the least significant ordeR of said binary numbers to be added.

Claim 20

Apparatus for simultaneously adding a plurality M of binary numbers having N digits of weights 20, 21, 22 . . . 2N 1 in successively increasing orders 1, 2, 3 . . . N, comprising: a first plurality of registers, one for each order of said binary numbers, a given register having a plurality of memory elements b1 to bM, each memory element being adapted to store a digit of a different binary number but of the same binary order as other memory elements of the same register; a means associated with and connected to each of said first plurality of registers for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register, and in response thereto, generating a binary-coded group of n signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N1 corresponding to an associated one of said orders 1, 2, 3 . . . N, and j is an integer from 0 to n-1; a second plurality of registers, one for each of said first plurality of registers, each register having a plurality of memory elements b1 to bn, where n is the number of binary digit signals generated by a given one of said first means associated with one of said first plurality of registers, a given one of said second plurality of registers being connected to receive and store in memory elements thereof n binary signals generated by one of said first means associated with one of said first plurality of registers associated with said given one of said second plurality of registers; and a second means associated with and connected to each of said second plurality of register for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register, and in response thereto, generating a binary-coded group of three signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N1 corresponding to an associated one of said orders 1, 2, 3 . . . N andj is an integer from 0 to 2; and third means connected to all of said second means for adding in parallel signals of binary-coded groups generated by all of said different second means, signals of equal weight being added together to provide the sum of said binary numbers being added together.

Claim 21

Apparatus for simultaneously adding a plurality M of binary numbers having N digits of weights 20, 21, 22 . . . 2N 1 in successively increasing orders 1, 2, 3 . . . N, comprising: a first plurality of registers, one for each order of said binary numbers, a given register having a plurality of memory elements b1 to bM, each memory element being adapted to store a digit of a different binary number but of the same binary order as other memory elements of the same register; a means associated with and connected to each of said first plurality of registers for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register, and in response thereto, generating a binary-coded group of n signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N1 corresponding to an associated one of said orders 1, 2, 3 . . . N, and j is an integer from 0 to n-1; a second plurality of registers, one for each of said first plurality of registers, each register having a plurality of memory elements b1 to bn, where n is the number of binary digit signals generated by a given one of said first means associated with one of said first plurality of registers, a given one of said second plurality of registers being connected to receive and store in memory elements thereof n binary signals generated by one of said first means associated with one of said first plurality of registers associated with said given one of said second plurality of registers; and a second means associated with and connected to each of said second plurality of register for independently reordering the binary ones of a given order at one end of a column of binary memory elements, in each column detecting the boundary level between a binary one and a binary zero after the reordering to determine the number of binary ones stored in its associated register, and in response thereto, generating a binary-coded group of three signals representative of the number of binary ones stored, each signal having a weight equal to the product 2i.2j, where i is one of a series of N integers 0, 1, 2 . . . N1 corresponding to an associated one of said orders 1, 2, 3 . . . N andj is an integer from 0 to 2; and third means connected to all of said second means for adding in parallel signals of binary-coded groups generated by all of said different second means, signals of equal weight being added together to provide the sum of said binary numbers being added together.

Claim 22

Apparatus as defined in claim 18 wherein said binary ones are grouped together in a given register in memory elements b1 to bk, where k is the number of binary ones in said given register, by shifting binary ones toward said memory element b1 in accordance with the following control function: bi bibi 1 where bi represents the future state of the i-th memory element and i is one of a series of integers 1, 2, . . . k . . . x, and x is equal to the number of binary elements in said given register.

Claim 23

Apparatus as defined in claim 19 wherein said binary-coded group of n signals generated by said different first means and binary-coded group of three signals generated by said different second means is each generated by different means for converting k to a binary number.

Claim 24

In combination A register for storing M binary digits and apparatus for asynchronously grouping all binary ones together in binary memory elements b1, b2, . . . bk of said register, and all binary zeros in binary memory elements bk 1, . . . bM comprising a plurality of control elements, one between each pair of adjacent binary memory elements, which functions in accordance with the following equation: bi bibi 1 where bi represents the future state of a i-th binary memory element and i is one of a series of integers 1, 2, . . . k . . . M.

Claim 25

In combination A register for storing M binary digits and apparatus for asynchronously grouping all binary ones together in binary memory elements b1, b2, . . . bk of said register, and all binary zeros in binary memory elements bk 1, . . . bM comprising a plurality of control elements, one between each pair of adjacent binary memory elements, which functions in accordance with the following equation: bi bibi 1 where bi represents the future state of a i-th binary memory element and i is one of a series of integers 1, 2, . . . k . . . M.

Claim 26

Apparatus as defined in claim 21 including means for disabling operation of said plurality of control elements while said M binary digits are being entered into said register.