Method and apparatus for calculating the residue of a signed binary number

Apparatus for calculating the reside of a signed binary number of "n" bits in the two's complement notation with respect to a check base "m", the quantity (n-1) bits of said number being of lesser significance than the sign bit, and being partitioned into number segments of b bits each with each number segment having segment boundaries, where m=(2.sup.b -1) and m, n, and b are positive integers greater than one, comprising:

• circuit means for forming a sign segment of b bits, the bit position of the sign segment corresponding to the bit position of the sign bit in the binary number with respect to a boundary of a number segment being filled with a logical zero, and all other bit positions of the sign segment being filled by the sign bit;
• carry save adder means for adding the bits of the number and sign segments and for producing a sum segment and a carry segment each of b bits, the lowest level of the carry save adders consisting of a single carry save adder, means for rotating the bits of each carry segment produced by each carry save adder so that the most significant bit of each carry segment becomes the least significant bit of its corresponding rotated carry segment;
• circuit means for applying the number and sign segments of the binary number and the sum and rotated carry segments to carry save adders to reduce them to a single sum segment and a single rotated carry segment;
• a one's complement full adder for producing a sum in 1's complement notation of said single sum segment and said single rotated carry segment;
• and circuit means for applying said sum segment and said rotated carry segment to the full adder, said full adder producing the sum in 1's complement notation of said sum segment and said rotated carry segment, said sum being the residue of said signed binary number with respect to the check base.

The method of calculating the residue of a signed binary number with respect to a given check base, comprising the steps of:

• partitioning the bits of the binary number other than the sign bit into number segments, each of b bits per number segment starting with the least significant bit of the binary number, each of said number segments having boundaries;
• forming a sign segment of b bits in which the bit position in the sign segment corresponding to that of the sign bit relative to the closest boundary of a number segment is filled with a logical zero and all other bit positions are filled with the sign bit;
• applying the number and sign segments to a plurality of carry save adders, each of which produces a sum segment and carry segment each of b bits;
• rotating the bits of each carry segment to form rotated carry segment in which the most significant bit of each carry segment becomes the least significant bit of its corresponding rotated carry segment;
• reducing the sign and number segments and the sum and rotated carry segments produced by carry save adders to a single sum segment and a single rotated carry segment;
• and
• adding the single sum segment and single rotated carry segment in a one's complement adder to produce the residue of said signed binary number with respect to the given check base.