Abstract:
A frequency offset estimation based on state-based differential accumulation and the device thereof are disclosed. The concept of the sate-based operation is introduced by mathematical derivations. The knowledge of received data symbols and timing is utilized. Then the detailed operations are also given by both equations and conceptual descriptions. It is unnecessary to estimate the channel jointly or concurrently, while the differential operation over the received samples of the same state is performed. Such operation is obviously much simpler and easier to implement in VLSI than all the other techniques.

Description:
This application claims benefit to provisional application 60,312,618 filed Aug. 15, 2001. 

   FIELD OF THE INVENTION 
   The present invention relates to frequency offset estimations for use in communications systems, and particularly to a frequency offset estimation based on state-based differential accumulation. 
   BACKGROUND OF THE INVENTION 
   Many modern communication systems are carrier-modulated systems that transmit information bearing signals through some specified bands. Due to the mismatch between the local oscillators of the transmitter and the receiver, a carrier frequency offset is seen at the receiver. In general, a large frequency offset causes rapid phase rotation, which could be far beyond the tracking capability of the receiver functions, such as the carrier phase tracking loop and the channel estimator. It is thus desired to have an initial frequency offset estimation to reduce the amount of frequency offset seen by the remaining part of the receiver. Some current frequency offset estimation algorithms are based on the ideal channel condition of additive white Gaussian noise (AWGN) and in some applications, a communications channel experiences severe inter-symbol interference (ISI). One example is the multi-path fading channel for wireless communications where ISI leads to extra noise terms and degrades the performance of prior art frequency offset estimations. 
   Several prior art frequency offset estimation schemes used in the ISI channels are briefly described herein. A “Fourier Coefficients after Non-linear Operation” algorithm performs the following steps:
         Do some non-linear operation, such as differential detection,   Calculate the Fourier coefficients for some fundamental frequencies at the output of the non-linear operation,   Perform another operation on these coefficients.   Estimate the frequency offset from its phase.
 
This algorithm does not require knowledge of received data symbols and timing, but it makes some approximations based on the assumption of the channel response. Another prior art scheme, “Jointly Channel and Frequency Offset Estimation”, utilizes a maximal-likelihood (ML) type of jointly channel and frequency offset estimator in which the algorithm has to search the maximal point of the non-linear ML equation after certain matrix operations are performed. This algorithm requires the knowledge of received data symbol and timing. The “Phase Rotation of Channel Estimation” method estimates frequency offset by neglecting the effect of frequency offset within a short time, then the frequency offset is estimated by the phase rotation of the channel coefficients. This method splits the channel and frequency offset estimations and requires knowledge of received data symbols and timing. The “Maximum Stated-based Accumulation (MSA)” method utilizes a modified version of the non-linear ML equation which is obtained by collecting the terms corresponding to the same state to form a whole while finding the maximal point of the modified non-linear equation. Knowledge about the received data symbols and timing is required.
       

   SUMMARY OF THE INVENTION 
   The object of the present invention is to provide a frequency offset estimation system and method utilizing inter-symbol interference in a channel communication system. An advantage of the present invention is that it does not require intensive computation of Fourier coefficients or maximization of any non-linear equations as in the prior art. Further, according to the present invention, it is not necessary to frequency offset-estimate the channel jointly or concurrently while the differential operation over the received samples of the same state is being performed. Thus the present invention is simpler and easier to implement than other prior art techniques. 
   The present invention provides a frequency offset estimation system and method utilizing a slow channel variation with respect to a predetermined observation time, the channel being treated as in a static condition within an observation window. In a receiving unit of the channel, there are a plurality of data symbols being pre-stored or detected and a receiving sample sequence being received. A predetermined number of data symbols of the plurality of data symbols are defined as a state, and the plurality of data symbols are divided into a first, a second, and up to an n th  state, each having a length equal to a predetermined number whereby that predetermined number is smaller then the number of said data symbols. The receiving symbol sequence has a phase shift and an angular frequency offset and is formed by a plurality of receiving sample sections. Each of said plurality of receiving sample sections contains a plurality of samples which are received continuously. The method of the present invention comprises the steps of first executing a complex multiplication of two selected receiving sample sections of the plurality of receiving sample sections of the receiving sample sequence so at to obtain a value wherein the two selective receiving sample sections are mapped to the same state of the data symbol and each receiving sample section is designated by a symbol index whereby the symbol indices form a series of continuous integers corresponding to the respective continuous receiving samples of the received symbol sequence; then dividing the multiplied value by a difference of the respective symbol indices of the two selective receiving sample sections thereby acquiring an estimated frequency offset value; and finally weight-averaging a plurality of estimated frequency offset values for different receiving sample section pairs. The various objects and advantages of the present invention will be more readily understood from the following detailed description when read in conjunction with the appended drawings. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows the hardware implementations and block diagrams for the SDA algorithm without state reduction according to the present invention. 
       FIG. 2  shows the hardware implementations and block diagrams for the SDA algorithm with state reduction according to the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   The preferred algorithmic embodiment of the present invention is termed the “State-based Differential Accumulation (SDA)” and utilizes knowledge of received data symbols and timing. In the following description of the present invention, the concept of the state-based operation is first described by mathematical derivation. Then the detailed operations are presented utilizing both equations and conceptual descriptions. 
   Assuming that the channel variation in a communications system is slow with respect to an observation time, and a channel is thus treated as in static condition within an observation window, then a continuous-time received signal can be written as, 
         r   ⁢     (   t   )       =       A   ⁢           ⁢     ⅇ     j   ⁢           ⁢   θ       ⁢     ⅇ     j   ⁢           ⁢     ω   d     ⁢   t       ⁢       ∑     k   =     -   ∞       ∞     ⁢       d   k     ⁢     g   ⁢     (     t   -   kT     )             +     w   ⁢     (   t   )             
 
