Patent Publication Number: US-7224715-B1

Title: Method and system for maximum likelihood clock and carrier recovery in a direct sequence spread spectrum communication system

Description:
REFERENCE TO RELATED APPLICATIONS 
   This application claims the benefit of the priority of U.S. Provisional Application No. 60/474,381 filed May 30 2003. 

   BACKGROUND 
   The present invention discloses a method and system for clock and carrier recovery in a wireless communication system. More particularly, the present invention discloses a method and system for clock and carrier recovery in a direct sequence spread spectrum communication system. 
   In a typical wireless spread spectrum data communication system, the transmitter accepts a bit stream from a source and encodes it into a signal constellation point commonly known as a symbol. The signal constellation is a set of message points corresponding to the set of bits to be transmitted. The standard modulation techniques used for forming the symbol are Binary Phase Shift Keying (BPSK) and Quadrature Phase Shift Keying (QPSK). A sampled spreading sequence (for example a Barker Sequence) lasting over one symbol period is multiplied by the symbol to be transmitted to generate the samples of the signal to be transmitted in the baseband. The resulting samples are then fed to a Digital to Analog Converter (DAC) to generate the baseband analog signal. This analog signal is filtered to meet the required spectral mask and then fed to an up-converter, where a Radio Frequency (RF) carrier is modulated by the analog baseband signal. The output is then filtered and transmitted by means of an antenna. Clocks used for the DAC and the up-converter are derived from a common master clock to avoid non-coherency. 
   The signal is then transmitted through the channel and is received by the receiver. The signal is subjected to multi-path, thermal noise, co-channel and adjacent channel interferences while traveling through the channel. The receiver, after receiving the waveform, reverses the processing done on the signal at the transmitter to get the original signal that was generated by the signal source. The process involves down-conversion of the received RF signal to the baseband and then sampling the baseband analog signal by an Analog to Digital Converter (ADC). The output from the ADC is fed to the baseband processing engine for recovering the bit stream from the received quantized samples. At the receiver also, the clocks for the ADC and the down-converter are derived from a common master oscillator for clock coherency. The received baseband signal has clock and carrier offsets as the transmit and receive clock sources are different. The transmit and receive clocks can vary independently around their nominal values. The clock variation is caused mainly by the crystal frequency drift, which is susceptible to ambient temperature fluctuation, aging and other imperfections. These variations lead to a clock error, which is the difference between the transmit and the receive clocks. This clock error is expressed in terms of a normalized sampling rate error between the transmitter and receiver. The receiver has to estimate and compensate for these offsets in order to successfully decode the bit stream. 
   As a result of the imperfections and inaccuracies mentioned above, there is an offset in the sampling rates of the transmitter DAC and the receiver ADC. Further, the imperfections in the local oscillators, used for up-conversion and down-conversion respectively, result in a carrier offset. The carrier offset, if left uncompensated, results in a continuous rotation in the signal constellation. This offset needs to be compensated for an error-free decision at the receiver. Thus, clock and carrier recovery is an essential process in the receiver. The receiver needs to estimate and track the clock error in the presence of the imperfections and the fluctuations mentioned in the previous paragraph. 
   In most of the data communication systems, a Phase Locked Loop (PLL) performs clock and carrier recovery. However, the PLL has its limitations. Traditionally used PLLs suffer from problems like lock-in and pull-in range limitations, and trade-offs between accuracy and convergence time. Analog PLLs also suffer from inflexibility and difficulty in implementation unlike the PLLs implemented in full software i.e. implementation using a Digital Signal Processor (DSP), or in digital hardware i.e. implementation using a Field Programmable Gate Array (FPGA) or an Application Specific Integrated Circuit (ASIC). Further, the performance accuracy of PLLs is limited by the precision of the analog devices used in the PLL, the device noise and the variation in the performance due to temperature fluctuations and aging. In addition to this, it is difficult to integrate PLLs with digital hardware for single chip implementation. 
   An all-digital carrier recovery is, therefore, much superior to the analog implementation. The performance of the digital implementation is also superior and more precise because its performance depends only on the noise in the input signal. Most of the schemes in all-digital implementation are based on a digital PLL having a Numerically Controlled Oscillator (NCO), digital loop filter and digital hardware to generate control signal for input to the NCO. 
   U.S. Pat. No. 5,361,276 entitled “All Digital Maximum Likelihood Based Spread Spectrum Receiver” granted to AT&amp;T Bell Laboratories, NJ, USA filed on Sep. 13, 1993 discloses a spread spectrum receiver that uses a NCO to generate phase correction and overall frequency correction of the received signal. The receiver also comprises a digital frequency offset correction device for modifying the digital signal in accordance with a frequency correction term to correct the frequency offset in the received analog signal. In addition to this, WIPO Publication number 2001/50631A2 titled “Carrier Tracking Loop For Direct Sequence Spread Spectrum Systems” of Thomson Licensing S.A., France filed on Dec. 22, 2000 discloses a Carrier Tracking Loop (CTL) that is a phase error estimator for receiving the output symbol data. Further, a CTL phase error signal is generated based on the rotation of the spread-spectrum signal, and another CTL is used for generating the counter-rotating signal based on the CTL phase error signal. 
   Both the patents mentioned above use a NCO in their implementation. These are, therefore, digital translations of the analog counterpart of the PLL. Hence, these implementations also suffer from the traditional built-in problems with PLLs. 
   Some other methods that use Fast Fourier Transform (FFT) for carrier offset estimation and a frequency synthesizer for correction of LO (Local Oscillator) frequency have been proposed. European Patent number 892,528A2 titled “Carrier recovery for DSSS signals” granted to Nokia Mobile Phones Ltd., Espoo, Finland presents a device and a method for detection of direct sequence spread spectrum (DSSS) clocks using pseudo-random noise (PN) modulation when offsets are present in the carrier frequency. This is achieved by means of calculations using the Fast Fourier Transform (FFT). 
   The disadvantage of using the above-mentioned approach is that it is complex to implement and expensive in terms of the number of calculations needed. Thus, this scheme requires an expensive synthesizer with a fine enough frequency resolution to correct the carrier offset. 
   From the above discussion, it is apparent that there is a need for an all-digital scheme that is easy to implement and does not require extra digital hardware (such as the NCO, loop filter and the like). Further, the scheme should be easily implemented both in software (for example, using a digital signal processor) and in hardware (for example, using an FPGA or an ASIC). There is also a need for a system that is devoid of complex and expensive operations (like the FFT) and is efficient in correcting the carrier offset without disturbing the local oscillator. 
   SUMMARY  
   The present invention provides a method and system for joint clock and carrier recovery in a direct sequence spread spectrum (DSSS) communication system using a maximum likelihood estimator. 
   An objective of the present invention is to provide a linear estimator for both clock and carrier recovery in a DSSS communication system. 
   Another objective of the present invention is to provide a method and system for both clock and carrier recovery in a DSSS communication system that is suited for full digital implementation without needing additional hardware. 
   Another objective of the present invention is to provide a method and system for both clock and carrier recovery in a DSSS communication system that is computationally efficient and easy to implement. 
   Yet another objective of the present invention is to provide a method and system for correcting the carrier offset without disturbing the local oscillator. 
   To achieve the foregoing objectives, and in accordance with the purpose of the present invention as broadly described herein, the present invention provides a method and system for joint clock and carrier recovery in a direct sequence spread spectrum (DSSS) communication system using a maximum likelihood estimator. The method and the system use a pre-defined training sequence for this purpose. The pre-defined training sequence is first encoded into a Differential Binary Phase Shift Keying (DBPSK) symbol sequence and then spread using a spreading sequence. The spread symbol stream is then modulated onto a carrier frequency and is thereafter transmitted wirelessly over a channel. The stream is thereafter received by a receiver. The signal received at the receiver is down-converted to the baseband of the frequency spectrum and is sampled at a pre-defined sampling rate. Thereafter, the symbol boundary is estimated using the sampled signal. The maximum likelihood estimate of the mean of the phase error is then computed. This computation involves buffering the samples with symbol boundary alignment. The samples are then decimated and de-spread to form a differential symbol. The phase angle of this differential symbol is then extracted and a hard decision is performed on the phase angle. Thereafter, the phase error introduced in the transmitted symbols is calculated and accumulated using maximum likelihood weighting. These steps are performed L times, L being the estimation length in terms of the number of DBPSK symbols. This results in the maximum likelihood estimate of the mean of the phase error. After this, the maximum likelihood estimates of the carrier frequency offset and the clock error are computed. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The preferred embodiments of the invention will hereinafter be described in conjunction with the appended drawings provided to illustrate and not to limit the invention, wherein like designations denote like elements, and in which: 
       FIG. 1  is a block diagram of the basic elements in a typical transmitter and receiver of a Wireless Local Area Network (WLAN); and 
       FIG. 2A  and  FIG. 2B  are flowcharts of the method of clock and carrier recovery at the receiver of a Direct Sequence Spread Spectrum (DSSS) communication system in accordance with a preferred embodiment of the present invention. 
   

   DESCRIPTION OF PREFERRED EMBODIMENTS 
   The present invention provides a method and system for joint clock and carrier recovery in a DSSS communication system using a maximum likelihood estimator. 
   In a DSSS communication system such as IEEE 802.11b based WLAN, an information bit sequence is first encoded into Differential Binary Phase Shift Keying (DBPSK) or Differential Quaternary Phase Shift Keying (DQPSK) symbols, which are then spread using a spreading sequence. The spreading is achieved by multiplying the symbol with a spreading sequence. The signal formed after the spreading is modulated onto a carrier frequency and then transmitted over-the-air. 
   Referring now primarily to  FIG. 1 , the basic elements in a typical WLAN communication system will hereinafter be described. A baseband signal generator  102  generates a signal that needs to be transmitted. The transmitter modem, which is a part of baseband signal generator  102 , generates samples of the signal and passes it through a Digital to Analog Converter (DAC)  104 . DAC  104  has a sampling rate f st  with an unknown error df st . The signal is then passed through a Low Pass Filter (LPF)  106  to meet the required spectral mask. Thereafter, the signal is passed onto a multiplier  108  that is responsible for up-converting the baseband signal to carrier frequency f c  with an unknown error df ct . The signal at the output of multiplier  108  is then transmitted by a transmitter antenna  110 . All the frequencies used at the transmitter are generated by a master oscillator  112 . Further, the carrier frequency f c  is generated by a clock multiplier  114 , which also sources the clock from a master oscillator  112 . 
   The transmitted signal is received by a receiving antenna  116  present at a remote receiver. The received signal is first down-converted from the carrier frequency by a multiplier  118  and an LPF  120 . Multiplier  118  multiplies the received signal with a sine wave function that results in the conversion of the received signal into a signal containing a baseband component as well as a high frequency narrow band component. LPF  120  filters out the high frequency component so that only the baseband signal remains. The down-conversion frequency is f c  with a carrier offset of df cr . After this, the signal is sampled and converted to digital form by an Analog to Digital Converter (ADC)  122 . ADC  122  has a sampling rate f sr  with an unknown error df sr . The resulting signal from ADC  122  is then processed by a baseband signal processor  124  for the purpose of demodulation and decoding. All the frequencies used at the receiver are generated by a master oscillator  126 . Further, the carrier frequency f c  (with the offset df cr ) is generated by a clock multiplier  128 , which sources the clock from master oscillator  126 . 
   The mismatch in the sampling rates of DAC  104  and ADC  122  arises due to the fact that master oscillator  112  at the transmitter and master oscillator  126  at the receiver use crystals that are non-coherent. Moreover, master oscillator frequencies vary independently around their nominal values. The variation is mainly caused by the crystal frequency drift, which is susceptible to ambient temperature fluctuation, aging and other imperfections. The difference in master oscillator  112  at the transmitter and master oscillator  126  at the receiver also gives rise to the mismatch in the upconversion and downconversion frequencies. 
   Thus, there is a mismatch between the sampling rate at the receiver and the sampling rate at the transmitter. Also, there is a mismatch between the carrier frequency used for downconversion at the receiver and the carrier frequency used for upconversion at the transmitter. Moreover, these mismatches vary with time around their nominal values. For effective demodulation and decoding of the received data in a WLAN system, these mismatches need to be rectified so that the transmitter and the receiver are synchronized. 
   In accordance with a preferred embodiment of the present invention, a pre-defined training sequence or unknown data sequence is transmitted to enable joint clock and carrier recovery in a WLAN system. Each bit of the known training sequence is first encoded into a DBPSK symbol that is then spread by a pre-defined spreading sequence, hereinafter referred to as the spreading sequence. The training sequence is used to make an estimation of the clock and carrier offsets. This is then tracked over the entire burst of the received signal. Let N denote the length of the spreading sequence. Thus, N is also the number of chips per symbol of the pre-defined training sequence, i.e. the spreading factor. 
   Referring now primarily to  FIG. 2A  and  FIG. 2B , the method of estimation of the clock and carrier offset at the receiver in a DSSS communication system in accordance with a preferred embodiment of the present invention is hereinafter described. At step  202 , a signal (hereinafter referred to as the received signal) corresponding to the transmitted training sequence is received by the receiver. Thereafter, at step  204 , the received signal is downconverted to a baseband signal using multiplier  118  and LPF  120 . 
   At step  206 , the baseband signal is sampled by ADC  122  at a pre-defined sampling rate to obtain samples of received signal. Let M denote the number of samples per symbol. Thereafter, at step  208 , a symbol boundary is estimated for the received signal using the samples obtained. A number of methods exist in the art for performing symbol boundary estimation. In a preferred embodiment of the present invention, the method described in the patent application titled ‘A method of channel characterization in direct sequence spread spectrum based WLAN’, filed on Apr. 23, 2003 as application Ser. No. 10/423,739, is used for symbol boundary estimation. In this method, a desired set of cross correlations, for a set of equally spaced time lags, is computed between the samples of the received signal and the spreading sequence. This set of cross correlations is used for channel characterization. The time lag corresponding to the highest magnitude cross correlation element in the selected set of cross correlations is the desired estimate of the symbol boundary. 
   Referring back to  FIG. 2A  and  FIG. 2B , at step  209 , a counter is initialized to zero. Thereafter, steps  210  to  228  are repeated L times, L being the estimation length in terms of the number of DBPSK symbols used for the estimation of the clock and carrier offsets. 
   Consider the k th  iteration of steps  210  to  228 . At step  210 , M samples of the received signal are buffered with symbol boundary alignment, the M buffered samples covering a complete symbol duration. The first of the M samples is the sample at the time instant corresponding to the estimate of the symbol boundary obtained at step  208 . Thereafter, at step  212 , the buffered samples are decimated. In decimation, N samples out of a total of M samples are retained so that the N retained samples cover the complete symbol duration. Thereafter, at step  214 , the N retained samples are de-spread using the pre-defined spreading code to obtain a de-spread symbol corresponding to the samples. The k th  de-spread symbol is given by: 
                   S   k     =       ∑     n   =   0       N   -   1       ⁢       y     n   ,   k       ⁢     b   n                 (   1   )               
