Method and apparatus for calculating the residue of a binary number

Apparatus for calculating the residue of a binary number of "n" bits with respect to a check base "m", said binary number being partitioned into a segment of "b" contiguous bits beginning with the least significant of the binary number, higher order bit positions of the segment containing the most significant bit of the binary number, being filled by logical 0's, where m=2.sup.b -1 and m, n and b are integers greater than 1, comprising:

• levels of carry save adders for adding the bits of the segments of the binary number and for producing a sum segment and a carry segment, 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 segments of the binary number and the sum and the rotated carry segments to carry save adders to reduce them to a single sum segment and a single rotated carry segment produced by the lowest carry save adder;
• a one's complement full adder for producing the residue of b bits of the binary number;
• and
• circuit means for applying the sum and rotated carry segments of the lowest level carry save adder to the full adder.

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

• partitioning the binary number into segments, each segment consisting of a plurality of contiguous bits beginning with the least significant bit of the binary number;
• filling higher order bit positions of the segment containing the most significant bit of the binary number with logical zeroes;
• applying the segments into which the binary number is partitioned to a plurality of carry save adders each carry save adder producing a sum segment and a carry segment;
• rotating the bits of the carry segments to form rotated carry segments in which the most significant bit of each carry segment becomes the least significant bit of the corresponding rotated carry segment;
• applying any segments into which the binary number is partitioned not previously applied to a carry save adder, sum segments and rotated carry segments to additional carry save adders until all the segments into which the binary number is partitioned and all rotated carry and sum segments are reduced to a single sum segment and a single rotated carry segment;
• and
• adding the single sum segment and the single rotated carry segment in a one's complement full adder to produce the residue of said binary number.