Method and apparatus for modulo operation

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.sup.k+1.

Claims

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.sup.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.sup.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.sup.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.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 illustrates a first method for remainder computation according to the aspects of the present invention.

(2) FIG. 2 illustrates a second method for remainder computation according to the aspects of the present invention.

(3) FIG. 3 illustrates a wireless mobile station diagram, which may be employed with aspects of the invention described herein.

(4) FIG. 4 illustrates an application processor subsystem for a wireless mobile station, which may be employed with aspects of the invention described herein.

(5) FIG. 5 illustrates a baseband subsystem for a wireless mobile station, which may be employed with aspects of the invention described herein.

(6) FIG. 6 illustrates an RF subsystem for a wireless mobile station, which may be employed with aspects of the invention described herein.

DETAILED DESCRIPTION

(7) The foregoing aspects, features and advantages of the present invention will be further appreciated when considered with reference to the following description of exemplary embodiments and accompanying drawings, wherein like reference numerals represent like elements. In describing the exemplary embodiments of the invention illustrated in the appended drawings, specific terminology will be used for the sake of clarity. However, the invention is not intended to be limited to the specific terms used.

(8) Two methods and apparatus are described to efficiently compute the remainder of any number when the divisor is a class of Cunningham numbers. The first method is illustrated with an example where the dividend is m=173 and the divisor is n=5=2.sup.2+1. The computation of a remainder according to the aspects of the present invention is illustrated in the table contained FIG. 1. Row 1 in FIG. 1 shows the binary representation of the dividend. Row 2 shows the weight of each bit position for binary representation. Row 3 shows the nearest number that is integral multiple of the divisor and is closest to the weight of each bit position. Row shows the difference (Δ) between Row 2 and Row 3. Row 5 shows the multiplication of Row 4 with Row 1 to get only the values in Row 4 that are relevant for the given dividend. Row shows the combination of all the valid Δ from Row 5. According to an aspect of the present invention, the valid Δ from Row 5 are combined to generate the partial sum in Row 6. According to another aspect of the present invention, if this partial sum is negative, then the divisor (in this example the divisor n=5) is added recursively until the updated partial sum becomes positive. When the partial sum becomes positive, that is the required remainder of the division operation. According to another aspect of the invention, if the partial sum in Row 6 is positive but greater than the divisor, then the divisor is subtracted from the partial sum until it becomes less than the divisor. When the partial sum does become less than divisor, that is the required remainder of the division operation.

(9) For the 3GPP LTE specific remainder computation specified by EQ. 1, the computation of the remainder may be performed more efficiently as illustrated in FIG. 2. Based on the definition of the parameter Y.sub.k in EQ. 1, its value is constrained to be within 32 bits. As shown in FIG. 2, the product of the two terms (A*Y.sub.k-1) is computed first. This may be implemented in a number of different ways such as a 16×16 bit multiplier. Alternatively, the multiplication may be implemented with a shift-and-add method by using only adders or using canonical signed digit representation of the input number which may require fewer adders and subtractors than shift-and-add method.

(10) Regardless of the product term that is obtained, it is then split into two parts: upper 16 bits (U16) and lower 16 bits (L16) as shown in FIG. 2. This is equivalent to grouping the dividend into 16-bit groups, i.e., according to the power of the base of the divisor n. The operation in EQ. 1 can be carried out by subtracting U16 from L16 as shown in FIG. 2 to obtain the remainder (REM). If the result of subtraction (REM) is positive then the final result of EQ. 1 is obtained (FINAL_REM). If the result of subtraction is negative then the final result of EQ. 1 (FINAL_REM) is obtained by adding divisor D=65537 to the REM. For example, suppose the product term (A*Y.sub.k-1)=492022758. The binary representation of this number is: 00011101010100111010101111100110
The upper 16 bits (U16) are 0001110101010011 and the lower 16 bits (L16) are 1010101111100110. Therefore, REM=L16−U16=1010101111100110−0001110101010011 =44006−7507 =36499
Since this is a positive number, (492022758 mod 65537)=36499 is the final value of the remainder, i.e., FINAL_REM=REM.
As another example, suppose the product term (A*Y.sub.k-1)=3158323257. The binary representation of this number is: 10111100010000000011000000111001
The upper 16 bits (U16) are 1011110001000000 and the lower 16 bits (L16) are 0011000000111001. Therefore, REM=L16−U16=0011000000111001−1011110001000000 =12345−48192 =−35847

(11) Since this is a negative number, value of D is added to the answer: −35847+D=29690 to obtain the final answer, i.e., FINAL_REM=REM+D. This is the same as the remainder obtained by direct computation, i.e., (3158323257 mod 65537)=29690.

(12) The methods disclosed according to aspects of this invention enable a reduced complexity implementation of remainder computation when the divisor belongs to a class of Cunningham numbers such that they are of the form b.sup.k+1 and where k is even. The disclosed method may reduce the hardware complexity and power consumption of the 3GPP LTE client terminals.

(13) By way of example only, the above described method may be implemented in a user device such as a wireless mobile station (MS).

(14) As shown in FIG. 3, MS 100 may include an application processor subsystem 101, baseband subsystem 102 and a radio frequency (RF) subsystem 104 for use with a wireless communication network. A display/user interface 106 provides information to and receives input from the user. By way of example, the user interface may include one or more actuators, a speaker and a microphone. In some mobile devices, certain combination of the application processor subsystem 101, the baseband subsystem 102 and the RF subsystem 104 are all Integrated as one integrated chip.

(15) The application processor subsystem 101 as shown in FIG. 4 may include a controller 108 such as a microcontroller, another processor or other circuitry. The baseband subsystem 102 as shown in FIG. 5 may include a controller 118 such as a microcontroller or other processor. The RF subsystem 104 as shown in FIG. 6 may include a controller 128 such as a microcontroller, another processor or other circuitry. The controller 108 desirably handles overall operation of the MS 100. This may be done by any combination of hardware, software and firmware running on the controller 108. Such a combination of hardware, software and firmware may embody any methods in accordance with the aspects of the present invention.

(16) In FIG. 4 the peripherals 114 such as a full or partial keyboard, video or still image display, audio Interface, etc may be employed and managed through the controller 108.

(17) Aspects of the present invention may be implemented in firmware of the controller 108 of the application processor in FIG. 4 and/or the controller 118 of the baseband subsystem as shown in FIG. 3. In another alternative, aspects of the present invention may also be implemented as a combination of firmware and hardware of the application processor subsystem 101 and/or the baseband subsystem 102. For instance, signal processing functionality of any or all of the FIG. 5 may be implemented in firmware and/or software, which is executed by the system hardware. It may be part of the baseband subsystem, the receiver subsystem or be associated with both subsystems. In one example, the controller 118 and/or the signal processor 110 may include or control the protocol entity circuitry. The software may reside in internal or external memory and any data may be stored in such memory. The hardware may be an application specific integrated circuit (ASIC), field programmable gate array (FPGA), discrete logic components or any combination of such devices. The terms controller and processor are used interchangeably herein.

(18) The consumer electronics devices that may use the aspects of the invention may include smartphones, tablets, laptops, gaming consoles, cameras, video camcorders, TV, car entertainment systems, etc.

(19) Although aspects of the invention herein have been described with reference to particular embodiments, it is to be understood that these embodiments are merely illustrative of the principles and applications of the aspects of the present invention. It is therefore to be understood that numerous modifications may be made to the illustrative embodiments and that other arrangements may be devised without departing from the spirit and scope of the aspects of the present invention as defined by the appended claims. Aspects of each embodiment may be employed in the other embodiments described herein.