Method and apparatus for modulo operation

Patent metadata

Field	Value
Publication number	US-9841946-B1
Application number	US-201514938053-A
Country	US
Kind code	B1
Filing date	Nov 11, 2015
Priority date	Nov 11, 2015
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

In some applications, such as randomization and cryptography, remainder computation for a number is required. The remainder computation is also used in modulo arithmetic. The remainder computation can be simplified when the divisor belongs to a certain class of numbers. A method and apparatus are disclosed that enable low complexity implementation of remainder computation of any number when the divisor belongs to a type of numbers that can be represented as 2 k +1.

First claim

The invention claimed is:

1. A method for searching information of a communication signal received at a communication device from a wireless communication network for a predetermined message, in which the searching includes computation, based on the information of the communication signal, of a remainder of dividing a dividend by a divisor, and in which the divisor is equal to any of b k ±1, b and k are integers and b is not a power of another number, the method comprising:
controlling, by a processing device, the searching,
in which the searching includes, for each bit position of a binary representation of the dividend:
subtracting, from a weight of the bit position, an integral multiple of the divisor nearest to the weight of the bit position, to obtain a difference, and
multiplying the difference by a value of the bit position to obtain a product;

controlling, by the processing device, summing the products respectively for the bit positions to obtain a first sum, in which the remainder is the first sum unless the first sum is (i) negative or (ii) positive and greater than the divisor; and
in which the searching includes
when the first sum is negative, adding the divisor recursively to the first sum to obtain a second sum until the second sum is positive, in which the remainder is the second sum when the second sum is positive, and
when the first sum is positive and greater than the divisor, recursively subtracting the divisor from the first sum to obtain a third sum until the third sum is less than the divisor, in which the remainder is the third sum when the third sum is less than the divisor.

2. An apparatus for searching information of a communication signal received at a communication device from a wireless communication network for a predetermined message, in which the searching includes computation, based on the information of the communication signal, of a remainder of dividing a dividend by a divisor, and in which the divisor is equal to any of b k ±1, b and k are integers and b is not a power of another number, the apparatus comprising:
circuitry configured to control the searching,
in which the searching includes, for each bit position of a binary representation of the dividend:
subtracting, from a weight of the bit position, an integral multiple of the divisor nearest to the weight of the bit position, to obtain a difference, and
multiplying the difference by a value of the bit position to obtain a product;

in which the searching includes summing the products respectively for the bit positions to obtain a first sum, in which the remainder is the first sum unless the first sum is (i) negative or (ii) positive and greater than the divisor; and
in which the searching includes
when the first sum is negative, adding the divisor recursively to the first sum to obtain a second sum until the second sum is positive, in which the remainder is the second sum when the second sum is positive, and
when the first sum is positive and greater than the divisor, recursively subtracting the divisor from the first sum to obtain a third sum until the third sum is less than the divisor, in which the remainder is the third sum when the third sum is less than the divisor.

3. A wireless communication device comprising:
a receiver to receive a communication signal obtained from a wireless communication network;
a processing device configured to control searching information of the communication signal for a predetermined message, in which the searching includes computation, based on the information of the communication signal, of a remainder of dividing a dividend by a divisor, and in which the divisor is equal to any of b k ±1, b and k are integers and b is not a power of another number;
in which the searching includes, for each bit position of a binary representation of the dividend:
subtracting, from a weight of the bit position, an integral multiple of the divisor nearest to the weight of the bit position, to obtain a difference, and
multiplying the difference by a value of the bit position to obtain a product;

in which the searching includes summing the products respectively for the bit positions to obtain a first sum, in which the remainder is the first sum unless the first sum is (i) negative or (ii) positive and greater than the divisor; and
in which the searching includes
when the first sum is negative, adding the divisor recursively to the first sum to obtain a second sum until the second sum is positive, in which the remainder is the second sum when the second sum is positive, and
when the first sum is positive and greater than the divisor, recursively subtracting the divisor from the first sum to obtain a third sum until the third sum is less than the divisor, in which the remainder is the third sum when the third sum is less than the divisor.

Assignees

• Mbit Wireless Inc

Inventors

• Patel Bhaskar
• Govindswamy Arumugam

Classifications

• G06F7/72 Primary

  using residue arithmetic · CPC title

• G06F7/727

  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/38 Primary

  Methods or arrangements for performing computations using exclusively denominational number representation, e.g. using binary, ternary, decimal representation · CPC title