Abstract:
A method of decoding is provided comprising processing iterations. In each processing iteration, there is a first Max-Log-MAP decoding operation giving rise to a systematic error due to the Max-Log approximation, and a first weighting operation to weight extrinsic information from the first decoding operation to be applied as a priori information to the second Max-Log-MAP decoding operation. This is followed by a second Max-Log-MAP decoding operation, also giving rise to a systematic error due to the Max-Log approximation, and a second weighting operation to weight extrinsic information from the second decoding to be applied as a priori information to the first Max-Log-MAP decoding of the next iteration. The weights are applied to compensate for the systematic error due to the Max-Log approximation made in the last Max-Log-MAP decoding operation.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention relates to decoding, and more particularly, to decoding using a Max-Log-MAP decoding scheme.  
       DESCRIPTION OF THE RELATED ART  
       [0002]     In the field of wireless telecommunications, in particular code division multiple access (CDMA), the demand for low-cost and low-power decoder chips, particularly for use in mobile user terminals has resulted in renewed interest in low-complexity decoders.  
         [0003]     Several known approaches seeking to reduce complexity of an optimum Maximum A posteriori Probability (MAP) decoder are known, such as the Log-MAP and Max-Log-MAP schemes.  
       SUMMARY OF THE INVENTION  
       [0004]     A method of decoding and a decoding apparatus according to the present invention are defined in the independent claims to which the reader should now refer. Preferred features are laid out in the dependent claims.  
         [0005]     An example of the present invention is a method of decoding comprising processing iterations. In each processing iteration, there is a first Max-Log-MAP decoding operation giving rise to a systematic error due to the Max-Log approximation, and a first weighting operation to weight extrinsic information from the first decoding operation to be applied as a priori information to the second Max-Log-MAP decoding operation. This is followed by a second Max-Log-MAP decoding operation, also giving rise to a systematic error due to the Max-Log approximation, and a second weighting operation to weight extrinsic information from the second decoding to be applied as a priori information to the first Max-Log-MAP decoding of the next iteration. The weights are applied to compensate for the systematic error due to the Max-Log approximation made in the last Max-Log-MAP decoding operation.  
         [0006]     It can thus be considered that a modification to a known Max-Log-MAP iterative decoder is provided, basically using correction weights for the extrinsic information at each iteration in order to correct the error caused by the Max-Log approximation in the extrinsic information provided by the previous decoding iteration. This can be achieved by applying optimised weight factors to the extrinsic information in each decoding iteration. Applying such weights not only allows the inherent advantages of a Max-Log-MAP decoder to be kept, such as of low complexity and insensitivity to input scaling, but tends to result in improved performance. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]     An embodiment of the present invention will now be described by way of example and with reference to the drawings, in which:  
         [0008]      FIG. 1  is a diagram illustrating a turbo-decoder for parallel concatenated codes (PRIOR ART),  
         [0009]      FIG. 2  is a diagram illustrating a known Max-Log-MAP decoder (PRIOR ART),  
         [0010]      FIG. 3  is a diagram illustrating a Max-Log-MAP decoder according to the present invention,  
         [0011]      FIG. 4  is a diagram illustrating determination of weights to be applied to the Max-Log-MAP decoder shown in  FIG. 3 , and  
         [0012]      FIG. 5  is a diagram illustrating a turbo-decoder for parallel concatenated codes including the Max-Log-MAP decoder shown in  FIGS. 3 and 4 . 
     
    
     DETAILED DESCRIPTION  
       [0013]     As background, turbo-coding will first be explained generally, before focussing in on Log-MAP decoding and then Max-Log-MAP decoding. An improvement to Max-Log-MAP decoding will then be presented.  
         [heading-0014]     Turbo-Decoding  
         [0015]      FIG. 1  shows a known turbo-decoder  2  for a parallel concatenated code of rate ⅓ (i.e. where one information bit has two associated parity bits), as presented for example in the book by B. Vucetic and J.Yuan, entitled “Turbo codes”, published by Kluwer Academic Publishers, 2000. The code is termed parallel concatenated because two known recursive systematic convolutional encoders (not shown) within a turbo-encoder (not shown) have operated on the same set of input bits rather than one encoding the output of the other.  
         [0016]     Given systematic (i.e. information) bit x t,0  and parity (i.e. check sequence) bits x t,1  and x t,2 , generated at the turbo-encoder (not shown) and assuming transmission through an additive white gaussian noise (AWGN) channel at time t, the corresponding received signals at the turbo-decoder  2  may be written as Λ c (x t,0 ), Λ c (x t,1 ) and Λ c (x t,2 ). Turbo decoding is performed in an iterative manner using two soft-output decoders  4 , 6 , with the objective of improving data estimates from iteration i to iteration i+1. Each soft-output decoder  4 , 6  generates extrinsic information Λ e   i (x t ) on the systematic bits which then serves as a priori information Λ a   i (x t,0 ) for the other decoder  6 , 4 . Extrinsic information is the probabilistic information gained on the reliability of the systematic bits. This information is improved on through decoding iterations. In order to minimise the probability of error propagation, the decoders  4 ,  6  are separated by interleaving process such that extrinsic information bits passing from decoder  4  to decoder  6  are interleaved, and extrinsic information bits passing from decoder  6  to decoder  4  are de-interleaved.  
         [0017]     As regards, a choice of soft output decoders,  4 , 6 , a maximum a posteriori probability (MAP) scheme would be the optimum decoding scheme in the sense that it results in a minimum probability of bit error. However, the MAP scheme is computationally complex and, as a result is usually implemented in the logarithmic domain in the form of Log-MAP or Max-Log-MAP scheme. While the former is a mathematical equivalent of MAP, the latter scheme involves an approximation which results in even lower complexity, albeit at the expense of some degradation in performance.  
         [0018]     For further background, the reader is referred to the book by B. Vucetic and J. Yuan, entitled “Turbo codes”, published by Kluwer Academic Publishers, 2000.  
         [heading-0019]     Log-MAP Algorithm  
         [0020]     The known log-domain implementation of the MAP scheme requires log-likelihood ratios (LLR) of the transmitted bits at the input of the decoder. These LLRs are of the form  
               Λ   ⁡     (   x   )       =       log   ⁢           ⁢       Pr   ⁡     (     x   =     +   1       )         Pr   ⁡     (     x   =     -   1       )           =       2     σ   n   2       ⁢   r               (   1   )             
 
 where Pr(A) represents the probability of event A, x is the value of the transmitted bit, r=x+n is the received signal at the output of an additive white gaussian noise (AWGN) channel where x is the data value, and n is the noise assumed to have an expected value E{|n| 2 }=σ n   2  where σ n   2  is the variance of the noise. 
 
         [0022]     Given LLRs for the systematic and parity bits as well as a priori LLRs for the systematic bits, the Log-MAP decoder computes new LLRs for the systematic bits as follows:  
                     Λ   ⁡     (     x     t   ,   0       )       =     log   ⁢         ∑     t   =   0         M   s     -   1       ⁢     exp   ⁢     {           α   _       t   -   1       ⁡     (     l   ′     )       +         γ   _     t   1     ⁡     (       l   ′     ,   l     )       +         β   _     t     ⁡     (   l   )         }             ∑     t   =   0         M   s     -   1       ⁢     exp   ⁢     {           α   _       t   -   1       ⁡     (     l   ′     )       +         γ   _     t   0     ⁡     (       l   ′     ,   l     )       +         β   _     t     ⁡     (   l   )         }                         =         Λ   a     ⁡     (     x   t     )       +       Λ   c     ⁡     (     x   t     )       +       Λ   e     ⁡     (     x   t     )                       (   2   )             
 
 where γ t   q (l′,l) denotes the logarithmic transition probability for a transition from state l′ to state l of the encoder trellis at time instant t given that the systematic bit takes on value q{1,0} and M s  is the total number of states in the trellis. (For further explanation of trellis structures the reader is again referred to the Vucetic and Yuan book). 
 
         [0024]     Note that the new information at the decoder output regarding the systematic bits is encapsulated in the extrinsic information term Λ e (x t,0 ). Coefficients α t (l′) are accumulated measures of transition probability at time t in the forward direction in the trellis. Coefficients β t (l) are accumulated measures of transition probability at time t in the backward direction in the trellis. For a data block corresponding to systematic bits x 1,0  to x t,0  and parity bits x 1,1  to x t,1 , these coefficients are calculated as described below.  
         [0025]     Using the following initial values in a forward direction: 
 
