Abstract:
A path metric computation method and apparatus for estimating a maximum likelihood sequence in a wireless communication network. The proposed method applies the statistical properties of estimated channel impulse response to reduce the computational load. A threshold is set to check the significance of each autocorrelation value in order to determine the contribution to the path metric increment. The corresponding terms in the path metric equation with insignificant autocorrelation values are thus discarded to reduce the complexity of path metric computation.

Description:
BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   The present invention relates to an equalizer used in a communication network, and more specifically, to a method and apparatus for simplifying the metric calculation of Maximum Likelihood Sequence Estimation (MLSE). 
   2. Description of the Related Art 
   The modulation algorithm employed in both Global System for Mobile (GSM) and General Packet Radio System (GPRS) communication networks is Gaussian Minimum Shift Keying (GMSK), which induces inter-symbol interference (ISI) in the received signal sampled at a specific rate. ISI is the residual effect of other neighboring symbols when decoding a certain symbol and this residual effect is due to the occurrence of pulses before and after the sampling instance. The unavoidable presence of ISI in the system, however, introduces errors in the decision device at the receiver output. Therefore, in the filter design of the GSM/GPRS receiver and transmitter, the object is to diminish the effects of ISI and thereby deliver the digital data to the destination with the smallest error rate possible. An equalizer is a widely used approach for compensating or reducing the ISI effect. 
   In general, there are three types of equalizers: maximum likelihood (ML) equalizer, liner equalizer, and decision feedback equalizer. The ML equalizer is based on the maximum likelihood sequence detection criterion, whereas the linear equalizer is based on the use of a linear filter with adjustable coefficients. The decision feedback equalizer is based on the use of previous detected symbols to suppress the ISI in the present symbol being detected. The performance and complexity of these equalizers are listed in the table shown in  FIG. 1 . The ML equalizer has optimum performance among the three equalizers. The complexity of the ML equalizer, however, is the highest. In  FIG. 1 , L indicates the length of ISI. 
   An exemplary transmission model of a wireless communication system is shown in  FIG. 2 . A signal  21  from the transmitter  22  is first filtered by a Low Pass (LP) filter  221 , converted to radio frequency (RF) by multiplying a carrier in a multiplier  222 , and finally passed to a processing unit  223  before transmission to the channel  24 . The processing unit  223  extracts the real part of the signal. The characteristic of the channel  24  is modeled by a channel response block  241  with channel noise  23 . The channel noise  23  is generally assumed as Additive White Gaussian Noise (AWGN). The multiplier  261  in the receiver  26  converts back the frequency of the signal received by the receiver by multiplying the same frequency as the carrier frequency. The LP filter  262  receives the down converted signal, and outputs a received signal  25 . The equalizer  263  compensates the ISI of the received signal  25 , and outputs an estimated signal  27 . The received signal r(t)  25  is expressed by Equation [1]. 
   
     
       
         
           
             
               
                 
                   r 
                   ⁡ 
                   
                     ( 
                     t 
                     ) 
                   
                 
                 = 
                 
                   
                     
                       ∑ 
                       n 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         a 
                         n 
                       
                       ⁢ 
                       
                         h 
                         ⁡ 
                         
                           ( 
                           
                             t 
                             - 
                             nT 
                           
                           ) 
                         
                       
                     
                   
                   + 
                   
                     n 
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 1 
                 ] 
               
             
           
         
       
     
   
   h(t) denotes the overall channel response of the system, and it can be derived by performing convolution to the transmitter&#39;s impulse response f t (f), receiver&#39;s impulse response f r (t), and channel model response g(t), h(t)=f t (t)*g(t)*f r (t). 
   The channel noise n(t)  23  herein is assumed to be stationary Gaussian noise with zero mean and variance N o . Let {a n } (which is also the signal  21  in  FIG. 2 ) be a hypothetical sequence of pulse amplitudes transmitted during a time period I. The equalizer  263  is assumed to be a ML equalizer, which determines the best estimation of {a n } as the estimated sequence {â n } (signal  27  of  FIG. 2 ). The estimated sequence {α n }={â n } is derived by maximizing the likelihood function as shown in Equation [2.
 
p[r(t),t ε I |{α n }]  Equation [2]
 
   The probability of 0s and 1s in the transmitted sequences are assumed to be equal, therefore, Equation [2] can be rewritten as: 
   
     
       
         
           
             
               
                 
                   p 
                   ⁡ 
                   
                     [ 
                     
                       
                         { 
                         
                           α 
                           n 
                         
                         } 
                       
                       ❘ 
                       
                         r 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                     
                     ] 
                   
                 
                 = 
                 
                   
                     
                       p 
                       ⁡ 
                       
                         ( 
                         
                           
                             r 
                             ⁡ 
                             
                               ( 
                               t 
                               ) 
                             
                           
                           ❘ 
                           
                             { 
                             
                               α 
                               n 
                             
                             } 
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       p 
                       ⁡ 
                       
                         ( 
                         
                           { 
                           
                             α 
                             n 
                           
                           } 
                         
                         ) 
                       
                     
                   
                   
                     p 
                     ⁡ 
                     
                       ( 
                       
                         r 
                         ⁡ 
                         
                           ( 
                           t 
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 3 
                 ] 
               
             
           
         
       
     
   
   p[{α n }|r(t)] is also called the posteriori probability. The probability of the estimated sequence p[{α n }] and the received signal r(t) are both assumed to be constant. Since the objective of the ML equalizer is to maximize the likelihood function shown in Equation [2], the posteriori probability must also be maximized. If the sequence {α n } was the actual sequence of the pulse amplitude transmitted during time period I, the power density function of the noise signal n(t) can be expressed as shown in Equation [4]. 
   
     
       
         
           
             
               
                 
                   
                     n 
                     ⁡ 
                     
                       ( 
                       
                         t 
                         ❘ 
                         
                           { 
                           
                             α 
                             n 
                           
                           } 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       r 
                       ⁡ 
                       
                         ( 
                         t 
                         ) 
                       
                     
                     - 
                     
                       
                         ∑ 
                         
                           nT 
                           ∈ 
                           I 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           α 
                           n 
                         
                         ⁢ 
                         
                           h 
                           ⁡ 
                           
                             ( 
                             
                               t 
                               - 
                               nT 
                             
                             ) 
                           
                         
                       
                     
                   
                 
                 , 
                 
                   t 
                   ∈ 
                   I 
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 4 
                 ] 
               
             
           
         
       
     
   
   The ML function of Equation [2] thus becomes: 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         p 
                         ⁡ 
                         
                           ( 
                           
                             
                               r 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             ❘ 
                             
                               { 
                               
                                 α 
                                 n 
                               
                               } 
                             
                           
                           ) 
                         
                       
                       = 
                       
                         p 
                         ⁡ 
                         
                           [ 
                           
                             
                               n 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             ❘ 
                             
                               { 
                               
                                 α 
                                 n 
                               
                               } 
                             
                           
                           ] 
                         
                       
                     
                   
                 
                 
                   
                     
                       = 
                       
                         
                           
                             ( 
                             
                               1 
                               
                                 2 
                                 ⁢ 
                                 π 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   N 
                                   o 
                                 
                               
                             
                             ) 
                           
                           N 
                         
                         ⁢ 
                         
                           exp 
                           ⁡ 
                           
                             ( 
                             
                               
                                 
                                   
                                     
                                       
                                         - 
                                         
                                           1 
                                           
                                             2 
                                             ⁢ 
                                             
                                               N 
                                               o 
                                             
                                           
                                         
                                       
                                       ⁢ 
                                       
                                         ∑ 
                                         
                                           k 
                                           = 
                                           1 
                                         
                                         N 
                                       
                                     
                                     ⁢ 
                                     
                                         
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                        
                                       
                                         
                                           r 
                                           k 
                                         
                                         - 
                                         
                                           
                                             ∑ 
                                             n 
                                           
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           
                                             
                                               α 
                                               n 
                                             
                                             ⁢ 
                                             
                                               h 
                                               kn 
                                             
                                           
                                         
                                       
                                        
                                     
                                     2 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 5 
                 ] 
               
             
           
         
       
     
   
   The probability of the ML function p[r(t)|{α n }] is proportional to the logarithm. p[r(t)|{α n }]: 
   
     
       
         
           
             
               
                 
                   - 
                   
                     
                       ∫ 
                       
                         - 
                         ∞ 
                       
                       ∞ 
                     
                     ⁢ 
                     
                       
                         
                            
                           
                             
                               r 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                             - 
                             
                               
                                 ∑ 
                                 n 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   α 
                                   n 
                                 
                                 ⁢ 
                                 
                                   h 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       t 
                                       - 
                                       nT 
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                            
                         
                         2 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ⅆ 
                         t 
                       
                     
                   
                 
                 = 
                 
                   
                     - 
                     
                       
                         ∫ 
                         
                           - 
                           ∞ 
                         
                         ∞ 
                       
                       ⁢ 
                       
                         
                           
                              
                             
                               r 
                               ⁡ 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                              
                           
                           2 
                         
                         ⁢ 
                         
                           ⅆ 
                           t 
                         
                       
                     
                   
                   + 
                   
                     2 
                     ⁢ 
                     Re 
                     ⁢ 
                     
                       
                         ∑ 
                         n 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         [ 
                         
                           
                             α 
                             n 
                             * 
                           
                           ⁢ 
                           
                             
                               ∫ 
                               
                                 - 
                                 ∞ 
                               
                               ∞ 
                             
                             ⁢ 
                             
                               
                                 r 
                                 ⁡ 
                                 
                                   ( 
                                   t 
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 
                                   h 
                                   * 
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     t 
                                     - 
                                     nT 
                                   
                                   ) 
                                 
                               
                               ⁢ 
                               
                                 ⅆ 
                                 t 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                   - 
                   
                     
                       ∑ 
                       n 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ∑ 
                         m 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           α 
                           n 
                           * 
                         
                         ⁢ 
                         
                           α 
                           m 
                         
                         ⁢ 
                         
                           
                             ∫ 
                             
                               - 
                               ∞ 
                             
                             ∞ 
                           
                           ⁢ 
                           
                             
                               
                                 h 
                                 * 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   t 
                                   - 
                                   nT 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                               h 
                               ⁡ 
                               
                                 ( 
                                 
                                   t 
                                   - 
                                   mT 
                                 
                                 ) 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ⅆ 
                               t 
                             
                           
                         
                       
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 6 
                 ] 
               
             
           
         
       
     
   
   The first term of Equation [6] is a constant, thus it can be discarded when calculating the metric. A correlation metric (MC) can be derived from the previous steps as shown in Equation [7]. 
   
     
       
         
           
             
               
                 
                   
                     CM 
                     ⁡ 
                     
                       ( 
                       
                         { 
                         
                           α 
                           I 
                         
                         } 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       2 
                       ⁢ 
                       Re 
                       ⁢ 
                       
                         
                           ∑ 
                           
                             nT 
                             ∈ 
                             I 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               α 
                               n 
                               * 
                             
                             ⁢ 
                             
                               Z 
                               n 
                             
                           
                           ) 
                         
                       
                     
                     - 
                     
                       
                         ∑ 
                         
                           iT 
                           ∈ 
                           I 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             kT 
                             ∈ 
                             I 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             α 
                             n 
                             * 
                           
                           ⁢ 
                           
                             α 
                             k 
                           
                           ⁢ 
                           
                             s 
                             
                               i 
                               - 
                               k 
                             
                           
                         
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 where 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     z 
                     n 
                   
                   = 
                   
                     
                       
                         
                           
                             g 
                             MF 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         * 
                         
                           r 
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                       ⁢ 
                       
                         ❘ 
                         
                           t 
                           = 
                           nT 
                         
                       
                     
                     = 
                     
                       
                         
                           ∑ 
                           l 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             a 
                             
                               n 
                               - 
                               l 
                             
                           
                           ⁢ 
                           
                             s 
                             l 
                           
                         
                       
                       + 
                       
                         w 
                         n 
                       
                     
                   
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 
                   
                     s 
                     l 
                   
                   = 
                   
                     
                       
                         
                           
                             g 
                             MF 
                           
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         * 
                         
                           h 
                           ⁡ 
                           
                             ( 
                             t 
                             ) 
                           
                         
                       
                       ⁢ 
                       
                         ❘ 
                         
                           t 
                           = 
                           lT 
                         
                       
                     
                     = 
                     
                       
                         s 
                         
                           - 
                           l 
                         
                         * 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       and 
                     
                   
                 
                 ⁢ 
                 
                    
                 
                 ⁢ 
                 
                   
                     
                       g 
                       MF 
                     
                     ⁡ 
                     
                       ( 
                       t 
                       ) 
                     
                   
                   = 
                   
                     
                       h 
                       * 
                     
                     ⁡ 
                     
                       ( 
                       
                         - 
                         t 
                       
                       ) 
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 7 
                 ] 
               
             
           
         
       
     
   
   s 1  herein is the channel response autocorrelation. 
   Maximum Likelihood Sequence Estimation (MLSE) determines the most likely sequence originally transmitted by the sequence {α n } by maximizing the likelihood function shown in Equation [5], or equivalently, maximizing the metric shown in Equation [8]. 
   
     
       
         
           
             
               
                 
                   
                     J 
                     n 
                   
                   ⁡ 
                   
                     ( 
                     
                       { 
                       
                         α 
                         I 
                       
                       } 
                     
                     ) 
                   
                 
                 = 
                 
                   
                     2 
                     ⁢ 
                     Re 
                     ⁢ 
                     
                       
                         ∑ 
                         
                           nT 
                           ∈ 
                           I 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             α 
                             n 
                             * 
                           
                           ⁢ 
                           
                             Z 
                             n 
                           
                         
                         ) 
                       
                     
                   
                   - 
                   
                     
                       ∑ 
                       
                         iT 
                         ∈ 
                         I 
                       
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ∑ 
                         
                           kT 
                           ∈ 
                           I 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         
                           α 
                           i 
                           * 
                         
                         ⁢ 
                         
                           s 
                           
                             i 
                             - 
                             k 
                           
                         
                         ⁢ 
                         
                           α 
                           k 
                         
                       
                     
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 8 
                 ] 
               
             
           
         
       
     
   
   The MLSE algorithm obtained represents a modified version of the well-known Viterbi algorithm. The Viterbi algorithm is obtained by computing the recursive relation iteratively. 
   
     
       
         
           
             
               
                 
                   
                     J 
                     n 
                   
                   ( 
                   
                       
                   
                   ⁢ 
                   
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       α 
                       
                         n 
                         = 
                         1 
                       
                     
                     , 
                     
                       α 
                       n 
                     
                   
                   ) 
                 
                 = 
                 
                   
                     
                       J 
                       
                         n 
                         - 
                         1 
                       
                     
                     ( 
                     
                         
                     
                     ⁢ 
                     
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         α 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     ) 
                   
                   + 
                   
                     
                       Re 
                       [ 
                       
                         
                           α 
                           n 
                           * 
                         
                         ⁡ 
                         
                           ( 
                           
                             
                               2 
                               ⁢ 
                               
                                 Z 
                                 n 
                               
                             
                             - 
                             
                               
                                 s 
                                 0 
                               
                               ⁢ 
                               
                                 α 
                                 n 
                               
                             
                             - 
                             
                               2 
                               ⁢ 
                               
                                 
                                   ∑ 
                                   
                                     k 
                                     ≤ 
                                     
                                       n 
                                       - 
                                       1 
                                     
                                   
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     s 
                                     
                                       n 
                                       - 
                                       k 
                                     
                                   
                                   ⁢ 
                                   
                                     α 
                                     k 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                       ] 
                     
                     . 
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 9 
                 ] 
               
             
           
         
       
     
   
     FIG. 3  shows the architecture of the Viterbi Equalizer, wherein the received signal r(t) is estimated according to Equation [1]. 
   SUMMARY OF THE INVENTION 
   Accordingly, the object of the present invention is to reduce the complexity of metric calculation for Maximum Likelihood Sequence Estimation (MLSE) in Global System for Mobile (GSM) or General Packet Radio Service (GPRS) communication network. The path computation of equalizer causes most of the computation load, so the processing speed can be accelerated by simplifying the path computation. As a result, the power consumption of the Mobile Station (MS) can also be greatly reduced. 
   The present invention provides a path metric computation method for estimating a maximum likelihood sequence, wherein a survival path of each sample is determined according to the channel impulse response of N samples in the path metric computation. The autocorrelation values S(n) of the channel impulse response corresponding to the N samples (n ranges from 0 to N-1) is first calculated, subsequently, each autocorrelation value S(n) is normalized by dividing S(0) to obtain the normalized values NS (n). The normalized values NS (n) are compared to a preset threshold individually. Each S(n) is judged as a significant autocorrelation value if the corresponding NS(n) is greater than the threshold, otherwise, the S(n) is judged as an insignificant autocorrelation value. The insignificant autocorrelation values are discard as the autocorrelation values are too small to have an effect on the major path metric for determining the survival path. The survival path is therefore determined by considering only the significant autocorrelation values. 
   The path metric computation proposed in the present invention is implemented in an equalizer, and the Maximum Likelihood Sequence Estimation (MLSE) Viterbi equalizer is a commonly used equalizer in the GSM or GPRS communication network. The survival path is recorded until succeeding N samples have been passed to the equalizer, and the maximum likelihood sequence is derived by tracing back the survival path. 
   The present invention also provides a path metric computation apparatus comprising an autocorrelation calculator, a comparator, and a path metric computation unit. The autocorrelation calculator computes and passes the autocorrelation values S(n) to the comparator. The comparator only outputs autocorrelation values S(n) which are greater than a preset threshold to the path metric computation unit. The path metric computation unit computes the path metric and determines the survival path with the maximum path metric. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The present invention can be more fully understood by reading the subsequent detailed description in conjunction with the examples and references made to the accompanying drawings, wherein: 
       FIG. 1  is a table showing the comparison of performance and complexity between the three equalizers. 
       FIG. 2  is a block diagram illustrating the transmission model for a wireless communication system. 
       FIG. 3  is a block diagram illustrating the architecture of a Viterbi equalizer. 
       FIG. 4  is a sketch map showing the trellis diagram of the Viterbi equalizer. 
       FIG. 5  is a sketch map showing the trellis diagram of the Viterbi equalizer with reduced path computation. 
       FIG. 6  is a flowchart showing the path metric computation method according to the embodiment of the present invention. 
       FIG. 7  is a simple block diagram showing the path metric computation apparatus according to the embodiment of the present invention. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   An embodiment of the present invention assumes that the length of the channel impulse response h(t) is equal to the duration of five symbols (L=5), which means that each sample is assumed to have an inter-symbol interference (ISI) effect on 5 neighboring samples. Since the autocorrelation S 1  of the channel impulse response h(t) is symmetrical, relations shown in Equation [10] must be satisfied.
 
 S   l   =g   MF ( t )* h ( t )| t-lT   =S   -1   *   ,|l|&lt; 4  S   1 =0 ,|l|≧ 5  Equation [10]
 
   The path metric equation shown in Equation [9] can be expressed as following: 
   
     
       
         
           
             
               
                 
                   
                     J 
                     n 
                   
                   ( 
                   
                       
                   
                   ⁢ 
                   
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       α 
                       
                         n 
                         = 
                         1 
                       
                     
                     , 
                     
                       α 
                       n 
                     
                   
                   ) 
                 
                 = 
                 
                   
                     
                       J 
                       
                         n 
                         - 
                         1 
                       
                     
                     ( 
                     
                         
                     
                     ⁢ 
                     
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         α 
                         
                           n 
                           - 
                           1 
                         
                       
                     
                     ) 
                   
                   + 
                   
                     Re 
                     [ 
                     
                       
                         α 
                         n 
                         * 
                       
                       ( 
                       
                         
                           2 
                           ⁢ 
                           
                             Z 
                             n 
                           
                         
                         - 
                         
                           
                             s 
                             0 
                           
                           ⁢ 
                           
                             α 
                             n 
                           
                         
                         - 
                         
                           2 
                           ⁢ 
                           
                             
                               ∑ 
                               
                                 l 
                                 = 
                                 1 
                               
                               4 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 S 
                                 l 
                               
                               ⁢ 
                               
                                 α 
                                 
                                   n 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                       
                       ⁢ 
                       
                           
                       
                       ) 
                     
                     ] 
                   
                 
               
             
             
               
                 Equation 
                 ⁢ 
                 
                     
                 
                 [ 
                 11 
                 ] 
               
             
           
         
       
     
   
   A sketch map according to the path metric equation of Equation [11] is used to show the state transition and path metric calculation for L=5.  FIG. 4  shows the trellis diagram of the Viterbi equalizer with L=5. As shown in  FIG. 4 , there are 2 L-1 =2 5-1 =16 states. Each state J n  contains four bits representing a current sample and three previous samples (α n ,α n-1 ,α n-2 ,α n-3 ), and each state J n  is merged by two of the previous states J n-1  (α n-1 ,α n- 2,α n-3 ,α n-4 ). The two previous states are called competing paths, and the competing path with maximum path metric becomes the survival path of the current state. 
   Assuming there are N samples passed to the Viterbi equalizer, and each state calculates and compares the path metric with its competing path to determine the survival path for each sample. The survival path is recorded in each state until N samples have been passed to the Viterbi equalizer, and traced back to the recorded survival path history from the state with the maximum state metric. The most likely sequence that satisfies the previously described Maximum Likelihood (ML) function is determined by tracing back the survival path. 
   It is obvious from the previous description that path calculation causes most of the computational load in the equalizer. Therefore, by reducing the complexity of the path metric computation, the processing speed of the equalizer may be enhanced resulting in extending the battery life of the mobile station. 
   The path metric computation method and apparatus proposed in the present invention simplifies the computation executed by the Viterbi equalizer. The second term 
           Re   [       α   n   *     (       2   ⁢     Z   n       -       s   0     ⁢     α   n       -     2   ⁢       ∑     l   =   1     4     ⁢           ⁢       S   l     ⁢     α     n   -   1               ⁢           )     ]         
