Abstract:
A system and method for SSS detection under carrier frequency offset in an orthogonal frequency-division multiple access (OFDMA) downlink channel. A processor receives a signal sample that includes a transmission on a primary synchronization signal (PSS) and a transmission on a one secondary synchronization signal (SSS). The processor determines a correlation “P” of a first symbol transmitted in the PSS of the signal sample to a first known symbol at each time “t” of time increments k of the signal sample and a correlation “S” of a second symbol transmitted in the a SSS to a second known symbol at each time t-.5/7 msecs. The processor receives a candidate phase rotation of θ i  from a set of “i” candidates and determines a correlation “Cmax” over the time increments k representing a maximum amplitude of a combined correlation of S and P, with P rotated by θ i . The processor determines the cell identifier from the first and second known symbols that produced S and P of C max and an estimation of the frequency offset between a transmitter of the signal sample and a receiver of the signal sample.

Description:
BACKGROUND 
     The Long Term Evolution (LTE) standard under consideration by the 3rd Generation Partnership Project (3GPP), the signal bandwidth may be configured from 1.4 MHz to 20 MHz. LTE uses orthogonal frequency-division multiple access (OFDMA) as the downlink channel. The bandwidth of the channel can be configured to 1.4 MHz, 3 MHz, 5 MHz, 10 MHz, 15 MHz and 20 MHz. 
     A cell search is a process by which a receiver acquires time and frequency synchronization with a cell and detects the physical layer cell ID of that cell. In LTE systems, this process is facilitated by the use of a primary sync signal (PSS) and secondary sync signal (SSS) (sometimes also referred to as the primary sync channel PSCH and the SSCH secondary sync channel respectively). Synchronization signals are specific sequences inserted into the last two OFDM symbols in the first slot of sub-frame zero and five (slots number  0  and  10 ). The PSS is carried on the PSS channel and the secondary sync signal is carried on the SSS channel. The primary synchronization signal is typically used for timing and frequency acquisition whereas the secondary signal is typically used to acquire the Cell ID and other cell-specific information. Both the PSSC and the SSSC are located in a 960 kHz band at the center of the signal and arrive in a symbol every 5 ms. There are 3 possibilities of PSS and 168 possibilities of SSS. Thus, there are 3*168=504 possibilities each of which is referred to as a Cell ID. 
     The Cell ID in the LTE system is composed of two parts, Nid 1  and Nid 2 , where the Cell ID is calculated as Nid=Nid 1 *3+Nid 2 . The PSS (primary synchronization signal) corresponds to one of the three Nid 2  codes, and the SSS (secondary synchronization signal) corresponds to one of the 168 Nid 1  codes. The PSS symbol follows the SSS symbol in the LTE signal. 
     Synchronization (or acquisition) in an LTE system is a two-step procedure defined by the LTE standard specification. The first step is PSS detection to detect a time offset (frame timing) and Nid 2 , and the second step is SSS detection to select the Nid 1  that has the maximum correlation energy. 
     Correlation is used to indicate how closely the two signals are related. For example, if there are two sequences of data X=[x 1 , x 2 , . . . , x L ] and Y=[y 1 , y 2 , . . . , y L+M ], wherein X is the reference sequence of L samples long, and Y is the received sequence of L+M samples long, to be correlated with X. The correlation between X and Y at time shifts k of Y is defined in Equation 1: 
     
       
         
           
             
               
                 
                   
                     
                       ρ 
                       ⁡ 
                       
                         ( 
                         k 
                         ) 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         L 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           y 
                           
                             i 
                             + 
                             k 
                           
                         
                         * 
                         
                           conj 
                           ⁡ 
                           
                             ( 
                             
                               x 
                               i 
                             
                             ) 
                           
                         
                       
                     
                   
                   , 
                   
                     k 
                     = 
                     0 
                   
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     M 
                     - 
                     1. 
                   
                 
               
               
                 
                   [ 
                   1 
                   ] 
                 
               
             
           
         
       
     
     In our example, X is the PSS or SSS reference signal sampled in the time domain, Y is the received signal of X through a communication channel that is characterized by a time delay j and amplitude a. Y has the form Y=[0,0, . . . , 0,ax 1 , ax 2 , . . . , ax L ,0, . . . , 0]. As PSS and SSS sequences are designed to have a good self-correlation property, the correlation output will appear as illustrated in  FIG. 1 , with a peak correlation at the delay j and low correlation elsewhere. Therefore, correlation is widely used to test if a known reference signal is present in the received signal at a specific delay. 
     In the case of the PSS and the SSS, the delay identifies the timing of the arrival of the PSS signal and permits the SSS signal to be located. Using the timing and the cell ID, the receiver synchronizes with the base station transmitter. 
     With respect to the detection of the SSS, the typical approach is to use only the SSS correlation to find the SSS. This approach discards information that may be obtained from the correlation of the PSS and is not always satisfactory under real-world conditions. 
     In a typical wireless communication system, the signal to be transmitted is upconverted to a carrier frequency prior to transmission. The receiver is expected to tune to the same carrier frequency for down-converting the signal to baseband prior to demodulation. However, under real-world conditions, the carrier frequency of the receiver may not be the same as the carrier frequency of the transmitter. When this happens, the received baseband signal, instead of being centered at DC (0 MHz), will be centered at a frequency offset from the desired center frequency. 
     Using existing systems, the acquisition detection may experience a loss of more than 2.0 dB when the carrier frequency offset is ±2.5 KHz. One possible cause of such loss may be the acquisition algorithm that is used. 
     SUMMARY 
     Embodiments of the present application provide systems and methods for detecting the SSS in an LTE environment affected by frequency offset. Other embodiments are directed to using the correlation of P and S to obtain an estimate of the frequency offsets at a receiver. 
     In an embodiment, an SSS detection module uses correlation of both the PSS and the SSS to identify an SSS while accounting for frequency offsets between a base station and a receiver. 
    
    
     
       DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a correlation result of a signal at delay j. 
         FIG. 2A  is a vector diagram illustrating the use of both the PSS and SSS correlations to obtain a combined correlation where no frequency offset is present according to an embodiment. 
         FIG. 2B  is a vector diagram illustrating the affect on the combined correlation of a frequency offset is present according to an embodiment. 
         FIG. 3  is a block diagram illustrating the use of a detection module to optimize a combined correlation when a frequency offset is present according to an embodiment. 
         FIGS. 4A , B and C are vector diagrams illustrating the determination of a maximum combined correlation value C according to embodiments. 
         FIG. 5  is a block diagram illustrating the combination three correlations of P and S acquired in a single signal sample according to an embodiment. 
         FIG. 6  is a vector diagram illustrating the determination of a maximum combined correlation value C in view of a large frequency offset according to embodiments. 
     
    
    
     DETAILED DESCRIPTION 
     In an LTE environment, information is transmitted as symbols encoded in the phase of the transmitted signal with respect to its carrier. For proper extraction of the symbols, therefore, the receiver&#39;s local reference must be quite close in frequency to the carrier signal; a frequency difference causes the apparent phase relationship to “rotate” undesirably. Thus, the effects of frequency offsets may be described in terms of phase rotations of the signal from an ideal signal. 
     As previously noted, the PSS and SSS symbols are adjacent in the LTE signal.  FIG. 2A  is a vector diagram illustrating the use of both the PSS and SSS correlations to obtain a combined correlation where no frequency offset is present according to an embodiment. In this embodiment, the PSS correlation is combined with SSS correlation to improve the detection of the SSS. This coherent combining is equivalent to a correlation with double the length, which improves the performance by 3 dB. 
     However, this combining alone does not account for carrier frequency offset.  FIG. 2B  is a vector diagram illustrating the affect on the combined correlation when a frequency offset is present according to an embodiment. 
     In mathematical terms, the PSS correlation may be represented by P, SSS correlation may be represented by S, and the combined correlation may be represented by C. The following Equation describes a coherent combining method:
 
 C=P+S=P *exp( j* 0)+ S   [2]
 
     where P is the PSS correlation, exp(j*0) is the phase rotation of P by zero degrees (no phase rotation), and S is the SSS correlation. P and S are added together without considering frequency offset introduced phase rotation. Note that in Equation 2 above, P, S and C are complex numbers. 
     In an embodiment, the combined correlation is corrected for frequency offset by applying a rotation to correlation P. 
     Each LTE FDD frame is 10 msec in length. Each frame is divided into 20 slots. Thus, each slot is 0.5 msec in length. For a normal CP LTE signal, each slot contains 7 OFDM symbols. The PSS and SSS are carried on adjacent OFDM symbols. Thus, the time difference between the two OFDM symbols is the time for one symbol or 0.5 msec/7. For a frequency offset of ±2.5 KHz, the phase difference between these two OFDM symbols is 0.5 msec/7*±2.5 KHz*2π=±2.5π/7=±0.357π. This phase rotation corresponds to exp(j*±0.357π)=0.4339±0.9010i. 
     Assuming that P and S have the same amplitude, then the combined correlation is proportional to 1.4339±0.9010i, as illustrated in  FIG. 2B . Under 0 Hz frequency offset, the combined correlation is proportional to 2.0+0.0i. The loss at ±2.5 KHz can be calculated to be 20*log(abs(2.0+0.0i)/abs(1.4339±0.9010i))=1.45 dB. 
       FIG. 3  is a block diagram illustrating the use of a detection module to optimize a combined correlation when a frequency offset is present according to an embodiment. 
     An RF (radio frequency) wireless LTE signal is received by an antenna  302 . A radio frequency (RF) front-end  304  down-converts the signal from RF to baseband. The analog baseband signal is converted to a digital signal by an analog-to-digital converter (ADC)  306  to produce a sample signal  308 . 
     In an embodiment, signal sample  308  is 15 msec of LTE signal. PSS and SSS appears in the LTE signal every 5 msec. Thus, the sample signal contains three occurrences of PSS and SSS. The detection module  300  comprises a signal processor  310  that determines values for the PSS correlation (P) and SSS correlation (S). The detection module  300  further comprises an evaluator processor  312  that combines S with “N” rotated versions of P and selects the maximum combined correlation value C  316  according to Equation [3]: 
     
       
         
           
             
               
                 
                   C 
                   = 
                   
                     
                       max 
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         { 
                         
                           abs 
                           ⁡ 
                           
                             ( 
                             
                               
                                 P 
                                 * 
                                 
                                   exp 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       j 
                                       * 
                                       
                                         θ 
                                         i 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               + 
                               S 
                             
                             ) 
                           
                         
                         } 
                       
                       . 
                     
                   
                 
               
               
                 
                   [ 
                   3 
                   ] 
                 
               
             
           
         
       
     
     Equation [3] represents the operation in  FIG. 2B , where P is the PSS correlation, exp(j*θ i ) is the phase rotation of P by angle θ i , and S is the SSS correlation. P and S are thus added together considering the frequency offset introduced phase rotation. There are i possible candidate phase rotations. The one that produces the maximum norm (amplitude) for the combined correlation is selected as the best choice, and its resulting combined correlation is output as C. 
     In an embodiment, the “i” candidate phase rotations may be selected by the user of the detection module  300  from a datastore  314 . As illustrated, i=5 and the candidate phase rotations are ±2π/7, ±π/7, and 0. These five phase rotations −2π/7, −π/7, 0, π/7 and 2π/7 correspond to frequency offsets of 2 KHz, 1 KHz, 0 Hz, −1 KHz and −2 KHz. The middle point between −2π/7 and −π/7 is −1.5π/7, which corresponds to 1.5 KHz. Thus, each of the five candidate phase rotations in this example covers a ±0.5π/7 window around it. If we connect the five windows together, the candidate rotations cover ±2.5π/7, or equivalently ±2.5 KHz. These rotation angles correct (“de-rotate”) a frequency offset between −2.5 KHz and 2.5 KHz. The candidate phase rotation that “corrects” the phase of P such that the correlation of P and S is maximized represents the frequency offset that is being experienced by the receiver. 
     The determination of an optimum correlation using candidate phase rotations may also be used to provide an estimation of the frequency offset at a particular receiver (see,  FIG. 3 , block  316 ). The five phase rotations −2π/7, −π/7, 0, π/7 and 2π/7 in the previous example correspond to frequency offsets estimates of 2 KHz, 1 KHz, 0 Hz, −1 KHz and −2 KHz. 
     The signal processor  310 , the evaluator processor  312  and the datastore  314  are illustrated in  FIG. 3  as discrete components. However, the functions of these elements may be performed by a single DSP chip or by one or more FPGAs or ASICs. Alternatively, the computationally intensive signal processor  210  may be implemented on an FPGA and the computationally less intensive functioning blocks (the evaluator processor  312  and the datastore  314 ) on a DSP. 
     After synchronization (detecting time offset and Cell ID with PSS and SSS), an LTE receiver estimates the channel using the RS (Reference Signal) signals and performs data demodulation. If the original frequency offset is large, such as 1.2 kHz, the channel estimation using the RS cannot be performed on the received signal directly. The LTE RS is spaced  1  slot (0.5 msec) apart in time for the same subcarrier. Thus, the fine frequency offset estimation using the RS can only handle a frequency offset that is within ±1 kHz (1/0.5 ms=2 kHz corresponding to ±1 kHz range). 
     The above ±1 kHz frequency offset range may also include the Doppler frequency offset, which may be as large as ±0.3 kHz. Thus, the carrier frequency offset tolerance is reduced to within a ±0.7 kHz range. 
     The frequency offset estimate as determined above may be used to reduce a large frequency offset. 
     For example, let the actual frequency offset between transmitter and receiver be 1.2 kHz, the candidate phase rotation that produces C max  will be −π/7. Since −π/7 corresponds to a frequency offset of 1 KHz, the frequency offset is estimate as 1 KHz. 
     The original signal with 1.2 KHz frequency offset is expressed by Equation 4:
 
 r ( t )= a ( t )*exp(− j 2π( f   c +1200) t ),  [4]
 
     where f c  is the carrier frequency, r(t) is the received signal at time t and a(t) is the amplitude at time t. 
     Using the frequency offset estimate of 1 KHz, the frequency difference can be reduced to 200 Hz as illustrated in Equation 5:
 
 r ′( t )= r ( t )*exp( j 2π*1000 t )= a ( t )*exp(− j 2π( f   c +200) t )  [5]
 
     As the residue frequency offset after reduction using the output of our process is within ±0.5 kHz range, it may be suited for channel estimation. 
       FIGS. 4A , B and C are vector diagrams illustrating the determination of a maximum combined correlation value C according to embodiments. 
     As illustrated in  FIG. 4A , the maximum value of correlation C is reached when the offset angle is −2π/7, that is when P is rotated by −2π/7. In this example, P has a relative phase difference of +2.57π/7 compared to S, which is equivalent to an offset of 2.5 KHz. 
     As illustrated in  FIG. 4B , the maximum value of correlation C is reached when the offset angle is −π/7, that is when P is rotated by −π/7. In this example, P has a relative phase difference of π/7 compared to S, which is equivalent to an offset of 1.0 KHz. 
     As illustrated in  FIG. 4C , the maximum value of correlation C is reached when the offset angle is +π/7, that is when P is rotated by +π/7. In this example, P has a relative phase difference of −π/7 compared to S, which is equivalent to an offset of −1.0 KHz. 
       FIG. 5  is a block diagram illustrating the combination three correlations of P and S acquired in a single signal sample according to an embodiment. 
     Since the phase of the noise is uniformly distributed between −π and π, the algorithm described by Equation 3 may pick the phase rotation that aligns with the noise phase. As described above, in an embodiment, the sample signal is long enough to include three instances of a transmitted PSS signal. For example, if the sample is 15 msecs, the sample will include three instances of the PSS signal (identified herein as P 1 , P 2  and P 3 ). P 1 , P 2  and P 3  have the same phase rotation due to frequency offset. However the phase rotation of the noise components of these three signals will be uncorrelated. This property can be used to compensate for the noise. 
     Assuming a sample length of 15 msecs, the signal processor  310  provides samples (P 1 , S 1 ), (P 2 , S 2 ), and (P 3 , S 3 ) to operators  500 . The operators  500  receive candidate phase rotations from the datastore  314 . As illustrated, the candidate phase rotations are in a range from −2π/7 to +2π/7. However, this range is provided for illustration purposes only and is not meant as a limitation. In general terms, for each of “R” signal samples and “i” candidate phase rotations, C i  is evaluated at summers  502  using Equation 6:
 
 C   i   =Abs ( P   1 *exp( j*θ   i )+ S   1 )+ . . .  ABS ( P   R *exp( j*θ   i )+ S   R )  [6]
 
     The absolute value or the square of C i  is determined by operators  504 . As illustrated in  FIG. 5 , the values for “C” of the three (R=3) signal samples (P 1 ,  51 ), (P 2 , S 2 ), and (P 3 , S 3 ) at the candidate rotation angle are summed at summers  506 . This sum represents the correlation “C i ” at a particular candidate angle that has been compensated for noise. 
     The process is repeated for each of the candidate rotation angles and a maximum “Cmax” is determined from all of the C i  values determined over the R signal samples and the i candidate phase rotations. Cmax, in this embodiment, represents a noise compensated correlation value as well as an estimation of the frequency offset (block  508 ). 
     Because the phases of noise for the three observations are uniformly distributed between −π and π and uncorrelated, the probability that all three noise align in the same direction is very small, and thus the noise contribution is greatly reduced. 
     The square of the norm may typically be calculated on a signal processor  310  of the detection module  300  more efficiently than the norm itself. In an embodiment in which i=5 and R=3, Equation 3 may be replaced with Equation 7 below with little performance loss: 
     
       
         
           
             
               
                 
                   C 
                   = 
                   
                     
                       max 
                       
                         i 
                         = 
                         1 
                       
                       5 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       { 
                       
                         
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       
                                         P 
                                         1 
                                       
                                       * 
                                       
                                         exp 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             jθ 
                                             i 
                                           
                                           ) 
                                         
                                       
                                     
                                     + 
                                     
                                       S 
                                       1 
                                     
                                   
                                   ) 
                                 
                                 * 
                                 
                                   conj 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           P 
                                           1 
                                         
                                         * 
                                         
                                           exp 
                                           ⁡ 
                                           
                                             ( 
                                             
                                               jθ 
                                               i 
                                             
                                             ) 
                                           
                                         
                                       
                                       + 
                                       
                                         S 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               + 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       
                                         P 
                                         2 
                                       
                                       * 
                                       
                                         exp 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             jθ 
                                             i 
                                           
                                           ) 
                                         
                                       
                                     
                                     + 
                                     
                                       S 
                                       2 
                                     
                                   
                                   ) 
                                 
                                 * 
                                 
                                   conj 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         
                                           P 
                                           2 
                                         
                                         * 
                                         
                                           exp 
                                           ⁡ 
                                           
                                             ( 
                                             
                                               jθ 
                                               i 
                                             
                                             ) 
                                           
                                         
                                       
                                       + 
                                       
                                         S 
                                         2 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               + 
                             
                           
                         
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       P 
                                       3 
                                     
                                     * 
                                     
                                       exp 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           jθ 
                                           i 
                                         
                                         ) 
                                       
                                     
                                   
                                   + 
                                   
                                     S 
                                     3 
                                   
                                 
                                 ) 
                               
                               * 
                               
                                 conj 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       
                                         P 
                                         3 
                                       
                                       * 
                                       
                                         exp 
                                         ⁡ 
                                         
                                           ( 
                                           
                                             jθ 
                                             i 
                                           
                                           ) 
                                         
                                       
                                     
                                     + 
                                     
                                       S 
                                       3 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   [ 
                   7 
                   ] 
                 
               
             
           
         
       
     
     It may be observed that the gain achievable with this approach is results from searching the actual phase rotation caused by frequency offset. In an embodiment, the search is performed on five discrete points from −2π/7 to 2π/7, while the random noise phase is from −π to π, and also comes from the combination of three observations. If the maximum possible frequency offset is less than ±2.5 KHz, then the search window can be made smaller to improve the performance. 
     For ±2.5 KHz frequency offset, the phase rotation between adjacent symbols in extended CP (cyclic prefix) length LTE is ±2.5π/6=±0.417π. As this phase rotation is not much different from the phase rotation of ±0.357π for normal CP length LTE, the performance of the algorithm is comparable to the normal CP case. In an embodiment, the candidate phase rotations for extended CP length LTE are ±π/3, ±π/6, and 0. The worst case loss can be calculated to be 20*log(abs(2.0+0.0i)/abs(1+exp(j*±π0.5/6))=20*log(abs(2.0+0.0i)/abs(1.9659±0.2588 i))=0.075 dB. 
     When the frequency offset gets larger, there is performance loss in calculating the PSS and SSS correlations P and S, as the correlation is calculated assuming zero frequency offset for the length of correlation. However, as the frequency offset gets larger, this assumption no longer holds. The loss at 2.5 KHz frequency offset is estimated to be about 0.5 dB. 
     Also from the above description of the proposed algorithm, the search window will become wider for large frequency offset, and eventually the search window will be from −π to π and thus render the described algorithm with no gain. 
     In an embodiment, a detection module is configured to divide the correlation for PSS and SSS into smaller segments such as Sa, Sb, Pa and Pb (correlation length is halved) in increasing time order. In this embodiment, the four segments are combined with candidate phase rotations as illustrated in  FIG. 6  and represented by Equation 8: 
     
       
         
           
             
               
                 
                   C 
                   = 
                   
                     
                       max 
                       i 
                     
                     ⁢ 
                     
                       { 
                       
                         abs 
                         ⁡ 
                         
                           ( 
                           
                             
                               Pb 
                               * 
                               
                                 exp 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     j 
                                     * 
                                     3 
                                     ⁢ 
                                     
                                       θ 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             + 
                             
                               Pa 
                               * 
                               
                                 exp 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     j 
                                     * 
                                     2 
                                     ⁢ 
                                     
                                       θ 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             + 
                             
                               Sb 
                               * 
                               
                                 exp 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     j 
                                     * 
                                     
                                       θ 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             + 
                             Sa 
                           
                           ) 
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   [ 
                   8 
                   ] 
                 
               
             
           
         
       
     
     The phase rotation at ±2.5 KHz between adjacent segments is halved to ±2.5π/14 and the phase rotation steps to search are now ±2π/14, ±π/14, and 0. These phase rotations of ±2π/14, ±π/14, and 0 correspond to frequency offset of ±2 KHz, ±1 KHz, and 0 Hz. The phase rotation that gives the maximum correlation also gives the estimated frequency offset. 
     The PSS detection process may use the original two-segment combining algorithm to combine Pa and Pb: 
     
       
         
           
             
               
                 
                   P 
                   = 
                   
                     
                       max 
                       i 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       { 
                       
                         abs 
                         ⁡ 
                         
                           ( 
                           
                             
                               Pb 
                               * 
                               
                                 exp 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     j 
                                     * 
                                     
                                       θ 
                                       i 
                                     
                                   
                                   ) 
                                 
                               
                             
                             + 
                             
                               P 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               a 
                             
                           
                           ) 
                         
                       
                       } 
                     
                   
                 
               
               
                 
                   [ 
                   9 
                   ] 
                 
               
             
           
         
       
     
     For simplicity of algorithm description, Equation 9 uses only one data observation. However, when multiple data observations are available, the previous combining algorithm for independent observations may be used. 
     For even higher freq offsets, the correlation can be divided into 8 segments, 16 segments and etc, depending on the maximum possible frequency offset, the required performance gain and the available computation resources. For example, for the same maximum frequency offset, dividing into 16 segments would provide better performance but at more computations required. There are diminishing returns to dividing into more segments, so a tradeoff can be made that can achieve reasonable performance at reasonable cost. 
     Since the phase rotations are symmetric such as ±2θ, ±θ, and 0, the complex multiplication associated with the phase rotation can be reused in a manner similar to the butterfly operations as in a fast Fourier transform (FFT) to reduce computation. 
     The foregoing method descriptions and the process flow diagrams are provided merely as illustrative examples and are not intended to require or imply that the steps of the various embodiments must be performed in the order presented. As will be appreciated by one of skill in the art the order of steps in the foregoing embodiments may be performed in any order. Further, words such as “thereafter,” “then,” “next,” etc. are not intended to limit the order of the steps; these words are simply used to guide the reader through the description of the methods. 
     The various illustrative logical blocks, modules, circuits, and algorithm steps described in connection with the embodiments disclosed herein may be implemented as electronic hardware, computer software, or combinations of both. To clearly illustrate this interchangeability of hardware and software, various illustrative components, blocks, modules, circuits, and steps have been described above generally in terms of their functionality. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the overall system. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present invention. 
     The hardware used to implement the various illustrative logics, logical blocks, modules, and circuits described in connection with the aspects disclosed herein may be implemented or performed with a general purpose processor, a digital signal processor (DSP), an application specific integrated circuit (ASIC), a field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, or any combination thereof designed to perform the functions described herein. A general-purpose processor may be a microprocessor, but, in the alternative, the processor may be any conventional processor, controller, microcontroller, or state machine. A processor may also be implemented as a combination of the computing devices, e.g., a combination of a DSP and a microprocessor, a plurality of microprocessors, one or more microprocessors in conjunction with a DSP core, or any other such configuration. Alternatively, some steps or methods may be performed by circuitry that is specific to a given function. 
     In one or more exemplary embodiments, the functions described may be implemented in hardware, software, firmware, or any combination thereof. If implemented in software, the functions may be stored on or transmitted over as one or more instructions or code on a computer-readable medium. The steps of a method or algorithm disclosed herein may be embodied in a processor-executable software module which may reside on a computer-readable medium. Computer-readable media includes both computer storage media and communication media including any medium that facilitates transfer of a computer program from one place to another. A storage media may be any available media that may be accessed by a computer. By way of example, and not limitation, such computer-readable media may comprise RAM, ROM, EEPROM, CD-ROM or other optical disc storage, magnetic disk storage or other magnetic storage devices, or any other medium that may be used to carry or store desired program code in the form of instructions or data structures and that may be accessed by a computer. 
     Also, any connection is properly termed a computer-readable medium. For example, if the software is transmitted from a website, server, or other remote source using a coaxial cable, fiber optic cable, twisted pair, digital subscriber line (DSL), or wireless technologies such as infrared, radio, and microwave, then the coaxial cable, fiber optic cable, twisted pair, DSL, or wireless technologies such as infrared, radio, and microwave are included in the definition of medium. Disk and disc, as used herein, includes compact disc (CD), laser disc, optical disc, digital versatile disc (DVD), floppy disk, and blu-ray disc where disks usually reproduce data magnetically, while discs reproduce data optically with lasers. Combinations of the above should also be included within the scope of computer-readable media. Additionally, the operations of a method or algorithm may reside as one or any combination or set of codes and/or instructions on a machine readable medium and/or computer-readable medium, which may be incorporated into a computer program product. 
     The preceding description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein. Further, any reference to claim elements in the singular, for example, using the articles “a,” “an,” or “the,” is not to be construed as limiting the element to the singular.