Back to results
US 9,870,201 B1Granted
Method and apparatus for modulo arithmetic
AssigneeMbit Wireless, Inc.
InventorsAngelin Jeyachandra, Bhaskar Patel
Life of this patent
Estimating the term…
Abstract
The procedure of finding the remainder of a division is referred to as modulo operation. Modulo arithmetic is used in many applications. A method and apparatus are disclosed that enable faster and less complex implementation of modulo arithmetic for a certain class of numbers.
Claims17
A method for computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the method comprising:
- controlling, by a processing device:
- (A) for each ith bit position of an n bit binary representation of the dividend X:
- when a value of the bit position is equal to 1, outputting, as an output for the bit position, a weight of the bit position, and
- when a value of the bit position is equal to 0, outputting, as the output for the bit position, a value equal to zero,
- in which the weights of the ith bit positions respectively are residues of 2i mod N, wherein i=0, 1, . . . , n−1;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions;
- and
- wherein a value of p is equal to one when (A) is performed a first time, and controlling, by the processing device:
- (B) when N≦X(p)<2┌log2N┐ is determined to be true, subtracting N from the dividend X to obtain a final remainder X mod N, in which X(p) is equal to the value of X when (A) is performed a pth time, and
- when N≦X(p)<2┌log2N┐ is determined not to be true, performing (A) and then performing (B),
- in which p is incremented by one each time (A) is performed after (A) is performed the first time,
- wherein, when (A) is performed a given time, the sum of the outputs for the respective bit positions at the given time (A) is performed is determined by an adder,
- in which the adder has a bit size according to a value of p corresponding to the given time (A) is performed and is supplied with the outputs for the respective bit positions at the given time (A) is performed.
11 more elements
A method for modulo 3 computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the method comprising:
- controlling, by a processing device:
- (A) for each even ith bit position of an n bit binary representation of the dividend X:
- outputting, as an output for the bit position, a value of the bit position, and for each odd ith bit position of the n bit binary representation of the dividend X
- outputting, as the output for the bit position, a value equal to zero when the value of the bit position is equal to zero and a value equal to two when the value of the bit position is equal to one;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions,
- wherein the output for each odd ith bit position of the n bit binary representation is obtained by providing the value of the odd ith bit position to a shifter that performs a binary left shift operation.
4 more elements
A method for computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the method comprising:
- controlling, by a processing device, for an n bit binary representation of the dividend X:
- for each ith bit position of the n bit representation input in an n bit register,
- when a value of the bit position at the n bit register is equal to 1, outputting, as an output of the register for the bit position, a weight of the bit position, and
- when a value of the bit position at the n bit register is equal to 0, outputting, as the output of the register for the bit position, a value equal to zero,
- in which the weights of the bit positions are respectively equal to 2i modulo N, wherein i=0, 1, . . . , n−1;
- and
- controlling, by the processing device, determining, as the remainder, a sum of predetermined outputs of the outputs for the respective bit positions by an adder having a bit size equal to the number of the predetermined outputs,
- in which the predetermined outputs include all of the outputs, in which a number of all of the outputs is n, except each at least two outputs of the outputs forming a modulo N bit pair, and
- in which the at least two outputs forming a given modulo N bit pair (i) are obtained for bit positions of the dividend having a value equal to one and (ii) have respective weights, in which a sum of the respective weights is equal to N.
6 more elements
An apparatus for computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the apparatus comprising:
- circuitry configured to control:
- (A) for each ith bit position of an n bit binary representation of the dividend X:
- when a value of the bit position is equal to 1, outputting, as an output for the bit position, a weight of the bit position, and
- when a value of the bit position is equal to 0, outputting, as the output for the bit position, a value equal to zero,
- in which the weights of the ith bit positions respectively are residues of 2i mod N, wherein i=0, 1, . . . , n−1;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions;
- and
- wherein a value of p is equal to one when (A) is performed a first time, and
- wherein the circuitry is configured to control:
- (B) when N≦X(p)<2┌log2N┐ is determined to be true, subtracting N from the dividend X to obtain a final remainder X mod N, in which X(p) is equal to the value of X when (A) is performed a pth p time, and
- when N≦X(p)<2┌log2N┐ is determined not to be true, performing (A) and then performing (B),
- in which p is incremented by one each time (A) is performed after (A) is performed the first time,
- wherein, when (A) is performed a given time, the sum of the outputs for the respective bit positions at the given time (A) is performed is determined by an adder of the circuitry,
- in which the adder has a bit size according to a value of p corresponding to the given time (A) is performed and is supplied with the outputs for the respective bit positions at the given time (A) is performed.
12 more elements
An apparatus for modulo 3 computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the apparatus comprising:
- circuitry configured to control:
- (A) for each even ith bit position of an n bit binary representation of the dividend X:
- outputting, as an output for the bit position, a value of the bit position, and for each odd ith bit position of the n bit binary representation of the dividend X
- outputting, as the output for the bit position, a value equal to zero when the value of the bit position is equal to zero and a value equal to two when the value of the bit position is equal to one;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions,
- wherein the output for each odd ith bit position of the n bit binary representation is obtained by providing the value of the odd ith bit position to a shifter of the circuitry that performs a binary left shift operation.
4 more elements
An apparatus for computation of a remainder of dividing a dividend X by a divisor N when processing a signal obtained from a processing system, the apparatus comprising:
- circuitry configured to control, for an n bit binary representation of the dividend X:
- for each ith bit position of the n bit representation input in an n bit register,
- when a value of the bit position at the n bit register is equal to 1, outputting, as an output of the register for the bit position, a weight of the bit position, and
- when a value of the bit position at the n bit register is equal to 0, outputting, as the output of the register for the bit position, a value equal to zero,
- in which the weights of the bit positions are respectively equal to 2i modulo N, wherein i=0, 1, . . . , n−1;
- and
- wherein the circuitry is configured to control determining, as the remainder, a sum of predetermined outputs of the outputs for the respective bit positions by an adder having a bit size equal to a number of the predetermined outputs,
- in which the predetermined outputs include all of the outputs, in which a number of all of the outputs is n, except each at least two outputs of the outputs forming a modulo N bit pair, and
- in which the at least two outputs forming a given modulo N bit pair (i) are obtained for bit positions of the dividend having a value equal to one and (ii) have respective weights, in which a sum of the respective weights is equal to N.
6 more elements
A communication device comprising:
- a receiver to receive a signal;
- and
- a processing device to control computation of a remainder of dividing a dividend X by a divisor N when processing the signal:
- wherein the processing device is configured to control:
- (A) for each ith bit position of an n bit binary representation of the dividend X:
- when a value of the bit position is equal to 1, outputting, as an output for the bit position, a weight of the bit position, and
- when a value of the bit position is equal to 0, outputting, as the output for the bit position, a value equal to zero,
- in which the weights of the ith bit positions respectively are residues of 2i mod N, wherein i=0, 1, . . . , n−1;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions;
- and
- wherein a value of p is equal to one when (A) is performed a first time, and
- wherein the processing is configured to control:
- (B) when N≦X(p)<2┌log2N┐ is determined to be true, subtracting N from the dividend X to obtain a final remainder X mod N, in which X(p) is equal to the value of X when (A) is performed a pth time, and
- when N≦X(p)<2┌log2N┐ is determined not to be true, performing (A) and then performing (B),
- in which p is incremented by one each time (A) is performed after (A) is performed the first time,
- wherein, when (A) is performed a given time, the sum of the outputs for the respective bit positions at the given time (A) is performed is determined by an adder,
- in which the adder has a bit size according to a value of p corresponding to the given time (A) is performed and is supplied with the outputs for the respective bit positions at the given time (A) is performed.
15 more elements
A communication device comprising:
- a receiver to receive a signal;
- and
- a processing device for modulo 3 computation of a remainder of dividing a dividend X by a divisor N when processing the signal,
- wherein the processing device is configured to control:
- (A) for each even ith bit position of an n bit binary representation of the dividend X:
- outputting, as an output for the bit position, a value of the bit position, and for each odd ith bit position of the n bit binary representation of the dividend X
- outputting, as the output for the bit position, a value equal to zero when the value of the bit position is equal to zero and a value equal to two when the value of the bit position is equal to one;
- and
- setting the dividend X equal to a sum of the outputs for the respective bit positions,
- wherein the output for each odd ith bit position of the n bit binary representation is obtained by providing the value of the odd ith bit position to a shifter that performs a binary left shift operation.
7 more elements
A communication device comprising:
- a receiver to receive a signal;
- and
- a processing device for computation of a remainder of dividing a dividend X by a divisor N when processing the signal,
- wherein the processing device is configured to control, for an n bit binary representation of the dividend X:
- for each ith bit position of the n bit representation input in an n bit register,
- when a value of the bit position at the n bit register is equal to 1, outputting, as an output of the register for the bit position, a weight of the bit position, and
- when a value of the bit position at the n bit register is equal to 0, outputting, as the output of the register for the bit position, a value equal to zero,
- in which the weights of the bit positions are respectively equal to 2i modulo N, wherein i=0, 1, . . . , n−1;
- and
- wherein the processing device is configured to control, determining, as the remainder, a sum of predetermined outputs of the outputs for the respective bit positions by an adder having a bit size equal to the number of the predetermined outputs,
- in which the predetermined outputs include all of the outputs, in which a number of all of the outputs is n, except each at least two outputs of the outputs forming a modulo N bit pair, and
- in which the at least two outputs forming a given modulo N bit pair (i) are obtained for bit positions of the dividend having a value equal to one and (ii) have respective weights, in which a sum of the respective weights is equal to N.
9 more elements
Dependencies are inferred from the claim text.