where,
         S k  denotes the k th  de-spread symbol,   y n,k  denotes the n th  sample from the N retained samples, the N retained samples corresponding to the k th  symbol used in the estimation, and   b n  denotes the n th  sample of the spreading sequence.       
   Referring back to  FIG. 2A  and  FIG. 2B , the de-spread symbol S k  is used at step  216  to form a differential symbol. The differential symbol is given by:
 
 D   k   =S   k   S   k−1 *   (2)
 
where,
         S k−1  denotes the (k−1) th  de-spread symbol, with S −1 =1, and   * denotes the complex conjugate operation.       

   At step  218 , the phase angle of the differential symbol D k  is extracted. This gives an estimate of the transmitted phase of the DBPSK symbol in k th  symbol interval. Thereafter, at step  220 , a differential angle, d k , is extracted by performing a hard decision on the estimated phase. Then, at step  222 , a phase error, φ k , introduced in the transmitted symbols is estimated. The phase error is given by:
 
φ k =∠( D   k )− d   k    (3)
 
where,
         ∠(x) denotes the principal argument of the complex number x.   d k  is known at the receiver prior, if the transmitted sequence is known. Otherwise, it is to be extracted from received data.       

   Thereafter, the current value of the phase error is accumulated at step  224  with the previously estimated phase errors, multiplying these errors with the maximum likelihood weights as given in (4). 
                   W   k     =       6   ⁢           ⁢     k   ⁡     (     L   -   k     )           L   ⁡     (       L   2     -   1     )                 (   4   )               