where
         A is a scalar and is the gain of the channel,   θ is the phase shift of the received signal from the transmitted signal,   ω d  is the angular frequency offset of the channel,   d k  is the k-th transmitted data symbol.   g(t) is the equivalent composite impulse response combing the effects of transmission pulse shaping filters, channel impulse responses, and receiving filters.   T is the period of data symbol transmission.   w(t) is the additive noise process.       

   Taking samples at a rate of 
         M   T     ,       
 
a received sample sequence is obtained 
               r   ⁡     [   n   ]       =       ⁢       r   ⁡     (     t   =     n   ·     T   M         )       =       A   ⁢           ⁢     ⅇ   jθ     ⁢     ⅇ     j   ⁢           ⁢     ω   d     ⁢     n   ·     T   M           ⁢       ∑     k   =     -   ∞       ∞     ⁢       d   k     ⁢     g   ⁡     (       n   ·     T   M       -   kT     )             +                       ⁢     w   ⁡     (     t   =     n   ·     T   M         )                   =       ⁢       A   ⁢           ⁢     ⅇ   jθ     ⁢     ⅇ       j   ·         ω   d     ⁢   T     M       ⁢   n       ⁢       ∑     k   =     -   ∞       ∞     ⁢       d   k     ⁢     g   ⁡     (       T   M     ⁢     (     n   -   kM     )       )             +     w   ⁡     (     t   =     n   ·     T   M         )                     =       ⁢       A   ⁢           ⁢     ⅇ   jθ     ⁢     ⅇ       j   ·       Ω   d     M       ⁢   n       ⁢       ∑     k   =     -   ∞       ∞     ⁢       d   k     ⁢     g   ⁡     [     n   -   kM     ]             +     w   ⁡     [   n   ]                   
 
where
         Ω d =ω d ·T is the angular shift over one symbol period, and 
         g   ⁡     [   n   ]       =     g   ⁢     (     t   =     n   ·     T   M         )           
         w   ⁡     [   n   ]       =     w   ⁢     (     t   =     n   ·     T   M         )           
 
where g[n] and w[n] are the discrete-time sampled version of their continuous-time counterparts.
       

   In the concept of state-based differential operation, for practicality, the impulse response is truncated to some finite length, for example L times the symbol periods. Without loss of generality, assuming that
 
 g[n]= 0  ∀n∉{ 0,1,2, . . . , ( LM− 1)}
 
