Abstract:
The present invention generates exponents of elements of a Zadoff-Chu sequence representing a preamble for uplink synchronization of mobile stations or a mobile station reference signal by first obtaining (S 1 ) a preamble index defining the Zadoff-Chu sequence. Then it determines an initial exponent (S 3 ) of the first element in the Zadoff-Chu sequence and an initial first difference (S 2 , S 4 ) between exponents of consecutive elements of the Zadoff-Chu sequence. Finally it determines (S 5 -S 9 ) exponents of the remaining elements in the Zad-off-Chu sequence from the initial first difference and the initial exponent in an iterative procedure that avoids multiplication operations.

Description:
TECHNICAL FIELD 
       [0001]    The present invention relates generally to efficient Zadoff-Chu sequence generation, and especially to generation of preambles and reference signal sequences in mobile communication systems. 
       BACKGROUND 
       [0002]    In a mobile communications system, uplink synchronization is required before data can be transmitted in the uplink. In E-UTRA, uplink synchronization of a mobile is initially performed in the random access procedure. The mobile initiates the random access procedure by selecting a random access preamble from a set of allocated preambles in the cell where the mobile is located, and transmitting the selected random access preamble. In the base station, a receiver correlates the received signal with a set of all random access preambles allocated in the cell to determine the transmitted preamble. 
         [0003]    The random access preamble sequences in E-UTRA are designed such that the autocorrelation is ideal and such that the cross-correlation between two different preambles is small. These properties enable accurate time estimates needed for the uplink synchronization and good detection properties of the preambles. These random access preamble sequences in E-UTRA are derived from Zadoff-Chu sequences of odd length. Zadoff-Chu sequences p u,q (n) of length N, where N is odd, are defined as (see [1]): 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           p 
                           
                             u 
                             , 
                             q 
                           
                         
                          
                         
                           ( 
                           n 
                           ) 
                         
                       
                       = 
                       
                         W 
                         
                           
                             
                               un 
                                
                               
                                 ( 
                                 
                                   n 
                                   + 
                                   1 
                                 
                                 ) 
                               
                             
                             / 
                             2 
                           
                           + 
                           qn 
                         
                       
                     
                     , 
                     
                       
 
                     
                      
                     
                       n 
                       = 
                       0 
                     
                     , 
                     1 
                     , 
                     … 
                      
                     
                         
                     
                     , 
                     
                       
                         N 
                         - 
                         1 
                       
                       ; 
                     
                   
                    
                   
                     
 
                   
                    
                   
                     W 
                     = 
                     
                        
                       
                         
                           - 
                           j2π 
                         
                         N 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the integers u and N are relatively prime, i.e. the greatest common divisor of u and N is 1. Furthermore, q is an arbitrary integer and j is the imaginary unit. The random access preambles in E-UTRA are defined in time domain as cyclic shifts of Zadoff-Chu root sequences of odd length with q=0 (see [2]): 
         [0000]        p   u ( n )= p   u,0 ( n )= W   un(n+1)/2   ,n= 0,1 , . . . ,N− 1  (2)
 
         [0004]    The random access preamble in E-UTRA contains a cyclic prefix, which makes it advantageous to perform the correlation of the received signal with the random access preambles in the frequency domain. The structure of a random access preamble receiver in a base station is shown in  FIG. 1 . 
         [0005]    In  FIG. 1  a received signal is forwarded to a block  10  for removing the cyclic prefix (CP). The remaining signal is subjected to a Discrete Fourier Transform (DFT) in block  12 . The obtained discrete Fourier transform is forwarded to a set of correlators  14 , where it is multiplied element-wise by a set of DFTs of preamble sequences indexed by u min  . . . u max  and generated by blocks  16 . The products are subjected to an Inverse Discrete Fourier Transform (IDFT) in blocks  18 . The correlator output signals are then forwarded to a corresponding set of detectors  20 , which determine the generated preamble that best matches the received signal. 
         [0006]    The preambles used for uplink synchronization are also generated in the mobile stations. Another application of Zadoff-Chu sequences is generation of mobile station reference signal sequences transmitted on the uplink. In contrast to the random access preambles, which are defined in time domain, the reference signals in E-UTRA are defined in frequency domain by (2) together with truncation of the Zadoff-Chu sequence, i.e. some samples at the end of the sequence are not included in the reference signal. 
         [0007]    The exponent un(n+1)/2+qn in the definition of the Zadoff-Chu sequence is always an integer because either n or n+1 is even and so one of them must be divisible by 2. Furthermore, since u, q and n are all integers, the exponent must be an integer as well. Since the function W m  is periodic in m with period N and all entities in the exponent are integers, all arithmetic can be performed modulo N in the exponent un(n+1)/2+qn. 
         [0008]    Division modulo N differs from ordinary division and involves the inverse modulo N. The inverse of b modulo N is defined as the integer such that 0&lt;b −1 &lt;N and bb −1 =1 mod N. The inverse modulo N of b exists if and only if b and N are relatively prime. If N is prime b −1  exists for all b≠mod N. Division of a by b modulo N is accomplished by multiplying a by the inverse modulo N of b:ab −1 . 
         [0009]    Performing the arithmetic modulo N in the exponent gives an alternative and useful expression of the Zadoff-Chu sequence: 
         [0000]        p   u,q ( n )= W   un(n+1)·2     −1     qn   ,n= 0,1 , . . . ,N− 1  (3)
 
         [0010]    Note that with the notation used for modulo N arithmetic, 2 −1  is not the same as ½. Instead it denotes the inverse modulo N of 2 (which depends on N). 
         [0011]    It has been shown (see [3]) that the DFT of p u (n) is given by: 
         [0000]        P   u ( k )= W   −k(k+u)·2     −1     u     −1Σ     n=0   N-1   p   u (( n+u   −1   k )mod  N )  (4)
 
         [0012]    Since the sum in (4) is always over all elements of p u (n), the sum is independent of k, thus: 
         [0000]        P   u ( k )= A   u   W   −k(k+u)·2     −1     u     −1     (5)
 
         [0000]    where A u  is independent of k. From Parseval&#39;s theorem one can show (see [4]) that |A u |=√{square root over (N)} for any value of u and thus A u =√{square root over (N)}e jφ     u   , where e jφ     u    is a constant complex phase factor. 
         [0013]    Comparing (3) and (5) it is clear that the DFT of the Zadoff-Chu sequence is itself a Zadoff-Chu sequence multiplied by a constant: 
         [0000]        P   u ( k )= A   u   W   −k(k+u)·2     −1     u     −1     =A   u   p   −u     −1     ,  q   ( k ),  q =( u   −1 −1)·2 −1   (6)
 
         [0014]    In each correlator  14  in  FIG. 1 , the received signal is multiplied element-wise with the DFT of a preamble in the cell. 
         [0015]    In a straightforward generator of the DFT of the preamble, the exponent a(k)=−k(k+u)·2 −1 u −1  in (6) is calculated for every value of k and the values of W a(k)  are either calculated or read from a table. The detectors  20  only need the absolute values of the respective correlator outputs, so only the absolute value of A u  is relevant. Since the absolute value, |A u |=√{square root over (N)} for any value of u, A u  can be completely discarded in the correlators. Thus, for the purpose of correlation the preamble may be represented by a Zadoff-Chu sequence both in the time and frequency domain, which implies that a representation of the DFT of the preamble may be generated directly in the frequency domain as a Zadoff-Chu sequence. 
         [0016]    The sequence generation in existing technology requires two multiplications to calculate the exponent a(k)=−k(k+u)·2 −1 u −1  in (6) for every sample in the sequence. The total computational complexity of these multiplications may be significant for long sequences. For instance, the length of the random access preamble in E-UTRA is N=839 for most preamble formats, and in a worst case the receiver needs to correlate the received signal with as many as 64 different Zadoff-Chu sequences (this corresponds to 64 blocks  16  in  FIG. 1 ). 
       SUMMARY 
       [0017]    An object of the present invention is to generate the exponents of elements of Zadoff-Chu sequences for radio communication systems with less complexity than the prior art. 
         [0018]    This object is achieved in accordance with the attached claims. 
         [0019]    Briefly, the present invention generates the exponents of elements of a Zadoff-Chu sequence of length N, where N is odd, in an iterative procedure based on modulo N arithmetic to avoid multiplications. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0020]    The invention, together with further objects and advantages thereof, may best be understood by making reference to the following description taken together with the accompanying drawings, in which: 
           [0021]      FIG. 1  is a block diagram illustrating the structure of a random access preamble receiver in a base station; 
           [0022]      FIG. 2  is a flow chart illustrating an embodiment of the method in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the frequency domain, a preamble for uplink synchronization of mobile stations; 
           [0023]      FIG. 3  is a block diagram of an embodiment of an apparatus in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the frequency domain, a preamble for uplink synchronization of mobile stations: 
           [0024]      FIG. 4  is a flow chart illustrating an embodiment of the method in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the time domain, a preamble for uplink synchronization of mobile stations; and 
           [0025]      FIG. 5  is a block diagram of an embodiment of an apparatus in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the time domain, a preamble for uplink synchronization of mobile stations. 
       
    
    
     DETAILED DESCRIPTION 
       [0026]    According to the present invention the exponent a(k) is calculated iteratively from a(k−1) and from the first and second differences between subsequent values of a(k): 
         [0000]        d   (1) ( k )= a ( k )− a ( k− 1)=−(2 k+u− 1)·2 −1   u   −1   (7)
 
         [0000]      and 
         [0000]        d   (2) ( k )= d ( 1 )( k )− d ( 1 )( k− 1)=−2·2 −1   u   −1   =−u   −1   (8)
 
         [0027]    Such an iterative calculation of the exponent is possible since a(k) is a quadratic polynomial in k. This is similar to the calculation of a quadratic permutation polynomial for interleavers given in [5]. The initial values a(0) and d (1) (0) are given by: 
         [0000]        a (0)=0 and  d   (1) (0)=(1 −u )·2 −1   u   −1 ( u   −1 −1)·2 −1   (9)
 
         [0028]    It is straightforward to show that with ordinary arithmetic: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                       
                         ( 
                         1 
                         ) 
                       
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   u 
                                   
                                     - 
                                     1 
                                   
                                 
                                 - 
                                 1 
                               
                               2 
                             
                             , 
                           
                         
                         
                           
                             
                               u 
                               
                                 - 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             odd 
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   u 
                                   
                                     - 
                                     1 
                                   
                                 
                                 2 
                               
                               + 
                               
                                 
                                   N 
                                   - 
                                   1 
                                 
                                 2 
                               
                             
                             , 
                           
                         
                         
                           
                             
                               u 
                               
                                 - 
                                 1 
                               
                             
                              
                             
                                 
                             
                              
                             even 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
         [0029]    From (7), (8), (9) and (10), the exponents a(k) are calculated iteratively for all values of k by the following procedure: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                     = 
                     0 
                   
                    
                   
                     
 
                   
                    
                   
                     
                       d 
                       
                         ( 
                         1 
                         ) 
                       
                     
                      
                     
                       ( 
                       0 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       u 
                                       
                                         - 
                                         1 
                                       
                                     
                                     - 
                                     1 
                                   
                                   2 
                                 
                                 , 
                               
                             
                             
                               
                                 
                                   u 
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                     
                                 
                                  
                                 odd 
                               
                             
                           
                           
                             
                               
                                 
                                   
                                     
                                       u 
                                       
                                         - 
                                         1 
                                       
                                     
                                     2 
                                   
                                   + 
                                   
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     2 
                                   
                                 
                                 , 
                               
                             
                             
                               
                                 
                                   u 
                                   
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                     
                                 
                                  
                                 even 
                               
                             
                           
                         
                          
                         
                           
 
                         
                          
                         for 
                          
                         
                             
                         
                          
                         k 
                       
                       = 
                       
                         
                           
                             1 
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             N 
                           
                           - 
                           
                             1 
                              
                             
                               
 
                             
                              
                             
                               
                                 d 
                                 
                                   ( 
                                   1 
                                   ) 
                                 
                               
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                         
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     d 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   u 
                                   
                                     - 
                                     1 
                                   
                                 
                               
                               ) 
                             
                              
                             
                                 
                             
                              
                             mod 
                              
                             
                                 
                             
                              
                             N 
                              
                             
                               
 
                             
                              
                             
                               a 
                                
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                           
                           = 
                           
                             
                               ( 
                               
                                 
                                   a 
                                    
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     d 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                               
                               ) 
                             
                              
                             
                                 
                             
                              
                             mod 
                              
                             
                                 
                             
                              
                             N 
                              
                             
                               
 
                             
                              
                             end 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0030]    Note that the expression d (2) (k) is not explicitly involved in this procedure, since it is a constant that may be used directly. In an alternative embodiment the calculations modulo N in (11) can be simplified to give the following procedure: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       a 
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                     = 
                     0 
                   
                    
                   
                     
 
                   
                    
                   
                     
                       
                         d 
                         
                           ( 
                           1 
                           ) 
                         
                       
                        
                       
                         ( 
                         0 
                         ) 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         u 
                                         
                                           - 
                                           1 
                                         
                                       
                                       - 
                                       1 
                                     
                                     2 
                                   
                                   , 
                                 
                               
                               
                                 
                                   
                                     u 
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                       
                                   
                                    
                                   odd 
                                 
                               
                             
                             
                               
                                 
                                   
                                     
                                       
                                         u 
                                         
                                           - 
                                           1 
                                         
                                       
                                       2 
                                     
                                     + 
                                     
                                       
                                         N 
                                         - 
                                         1 
                                       
                                       2 
                                     
                                   
                                   , 
                                 
                               
                               
                                 
                                   
                                     u 
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                       
                                   
                                    
                                   even 
                                 
                               
                             
                           
                            
                           
                             
 
                           
                            
                           for 
                            
                           
                               
                           
                            
                           k 
                         
                         = 
                         
                           
                             
                               1 
                                
                               
                                   
                               
                                
                               … 
                                
                               
                                   
                               
                                
                               N 
                             
                             - 
                             
                               1 
                                
                               
                                 
 
                               
                                
                               
                                 
                                   d 
                                   
                                     ( 
                                     1 
                                     ) 
                                   
                                 
                                  
                                 
                                   ( 
                                   k 
                                   ) 
                                 
                               
                             
                           
                           = 
                           
                             
                               
                                 
                                   
                                     d 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   
                                     u 
                                     
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     
 
                                   
                                    
                                   if 
                                    
                                   
                                       
                                   
                                    
                                   
                                     
                                       d 
                                       
                                         ( 
                                         1 
                                         ) 
                                       
                                     
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                               
                               &lt; 
                               
                                 0 
                                  
                                 
                                     
                                 
                                  
                                 then 
                                  
                                 
                                     
                                 
                                  
                                 
                                   
                                     d 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                               
                             
                             = 
                             
                               
                                 
                                   
                                     d 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                   
                                    
                                   
                                     ( 
                                     k 
                                     ) 
                                   
                                 
                                 + 
                                 
                                   N 
                                    
                                   
                                     
 
                                   
                                    
                                   
                                     a 
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                 
                               
                               = 
                               
                                 
                                   
                                     
                                       a 
                                        
                                       
                                         ( 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                     + 
                                     
                                       
                                         
                                           d 
                                           
                                             ( 
                                             1 
                                             ) 
                                           
                                         
                                          
                                         
                                           ( 
                                           k 
                                           ) 
                                         
                                       
                                        
                                       
                                         
 
                                       
                                        
                                       if 
                                        
                                       
                                           
                                       
                                        
                                       
                                         a 
                                          
                                         
                                           ( 
                                           k 
                                           ) 
                                         
                                       
                                     
                                   
                                   &gt; 
                                   
                                     N 
                                     - 
                                     
                                       1 
                                        
                                       
                                           
                                       
                                        
                                       then 
                                        
                                       
                                           
                                       
                                        
                                       
                                         a 
                                          
                                         
                                           ( 
                                           k 
                                           ) 
                                         
                                       
                                     
                                   
                                 
                                 = 
                                 
                                   
                                     a 
                                      
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                   - 
                                   
                                     N 
                                      
                                     
                                       
 
                                     
                                      
                                     end 
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0031]      FIG. 2  is a flow chart illustrating an embodiment of the method in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the frequency domain, a preamble for uplink synchronization of mobile stations. Step S 1  obtains the preamble index u of the sequence to be generated. Step S 2  inverts u modulo N. Steps S 3  sets the initial value  a (0)=0 and step S 4  determines d (1) (0) in accordance with the first parts of (11) and (12). Step S 5  sets k=1. Step S 6  tests whether k&lt;N. If so, step S 7  updates d (1) (k) and step S 8  updates a(k). Thereafter step S 9  increments k and the procedure returns to step S 6 . The procedure ends at step S 10  when k=N. Steps S 5 -S 10  can, for example, be implemented by a for loop as in (11) or (12). 
         [0032]      FIG. 3  is a block diagram of an embodiment of an apparatus in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the frequency domain, a preamble for uplink synchronization of mobile stations. The index u of the sequence to be generated is forwarded to a modulo N inverter  30 . The modulo N inverted value u −1  is forwarded to an initial value provider  32 , which calculates d (1) (0) and a(0). The modulo N inverted value u −1  is also forwarded to a sign inverter  34 , which stores the sign inverted value −u −1 . The sign inverted value −u −1  and the initial value d (1) (0) are forwarded to a modulo N adder  36 , which iteratively calculates successive values d (1) (k) in accordance with either: 
         [0000]        d   (1) ( k )=( d   (1) ( k− 1)− u   −1 )mod  N   (13)
 
         [0000]      or 
         [0000]        d   (1) ( k )= d   (1) ( k− 1)− u   −1  if d (1) ( k )&lt;0 then d (1) ( k )=( k )+ N   (14)
 
         [0033]    This is represented by the indicated feedback loop to modulo N adder  36 , which includes a delay element D that introduces a delay corresponding to 1 iteration. 
         [0034]    Similarly the initial value a(0) is used to start iterative calculations of successive values a(k) in a modulo N adder  38  using the calculated values d (1) (k) in accordance with either: 
         [0000]        a ( k )=( a ( k− 1)+ d   (1) ( k ))mod  N   (15)
 
         [0000]      or 
         [0000]        a ( k )= a ( k− 1)+ d   (1) ( k ) if a( k )&gt; N− 1 then a( k )= a ( k )− N   (16)
 
         [0035]    This is represented by the indicated feedback loop to modulo N adder  38 , which includes a delay element D that introduces a delay corresponding to 1 iteration. 
         [0036]    The resulting exponents a(k) are forwarded to an exponentiating unit  40  which forms the elements W a(k)  of the sequence using the value W=e −j2π/N  stored in a memory cell  42 . 
         [0037]    Due to the structure of (13)-(16) the iterations (in the iteration unit IU including blocks  34 ,  36 ,  38 , D) may be performed by first calculating all the values d (1) (k) and then using these values to calculate the values a(k). Such a procedure, however, requires storing the values d (1) (k) until they are needed for calculating the values a(k). As an alternative, illustrated by (11) and (12), both iterations may be performed in parallel, which requires storing only the values of d (1) (k) and a(k) used in the next iteration. 
         [0038]    Although the description has so far been restricted to generation of Zadoff-Chu sequences representing preambles in base station receivers for uplink synchronization of mobile stations, other applications where the same principles may be used are also feasible. One such application is generation of the preambles in the mobile station. Another application is generation of reference signal sequences, which are also represented by Zadoff-Chu sequences, in mobile and base stations. 
         [0039]    It is also possible to generate Zadoff-Chu sequences representing preambles in the time domain instead of the frequency domain. For example, the mobile station may generate the preamble either in the time domain or the frequency domain. In the time domain the exponents a(k)=−k(k+u)·2 −1  u −1  in (6) are replaced by the exponents a(n)=un(n+1)·2 −1  in (3). Thus (7) and (8) will be replaced by 
         [0000]        d   (1) ( n )= a ( n )− a ( n− 1)= nu   (17)
 
         [0000]      and 
         [0000]        d   (2) ( n )= d   (1)(   n )− d   (1) ( n− 1)= u,   (18)
 
         [0000]    respectively. This implies that (11) will be replaced by: 
         [0000]        a (0)=0 
         [0000]        d   (1) (0)=0 
         [0000]      for  n= 1  . . . N− 1 
         [0000]        d   (1) ( n )=( d   (1) ( n− 1)+ u )mod  N    
         [0000]        a ( n )=( a ( n− 1)+ d   (1) ( n ))mod  N    
         [0000]      end  (19)
 
         [0000]    and (12) will be replaced by: 
         [0000]        a (0)=0 
         [0000]        d   (1) (0)=0 
         [0000]      for  n= 1  . . . N− 1 
         [0000]        d   (1) ( n )= d   (1) ( n− 1)+ u    
         [0000]      if  d   (1) ( n )&lt;0 then  d   (1) ( n )=( n )+ N    
         [0000]        a ( n )= a ( n− 1)+ d   (1) ( n ) 
         [0000]      if  a ( n )&gt; N− 1 then  a ( n )= a ( n )− N  
 
         [0000]      end  (20)
 
         [0040]      FIG. 4  is a flow chart illustrating an embodiment of the method in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the time domain, a preamble for uplink synchronization of mobile stations. Step S 11  obtains the preamble index u of the sequence to be generated. Steps S 12  and S 3  set the initial values a(0) and d (1) (0), respectively, to 0 in accordance with the first parts of (19) and (20). Step S 4  sets n=1. Step S 15  tests whether n&lt;N. If so, step S 16  updates d (1) (n) and step S 17  updates a(n). Thereafter step S 18  increments n and the procedure returns to step S 15 . The procedure ends at step S 19  when n=N. 
         [0041]    Steps S 14 -S 19  can, for example, be implemented by a for loop as in (19) or (20). 
         [0042]      FIG. 5  is a block diagram of an embodiment of an apparatus in accordance with the present invention for generating exponents of elements of a Zadoff-Chu sequence representing, in the time domain, a preamble for uplink synchronization of mobile stations. The index u of the sequence to be generated is forwarded from a memory cell  44  to a modulo N adder  36 . Modulo N adder  36  also receives the initial value d (1) (0) from an initial value provider  32 . Modulo N adder  36  iteratively calculates successive values d (1) (n) in accordance with either: 
         [0000]        d   (1) ( n )=( d   (1) ( n− 1)+ u )mod  N   (21)
 
         [0000]      or 
         [0000]        d   (1) ( n )= d   (1) ( n− 1)+ u if d   (1) ( n )&lt;0 then d (1) ( n )= d   (1) ( n )+ N   (22)
 
         [0043]    This is represented by the indicated feedback loop to modulo N adder  36 , which includes a delay element D that introduces a delay corresponding to 1 iteration. 
         [0044]    Similarly the initial value a(0) is used to start iterative calculations of successive values a(n) in a modulo N adder  38  using the calculated values d (1) (n) in accordance with either: 
         [0000]        a ( n )=( a ( n− 1)+ d   (1) ( n ))modulo  N   (23)
 
         [0000]      or 
         [0000]        a ( n )= a ( n− 1)+ d   (1) ( n ) if a( n )&gt; N− 1 then a( n )= a ( n )− N   (24)
 
         [0045]    This is represented by the indicated feedback loop to modulo N adder  38 , which includes a delay element D that introduces a delay corresponding to 1 iteration. 
         [0046]    The resulting exponents a(n) are forwarded to an exponentiating unit  40  which forms the elements W a(n)  of the sequence using the value W=e −j2π/N  stored in a memory cell  42 . 
         [0047]    Due to the structure of (21)-(24) the iterations (in the iteration unit IU including blocks  44 ,  36 ,  38 , D) may be performed by first calculating all the values d (1) (n) and then using these values to calculate the values a(n). Such a procedure, however, requires storing the values d (1) (n) until they are needed for calculating the values a(n). As an alternative, illustrated by (19) and (20), both iterations may be performed in parallel, which requires storing only the values of d (1) (n) and a(n) used in the next iteration. 
         [0048]    The principles described above for generating Zadoff-Chu sequences representing preambles in the time domain may also be used to generate reference signals in the frequency domain, both in mobile and base stations, if this is desirable. 
         [0049]    Typically the various blocks in the described embodiments are implemented by one or several micro processors or micro/signal processor combinations and corresponding software. 
         [0050]    It is appreciated that the present invention provides a simple way to generate Zadoff-Chu sequences avoiding multiplications. An advantage is a complexity reduction in the implementation of the Zadoff-Chu sequence generation compared to the prior art. 
         [0051]    It will be understood by those skilled in the art that various modifications and changes may be made to the present invention without departure from the scope thereof, which is defined by the appended claims. 
       ABBREVIATIONS 
       [0000]    
       
         3GPP 3rd Generation Partnership Project 
         DFT Discrete Fourier Transform 
         E-UTRA Evolved UMTS Terrestrial Radio Access 
         IEEE Institute of Electrical and Electronics Engineers 
         TS Technical Specification 
         UMTS Universal Mobile Telephony System 
       
     
       REFERENCES 
       [0000]    
       
         [1] B. Popovic, “Generalized chirp-like polyphase sequences with optimum correlation properties,” IEEE Trans. Inform. Theory, vol. 38, no. 4, pp. 1406-1409, 1992. 
         [2] 3GPP, TS 36.211, “Physical Channels and modulation” v 8.2.0, section 5.7.2, March 2008. 
         [3] 3GPP R1-071409, Huawei, “Efficient matched filters for paired root Zadoff-Chu sequences,” March 2007. 
         [4] D. V. Sarwate, “Bounds on crosscorrelation and autocorrelation of sequences,” IEEE Trans. Inform. Theory, vol. IT-25, pp 720-724, 1979. 
         [5] M. K. Cheng et al, “An interleaver implementation for the serially concatenated pulse-position modulation decoder,” in Proc. IEEE International Symposium on Circuits and Systems, 2006.