where,
         k takes integer values from 0 to L−1, and   L denotes the estimation length.       
   The accumulated phase error can be represented as:
 
Φ k =W k φ k +Φ k−1    (5)
 
where
         Φ k  denotes the accumulated phase after k weighted phase error estimates,   k takes integer values from 0 to L−1, and   Φ −1 =0.       

   After the accumulation of the phase error, the counter is incremented by 1 at step  226 . Thereafter, at step  228 , a check is made to ascertain whether the counter is equal to L. If the counter at step  228  is not equal to L, steps  210  to  228  are repeated, as shown with the help of connector  230 . 
   If the counter at step  228  is equal to L, steps  210  to  228  are not repeated. Note that L values of the phase error, φ k , have been estimated by the L iterations of steps  210  to  226 . Once these L values have been estimated and accumulated with weighting as above, the final result gives the maximum likelihood estimate, m Φ   ML , of the mean, m φ , of the phase error:
 
m Φ   ML =Φ L−1    (6)
 
   Thereafter, the maximum likelihood estimate of the carrier frequency offset, Δω c   ML , is computed at step  232  using m 101   ML . The relationship between Δω c   ML  and m Φ   ML  is given by: 
                   Δω   c   ML     =       m   ϕ   ML     N             (   7   )               
where, N is the number of samples per symbol.
 
   Once Δω c   ML  has been computed, the maximum likelihood estimate, Δ clock   ML , of the clock error at the receiver is computed at step  234  using the following equation: 
                   Δ   clock   ML     =         -     f   sr         2   ⁢   π   ⁢           ⁢     f   c         ⁢     Δω   c   ML               (   8   )               