then consider n=l·M+i, where l∈Z,i∈{0,1,2, . . . ,(M−1)}, 
               r   ⁡     [     n   =     lM   +   i       ]       =       ⁢       A   ⁢           ⁢     ⅇ     j   ⁢           ⁢   θ       ⁢     ⅇ       jΩ   d     ⁡     (     l   +     i   M       )         ⁢       ∑     k   =     l   -   L       l     ⁢       d   k     ⁢     g   ⁡     [         (     l   -   k     )     ⁢   M     +   i     ]             +     w   ⁡     [   n   ]                     =       ⁢         ⅇ     j   ⁢           ⁢       Ω   d     ⁡     (     l   +     i   M       )           ·     X   ⁡     (       S   l     ,   i     )         +     w   ⁡     [   n   ]                   
 
where 
         X   ⁢     (       S   l     ,   i     )       =     A   ⁢           ⁢     ⅇ     j   ⁢           ⁢   θ       ⁢       ∑     k   =     l   -   L       l     ⁢       d   k     ⁢     g   ⁡     [         (     l   -   k     )     ⁢   M     +   i     ]                 
         S l ={d l−L ,d   l−L+1 , . . . , d l } is the state during the l-th symbol.
 
Then the state is formed by the current and previous L data symbols. Only these symbols contribute to the channel ISI related term, X(S l ,i). The receiving samples of the same state and the same offset i can be used to remove the channel effect and estimate the frequency offset. This can be shown as follows.
       

   Neglecting the noise term, for any S l     1   =S l     2    and l 1 ≠l 2 , gives
 
 X ( S   l     1     ,i )= X ( S   l     2     ,i ).
 
Performing the differential operation and defining a new variable for the result, gives
 
 u   i ( l   1   ,l   2 )= r*[l   1   M+i]r[l   2   M+i]=e   jΩ     d     (l     2     −l     1     )   ·|X ( S   l     1     ,i )| 2 
 
The angle of the differential operation result contains the frequency offset information. Thus, the frequency offset can be obtained by 
         Ω   d     =       1     Δ   l       ⁢   ∠   ⁢           ⁢       u   i     ⁢     (       l   1     ,     l   2       )             
 
where Δ l =l 2 −l 1  is the index difference.
 
   To reduce the variance of the estimator, multiple occurrences at the output of the differential operator can be accumulated before taking the phase. For different values of the index difference Δ l , the accumulation is preferably done separately since they are not coherent in phase. The accumulation variable can be calculated as 
         V   ⁢     (     Δ   l     )       =       ∑           l   2     -     l   1       =     Δ   l         S       l   2     =     S     l   2               ⁢       ∑     i   =   0       M   -   1       ⁢       u   i     ⁢     (       l   1     ,     l   2       )               
 
   For any two indices spaced with Δ l  and having the same state, a differential operation is executed with their corresponding samples and the results are accumulated according to the accumulation variable of the index difference Δ l . Frequency offset can be estimated from each of the accumulation variables by 
         Ω   d     Δ   l       =       1     Δ   l       ⁢   ∠   ⁢           ⁢     V   ⁢     (     Δ   l     )             
 
   Due to the ambiguity from phase wrap-around, the resolvable range of the estimator is 
              Ω   d     Δ   l            &lt;       π     Δ   l       .         
 
This leads to a consideration to avoid using large values of Δ l .
 
   A weighted average can be performed over the frequency estimation from different values of Δ l , 
         Ω   d     =       1       ∑         Δ   ⁢             l     =   1       Δ     l   ,   max         ⁢     C   ⁢     (     Δ   l     )           ⁢       ∑         Δ   ⁢             l     =   1       Δ     l   ,   max         ⁢       C   ⁢     (     Δ   l     )       ·     Ω   d     Δ   l                 
 
