Binary multiplication by addition with non-verlapping multiplier recording

Claim 2

In a data processing system wherein an operand B is multiplied by an operand A where A includes the non-overlapping bytes Ai, to form the product P an apparatus for performing the operation (Ai)(B) + C(i-1) R1(i),R2(i) comprising a recoder for recoding the bytes Ai into an x-bit code, multiple gate means for forming x partial sums of said operand B under control of said x-bit code, a multiple input adder for receiving the x partial sums from said multiple gates for concurrently adding said partial sums and C(i-1) to form the partial results R1(i), R2(i).

Claim 3

The data processing system of claim 1 further including an adder for adding the resultants R1(i) and R2(i) to form a partial product Ci.

Claim 4

The data processing system of claim 1 wherein said bytes Ai are each eight bits, wherein x is 5 and wherein said recoder is an 8-to-5 recoder.

Claim 5

The data processing system of claim 3 wherein said eight bits of said operand bytes Ai represent the binary values 20, 21, . . . , 27 and wherein said recoder forms the recoded outputs in multiples of 20, 22, 24, 26, and 28.

Claim 6

The data processing system of claim 4 wherein said recoded outputs are further multiplied by the five factors 0, + or - 1, or + or - 2.

Claim 7

A data processing system where an operand B is multiplied by an operand A to form the product P where P includes the bytes P1, P2, . . . , P8 where A includes the non-overlapping Ai bytes A1, A2, A3 and A4 each having y bits, the apparatus comprising, a recoder for recoding each byte Ai to form x control signals where x equals the largest whole number in (y/2+1), multiple gate means for forming x partial sums of said operand B in response to said control signals for each of said bytes Ai, a multiple input adder for receiving the outputs from said multiple gates and for receiving a partial product C(i-1) to perform operations (Ai)(B) + C(i-1) R1(i), R2(i) for all values of i equal to 1, 2, 3 and 4 and wherein the value of C(0) is 0, a two input adder for adding the partial results R1(i) and R2(i) to form the partial product Ci for all values of i equal to 1, 2, 3 and 4 where P1 is the lowest order byte of C1 and for adding the partial product C4 to bytes from thE partial product C3 to form the bytes P4, P5, . . . , P8, means including a byte adder for adding the lowest order byte of the partial product Ci to the next lowest order byte of the partial product C(i-1) to form the bytes Pi for i equal to 2 and 3 whereby P2 and P3 are formed.

Claim 8

A data processing system where an operand B is multiplied by an operand A to form the product P where P includes the bytes P1, P2, . . . , P8 where A includes the non-overlapping Ai bytes A1, A2, A3 and A4 each having y bits, the apparatus comprising, a recoder for recoding each byte Ai to form x control signals where x equals the largest whole number in (y/2+1), multiple gate means for forming x partial sums of said operand B in response to said control signals for each of said bytes Ai, a multiple input adder for receiving the outputs from said multiple gates and for receiving a partial product C(i-1) to perform operations (Ai)(B) + C(i-1) R1(i), R2(i) for all values of i equal to 1, 2, 3 and 4 and wherein the value of C(0) is 0, a two input adder for adding the partial results R1(i) and R2(i) to form the partial product Ci for all values of i equal to 1, 2, 3 and 4 where P1 is the lowest order byte of C1 and for adding the partial product C4 to bytes from thE partial product C3 to form the bytes P4, P5, . . . , P8, means including a byte adder for adding the lowest order byte of the partial product Ci to the next lowest order byte of the partial product C(i-1) to form the bytes Pi for i equal to 2 and 3 whereby P2 and P3 are formed.

Claim 9

The system of claim 6 wherein x equals five and wherein said bytes are eight binary bits, whereby said recoder recodes from 8-to-5 to form the weights 20, 22, 24, 26, 28 and wherein each weight is additionally multiplied by one of the five values, 0, + or - 1, + or - 2.

Claim 10

The system of claim 7 wherein the 20, 22, 24, 26, 28 multiplications are achieved by shifting B by 0 bits, 2 bits, 4 bits, 6 bits and 8 bits, respectively, and where each of those shifted values of B are further multiplied by 0, +1, -1, +2 or -2 by making the shifted value of B equal to all 0''s, by using the shifted value of B, by complementing the shifted value of B and inserting a carry-in in the low-order bit position, by shifting the shifted value of B one additional bit, and by complementing and shifting one additional bit the shifted value of B and inserting a carry-in in the low order bit position, respectively.

Claim 11

A data processing system where an operand B is multiplied by an operand A where A includes the four non-overlapping Ai bytes A1, A2, A3 and A4, the improvement comprising, a recoder for recoding each byte Ai to form five control signals, multiple gate means for forming five partial sums of said operand B in response to said five control signals for each of said bytes Ai, a multiple input adder for receiving the outputs from said multiple gates and for receiving a partial product C(i-1) to perform operations (Ai)(B) + C(i-1) R1(i),R2(i) for all values of i equal to 1, 2, 3 and 4 and wherein the value for i 1 of C0 is 0, a two input adder for adding the partial results R1(i) and R2(i) to form the partial product Ci for all values of i equal to 1, 2, 3 and 4, first store means for storing the partial product Ci for all values of i equal to 1, 2, 3 and 4, means for connecting the three bytes Ci(3), Ci(2) and Ci(1), for each partial product Ci for i equal to 1, 2, and 3, from said first store means to said multiple input adder, second store means for storing the bytes Ci(5) and Ci(4) received from said first store means where the byte C1(5) is the low-order product byte P1, byte adder means connected to receive bytes from said first and second store means for adding the bytes C1(4) and C2(5) and the bytes C2(4) and C3(5) to form the product bytes P2 and P3, respectively, means connecting the partial product C4 and the bytes C3(4), C3(3), C3(2) and C3(1) to said two input adder for addition to form the high-order product bytes P4, P5, P6, P7 and P8 whereby the product AB P is formed with P equal to P1, P2, . . . , P8.

Claim 12

A data processing system where an operand B is multiplied by an operand A where A includes the four non-overlapping Ai bytes A1, A2, A3 and A4, the improvement comprising, a recoder for recoding each byte Ai to form five control signals, multiple gate means for forming five partial sums of said operand B in response to said five control signals for each of said bytes Ai, a multiple input adder for receiving the outputs from said multiple gates and for receiving a partial product C(i-1) to perform operations (Ai)(B) + C(i-1) R1(i),R2(i) for all values of i equal to 1, 2, 3 and 4 and wherein the value for i 1 of C0 is 0, a two input adder for adding the partial results R1(i) and R2(i) to form the partial product Ci for all values of i equal to 1, 2, 3 and 4, first store means for storing the partial product Ci for all values of i equal to 1, 2, 3 and 4, means for connecting the three bytes Ci(3), Ci(2) and Ci(1), for each partial product Ci for i equal to 1, 2, and 3, from said first store means to said multiple input adder, second store means for storing the bytes Ci(5) and Ci(4) received from said first store means where the byte C1(5) is the low-order product byte P1, byte adder means connected to receive bytes from said first and second store means for adding the bytes C1(4) and C2(5) and the bytes C2(4) and C3(5) to form the product bytes P2 and P3, respectively, means connecting the partial product C4 and the bytes C3(4), C3(3), C3(2) and C3(1) to said two input adder for addition to form the high-order product bytes P4, P5, P6, P7 and P8 whereby the product AB P is formed with P equal to P1, P2, . . . , P8.