Method and apparatus for modulo arithmetic

Patent metadata

Field	Value
Publication number	US-9870201-B1
Application number	US-201615060850-A
Country	US
Kind code	B1
Filing date	Mar 4, 2016
Priority date	Mar 4, 2016
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

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.

First claim

The invention claimed is:

1. 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 i th 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 i th bit positions respectively are residues of 2 i 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 ┌log 2 N┐ 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 p th time, and
when N≦X (p) <2 ┌log 2 N┐ 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.

2. 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 i th 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 i th 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 i th bit position of the n bit binary representation is obtained by providing the value of the odd i th bit position to a shifter that performs a binary left shift operation.

3. The method of claim 2 ,
wherein a value of p is equal to one when (A) is performed a first time, and
the method further comprising:
controlling, by the processing device:
(B) when N≦X (p) <2 ┌log 2 N┐ is determined to be true, determining a final remainder X mod N to be equal to zero, in which X (p) is a value of X when (A) is performed a p th time, and
when N≦X (p) <2 ┌log 2 N┐ 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, and (A) is performed not more than three times.

4. The method of claim 3 ,
wherein, when (B) is performed, p is equal to 3 and N≦X (p) <2 ┌log 2 N┐ is determined not to be true, the final remainder X mod N is determined to be equal to X (p) .

5. The method of claim 2 ,
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.

6. 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 i th 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 2 i 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.

7. The method of claim 6 ,
wherein the at least two outputs forming the given modulo N bit pair correspond to at least two adjacent first and second bit positions of the n bit binary representation of the dividend.

8. 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 i th 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 i th bit positions respectively are residues of 2 i 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 ┌log 2 N┐ 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 p th p time, and
when N≦X (p) <2 ┌log 2 N┐ 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.

9. 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 i th 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 i th 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 d

Assignees

• Mbit Wireless Inc

Inventors

• Jeyachandra Angelin
• Patel Bhaskar

Classifications

• G06F7/72 Primary

  using residue arithmetic · CPC title

• G06F7/727 Primary

  Modulo N arithmetic, with N being either (2**n)-1,2**n or (2**n)+1, e.g. mod 3, mod 4 or mod 5 (G06F7/728 takes precedence) · CPC title

• G06F7/535

  Dividing only · CPC title