Abstract:
A spread spectrum receiver ( 124 ) for receiving and decoding a data frame having one of a plurality of coding rates is coupled to a rate determination device ( 132 ). The rate determination device ( 132 ) is coupled to receive a data frame coded at one of the plurality of coding rates and to receive symbol data from the receiver ( 124 ). The rate determination device ( 132 ) is adapted to determine a probability based at least upon an rate-based symbol repetition constraints within the data frame, wherein the probability is an indication of the rate at which the data frame is encoded.

Description:
TECHNICAL FIELD  
         [0001]    This patent relates to receivers for use in a spread spectrum communication system.  
         BACKGROUND  
         [0002]    In a spread spectrum communication system, downlink transmissions from a base station to a mobile station include a pilot channel and a plurality of traffic channels. The pilot channel is demodulated by all users. Each traffic channel is intended for demodulation by a single user, though more than one channel may be intended for a given user. Therefore, each traffic channel is spread using a unique code known by both the base station and the mobile station. The pilot channel is spread using a code known by the base station and all mobile stations. Multiplication of the pilot channel and traffic channel symbols by unique code sequences comprised of chips having duration much less than the symbol duration spreads the spectrum of transmissions in the system.  
           [0003]    One example of a spread spectrum communication system is a cellular radiotelephone system according to Telecommunications Industry Association/Electronic Industry Association (TIA/EIA) Interim Standard IS-95, “Mobile Station-Base Station Compatibility Standard for Dual-Mode Wideband Spread Spectrum Cellular System” (IS-95). Individual users in the system use the same frequency spectrum but are distinguishable from each other through the use of individual spreading codes. IS-95 is an example of a direct sequence code division multiple access (DS-CDMA) communication system. In a DS-CDMA system, transmissions are spread by a pseudorandom noise (PN) code. Data is spread by a sequence of chips, where the chip is the spread spectrum minimal-duration keying element.  
           [0004]    Other spread spectrum systems include radiotelephone and data systems operating at various frequencies and utilizing various spreading techniques. Among these additional systems are third-generation spread spectrum communication systems (3G), wideband code division multiple access systems (W-CDMA) and CDMA2000.  
           [0005]    As allowed in IS-95 and the other direct sequence spread spectrum communication protocols, the forward link frames can be at one of four possible rates: full-rate, half-rate, quarter-rate and eighth-rate. In existing receivers, a rate determination algorithm is used to determine that rate at which the forward link frames are encoded. As is generally practiced, the received frames are decoded at each of the four possible rates using a Viterbi decoder. Typically, the inputs to the rate determination algorithm include the cyclical redundancy check (CRC) data appended to the full and half-rate frames, estimates of the channel symbol error rates based on re-encoding the Viterbi decoder output, quality bits associated with the distance between merging paths in the decoder trellis, and the total Euclidean distance between the output of the receiver and the decoded codeword.  
           [0006]    This process is inefficient. It suffers from added current drain associated with the multiple decodings and may require a faster clock and additional circuitry. The frame needs only to be decoded once to obtain the coded data, but at the correct rate. Decoding at the wrong rate results in unusable data. Various approaches have been suggested to predict the frame rate prior to decoding, but in most instances these approaches are computationally complex and are not sufficiently reliable.  
           [0007]    Thus, there is a need for a spread spectrum receiver that provides-pre-decoding rate determination. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0008]    This disclosure will describe several embodiments to illustrate its broad teachings. Reference is also made to the attached drawings.  
         [0009]    [0009]FIG. 1 is a block diagram of a communication system.  
         [0010]    [0010]FIG. 2 is a block diagram of a spread spectrum receiver incorporating rate determination.  
         [0011]    [0011]FIG. 3 is a flow diagram illustrating a method of rate determination in a spread spectrum receiver. 
     
    
     DETAILED DESCRIPTION  
       [0012]    A spread spectrum receiver incorporates rate determination. In an embodiment of the receiver, a maximum-likelihood decision rule is applied for pre-decoding rate determination. While the following discussion refers to the IS-95 interim standard, the disclosure has application to virtually any spread spectrum communication system.  
         [0013]    Referring to FIG. 1, a communication system  100  includes a plurality of base stations including base station  102  and base station  104 . Each base station is separately coupled to a mobile switching center  106 , which controls communication within the system and between the system and the public switch telephone network  108 . The communication system  100  may be a cellular telephone system operating according to IS-95, CDMA2000, 3G, W-CDMA or other direct sequence spread spectrum communication standards, another type of cellular or mobile communication system, a fixed wireless loop system or other type of radio system.  
         [0014]    Each base station is configured for radio frequency (RF) communication with fixed or mobile transceivers such as mobile station  110 . Accordingly, each base station includes a receiver such as receiver  112  of the base station  102  and receiver  114  of the base station  104  and a transmitter such as transmitter  116  of the base station  102  and the transmitter  118  of the base station  104 . Each transmitter transmits a spread spectrum signal including a first signal and a second signal, the first signal being substantially orthogonal to the second signal. The first signal may be, for example, the pilot channel in the IS-95 implementation and the second signal may be one or more traffic channels. In IS-95, the pilot channel and the traffic channels are covered using a Walsh or Hadamard code, so that at transmission, the channels are all substantially orthogonal.  
         [0015]    The mobile station  110  includes a RF front end  120 , a receiver  124 , a transmitter  126 , a control section  128  and a user interface  130 . The RF front end  120  filters the spread spectrum signals and provides conversion to baseband signals. The RF front end  120  further provides analog to digital conversion, converting the baseband signals to streams of digital data for further processing. The receiver  124  demodulates the digital data and provides the demodulated data to the control section  128 .  
         [0016]    The control section  128  controls overall operation of the mobile station  110 , including assignment of the RAKE fingers. The control section also controls interaction of the radio components and the user interface  130 . The user interface  130  typically includes a display, a keypad, a speaker and a microphone. The transmitter  126  modulates data for transmission to a remote receiver, such as one of the base stations. The modulated data are processed by the front end  120  and transmitted at radio frequency.  
         [0017]    Positioned between the receiver  124  and the RF front end  120  is a rate determination device  132 . The rate determination device  132  may operate under the control of control  128  or may contain its own processor or other suitable processing and control capability (not depicted) to function as described herein and determines the rate of the incoming frames and communicates this information to the receiver  124 . The receiver  124  uses the rate information to decode the received frames according to the rate information in an efficient manner. That is, the rate determination device  132  receives data from the receiver  124  that is then used to predict, a priori, the rate of the next frame to be decoded. The determined rate information is then communicated by the rate determination device  132  back to the receiver  124  thus allowing the receiver  124  to decode the frame one time at the correct rate.  
         [0018]    The rate determination device  132  may use a single rate determination algorithm or multiple rate determination algorithms tailored to the various conditions in which the mobile station  110  is operating. For example, a rate determination algorithm may have parameters that are a function of the signal-to-noise ratio (SNR), the fading rate of the channel, or other channel characteristics or the algorithm may be specifically tailored for a particular coding scheme, such as Rate Set 1 or Rate Set 2. The rate determination device  132  may be informed of the channel conditions by the receiver  124  or by the control  128  in order to select an appropriate rate determination algorithm. Alternatively the rate determination device  132  may self-determine the channel characteristics.  
         [0019]    [0019]FIG. 2 illustrates a RAKE receiver  200  that may be incorporated into the receiver  124 . The RAKE receiver  200  includes a plurality of fingers, generally illustrated as finger  202 . Each finger  202  contains a despreader  204  for despreading the baseband signals received from the RF front end  120 . The output signals of each finger are then multiplied by the conjugate of the estimate of the complex channel gain for the given finger and combined in a combiner  208  to provide the data signal estimate, s(t). The rate information is provided by the rate determination device  132  to the decoder  206 .  
         [0020]    The rate determination device  132  may use any rate determination algorithm suitable for the communication protocol being used within the communication system  100  and for the existing channel conditions. As an example, described herein are rate determination algorithms suitable for use with a spread spectrum code division multiple access communication system. While the above-described process of decoding each frame at each of the four possible rates may be used as one of the possible rate determination algorithms, it is preferable that the rate determination algorithm provides an indication of frame rate prior to decoding to improve computational efficiency as well as reduce decoding delay. In that regard, additional algorithms are described herein in connection with the IS-95 interim standard.  
         [0021]    Two rate sets are defined for IS-95. In the first, referred to as Rate Set 1, a full-rate frame contains 192 information symbols that are encoded into 384 code symbols by a rate {fraction (1/2)} convolutional encoder. Half-rate, quarter-rate and eighth-rate frames contain 96, 48 and 24 information symbols and 192, 96, and 48 code symbols, respectively. Symbol repetition is used to fill up the frame, so that half-rate code symbols are repeated twice, and quarter-rate and eighth-rate code symbols are repeated four and eight times, respectively. Interleaving is used to mitigate the degradation of the communication link caused by fading.  
         [0022]    In Rate Set 2, a full-rate frame contains 288 information symbols, while half-rate, quarter-rate and eighth-rate frames contain 144, 72, and 36 information symbols, respectively. Rate Set 2 frames are encoded with the same rate {fraction (1/2)} convolutional code used for Rate Set 1. Symbols of the half-rate, quarter-rate, and eighth-rate frames are repeated 2, 4 and 8 times, respectively, resulting in a total of 576 code symbols per frame, regardless of rate. After repetition, two of every six code symbols are punctured to reduce the number of symbols per frame to 384.  
         [0023]    To simplify the discussion of the immediately following rate determination algorithm, only Rate Set 1 frames are considered. However, one of ordinary skill in the art will appreciate the modifications required to adapt the algorithm to Rate Set 2. Because of the repetition scheme used for Rate Set 1, it is possible to consider blocks of eight binary symbols. If the frame is full rate, no constraints are imposed on the sequence of symbols {b 1 , b 2 , . . . , b 8 }. However, for half-rate frames, a sequence is allowed if and only if b 1 =b 2 , b 2 =b 4 , b 5 =b 6  and b 7 =b 8 . Quarter-rate frames require both that b 1 =b 2 =b 3 =b 4  and b 5 =b 6 =b 7 =b 8 . Eighth rate frames admit only the two binary sequences for which b 1 =b 2 = . . . =b 8 . Let the sequence {y 1 , y 2 , . . . , y 8 } denote the corresponding output of the combiner of the RAKE receiver, e.g., combiner  208 .  
         [0024]    From the above description of the combiner output, even in the presence of fading, the ratio of the mean to the variance is the same for all symbols within a given frame, providing that forward link power control is slow so that the traffic-to-pilot power ratio is constant over the frame. If fast power control is used so that the traffic power changes every power control group, the weighting scheme must be modified so that the ratio of the symbol mean and variance is held constant over the frame.  
         [0025]    If no a priori distribution is assigned to the possible frame rates, then the maximum a posteriori decision (MAP) rule is equivalent to the maximum-likelihood (ML) decision rule which selects the rate r i , i≡{1, 2, 3, 4}, for which:  
         log( p ({ y   1   }|r   i )/ p ({ y   1   }|r   1 ))  
         [0026]    is maximized. From this equation it is apparent that only three log-likelihood ratios need to be calculated, since the log-likelihood ratio for full rate will always be 0. The four log-likelihood ratios are:  
               log          p        (       {     y   i     }     |     r   1       )         p        (       {     y   i     }     |     r   1       )           =   0                 log          p        (       {     y   i     }     |     r   2       )         p        (       {     y   i     }     |     r   1       )           ≈       4                 log                 2     -     2      y                   Δ   1                       log          p        (       {     y   i     }     |     r   3       )         p        (       {     y   i     }     |     r   1       )           ≈       6                 log                 2     -     2      y                   (       Δ   1     +     Δ   2       )                       log          p        (       {     y   i     }     |     r   4       )         p        (       {     y   i     }     |     r   1       )           ≈       7                 log                 2     -     2      y                   (       Δ   1     +     Δ   2     +     Δ   3       )                                     
 
         [0027]    The terms Δ 1 , Δ 2  and Δ 3  are:  
               Δ   1     =       ∑     i   =   1     4                     δ        (       y       2      i     -   1       ·     y     2      i         )                       Δ   2     =       ∑     i   =   0     1                     δ        (       s       4      i     +     1.4      i     +   2       ·     s       4      i     +     3.4      i     +   4         )                       Δ   3     =     δ        (       s     1   ,   4       ·     s   5.8       )                                   
 Δ 3 =δ(s 1.4  ·s 5.8 )  
         [0028]    where the partial-sum s j,k  is given by  
         s     j   .   k       =       ∑     i   =   j     k                       y   i     .                             
 
         [0029]    The parameter γ is the ratio of the mean and variance of y i , the output of the combiner for each symbol. This mean, however, is not known a priori. By modifying the receiver hardware, an estimation of γ can be made according to the equation:  
         γ   ^     =           ∑     i   =   1     384                          y   i                (       A   p   2            ∑     i   =   1     384                       ∑     j   =   1     3                              α   ^       i   ·   j            2           )          σ   2         ≈         A   t          μ        (     r   i     )             A   p          σ   2                                 
 
         [0030]    where A p   2  is the pilot amplitude and a i,j  is the complex channel gain of the different multipath rays. In the middle expression, the first term in the denominator is the sum of the squares of the channel estimates for the entire frame, and the second term σ 2  is known since it is determined by the receiver automatic gain control (AGC) circuit. Thus, while relatively computationally complex, it is possible to make an estimate of the parameter γ.  
         [0031]    All of the data dependence in the log-likelihood ratios is captured in the terms Δ1, Δ2 and Δ3. Examination of these terms yields the following observations:  
         [0032]    i) if two adjacent symbols (or partial sums) have the same sign, the corresponding contribution to the log-likelihood ratio is 0;  
         [0033]    ii) the contribution of adjacent symbols (partial sums, s i,j ) different in sign to the log-likelihood ratio is equal to the minimum amplitude of the two symbols (partial sums);  
         [0034]    iii) symbols (partial sums) differing in sign are attributed significance equal to γ, the ratio of the symbol mean and variance for the given frame.  
         [0035]    The first observation is consistent with intuition since it is only when adjacent symbols have different signs that they are not repetitions of the same symbol. Symbols that agree yield essentially no information because even if the rate is such that the second symbol is not required to be a repetition of the first, it is still allowed to be the same binary value as the first. The second observation also agrees with intuition since the confidence that two symbols agree or differ in sign should correspond (approximately) to the smaller of the two symbol amplitudes (e.g., given two symbols with amplitudes 0.25 and 100, the confidence that the two symbols have the same or different sign should be approximately equal to the smaller of the two amplitudes; i.e., 0.25.  
         [0036]    In implementation, the rate determination device  132  implements the above-described log-likelihood ratios. The rate decision is based on which of the log-likelihood ratios is largest.  
         [0037]    An alternative, simplified rule can be constructed for selecting between the four rates based on the above observations. Essentially, the measure of interest is the sum reliability of those pairs of symbols (or partials sums  
           s     j   .   k       =       ∑     i   =   j     k                     y   i         )                         
 
         [0038]    having opposite sign relative to the sum reliability of all pairs of symbols (or partial sums) in the frame. Thus, the sum reliability of all pairs of symbols (partial sums) is used to normalize the reliability pairs of the symbols (partial sums) having opposite sign. With this motivation, the following three measures may be defined:  
               Ψ   2     =         ∑     i   =   0     191                     δ        (       y       2      i     +   1       ,     y       2      i     +   2         )             ∑     i   =   0     191                     min        {            y       2      i     +   1            ,          y       2      i     +   2              }                         Ψ   3     =         ∑     i   =   0     95                     δ        (       s       4      i     +     1.4      i     +   2       ,     s       4      i     +     3.4      i     +   4         )             ∑     i   =   0     95                     min        {            s       4      i     +     1.4      i     +   2            ,          s       4      i     +     3.4      i     +   4              }                         Ψ   4     =         ∑     i   =   0     47                     δ        (       s       8      i     +     1.8      i     +   4       ,     s       8      i     +     5.8      i     +   8         )             ∑     i   =   0     47                     min        {            s       8      i     +     1.8      i     +   4            ,          s       8      i     +     5.8      i     +   8              }                                       
 
         [0039]    In the above, all three summations have been extended over the entire frame.  
         [0040]    All three measures defined above lie in the interval [0,1]. The measure ψ 2  weighs the reliability of pairs of symbols having opposite sign against the sum reliability of all pairs of symbols in the frame. Only pairs of symbols having opposite sign contribute to the numerator of ψ 2 , while all pairs of symbols contribute to the denominator. Similarly, ψ 3  and ψ 4  measure the reliability of pairs of partial sums having opposite sign relative to the reliability of all pairs of partial sums in the frame. These expressions are relatively computationally equivalent.  
         [0041]    The measures have the following properties:  
         [0042]    i) for any value of the signal-to-noise ratio E b /N 0 ,  
         [0043]    E(Ψ 2 |r 1 )=0.5  
         [0044]    E(Ψ 3 |r 1 )=E(Ψ 3 |r 2 )=0.5  
         [0045]    E(Ψ 4 |r 1 )=E(Ψ 4 |r 2 )=E(Ψ 4 |r 3 )=0.5  
         [0046]    ii) in the limit as Eb/No →∞,  
         [0047]    E(Ψ 2 |r 2 )=E(Ψ 2 |r 3 )=E(Ψ 2 |r 4 )=0  
         [0048]    E(Ψ 3 |r 3 )=E(Ψ 3 |r 4 )=0  
         [0049]    E(Ψ 4 |r 4 )=0.  
         [0050]    The Rate Set 1 decision rule is thus:  
         [0051]    Given a threshold η 1 ,  
         [0052]    i) if Ψ 4 ≦η 1 , rate=r 4 ;  
         [0053]    ii) if Ψ 3 ≦η 1  and Ψ 4 &gt;η 1 , rate=r 3 ;  
         [0054]    iii) if Ψ 2 ≦η 1  and Ψ 3 &gt;η 1  and Ψ 4 &gt;η 1 , rate=r 2 ;  
         [0055]    iv) if Ψ 2 &gt;η 1  and Ψ 3 &gt;η 1  and Ψ 4 &gt;η 1 , rate=r 1    
         [0056]    This decision rule exhibits an error floor that is a function of the threshold. The error floor may be made arbitrarily small by reducing the threshold η 1  (the limit on the error floor is  2   −48 , which is the probability that all 48 symbol pairs of a quarter-rate frame are equal). However, as the threshold is decreased, rate detection performance may be degraded at low values of E b /N 0 . Thus, reducing the threshold η 1  reduces the error floor and improves asymptotic performance while degrading rate detection performance at low signal-to-noise ratios. Ideally, if an estimate of the channel quality could be obtained, the threshold η 1  would be based on this quality estimate. This decision rule also suggests better performance on a fading channel than on a static channel.  
         [0057]    For Rate Set 2, a separate set of metrics is required. These metrics are:  
               Ω   2     =         ∑     i   =   0     95                     δ        (       y       4      i     +   1       ,     y       4      i     +   2         )             ∑     i   =   0     95                     min        {            y       4      i     +   1            ,          y       4      i     +   2              }                         Ω   3     =         ∑     i   =   0     47                     [       δ        (       s       8      i     +     1.8      i     +   2       ,     y       8      i     +   3         )       +     δ        (       y       8      i     +   4       ,     s       8      i     +     5.8      i     +   6         )       +     δ        (       y       8      i     +   7       ,     y       8      i     +   8         )         ]           ∑     i   =   0     47                     [       min        (            s       8      i     +     1.8      i     +   2            ,          y       8      i     +   3              )       +     min        (            y       8      i     +   4            ,          s       8      i     +     5.8      i     +   6              )       +     min        (            y       8      i     +   7            ,          s       8      i     +   8              )         ]                       Ω   4     =         ∑     i   =   0     23                     [       δ        (       s       16      i     +     1.16      i     +   3       ,     s       16      i     +     4.16      i     +   6         )       +     δ        (       s       16      i     +     7.16      i     +   8       ,     s       16      i     +     9.16      i     +   11         )       +     δ        (       s       16      i     +     12.16      i     +   14       ,     s       16      i     +     15.16      i     +   16         )         ]           ∑     i   =   0     23                     [       min        (            s       16      i     +     1.16      i     +   3            ,          s       16      i     +     4.16      i     +   6              )       +     min        (            s       16      i     +     7.16      i     +   8            ,          s       16      i     +     9.16      i     +   11              )       +     min        (            s       16      i     +     12.16      i     +   14            ,          s       16      i     +     15.16      i     +   16              )         ]                                     
 
         [0058]    The difference between these definitions and those given above for Rate Set 1 are due to the difference in the symbol repetition patterns used for the two rate sets. The properties ascribed above to the measures {ψ 2 , ψ 3  and ψ 4 } apply also to the measures {Ω 2 , Ω 3 , Ω 4 }. The Rate Set 2 decision rule is given by the following:  
         [0059]    Given a threshold η 2 ,  
         [0060]    i) if Ω 4 ≦η 2 , rate=r 4 ;  
         [0061]    ii) if Ω 3 ≦η 2  and Ω 4 &gt;η 2 , rate=r 3 ;  
         [0062]    iii) if Ω 2 ≦η 2  and Ω 3 &gt;η 2  and Ω 4 &gt;η 2 , rate=r 2 ;  
         [0063]    iv) if Ω 2 &gt;η 2  and Ω 3 &gt;η 2  and Ω 4 &gt;η 2 , rate=r 1    
         [0064]    This rate detection rule has little impact on the decoded frame error rate if the target frame error probability is 10 −2  or higher. Advantageously, (with respect to rate determination only) because of the relatively weaker coding scheme of Rate Set 2, a greater value of E b /N 0  is required to achieve the required 10 −2  frame error rate performance. Furthermore, because of the higher coding rate, a given value of the bit signal-to-noise ration E b /N o  corresponds to a larger value of the symbol signal-to-noie ratio E s /N o  for Rate Set 2 than for Rate Set 1. Since it is E s /N o , rather than E b /N o , which most directly affects rate detection performance, overall rate detection performance is slightly better for Rate Set 2 than for Rate Set 1.  
         [0065]    An additional decision rule that can be used for Rate Set 1, and can be extended to Rate Set 2 as well as to other rate set definitions with multiple frame rates implemented using repetition and puncturing, is given by the following:  
         [0066]    Rate=r i , where  
         [0067]    i=arg max {Λ i   3 , iε{1, 2, 3, 4}},  
         [0068]    with  
           Λ   1   3     =       a   1          (       (       ∑     i   =   1     8                     y   i   2       )     -     8                   δ   2         )         ,                         
 
         [0069]    Λ 2   3 =a 2 (s 1,2   2 +s 3,4   2 +s 5,6   2 +s 7,8   2 )− 8 δ 2 ),  
         [0070]    Λ 3   3 =a 3 ((s 1,4   2 +s 5,8   2 )− 8 δ 2 ),  
         [0071]    Λ 4   3 =a 4 (s 1,8   2 − 8 δ 2 ),  
         [0072]    and δis the interference variance at the output of the RAKE combiner, which can be estimated as  
             δ   ^     2     =       (       ∑     i   =   0     383                            y   i          2       )     -       (       ∑     i   =   0     383                          y   i            )     2         ,                         
 
         [0073]    or over a smaller subset of the channel symbols.  
         [0074]    A maximin criteria can be used to select {a i }. However, simulations have shown that the following values for {a i } yield better results,  
           a   1     =   1     ,       a   2     =     1     2         ,       a   3     =     1   2       ,       a   4     =       1     2        2         .                             
 
         [0075]    so that this additional Rate Set 1 decision rule is given by  
         [0076]    Rate=r i , where  
         [0077]    i=arg max {Λ i   3 , iε{l, 2, 3, 4}},  
         [0078]    with  
                 Λ   1   3     =     (       (       ∑     i   =   1     8                     y   i   2       )     -     8                   δ   2         )       ,                   Λ   2   3     =       1     2            (       (       s     1   ,   2     2     +     s     3   ,   4     2     +     s     5   ,   6     2     +     s     7   ,   8     2       )     -     8                   δ   2         )         ,                   Λ   3   3     =       1   2          (       (       s     1   ,   4     2     +     s     5   ,   8     2       )     -     8                   δ   2         )         ,                   Λ   4   3     =       1     2        2              (       s     1   ,   8     2     -     8                   δ   2         )         ,                               
 
         [0079]    This patent describes several specific embodiments including hardware and software embodiments of apparatus and methods for pre-decoding rate determination. However, one of ordinary skill in the art will appreciate that various modifications and changes can be made to these embodiments. Accordingly, the specification and drawings are to be regarded in an illustrative rather than restrictive sense, and all such modifications are intended to be included within the scope of the present patent.