Residue circuit
AssigneeNEC Corporation
InventorsTsugio Takahashi, Hitoshi Fujita, Hiroshi Okamoto
Life of this patent
Estimating the term…
Abstract
A residue circuit takes weights of even number bits of a dividend as 1 and weights of odd number bits of the dividend as 2. The circuit includes a plurality of adders for summing bits having weight 1 to output weight 1 at a summing output and weight 2 at a carry output, and a plurality of adders for summing bits having weight 2 to output weight 2 at a summing output and weight 1 at a carry output. With these adders, summing of respective bits of the dividend bits are performed taking the weights into account to repeat summing until the number of bits finally becomes 3 bits. Depending upon the pattern of this 3 bits, a remainder is output by a modulus 3 generation circuit.
Claims6
A residue circuit for calculating a remainder through division of a dividend of a binary number having six bits, comprising:
- first adding means for summing 3 bits in even number bits of even bits of said dividend to generate a summing output and a carry output;
- second adding means for summing 3 bits in odd number bits of even bits of said dividend to generate a summing output and a carry output;
- third adding means for summing said summing output of said first adding means and said carry output of said second adding means for generating a summing output and a carry output;
- fourth adding means for summing said summing output of said second adding means, said carry output of said first adding means and said carry output of said third adding means for generating a summing output and a carry output;
- and
- a remainder generation means for outputting a remainder with respect to divisor 3 according to a bit pattern of said summing output of said third adding means, said summing output and said carry output of said fourth adding means.
A residue circuit for calculating a remainder of a division for a binary dividend of 0th to nth bits and having at least four bits, comprising:
- a plurality of weight 1 adding means setting weights for respective even number bits of said dividend being 1 and for respective odd number bits of said dividend being 2, for generating a weight 1 signal at a summing output and a weight 2 signal at a carry output through addition of signals of weight 1;
- a plurality of weight 2 adding means for summing signals of weight 2 for generating a weight 2 signal at a summing output and a weight 1 signal at a carry output;
- said plurality of weight 1 adding means and said plurality of weight 2 adding means repeatedly performing summing processes for the signals having the same weights until the total number of signals of said summing outputs and said carry outputs becomes m which is smaller than n;
- and
- further comprising a remainder generation means for outputting a remainder with respect to a divisor 3 according to a pattern of m bits.
Dependencies are inferred from the claim text.