Patent Publication Number: US-6339624-B1

Title: Trellis decoding with multiple symbol noncoherent detection and diversity combining

Description:
STATEMENT OF RELATED APPLICATIONS 
     This application claims priority from U.S. provisional application No. 60/056,159 filed on Aug. 19, 1997 and having the same title. The contents of this provisional application are corporated herein by reference. 
     The present application is related to the subject matter of U.S. patent application Ser. No. 08/985,302 entitled TRELLIS CODING WITH MULTIPLE SYMBOL NONCOHERENET DETECTION AND INTERLEAVING TO COMBAT FREQUENCY OFFSET, the contents of which are herein incorporated by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     The present invention relates generally to digital communication systems and more particularly to a technique for providing enhanced performance. 
     The discussion that follows assumes an understanding of digital communication principles as known to those of skill in that art. A good general reference in the digital communication field is John G. Proakis, Digital Communications, (McGraw-Hill 1995), herein incorporated by reference. 
     Conventional Viterbi Algorithm 
     The Viterbi algorithm accepts as input a sequence of received symbols and determines the maximum likelihood sequence of transmitted symbols. The Viterbi algorithm is applied to decode convolutional coding or trellis coding applied at the transmitter end or to remove the effects of a partial response channel. The algorithm is perhaps best understood by reference to a so-called trellis diagram. A trellis diagram is a time-indexed state diagram. At each trellis stage, n, there are two or more states. Transitions between states at a trellis stage, n, and states at a trellis stage n+1 denote transmitted symbols. A path through the trellis consists of a number of successive transitions and denotes a sequence of symbols. The number of states at each stage and the correspondence between transitions and symbols are particular to the relevant trellis code, convolutional code, or partial response channel characteristics. The Viterbi algorithm uses received symbol information to identify a particular path through the trellis and thus determine the maximum likelihood sequence of transmitted symbols. 
     Computation of the maximum likelihood sequence proceeds on a stage-by-stage basis. Possible paths are eliminated once it becomes clear they cannot be the maximum likelihood path. Given received symbol information, the likelihood of a particular branch being taken is evaluated according to a measure known as the branch metric. For each state, the Viterbi algorithm computes the branch metrics for the surviving paths leading to that state. The branch metric will typically consist of the previously accumulated branch metric for the path plus the branch metric for the transition taken to the new state. Based on the accumulated branch metrics for all the paths leading to the state, the Viterbi algorithm selects a best path to the state and eliminates the other states. Only one path survives to each stage, permitting identification of the maximum likelihood transmitted symbol sequence. 
     FIG. 2 depicts the prior art operation of a Viterbi decoding algorithm assuming channel phase is known. Consider an AWGN channel model, 
     
       
         r n =e iΘ As n +W n , n= . . . 0,1,2, . . . ,  (1) 
       
     
     where Θ is channel phase; below we consider two cases where channel phase is known and where it is completely unknown. The transmitted symbol s n  is an MPSK symbol, where s k =e jφk , and φ k  is a uniformly distributed random phase taking values in {0,2π/M, . . . 2π(M−1)/M}. The received sample is r n , and w n  is an independent sample of zero mean white complex Gaussian noise of variance σ 2 . 
     The mathematics of a conventional Viterbi decoding algorithm for a convolutional code, assuming channel phase Θ is known will now be described. To simplify the description, assume the convolutional code has two branches into and out of each state. FIG. 2 depicts a state diagram wherein two states, u and v, at stage n−1, which both have a single branch into state w at stage n. Associated with state u is the previously determined winning path into state u, denoted by s u,0 ,s u,1 , . . . s u,n−1 , and a path metric m u . Associated with state v is the previously determined winning path into state v, denoted by s v,0 ,s v,1 , . . . s v,n−1 , and a path metric m z . Let s u,n  be the symbol on the branch from state u to state w, and let s v,n  be the symbol on the branch from state v to state w. Let s 0 ,s 1 , . . . s n− s n  be the first n actual transmitted symbols, and let r 0 ,r 1 , . . . r n−1 ,r n  be the corresponding received samples. The following discussion explains how to update state w at stage n, by finding the winning branch into state w, the winning path into state w, and the winning path metric for state w. The conventional Viterbi algorithm proceeds in four steps: 
     (1) Form two branch metrics 
     
       
         Re[r n s u,n *(s jΘ )*],  (2) 
       
     
     and 
     
       
         Re[r n s v,n *(s jΘ )*].  (3) 
       
     
     (2) Use branch metric (2) to form a candidate path metric for the top path, 
     
       
         m u=Re[r   n s u,n *(e jΘ )*],  (4) 
       
     
     and use branch metric (3) to form a candidate path metric for the bottom path, 
     
       
         m v +Re[r n s v,n *(e jΘ )*].  (5) 
       
     
     (3) Compare (4) and (5) and select a winner, say (4). 
     (4) Update state w at stage n. The winning path into state w at stage n is s w,0 ,s w,1 , . . . s w,n− , s w,n where 
     
       
         (s w,0 ,s w,1 , . . .s w,n−1 , s w,n )=(s u,0 ,s u,1 , . . . s u,n−1 , s u,n ). 
       
     
     The winning path metric is 
     
       
         m w =m u +Re[r n s u,n *(e jΘ )*]. 
       
     
     Non-coherent Viterbi Decoding Algorithm Operation 
     FIG. 3 depicts the prior art operation of a Viterbi decoding algorithm using multiple symbol noncoherent detection. Non-coherent Viterbi decoding is described in [9] A. N. D&#39;Andrea, U. Mengali, and G. M. Vitetta, “Approximate ML decoding of coded PSK with no explicit carrier phase reference,”  IEEE Transactions on Communications , Vol. 42, no. 2/3/4, February/March/April 1994, pp. 1033-1039, incorporated herein by reference. This approach can be used without an explicit phase reference, and so assume that Θ in (1) is uniformly distributed on (−π,π) FIG. 3 is the same as FIG. 2 except that each state has a path history variable associated with it; thus states u and v at stage n−1 have the path history variables W u,n−1  and W v,n−1 , associated with them, respectively, where W u,n−1  and W v,n−1  are defmed by          W     u   ,     n   -   1         =       ∑     k   =   0       n   -   1              α     n   -   1   -   k            r   k          s     u   ,   k     *               and             W     v   ,     n   -   1         =       ∑     k   =   0       n   -   1              α     n   -   1   -   k            r   k          s     v   ,   k     *           ,                   
     and α is a real number in the range 0≦α≦1. For a particular state x, x ε{u, v}, the path history variable is a function of the winning path into state x, s x,0 , s x,1 , . . .s x,n−1 , and the channel sample history r 0 , r 1 , . . . r n−1 , r n ; the path history variable for a particular path acts as a remodulated phase reference for that path and takes the place of the coherent phase reference term (e JΘ )*in steps (1)-(4) above. 
     The discussion will now turn to how to find the winning branch into state w at stage n, the winning path into state w, the winning path metric for state w, and the path history variable for state w at stage n, W w,n . The modified Viterbi algorithm proceeds in four steps: 
     (1a) Form two branch metrics 
     
       
         Re[r n s u,n *W* u,n−1 ],  (6) 
       
     
     and 
     
       
         Re[r n s v,n *W v,n−1 *]  (7) 
       
     
     (2a) Use branch metric (6) to form a candidate path metric for the top path, 
     
       
         m u +Re[r n s u,n *W u,n−1 *],  (8) 
       
     
     and use branch metric (7) to form a candidate path metric for the bottom path, 
     
       
         m v +Re[r n s v,n *W vn−1 *].  (9) 
       
     
     (3a) Compare (8) and (9) and select a winner, say (8). 
     (4a) Update state w at stage n. The winning path into state w at stage n is s w,0 ,s w,1 , . . . s w,n−1 ,s w,n  where 
     
       
         (s w,0 ,s w,1 , . . . s w,n−1 , s w,n )=(s u,0 ,s u,1 , . . .s u,n−1 , s u,n ). 
       
     
     The winning path metric is 
     
       
         m w =m u +Re[r n s u,n *W u,n− *]. 
       
     
     The winning path history variable is 
     Note that steps (1a)-(4a) are very similar to steps (1)-(4), with the path history variable taking the place of the coherent phase reference term (e jΘ )*. 
     Steps (1a)-(4a), illustrate one particular way of implementing trellis decoding with multiple symbol noncoherent detection. There are several other ways of implementing trellis decoding with multiple symbol noncoherent detection described in the literature which differ in how the branch metrics in (1a) are formed. However all approaches are fundamentally the same in that each branch metric in (1a) is formed using received samples and previous symbols along the winning path into that branch. 
     Diversity Receivers 
     One technique for improving performance in digital communications is to take advantage of information transmitted between a data source and a receiver via two or more different channels. This is known in the art as diversity reception. For example, a receiver site may have two different antennas. The two antennas may receive a signal generated by the same transmitter, albeit by somewhat different paths, or signals received from two different transmitters. The transmitters may have different locations, different frequencies, or both. By integrating the information received via two or more signals received via two or more different channels, one may obtain better performance than would be available with anyone signal independently. 
     Various receiver architectures have been developed for taking advantage of such multiple signals. For example, it is know to essentially employ a distinct receiver for each received signal. Each receiver has its own data output. The transmitted data is estimated by weighting each receiver output and either 1) adding the outputs together, 2) switching among the outputs, or 3) having the various receivers vote as to the transmitted data. The performance improvement achieved by this technique is relatively low. Also, tracking loops are required to set the weights for each received signals and these loops do not operate properly in low noise conditions. What is needed is an improved technique for taking advantage of signals received via diverse channels. 
     SUMMARY OF INVENTION 
     The present invention provides a method and apparatus for taking advantage of diverse signals. According to the present invention, trellis decoding takes advantage of multiple symbol noncoherent detection and diversity combining. Accordingly, combination of diverse signals effectively occurs pre-detection. Tracking loops are not necessary to set weights for each channel. In a QPSK embodiment employing a rate ½ convolutional code, an improvement in effective SNR of 1-3 dB may be achieved as compared with non-diverse reception. 
     In accordance with a first aspect of the present invention, a method for receiving a signal via diverse channels includes steps of: receiving a first signal via a first channel, receiving a second signal via a second channel, converting the first signal to a first stream of received symbols estimating a transmitted coded symbol stream, converting the second signal to a second stream of symbols estimating the transmitted coded symbol stream, and applying a Viterbi decoding procedure to the first stream of symbols and the second stream of symbols wherein branch metrics for the Viterbi decoding procedure are evaluated based on both the first stream of received symbols and the second stream of received symbols. 
     In accordance with a second aspect of the present invention, a receiver includes a non-coherent Viterbi decoder that accepts as input a first stream of received symbols and a second stream of received symbols, the first stream and the second stream estimating a transmitted symbol stream. The Viterbi decoder includes a branch metric evaluator that evaluates branch metrics responsive to both the first stream of received symbols and the second stream of received symbols, and a path history variable evaluator that evaluates path history variables responsive to both the first stream of received symbols and the second stream of received symbols. 
     In accordance with a third aspect of the present invention, an enhanced Viterbi decoder processes received symbol sequences by selecting a maximum likelihood path through states of a trellis. The path includes successive transitions between states. The enhanced Viterbi decoder include: an input port that receives a first stream of received symbols received via a first channel and a second stream of received symbols received via a second channel. The first stream and the second stream estimate a transmitted symbol stream. The enhanced Viterbi decoder further include: a branch metric evaluator that determines a likelihood measure for a particular transition between states. The likelihood measure is responsive to both the first stream and the second stream. The enhanced Viterbi decoder still further includes a path evaluator that selects and eliminates non-maximum likelihood paths based on a cumulative likelihood measure evaluated based on likelihood measures for successive transitions as evaluated by the branch metric evaluator. 
     A further understanding of the nature and advantages of the inventions herein may be realized by reference to the remaining portions of the specification and the attached drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1A depicts a diversity receiver architecture according to one embodiment of the present invention. 
     FIG. 1B is a functional representation of the operation of a non-coherent Viterbi decoder in accordance with one embodiment of the present invention. 
     FIG. 2 depicts the prior art operation of a Viterbi decoding algorithm assuming channel phase is known. 
     FIG. 3 depicts the prior art operation of a Viterbi decoding algorithm using multiple symbol noncoherent detection. 
     FIG. 4 depicts modified Viterbi decoder operation to take advantage of diverse signals in accordance with one embodiment of the present invention. 
    
    
     DESCRIPTION OF SPECIFIC EMBODIMENTS 
     FIG. 1A depicts a simplified representation of a diversity receiver architecture  100  according to one embodiment of the present invention. Diverse signals may be received by one of N antennas  102 . After appropriate downconversion, each signal is subject to equalization by one of N optional adaptive equalizers  104 . The output of each equalizer  104  is a stream of received symbol estimates. Each equalizer output is an input to a special non-coherent Viterbi decoder  106  in accordance with one embodiment of the present invention. The output of non-coherent Viterbi decoder  106  is an estimate of the transmitted symbol stream. 
     The present invention may take advantage of, e.g., frequency diversity in the form of multiple link frequencies, or spatial diversity, multiple antennas receiving signals from either a common transmitter or multiple transmitters. Thus, there may be various sources for the multiple symbol streams input to non-coherent Viterbi decoder  106 . 
     FIG. 1B is a functional representation of the operation of non-coherent Viterbi decoder  106 . The received symbol streams are accepted by an input port  108  and forwarded to a trellis memory  110 . Trellis memory  110  holds the received symbol information. During Viterbi processing, a path evaluator  114  identifies at each stage, a surviving path to each state. Information about the surviving paths is stored in trellis memory  110 . The evaluation and selection of surviving paths takes advantage of branch metrics evaluated for transitions between states at successive stages. These evaluations performed by a branch metric evaluator  112 . In a preferred embodiment, a phase reference for surviving paths is developed and maintained by a path history evaluator  116 . When only a single path survives to a given stage, it can be identified as a maximum likelihood path. A surviving path interpreter  118  then interprets this path to estimate the transmitted symbols, inherently removing the effect of any trellis code, convolutional code, or partial response channel characteristic whose structure is inherent in the design of the state machine encoded by the Viterbi decoder trellis. 
     FIG. 4 depicts modified Viterbi decoder operation to take advantage of diverse signals in accordance with one embodiment of the present invention. For the sake of simplified explanation, it is assumed there are two independent AWGN channels, with samples r o   (1)  . . . r n−1   (1), r   n   (1)  received from a first channel and samples r o   (2)  . . .r n−1   (2) , r n   (2)  received from a second channel. Further, it is assumed that the signal in the first channel is transmitted with an amplitude level A (1) , in noise power (σ (1) ) 2 , and that the signal in the second channel is transmitted with an amplitude level A (2) , in noise power (σ (2))   2 . 
     Like in FIGS. 2-3, the discussion assumes only two channels, and a trellis with two states at each stage with two possible surviving paths into each state. Of course, the present invention is usable with any trellis structure and with any number of diverse channels. One difference between FIG.  4  and FIG. 3 is that each state now has two path history variables associated with it. These are maintained by path history evaluator  116  of FIG.  1 B. Thus, state u has path history variables W u,n−1   (1)  and W u,n−1   (2)  associated it, where path history variable W u,n−   (1)  is for the first channel, defined by          W     u   ,     n   -   1         (   1   )       =       ∑     k   =   0       n   -   1              α     n   -   1   -   k            r   k     (   1   )            s     u   ,   k   ,     *                         
     and path history variable W u,n−1   (2)  is for the second channel, defined by          W     u   ,     n   -   1         (   2   )       =       ∑     k   =   0       n   -   1              α     n   -   1   -   k            r   k     (   2   )            s     u   ,   k   ,     *                         
     The path history variables for state W v,n−1   (1)  and W v,n−1   (1)  are associated with the first and second channel respectively, and defined similarly. 
     The present invention provides special techniques for finding the winning branch into state w at stage n, the winning path into state w, the winning path metric for state w, and the path history variables for state w at stage n, W w,n   (1)  and W w,n   (2) . It is assumed that estimates Â (1) , Â (2) , ({circumflex over (σ)} (1) ) 2 , and ({circumflex over (σ)} (2) ) 2  of A (1) , A (2) , ({circumflex over (σ)} (1) ) 2 , and ({circumflex over (σ)} 2 )) 2 , respectively, are available. The modified Viterbi algorithm proceeds in four steps: 
     (1b) Form two branch metrics                        A   ^       (   1   )           (       σ   ^       (   1   )       )     2            Re        [       r   n     (   1   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   1   )       )       *       ]         +           A   ^       (   2   )           (       σ   ^       (   2   )       )     2            Re        [       r   n     (   2   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   2   )       )       *       ]                
        and           (   10   )                       A   ^       (   1   )           (       σ   ^       (   1   )       )     2            Re        [       r   n     (   1   )                S     v   ,   n     *          (     W     v   ,     n   -   1         (   1   )       )       *       ]         +           A   ^       (   2   )           (       σ   ^       (   2   )       )     2              Re        [       r   n     (   2   )                S     v   ,   n     *          (     W     v   ,     n   -   1         (   2   )       )       *       ]       .               (   11   )                         
     (2b) Use branch metric (10) to form a candidate path metric for the top path,                  m   u     +           A   ^       (   1   )           (       σ   ^       (   1   )       )     2            Re        [       r   n     (   1   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   1   )       )       *       ]         +           A   ^       (   2   )           (       σ   ^       (   2   )       )     2            Re        [       r   n     (   2   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   2   )       )       *       ]           ,           (   12   )                         
     and use branch metric (11) to form a candidate path metric for the bottom path,                m   v     +           A   ^       (   1   )           (       σ   ^       (   1   )       )     2            Re        [       r   n     (   1   )                S     v   ,   n     *          (     W     v   ,     n   -   1         (   1   )       )       *       ]         +           A   ^       (   2   )           (       σ   ^       (   2   )       )     2              Re        [       r   n     (   2   )                S     v   ,   n     *          (     W     v   ,     n   -   1         (   2   )       )       *       ]       .               (   13   )                         
     (3b) Compare (12) and (13) and select a winner, say (12). 
     (4b) Update state w at stage n. The winning path into state w at stage n is S w,0 , S w,1 , . . . S w,n−1 , S w,n  where 
     
       
         (S w,0 S w,1 , . . . S w,n− , S w,n )=(S u,0 S u,1 , . . . S u,n−1 , S u,n ). 
       
     
     The winning path metric is          m   w     =       m   u     +                   A   ^       (   1   )           (       σ   ^       (   1   )       )     2            Re        [       r   n     (   1   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   1   )       )       *       ]         +           A   ^       (   2   )           (       σ   ^       (   2   )       )     2              Re        [       r   n     (   2   )                S     u   ,   n     *          (     W     u   ,     n   -   1         (   2   )       )       *       ]       .                                             
     The winning path history variables are 
     
       
         W w,n   (1) =r n   (1) S u,n *=αW u,n−1   (1)   
       
     
     and 
     
       
         W w,n   (2) =r n   (2) S u,n *=αW u,n−   (2) . 
       
     
     Steps (1b)-(4b), have illustrated one particular way of implementing trellis decoding with multiple symbol noncoherent detection with diversity combining which is based on the particular implementation of multiple symbol noncoherent detection discussed in (1a)-(4a). However, as was discussed in connection with (1a)-(4a), one can easily modify the particular way of doing multiple symbol noncoherent detection and obtain a superficially different implementation, which however in fundamental principle is the same as that illustrated. 
     In the foregoing specification, the invention has been described with reference to specific exemplary embodiments thereof. It will, however, be evident that various modifications and changes may be made thereunto without departing from the broader spirit and scope of the invention as set forth in the appended claims and their full scope of equivalents. 
     For example, although discussed for MPSK modulation, the same technique of diversity combining can be used with other modulations. Although discussed for the AWGN channel, the same technique can be used for other channel impairments such as fading channels. The branch metrics in diversity combining are weighted according to maximal ratio combining. The same techniques can be used if other combining weights are used, or if no combining weights are used. The same technique of diversity combining can be used in conjunction with other implementations of multiple symbol noncoherent detection described in the literature.