{overscore (α)} 0 (0)=0 and {overscore (α)} 0  (l)=−∞ for l≠0   (4), 
 
 the coefficients are calculated as  
                     γ   _     t   q     ⁡     (       l   ′     ,   l     )       =           {         Λ   a     ⁡     (     x     t   ,   0       )       +       Λ   c     ⁡     (     x     t   ,   0       )         }     ⁢     x     t   ,   0     q       +         Λ   c     ⁡     (     x     t   ,   1       )       ⁢     x     t   ,   1     q         2       ,   and           (   5   )                     α   _     t     ⁡     (   l   )       =       ∑       l   ′     =   0         M   s     -   1       ⁢       ∑     q   ∈     (     0   ,   1     )         ⁢     exp   ⁢       {           α   _       t   -   1       ⁡     (     l   ′     )       +         γ   _     t   q     ⁡     (       l   ′     ,   l     )         }     .                   (   6   )             
 
         [0027]     Using the following initial values in the backward direction: 
 
{overscore (β)} t (0)=0 and {overscore (β)} t (l)=−∞ for l≠0   (7), 
 
 the coefficients are calculated as  
                   β   _     t     ⁡     (   l   )       =       ∑       l   ′     =   0         M   s     -   1       ⁢       ∑     q   ∈     (     0   ,   1     )         ⁢     exp   ⁢       {           β   _       t   +   1       ⁡     (     l   ′     )       +         γ   _       t   +   1     q     ⁡     (       l   ′     ,   l     )         }     .                   (   8   )             
 
         [0029]     Equation (2) is readily implemented using the known Jacobian equality 
 