where
         C(Δ l ), Δ l =1,2, . . . , Δ l,max  are the weighting factors.       

   A maximal value of Δ l  is set under the consideration of frequency estimation range, as described above. The selection of weighting factor preferably minimizes the variance of estimation, and it may also take implementation complexity into account. In a simplest way, equal weights can be applied. Alternatively, the weighting factor can be proportional to the relative frequency of occurrences of Δ l . If the statistics of the data symbol sequence is known and fixed, the weighting factors can be calculated in advance. Otherwise, a set of counters is used to dynamically count the number of the occurrences of each Δ l . Then the counter values are used to generate the weighting factors. 
   The method of the present invention can be summarized as the following rules;
         Execute a complex multiplication of two segments in a receiving sample sequence, wherein the two segments are mapped to the same state of a series of data symbols and each segment is indicated by a symbol index; and the symbol indexes are a series of continuous integers corresponding to respective continuous segments of the received symbol sequence;   Divide the multiplied value by a difference value of respective symbol indexes of the two segments so as to acquire an estimated frequency offset value; and
 
Obtain an average estimated frequency offset value by weighted-averaging a plurality of estimate frequency offset values for different segments.
       

   The number of the states is M d   L+1  where M d  is the size of the set of the data symbol. The present invention preferably reduces the number of states. Consider a rotated received samples by the complex conjugate of the data symbol, and neglecting the noise term; 
                 r   R     ⁡     [     n   =       ⁢     lM   +   i       ]       =       d   l   *     ·     r   ⁡     [     n   =     lM   +   i       ]                     =       ⁢     A   ⁢           ⁢     ⅇ     j   ⁢           ⁢   θ       ⁢     ⅇ     j   ⁢           ⁢       Ω   d     ⁡     (     l   +     i   M       )           ⁢       ∑     k   =     l   -   L       l     ⁢       d   l   *     ⁢     d   k     ⁢     g   ⁡     [         (     l   -   k     )     ⁢   M     +   i     ]                         =       ⁢       ⅇ     j   ⁢           ⁢       Ω   d     ⁡     (     l   +     i   M       )           ·     X   ⁡     (       S     R   ,   l       ,   i     )                   
 
