Abstract:
A base sequence S(j) is not directly calculated but is indirectly calculated by the use of a numerical sequence M(n)=[v×n] mod p. A value of M(n) can be calculated by a recurrence formula without requiring modulo calculation. The value obtained is stored in a memory. M(n) satisfies S(j)=M(S(j−1)). By determining an initial value of S(j) and interleaving the value of M(n) stored in the memory, the base sequence S(j) can be calculated without modulo calculation.

Description:
[0001]     This application claims priority to prior Japanese application JP 2003-298493, the disclosure of which is incorporated herein by reference.  
       BACKGROUND OF THE INVENTION  
       [0002]     This invention relates to a mobile telephone, an interleave parameter calculating apparatus, an interleave parameter calculating method, and an interleave parameter calculating program each of which requires a reduced amount of calculation upon obtaining a base sequence for intra-row permutation in a turbo code interleaver.  
         [0003]     In a turbo code interleaver defined in 3GPP (3rd Generation Partnership Project) TS (Technical Specification) 25.212 ver. 3.10.0 as a standard of IMT2000 (International Mobile Telephony 2000) (W-CDMA (Wideband Code Division Multiple Access)), a base sequence S(j) for intra-row permutation is calculated by the use of a prime number p and an associated primitive root v.
 
 S ( j )=[ v×S ( j− 1)] mod  p, 
 
 j= 1, 2, . . . , ( p− 2), and  S (0)=1
 
         [0004]     The base sequence S(j) is calculated through a process illustrated in  FIG. 1 .  
         [0005]     A turbo code was presented by Berrou et al and is characterized in the following respects.  
         [0006]     (1) Concatenated coding in which an information sequence and a rearranged or interleaved information sequence interleaved by the interleaver are individually encoded by component encoders and combined into code words.  
         [0007]     (2) Iterative decoding in which decoding is iteratively carried out by the use of a decoding result of the other.  
         [0008]     Japanese Patent Application Publication (JP-A) No. 2003-152551 focuses upon interleaving by the interleaver and proposes a method of solving a problem in a mobile communication system, i.e., necessity of a large number of interleave patterns so as to meet a wide variety of interleaving lengths.  
         [0009]     In a processor used in a mobile telephone or the like, modulo calculation is often carried out digit by digit in order to reduce a circuit scale. Assuming that a data width is equal to 16 bits, 16 unit steps are required for calculation given by:
 
 S ( j )= S ( j ) mod  p  (step  S   104 ).
 
 It is assumed that a conditional branch (step S 105 ) requires two unit steps and each of the remaining steps (steps S 102  and S 103 ) requires one unit step. Then, in the process illustrated in  FIG. 1 , 20 unit steps are required in a single loop S(steps S 102  to S 105 ). 
 
         [0011]     According to the definition of 3GPP, the prime number p has a maximum value of 257. Therefore, this loop is repeated 255 times at maximum. Therefore, a processing time is disadvantageously increased.  
         [0012]     Herein, S(j) is calculated as the base sequence. However, if the number C of columns of the interleaver is equal to p−1, Sm(j) is required instead of S(j).
 
 Sm ( j )= S ( j )−1
 
 In this case, another unit step of subtracting 1 from each value of S(j) is required. Consequently, the single loop requires 21 steps. 
 
       SUMMARY OF THE INVENTION  
       [0014]     It is an object of this invention to provide means for decreasing the number of unit steps in a single loop for calculating a base sequence S(j) or Sm(j) and reducing a processing time.  
         [0015]     According to this invention, there is provided a mobile telephone comprising, in order to obtain a base sequence for intra-row permutation in a turbo code interleaver:  
         [0016]     calculating means for calculating M(n) represented by:
 
 M ( n )=[ v×n ] mod  p, 
 
 where n is a natural number, p is a prime number, and v is an associated primitive root, by the use of:
 
 M ( n )= M ( n− 1)+ v (if  M ( n −1)+ v&lt;p ), or
 
 M ( n )= M ( n− 1)+ v−p (if  M ( n− 1)+ v≧p );
 
         [0018]     first storing means for storing values obtained by the calculating means into a memory;  
         [0019]     reading means for reading the values stored in the memory by the first storing means;  
         [0020]     interleaving means for interleaving the values read by the reading means; and  
         [0021]     second storing means for storing a numerical sequence obtained by interleaving by the interleaving means into a memory.  
         [0022]     According to this invention, there is also provided an interleave parameter calculating apparatus comprising, in order to obtain a base sequence for intra-row permutation in a turbo code interleaver:  
         [0023]     calculating means for calculating M(n) represented by:
 
 M ( n )=[ v×n ] mod  p, 
 
 where n is a natural number, p is a prime number, and v is an associated primitive root, by the use of:
 
 M ( n )= M ( n− 1)+ v (if  M ( n− 1)+ v&lt;p ), or
 
 M ( n )= M ( n− 1)+ v−p (if  M ( n− 1)+ v≧p );
 
         [0025]     first storing means for storing values obtained by the calculating means into a memory;  
         [0026]     reading means for reading the values stored in the memory by the first storing means;  
         [0027]     interleaving means for interleaving the values read by the reading means; and  
         [0028]     second storing means for storing a numerical sequence obtained by interleaving by the interleaving means into a memory.  
         [0029]     According to this invention, there is also provided an interleave parameter calculating apparatus comprising, in order to obtain a base sequence for intra-row permutation in a turbo code interleaver:  
         [0030]     calculating means for calculating M(n) represented by:
 
 M ( n )=[ v×n ] mod  p, 
 
 where n is a natural number, p is a prime number, and v is an associated primitive root, by the use of:
 
 M ( n )= M ( n− 1)+ v (if  M ( n− 1)+ v&lt;p ), or
 
 M ( n )= M ( n− 1)+ v−p (if  M ( n− 1)+ v≧p );
 
         [0032]     first storing means for storing values obtained by the calculating means into a memory;  
         [0033]     reading means for reading the values stored in the memory by the first storing means;  
         [0034]     interleaving means for interleaving the values read by the reading means; and  
         [0035]     second storing means for storing a numerical sequence obtained by interleaving by the interleaving means into a memory.  
         [0036]     According to this invention, there is also provided an interleave parameter calculating method, comprising, in order to obtain a base sequence for intra-row permutation in a turbo code interleaver:  
         [0037]     a calculating step of calculating M(n) represented by:
 
 M ( n )=[ v×n ] mod  p, 
 
 where n is a natural number, p is a prime number, and v is an associated primitive root, by the use of:
 
 M ( n )= M ( n− 1)+ v (if  M ( n− 1)+ v&lt;p ), or
 
 M ( n )= M ( n− 1)+ v−p (if  M ( n− 1)+ v≧p );
 
         [0039]     a first storing step of storing values obtained by the calculating step into a memory;  
         [0040]     a reading step of reading the values stored in the memory by the first storing step;  
         [0041]     an interleaving step of interleaving the values read by the reading step; and  
         [0042]     a second storing step of storing a numerical sequence obtained by interleaving by the interleaving step into a memory.  
         [0043]     According to this invention, there is also provided an interleave parameter calculating program for making a computer execute, in order to obtain a base sequence for intra-row permutation in a turbo code interleaver:  
         [0044]     a calculating operation of calculating M(n) represented by;
 
 M ( n )=[v×n] mod  p, 
 
 where n is a natural number, p is a prime number, and v is an associated primitive root, by the use of:
 
 M ( n )= M ( n− 1)+ v (if  M ( n− 1)+ v&lt;p ), or
 
 M ( n )= M ( n− 1)+ v−p (if  M ( n− 1)+ v≧p );
 
         [0046]     a first storing operation of storing values obtained by the calculating operation into a memory;  
         [0047]     a reading operation of reading the values stored in the memory by the first storing operation;  
         [0048]     an interleaving operation of interleaving the values read by the reading operation; and  
         [0049]     a second storing operation of storing a numerical sequence obtained by interleaving by the interleaving operation into a memory.  
         [0050]     According to this invention, it is possible to obtain a base sequence without carrying out modulo calculation. Therefore, the amount of calculation is reduced and the speed of calculation is increased. Further, a circuit for modulo calculation is unnecessary. Therefore, a circuit scale is reduced and a cost is lowered.  
       BRIEF DESCRIPTION OF THE DRAWING  
       [0051]      FIG. 1  is a flow chart for describing calculation of a base sequence S(j) according to a conventional method;  
         [0052]      FIG. 2  is a block diagram showing a structure according to a first embodiment of this invention;  
         [0053]      FIG. 3  is a flow chart for describing calculation of M(n);  
         [0054]      FIG. 4  is a flow chart for describing an operation of reading M(n) from a memory;  
         [0055]      FIG. 5  is a block diagram showing a structure according to a second embodiment of this invention;  
         [0056]      FIG. 6  is a block diagram for use in describing a M(n) calculator illustrated in  FIG. 5 ; and  
         [0057]      FIG. 7  is a block diagram for use in describing a permutation unit illustrated in  FIG. 5 . 
     
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0058]     At first, a principle characterizing this invention will be described.  
         [0059]     For all values of n (0, 1, . . . , p−1), M(n) is calculated as:
 
 M ( n )=[ v×n ] mod  p 
 
 In order to help understanding of formula transformation, M(n) is rewritten by the use of:
 
 a ( n )=floor([ v×n]/p )
 
 Then, M(n) is given by:  
               M   ⁡     (   n   )       =       ⁢       [     v   ×   n     ]     ⁢   mod   ⁢           ⁢   p                 =       ⁢       [       v   ×     [     n   -   1     ]       -       a   ⁡     (     n   -   1     )       ×   p     +   v     ]     ⁢   mod   ⁢           ⁢   p                     =       ⁢       [       M   ⁡     (     n   -   1     )       +   v     ]     ⁢   mod   ⁢           ⁢   p       ,     ⁢                     
 
 where the floor ( ) function is for truncating the decimal value. 
 
 According to the definition of 3GPP, v&lt;p. Therefore, the following relationship is established.
 
 M ( n− 1)+ v&lt;M ( n− 1)+ p&lt; 2× p 
 
 Therefore, M(n) is represented by Equation (1). By calculating Equation (1) sequentially from n=1, M(n) can be calculated without requiring modulo calculation.  
                     M   ⁡     (   n   )       =     {             M   ⁡     (     n   -   1     )       +   v           (         if   ⁢           ⁢     M   ⁡     (     n   -   1     )         +   v     &lt;   p     )                 M   ⁡     (     n   -   1     )       +   V   -   p           (         if   ⁢           ⁢     M   ⁡     (     n   -   1     )         +   v     ≧   p     )                           n   =   2     ,   3   ,   …   ⁢           ,         (     p   -   2     )     ⁢           ⁢   and   ⁢           ⁢     M   ⁡     (   1   )         =   v                   (   1   )             
 
         [0065]     Using M(n), S(j) is represented by:  
               S   ⁡     (   j   )       =       ⁢       [     v   ×     S   ⁡     (     j   -   1     )         ]     ⁢   mod   ⁢           ⁢   p                 =       ⁢     M   ⁡     (     S   ⁡     (     j   -   1     )       )                 
 
 Thus, S(j) can be calculated without requiring modulo calculation. 
 
         [0067]     Now, description will be made of a process and an apparatus for realizing a method of calculating a base sequence without requiring modulo calculation according to the above-mentioned principle.  
         [0068]     First Embodiment  
         [0069]     Referring to  FIG. 2 , a processor  11  calculates M(n) and S(j). A M(n) memory  12  stores M(n) calculated by the processor  11 . A S(j) memory  13  stores S(j) calculated by the processor  11 .  
         [0070]     At first, the processor  11  calculates M(n). Referring to  FIG. 3 , a calculation process will be described. M(n) is initialized and calculated (steps S 201  to S 203 ). According to Equation (1), case classification is carried out (step S 204 ). If M(n)≧p, M(n) is given a value of M(n)−p (step S 205 ). A loop of the steps S 202  to S 205  is repeated while n&lt;(p−1) (YES in step S 206 ). If n=(p−1) (NO in step S 206 ), the loop is quitted. The result of calculation of M(n) is stored in the M(n) memory  12 .  
         [0071]     Next referring to  FIG. 4 , the processor  11  sets initial values j=0 and n=1 (step S 301 ). Thereafter, M(n) is read from the M(n) memory  12  according to S(j)=M(S(j−1)) (steps S 302  to S 305 ) and is stored in the S(j) memory  13 . In this manner, S(j) is produced in the S(j) memory  13 .  
         [0072]     Herein, it is assumed that each of conditional branches (steps S 204 , S 206 , S 305 ) requires two unit steps and each of the remaining steps (steps S 202 , S 203 , S 205 , S 302  to S 304 ) requires one unit step, like in the conventional method. Then, in this embodiment, 12 steps are required. Thus, the number of unit steps as the amount of processing is reduced. Since the prime number p has a maximum value of 257, it is possible to reduce the amount of processing by 2048 unit steps at maximum.  
         [0073]     In case where Sm(j) is calculated, it is necessary to merely change setting of the initial values. Specifically, the initial value of n in  FIG. 3  is given 0, M(n) in  FIG. 3  is given (v−1). and the initial value of n in  FIG. 4  is given 0. Thus, without increasing the number of unit steps, Sm(j) can be obtained.  
         [0074]     Depending upon the number C of columns of the interleaver, a required base sequence is different and selected from S(j) and S(j)−1=Sm(j). The required base sequence (represented by Sf(j)) is given by Equation (2).  
                     Sf   ⁡     (   j   )       =     {           S   ⁡     (   j   )             (         if   ⁢           ⁢   C     ==   p     ,     p   +   1       )               Sm   ⁡     (   j   )             (       if   ⁢           ⁢   C     ==     p   -   1       )                           j   =   0     ,   1   ,   …   ⁢           ,     p   -   2                   (   2   )             
 
         [0075]     Herein, S(j) and Sm(j) have maximum values 256 and 255 when p=257, respectively. In order to represent these values by binary numbers, 9 bits and 8 bits are required, respectively. When p=257, C=p−1. Therefore, Sf(j) is represented by 8 bits at maximum. Thus, by changing the initial values of M(0) and n to directly obtain Sf(j) depending upon the situation, the bit width of each of the M(n) and S(j) memories  12  and  13  can be reduced by 1 bit, as compared with the case where S(j) is calculated and then 1 is subtracted from S(j) depending upon the situation.  
         [0076]     Further, the M(n) memory  12  is unnecessary during turbo coding and decoding. Therefore, it is possible to reduce the circuit scale by using the M(n) memory  12  as a memory of a turbo codec during turbo coding and decoding.  
         [0077]     According to this embodiment, it is possible to decrease the number of unit steps of the process and to reduce an operation time of the processor. Further, by reducing the operation time of the processor, power consumption can be reduced.  
         [0078]     Second Embodiment  
         [0079]     Referring to  FIG. 5 , a M(n) calculator  41  calculates M(n). A M(n) memory  42  stores M(n) calculated by the M(n) calculator  41 . A permutation unit  43  interleaves M(n) to produce S(j). A S(j) memory  44  stores S(j) produced by the permutation unit  43 .  
         [0080]     Referring to  FIG. 6 , description will be made of the M(n) calculator  41 .  
         [0081]     The M(n) storage memory  42  is for storing a value of M(n).  
         [0082]     A memory address producing counter  54  produces a store address where the value of M(n) is to be stored.  
         [0083]     A register  55  has the value of M(n).  
         [0084]     A constant block  56  has a value of v.  
         [0085]     A constant block  57  has a value of −p.  
         [0086]     A selector  58  selects an output value depending upon the value of M(n)−p.  
         [0087]     A selector  59  selects the store address for the value of M(n).  
         [0088]     Thus, the M(n) calculator  41  includes the memory address producing counter  54 , the register  55 , the constant block  56 , the constant block  57 , the selector  58 , and the selector  59 .  
         [0089]     Referring to  FIG. 7 , the permutation unit  43  will be described.  
         [0090]     The M(n) memory  42  stores the value of M(n).  
         [0091]     The S(j) memory  44  is for storing the value of S(j).  
         [0092]     A selector  65  selects a read address of M(n).  
         [0093]     A selector  66  selects a store address for S(j).  
         [0094]     A register  68  has a value of the read address.  
         [0095]     A counter  69  has a value of the store address.  
         [0096]     Thus, the permutation unit  43  includes the selector  65 , the selector  66 , the register  68 , and the counter  69 .  
         [0097]     Turning back to  FIG. 6 , a fundamental operation of the M(n) calculator  41  is similar to that described in conjunction with  FIG. 3 . The operation of the M(n) calculator  41  will be described in detail. At first, in an initial state, the register  55  and the counter  54  have initial values “v” and “1” as M(0) and n, respectively. The value of M(n) in the register  55  and the value of v in the constant block  56  are added and the value p of the constant block  57  is subtracted. If the result of the above-mentioned calculation has a negative value (M+v−p&lt;0), a previous value (M+v) before subtraction is produced as the output value. Otherwise (M+v−0≧0), a subtracted value (M+v−p) is produced as the output value. The output value is stored in an address n of the memory  42 . For next calculation, the output value is stored in the register  55  and the value n of the counter  54  is incremented by 1. The above-mentioned operation is repeated until the value n of the counter  54  is equal to p−2.  
         [0098]     In  FIG. 7 , operation of the permutation unit  43  is started after completion of the above-mentioned operation of the M(n) calculator  41 . A fundamental operation is similar to that described in conjunction with  FIG. 4 . The register  68  and the counter  69  holds “1” and “0” as initial values of n and j, respectively. The value n of the register  68  is stored in the address j of the memory  44 . The value j of the counter  69  is incremented by 1. Subsequently, the value M(n) is read from an address n of the memory  42  and stored in the register  68 . The above-mentioned operation is repeated until the value j of the counter  69  is equal top −1.  
         [0099]     Thus, S(j) is produced in the S(j) memory  44 .  
         [0100]     In the manner similar to the first embodiment, Sm(j) can be obtained by setting “0” as the initial value of the register  55  in  FIG. 6  and “1” as the initial value of the register  68  in  FIG. 7 . In the manner similar to the first embodiment, the M(n) and the S(j) memories  42  and  44  can be reduced in size by directly calculating Sf(j). Further, in the manner similar to the first embodiment, the memory  42  can be used as a memory of a turbo codec.  
         [0101]     According to this embodiment, it is possible to reduce the circuit scale because a modulo calculator is not used. Further, since calculation of v×S(j) is not carried out and the maximum value is smaller than p×2, it is possible to reduce a calculation bit width.  
         [0102]     If an interleave parameter calculating apparatus for carrying out the operation described in this embodiment is used as a mobile radio apparatus such as a mobile telephone, it is possible to reduce the size of a main body of the mobile radio apparatus.  
         [0103]     According to this invention, a processor used in the mobile telephone is reduced in circuit scale so that the main body of the mobile telephone can be reduced in size.  
         [0104]     While this invention has thus far been described in conjunction with the preferred embodiments thereof, it will readily be possible for those skilled in the art to put this invention into practice in various other manners.