log( e   δ     1     +e   δ     2   )=max(δ 1 , δ 2 )+log(1+ −|δ     2     −δ     1   |)   (9) 
 
 and using a look up table to evaluate the correction function log(1+e −|δ     2     −δ     1     | ). 
 
 Max-Log-MAP decoding 
 
         [0032]     It is known that the complexity of the Log-MAP scheme can be further reduced by using the so-called Max-Log approximation, namely 
 
log( e   δ     1     +e   δ     2   + . . . )≈max(δ 1 ,δ 2 , . . . )   (10) 
 
 for evaluating Equation (2). (log, of course, denotes natural logarithm, i.e. log e ). The Max-Log-MAP scheme is often the preferred choice for implementing a MAP decoder, for example as shown in  FIG. 2 , since it has the advantage that its operation is insensitive to a scaling of the input LLRs. This means that knowledge or estimation of the channel&#39;s noise variance σ n   2  is not required. 
 
         [0034]     However, the known Max-Log approximation leads to accumulating a bias in the decoder output (extrinsic information), i.e. the Max-Log approximation results in biased soft outputs. A bias is, of course, an average of errors over time. This is due to the fact that the known Max-Log-MAP scheme uses the mathematical approximation of Equation (10) to simplify the computation of extrinsic information Λ e (x t,0 ). This approximation results in an error which accumulates from iteration to iteration and impedes the convergence of the turbo-decoder. Since in a turbo-decoder, each decoder output becomes a priori information for the following decoding process, the bias leads to sub-optimal combining proportions between the channel input and the a priori information, thereby degrading the performance of the decoder. In consequence, the known turbo-decoding process may not converge when the known Max-Log-MAP scheme is used for the constituent decoding processes.  
         [heading-0035]     Maximum Mutual Information Combining  
         [0036]     The inventors recognised these errors as a problem and so wanted to correct for such errors in an efficient manner whilst maintaining the benefits of the Max-Log-MAP approach.  
         [0037]     As mentioned above (see Equation (5)), the central operation in the known Max-Log-MAP scheme is the computation of logarithmic transition probabilities of the form  
                   γ   _     t   q     ⁡     (       l   ′     ,   l     )       =       1   2     ⁢     {         {         Λ   a     ⁡     (     x     t   ,   0       )       +       Λ   c     ⁡     (     x     t   ,   0       )         }     ⁢     x     t   ,   0     q       +         Λ   c     ⁡     (     x     t   ,   1       )       ⁢     x     t   ,   1     q         }               (   14   )             
 
 where Λ a (x t,0 ), Λ c (x t,0 ) and Λ c (x t,1 ) are inputs to the constituent decoder. 
 
         [0039]     The inventors realised that bias produced by the Max-Log-MAP scheme should be corrected by appropriate scaling of the terms Λ a (x t,0 ) and Λ c (x t,0 ) in the above equation by weights w a   i  and w c   i , resulting in  
                   γ   _     t   q     ⁡     (       l   ′     ,   l     )       =       1   2     ⁢     {         {         w   a   i     ⁢       Λ   a     ⁡     (     x     t   ,   0       )         +       w   c   i     ⁢       Λ   c     ⁡     (     x     t   ,   0       )           }     ⁢     x     t   ,   0     q       +         Λ   c     ⁡     (     x     t   ,   1       )       ⁢     x     t   ,   1     q         }               (   15   )             
 
 where i represents the iteration index. This is illustrated in  FIG. 3 , which shows a weight w a   i  applied to a priori information Λ a (x t,0 ), and a weight w c   i  applied to systematic information (LtRs) Λ c (x t,0 ) applied to a Max-Log-MAP decoder. The weights are normalised as described later in this text such that the ratio between the LLRs representing systematic and parity bits is not disturbed. 
 
         [0041]     This correction is simple and effective, and retains the advantage of Max-Log-MAP decoding in that soft inputs in the form of scaled LLRs are accepted.  
         [heading-0042]     Determination of Weights  
         [0043]     The optimum values of the weights w a   i  and w c   i  to be applied are those that maximise the transfer of mutual information from one Max-Log-MAP decoder to the other at every iteration. Mutual information is, of course the level of information as to knowledge of a data sequence. These optimum values can be mathematically written as  
               [           w     OPT   ,   a     i               w     OPT   ,   c     i           ]     =         (     R   ɛ   i     )       T   2       ⁢     eig   max     ⁢     {         (     R   ɛ   i     )         -   1     2       ⁢       (     R     λ   +   ɛ     i     )       T   2       ⁢       (     R   ɛ   i     )         -   T     2         }               (   26   )             
 
 where eig max (A) denotes the eigenvector corresponding to the largest eigenvalue of matrix A, and R are correlation matrices defined later on in this text. Equation (26) has more than one solution, but any of the solutions is optimum in maximising mutual information. 
 
         [0045]     The above-mentioned optimum weights are both normalised (divided) by w OPT,c   i  so that the weights to be applied become  
               [           w     OPT   ,   a     i               w     OPT   ,   c     i           ]     -&gt;     [             w     OPT   ,   a     i     /     w     OPT   ,   c     i               1         ]             (   27   )             
 
         [0046]     This normalisation is required to ensure that the natural ratio between Λ c (x t,0 ) and Λ c (x t,1 ) remains undisturbed.  
         [0047]     Computation of the weights in Equation (26) requires the (2×2) matrices R ε   i =R λ+ε   i −R λ   i  and R λ+ε   i  to be computed. These are:  
         R     λ   +   ɛ     i     =     [           E   ⁢     {         Λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   a   i     ⁡     (     x     t   ,   0       )         }             E   ⁢     {         Λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   c   i     ⁡     (     x     t   ,   0       )         }                 E   ⁢     {         Λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   a   i     ⁡     (     x     t   ,   0       )         }             E   ⁢     {         Λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   c   i     ⁡     (     x     t   ,   0       )         }             ]         
         R   λ   i     =     [           E   ⁢     {         λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       λ   a   i     ⁡     (     x     t   ,   0       )         }             E   ⁢     {         λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       λ   c   i     ⁡     (     x     t   ,   0       )         }                 E   ⁢     {         λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       λ   a   i     ⁡     (     x     t   ,   0       )         }             E   ⁢     {         λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       λ   c   i     ⁡     (     x     t   ,   0       )         }             ]         
 
 where Λ a   i (x t,0 )=λ t,a   i +ε t,a   i  and Λ c   i (x t,0 )=λ t,c   i ε t,c   i , where λ t,a   i  and λ t,c   i  the notional uncorrupted LLR values, ε t,a   i  and ε t,c   i  are the errors in LLR as detected compares to the notional uncorrupted LLR values, and “E” denotes statistical mean. 
 
         [0049]     It is proposed that the above statistical means be computed by averaging over a number of data blocks containing a total of say, N, information bits. In other words:  
                 R     λ   +   ɛ     i     =     [             1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   a   i     ⁡     (     x     t   ,   0       )                       1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   a   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   c   i     ⁡     (     x     t   ,   0       )             }                 1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   a   i     ⁡     (     x     t   ,   0       )                     1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   c   i     ⁡     (     x     t   ,   0       )       ⁢       Λ   c   i     ⁡     (     x     t   ,   0       )                   ]       ⁢     
     ⁢   and           (   28   )                   R   λ   i     =     [             α   i     ⁢     α   i               α   i     ⁢     β   i                   α   i     ⁢     β   i               β   i     ⁢     β   i             ]       ⁢     
     ⁢   where           (   29   )                 α   i     =         1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   a   i     ⁡     (     x     t   ,   0       )       ⁢     x     t   ,   0       ⁢           ⁢     β   i           =       1   N     ⁢       ∑     t   =   1     N     ⁢         Λ   c   i     ⁡     (     x     t   ,   0       )       ⁢     x     t   ,   0                       (   30   )             
 
         [0050]     The above operations to determine weights are performed only once and off-line.  
         [0051]     The averaging operations defined by equation (30) are undertaken in the average determining processor  8  shown in  FIG. 4 . Weight determinator  10  then calculated the weights according to equation (26) and normalises as per equation (27).  
         [heading-0052]     Example System  
         [0053]      FIG. 5  shows, by way of review, the resulting turbo-decoder  2 ′ for a parallel concatenated code of rate ⅓ (i.e. where one information bit has two associated parity bits).  
         [0054]     Given systematic (i.e. information) bit x t,0  and parity (i.e. check sequence) bits x t,1  and x t,2 , generated at the turbo-encoder (not shown) and assuming transmission through an additive white gaussian noise (AWGN) channel at time t, the corresponding received signals at the turbo-decoder  2 ′ may be written as Λ c (x t,0 ), Λ c (x t,1 ) and Λ c (x t,2 ).  
         [0055]     Turbo decoding is performed in an iterative manner using two Max-log-MAP decoders  4 ′, 6 ′ of known type as described above, with the objective of improving the data estimates from iteration i to iteration i+1. Each soft-output decoder  4 ′, 6 ′ generates extrinsic information Λ e   i (x t ) on the systematic bits which then serves as a priori information Λ a   i (x t,0 ) for the other decoder. The Extrinsic information is the probabilistic information gained on the reliability of the systematic bits. This information is improved on through decoding iterations. In order to minimise the probability of error propagation, the decoders  4 ′,  6 ′ are separated by interleaving process such that extrinsic information bits passing from decoder  4 ′ to decoder  6 ′ are interleaved, and extrinsic information bits passing from decoder  6 ′ to decoder  4 ′ are de-interleaved.  
         [0056]     Importantly, the a priori information is weighted as described above to remove the bias caused by the Max-log approximation.  
         [0057]     The weights are determined by feeding the turbo-decoder with the channel outputs {Λ c (x t,0 ), Λ c (x t,0 ),Λ c (x t,1 )}t=1 . . . N and performing I turbo iterations as per normal operation. By observing the constituent decoder inputs Λ c (x t,0 ) and Λ a (x t,0 ) at each iteration, the coefficients w a   i  are computed following Equations (26) to (30) as explained above.  
         [0058]     To review, it was found that the performance of a decoder can be improved by using the modified Max-Log-MAP decoder to approach that of a decoder using the optimum Log-MAP or MAP decoders. This is achieved at the expense of only two additional multiplications (each multiplication being to apply a weight to a priori information for each decoder) per iteration for each systematic bit. The weights are to correct for a bias caused by the Max-Log approximation. The advantages of a Max-Log-MAP decoder can be maintained, namely its insensitivity to scaling of the log-likelihood, and that an estimate of noise variance is not required.  
         [0059]     Since the weights need only be computed once for a particular turbo-decoder, the improved decoder retains the low complexity of a Max-Log-MAP approach. The values of optimal weights to be applied can be computed off-line.