where
 
 S   R,l   ={d   l   *d   l−L   , d   l   *d   l−L+1   , . . . , d   l   *d   l   }=d   l   *·{d   l−L   , d   l−L+1   , . . . , d   l   }=d   l   *·S   l 
 
   It is seen that phase rotation to the received samples causes the same phase rotation to the states. Also note that the state after rotation becomes 
               S     R   ,   l       =       ⁢     {         d   l   *     ⁢     d     l   -   L         ,       d   l   *     ⁢     d     l   -   L   +   1         ,   ⋯   ⁢           ,       d   l   *     ⁢     d   l         }                 =       ⁢       {         d   l   *     ⁢     d     l   -   L         ,       d   l   *     ⁢     d     l   -   L   +   1         ,   ⋯   ⁢           ,            d   l          2       }     .               
 
   In the case of PSK modulation, the last element in the state is a constant. The number of the states becomes M d   L , and the reduction factor is M d . In a more general way, the rotation phase can also be a mapping function from the data symbol other than its complex conjugate. 
   For the case of spread spectrum, if the spreading code or spreading waveform is periodic with the same period as the symbol time, the spreading waveform can be viewed as part of the pulse shaping and can be absorbed into the equivalent composite impulse response. Since the method of the present invention does not require the knowledge of pulse shaping or channel impulse response, it is also applicable to spread spectrum communication systems. 
   A block diagram without state reduction is shown in  FIG. 1 . The operations in the block diagrams are explained as follows. The detailed and mathematical descriptions of each operation are described above.  FIG. 1  illustrates a frequency offset estimation circuit according to the present invention. The circuit comprises a state selector  102 , a receiving end  103 , a state bank  107 , a differential operator  111  and an accumulating and averaging unit  114 . The state selector  102  determines a current state as a selective state ( 1011 ) based on the current and some previous data symbols ( 101 ) which is pre-stored in the receiving end  103  or is roughly detected by the receiving end  103 , the state selector outputs the selected state ( 1011 ). The receiving end  103  serves for receiving a receiving sample sequence ( 104 ) and having a counter  105  for generating a symbol index ( 106 ) responsive to the input sample sequence ( 104 ). The receiving end outputs the received sample sequence ( 104 ) and the symbol index ( 106 ). The state bank  107  has inputs of the selected states ( 1011 ) from the state selector  102 , received sample sequence ( 104 ) from the input end  103  and a symbol index ( 106 ) from the counter  105 . The state bank  107  divides the received sample sequence ( 104 ) into a plurality of data sample sections responsive to the selected state ( 1011 ). Each state unit stores one of the plurality of sample sections and a symbol index of last-time visit. Only contents of a selected state are modified responsive to the selected state ( 1011 ) and the symbol index ( 106 ). Then a selected sample section and a selected symbol index of the last-time visit are shifted to an output end of the state bank  107 . The contents of the state are then updated by new values of the sample sections and the symbol index. The state bank  107  outputs the samples sections and the selected symbol index of the last-time visit. The differential calculator  111  is installed between the state bank  107  and the receiving end  103  and receives inputs of the received sample sequence ( 104 ) and the symbol index ( 106 ) from the receiving end  103  and the selected sample section and the symbol index from the state bank  107 . The differential calculator  111  determines a complex conjugate to the selected samples of the selected last-time visit through a conjugate calculator  113 . Then it executes a complex multiplication to the received samples and the selected sample section of last-time visit to acquire a multiplied value through a complex multiplier  112 . The difference between the symbol index from the receiving symbol sequence and the symbol index from the state bank is also calculated to obtain an index difference. The differential calculator outputs the multiplied value and the index difference. The accumulating and averaging unit  114  has inputs of the multiplied value and the index difference from the differential calculator  111 . The accumulating and averaging unit  114  has a plurality of branches each corresponding to one index difference. The inputted multiplied value is dispatched to a corresponding branch  115  responsive to the index difference. The phase angle of the multiplied value is calculated by, for example, an inverse-tangent operation. The phase angles are scaled differently. The phase angle of each branch is divided by the index difference value of the branch. Finally, a weighted average operation is performed over the branches by a weighted average unit  119 , thereby acquiring the frequency offset in the receiving unit. The state bank  107  further comprises a distributor  108  (in the preferred embodiment, a multiplexer), a plurality of state units  1071  and a simple selector  110  (in the preferred embodiment, a demultiplexer). The distributor  108  has inputs to the received sample sequence  104  and the symbol index  106  from the receiving end  103 . It divides the sample sequence  104  into a plurality of sample section responsive to said symbol index  106  for distributing the sample sections and symbol indexes  106  to a corresponding state unit  1071  responsive to the selected state  1011  from the state selector  102 . The plurality of state units receives and stores corresponding inputs of the data sample sections and the symbol index. Each state unit  1071  has a symbol memory  1072  for recording the sample section and an index memory  1073  for storing the symbol index  106  from the receiving end in response to the selected state. The symbol selector  110  serves for selecting the data symbol and the symbol index of the last-time visit responsive to the selected state from the state selection. Each of the branch further comprises an accumulator  116 , a phase calculator  117  and a scale calculator  118 . The accumulator  116  has an input of the multiplied value for accumulating the multiplied values and the index difference. The phase calculator serves for determining a phase of the multiplied value. The scale calculator  118  serves for determining a scale of the multiplied value. 
   A block diagram with state reduction is shown in  FIG. 2 . A state reduction phase means  120  has an input of a selected data symbol from the plurality of data symbols  101  for calculating a phase of the selected data symbol, and outputs the phase of the selected data symbol. A first phase rotation means  121  receives the phase of the selected data symbol for rotating phases of other data symbols with the phase of the selected data symbol. A second phase rotation means  122  receives the phase of the selected data symbol for rotating phases of the receiving symbol sequence with the phase of the selected data symbol. As described above, the complex conjugate of the data symbol can be selected as the state-reduction phase. Other predetermined mapping from the data symbol to the phase is also possible. In general, the phase rotation block can be performed by the complex multiplication operation. When the phase rotation is only 0 or 180 degrees, only the polarity inverse is needed for phase rotation. When the phase rotation is 90 or 270 degrees, the real and imaginary parts are exchanged to perform the polarity inverse. 
   Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.