where,
         f c  denotes the carrier frequency, and   f sr  denotes the receiver sampling frequency.       
   The method of maximum likelihood clock and carrier recovery in a direct sequence spread spectrum communication system according to the present invention is also disclosed in a research paper authored by the inventors of the present invention. The paper titled ‘Maximum Likelihood Clock and Carrier Recovery in a Direct Sequence Spread Spectrum Communication System’ was presented by Kaushik Barman and Vellenki Umapathi Reddy at the 2002 IEEE International Conference on Personal Wireless Communications, held in New Delhi, India, on Dec. 15–17, 2002. This paper is not admitted as effective prior art as the present patent application has been filed within one year of presenting the paper. In addition to disclosing the method according to the present invention, the paper also mathematically proves that the estimators according to the present invention are the maximum likelihood estimators for clock and carrier recovery. The method of maximum likelihood clock and carrier recovery as disclosed in the paper has been fully described herein. 
   One mode of reduction to practice of the preferred embodiment of the present invention is hereinafter described. A training sequence at 1 Mbps comprising 128 symbols is first encoded into DBPSK symbols that is then spread to a bandwidth of 11 MHz using a Barker sequence of length 11 resulting in N=11 chips per symbol. The received signal is sampled at a frequency of 44 MHz resulting in M=44 i.e. 44 samples per symbol. In an alternative mode of reduction to practice, the received signal is sampled at a frequency of 22 MHz resulting in M=22 i.e. 22 samples per symbol. It would be apparent to anyone skilled in the art that any other sampling frequency that is a multiple of 11 MHz and more than double the bandwidth may also be used. 
   The method of joint clock and carrier recovery provided by the present invention is implemented using re-programmable blocks such as Digital Signal Processors (DSPs). This implementation involves programming the DSPs using program codes that embody the method outlined in  FIG. 2A  and  FIG. 2B . These program codes may be written in either DSP-specific assembly level language or a high-level language such as C. The embodiment of the present invention as a computer program product is used for joint clock and carrier recovery in a DSSS based communication system such as a WLAN. It can also be used for the simulation of a joint clock and carrier recovery system. 
   Alternatively, the method provided by the present invention may be implemented using digital logic in Field Programmable Gate Arrays (FPGAs) or in Application Specific Integrated Circuits (ASICs). An all-digital implementation is preferred due to the ease of re-programmability and upgradability of such an implementation. 
   The method provided by the present invention has a number of attractive features. First, the method is suitable for an all-digital implementation that does not require extra digital hardware (such as the Numerically Controlled Oscillator, the loop filter and the like). Second, the method is easily implemented both in software using a DSP and in hardware using an FPGA or an ASIC. Third, the method is efficient in correcting the carrier offset by de-rotating the ADC output samples digitally using estimated carrier offset, which does not involve any hardware to correct the local oscillator frequency. 
   While the preferred embodiments of the invention have been illustrated and described, it will be clear that the invention is not limited to these embodiments only. Numerous modifications, changes, variations, substitutions and equivalents will be apparent to those skilled in the art without departing from the spirit and scope of the invention.