in Equation [11] is the path metric increment, wherein Z n  is the output of the received signal passed to the match filter, thus, this term can be removed from the metric calculation. The term S 1  represents the autocorrelation of the channel impulse response. Under various fading channel simulations, the observed value of certain S 1  is very small compared to other S 1 . The corresponding contribution to the path metric increment of the insignificant S 1  is much less than other S 1 . Put simply, the insignificant S 1  does not dominate the major path metric increment for determining the survival path, hence the term with insignificant S 1  can be discarded to reduce the computational load. A sketch map of the reduced path metric computation proposed in the present invention is shown in  FIG. 5 . S 3  is assumed to be insignificant when compared to the other autocorrelation values S, and therefore the term S 3 α n-3  is ignored in the path metric computation. Accordingly, the total number of states is greatly reduced from 16 to 8 states.
 
     FIG. 6  is a flowchart illustrating the path metric computation method proposed in the present invention for determining significant autocorrelation values S(n) for metric computation. The autocorrelation values S(n) of the channel response are first calculated in step  602 , and each S(n) is normalized by S(0) to obtain the normalized value NS(n) in step  604 . Each of the normalized values NS(n) is then compared to a threshold (NS(n)&gt;threshold?) in step  606 , and if NS(n) is greater than the threshold, the corresponding S(n) will be kept for path metric computation (step  608 ), otherwise, the corresponding S(n) will be discarded (step  610 ). 
     FIG. 7  is a block diagram showing an embodiment of the path metric computation apparatus according to the present invention. The autocorrelation calculator  72  performs step  602  of  FIG. 6 , and passes the calculated autocorrelation values S(n) to the normalizer  74 . The normalzer  74  divides each S(n) by S(0) to obtain the normalized values NS(n). The comparator  76  receives the normalized values NS(n) and determines whether each of the NS(n) is greater than a preset threshold. The comparator  76  passes the corresponding S(n) to the path metric computation unit  78  only if the NS(n) is greater than the threshold, therefore, the path metric computation unit  78  estimates the maximum likelihood sequence without considering the effect of the insignificant S(n). 
   Finally, while the invention has been described by way of example and in terms of the above, it is to be understood that the invention is not limited to the disclosed embodiment. On the contrary, it is intended to cover various modifications and similar arrangements as would be apparent to those skilled in the art. Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.