| 摘要 |
Method and apparatus for calculating the residue of a binary number of "n" bits with respect to a given check base m where m=2b-1. The binary number is partitioned into segments, each of b bits starting with the least significant bit. If n is not an even multiple of b, higher order bit positions of the segment containing the most significant bit of the number are filled with logical zeros. The segments are applied to levels of carry save adders to reduce the segments of the binary number to a single sum segment of b bits and a single rotated carry segment of b bits where a rotated carry segment is a carry segment produced by a carry save adder, the most significant bit of which is rotated so that it becomes the least significant bit of the rotated carry segment. Carry segments produced by carry save adders of one level are converted to rotated carry segments before being applied to a carry save adder of a lower level carry save adder. The single sum segment and single rotated carry segment produced by the lowest level carry save adder are applied to a 1's complement full adder. The b bit output of the 1's complement full adder is the residue of the binary number with respect to the check base (2b-1).
|
