Method and device for calculating modulo operations
View Patent ↗A method for calculating a modulo operation a mod p uses a table (1) containing the values n*p for n=1, 2, . . . . In this case, a and p are positive integers where a mod p=a− n *p. An integral hypothesis n H is calculated for the unknown value n . Afterwards, the values n H *p and also at least one adjacent value (n H +1)*p and/or (n H −1)*p are looked up in the table (1). The expressions a−n H *p and also a−(n H +1)*p and/or a−(n H −1)*p are calculated and at least one of these expressions is compared with the value 0. n is thereupon determined.
1. A method for calculating a modulo operation a mod p using a table containing the values n*p for n=1, 2, . . . where a and p are positive integers and a mod p=a−n*p, comprising:
calculating, by a unit, an integral hypothesis n H for the unknown value n;
looking up, by a unit, the value n H *p and also at least one adjacent value (n H +1)*p and/or (n H −1)*p in the table;
calculating, by a unit, the expression a−n H *p and also at least one of the expressions a−(n H +1)*p and/or a−(n H −1)*p and comparing at least one of these expressions with the value 0; and
outputting, by a unit, the value a−n*p determined on the basis of the comparison,
wherein the method is used for calculating an intra-row permutation in the course of interleaving and/or deinterleaving of a bit stream according to a mobile radio standard.
2. The method according to claim 1 , wherein calculating the integral hypothesis n H comprises:
calculating a first approximation value for a/p of the form a/2 x , where x is a positive integer and is determined such that 2 x ≦p<2 x+1 holds true;
calculating n H from the first approximation value by disregarding the places after the decimal point of the approximation value.
3. The method according to claim 2 , wherein the first approximation value is calculated by right shifting the binary representation of a by x places.
4. The method according to claim 2 , wherein the least significant bit of the binary representation of the first approximation value has the significance 2 0 .
5. The method according to claim 1 , wherein calculating the integral hypothesis n H comprises:
calculating a first approximation value for a/p of the form a/2 x , where x is a positive integer;
calculating a correction value of the form p/2 x ;
inverting the correction value;
calculating a second approximation value as a product of the first approximation value and the inverted correction value; and
calculating n H from the second approximation value by disregarding the places after the decimal point of the second approximation value.
6. The method according to claim 5 , wherein x is determined such that 2 x ≦p<2 x+1 holds true.
7. The method according to claim 5 , wherein the correction value is calculated by right shifting the binary representation of p by x places.
8. The method according to claim 7 , wherein the least significant bit of the binary representation of the correction value has the significance 2 −t , where t is an integer greater than or equal to 1, in particular t=5.
9. The method according to claim 1 , wherein s(i)=a mod p where a=v*s(i−1) holds true, where p is a prime number and v is an integer.
10. The method according to claim 9 , wherein the mobile radio standard is the UMTS standard 3GPP TS 25.212.
11. A device for calculating a modulo operation a mod p, where a and p are positive integers and a mod p=a−n*p, comprising:
a table containing the values n*p for n=1, 2, . . . ,
a unit configured to calculate an integral hypothesis n H for the unknown value n,
a unit configured to look up the value n H *p and also at least one adjacent value (n H +1)*p and/or (n H −1)*p in the table,
a unit configured to calculate the expressions a−n H *p and also a−(n H +1)*p and/or a−(n H −1)*p and compare at least one of these expressions with the value 0, and
a unit configured to output the value a−n*p determined on the basis of the comparison.
12. The device according to claim 11 , wherein the unit configured to calculate an integral hypothesis n H contains a shift register, which carries out right shifting of the binary representation of the value of a by x places, where x is a positive integer and is determined such that 2 x ≦p<2 x+1 holds true.
13. The device according to claim 11 , wherein the unit configured to calculate an integral hypothesis n H furthermore comprises a ROM table with 2 t+1 entries and t+1 shift and addition stages, where t is a positive integer, in particular t=5.
14. The device according to claim 11 , comprising a state generator configured to calculate the values n*p for the entries of the table.