Abstract:
The present invention relates to a method for decoding at least one codeword, the at least one codeword having receive codeword been generated by an encoder comprising a structure providing a code representable by a set of branch transitions in a trellis diagram. Further, the present invention provides a respective decoder, as well as a mobile station and a base station in a communication network employing the decoder. Moreover a communication system comprising the base stations and mobile stations is provided. To reduce the influence of wrong information in a decoding process the present invention suggests using only a subset of reliable information in the forward and/or backward recursion of a Maximum A-Posteriori (MAP) Algorithm or Max-Log-MAP Algorithm.

Description:
FIELD OF THE INVENTION 
       [0001]    The present invention relates to a method for decoding at least one codeword, the at least one codeword having been generated by an encoder comprising a structure providing a code representable by a set of branch transitions in a trellis diagram. Further, the present invention provides a respective decoder, as well as a mobile station and a base station in a communication network employing the decoder. Moreover a communication system comprising the base stations and mobile stations is provided. 
       TECHNICAL BACKGROUND 
     Shift-Register Coding 
       [0002]    Convolutional codes and related codes may be generated by means of one or more cascaded or concatenated shift registers. For matters of simplicity, binary shift registers are considered in the following sections. The binary shift registers are capable of taking the value of either binary 0 or binary 1. When a shift occurs, the content of each register is forwarded to the subsequent register to be its new content. Usually the input to the encoder is used as the new content of the first register. 
         [0003]    The output of a binary shift register encoder is usually obtained by modulo-2 additions of several shift register contents prior to shifting. As an illustration, a simple binary shift-register encoder is shown in  FIG. 1 , where the number of shift registers r=2 and the number of states is M=4. Each shift register is represented by a D, and each modulo-2 addition unit is represented by “+”. Two output bits are obtained from one input bit: The first output bit is identical to the input bit (upper branch), while the second output bit is obtained by modulo-2 addition of the shift register states and the input bit (lower branch). 
         [0004]    In  FIG. 2  a state-transition diagram for the encoder from  FIG. 1  is shown. Each state is represented by the values of the shift register. Each transition is represented by a directed edge. A transition caused by an input bit of zero is denoted by a broken edge, while a transition caused by an input bit of one is denoted by a straight edge. Each edge is further labeled with the input bit followed by the corresponding output bits. An alternative representation of the state transition diagram is a trellis, which is composed of trellis elements as shown in  FIG. 3 . Further details about shift-register encoding (also known as convolutional encoding) may for example be found in Lin et al., “Error Control Coding: Fundamentals and Applications”, Prentice-Hall Inc., chapter 10. 
         [0005]    Shift registers are commonly employed for convolutional codes. Recently, they have also been used in “turbo codes” reaching very low error rates, which make them attractive for communication systems. 
         [0006]    Popular decoding algorithms for shift-register codes are for example the Viterbi algorithm and the maximum a-posteriori algorithm. While the former is often used for traditional convolutional codes, the latter is very popular for the decoding of turbo codes due to its soft a-posteriori probability output. 
       Maximum A-Posteriori Algorithm 
       [0007]    A brief description of the maximum a-posteriori algorithm is provided in the following paragraphs. For brevity, the binary case is considered in more detail. The extension to the non-binary case should impose no problem to those skilled in the art. Generally speaking in the non-binary case event probabilities may usually not be expressed by a log-likelihood ratio. Instead some (possibly logarithmic) absolute probability measure may be used. Evidently, all equations given subsequently involving log-likelihood ratios would have to be changed so that they hold for mentioned absolute probability measures. 
         [0008]    A simplifying characteristic of the binary case is that—since there are only two possible events—the event probabilities may be expressed in terms of a log-likelihood ratio (LLR), which is generally defined by 
         [0000]    
       
         
           
             
               
                 
                   LLR 
                   = 
                   
                     
                       ln 
                        
                       
                         
                           p 
                            
                           
                             ( 
                             
                               x 
                               = 
                               1 
                             
                             ) 
                           
                         
                         
                           p 
                            
                           
                             ( 
                             
                               x 
                               = 
                               0 
                             
                             ) 
                           
                         
                       
                     
                     = 
                     
                       ln 
                        
                       
                         
                           p 
                            
                           
                             ( 
                             
                               x 
                               = 
                               1 
                             
                             ) 
                           
                         
                         
                           1 
                           - 
                           
                             p 
                              
                             
                               ( 
                               
                                 x 
                                 = 
                                 1 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   1 
                 
               
             
           
         
       
     
         [0000]    as the natural logarithm of the ratio of probabilities that x is one of the two possible events. 
         [0009]    The following symbols are used throughout this document: 
         [0000]    
       
         
               
               
             
           
               
                   
               
             
             
               
                 k 
                 Information bit index 
               
               
                 K 
                 Number of information bits in one coded block 
               
               
                 r 
                 Number of shift registers in the encoder 
               
               
                 M 
                 Number of states within the encoder 
               
               
                 S k   
                 State for index k 
               
               
                 d k   
                 information bit number k, either 0 or 1, prior to encoding 
               
               
                 {circumflex over (d)} k   
                 information bit number k, either 0 or 1, after decoding 
               
               
                 x k   s   
                 Systematic value for bit d k  at the output of encoder, −1 or +1 
               
               
                 x k   p   
                 Parity value for bit d k  at the output of encoder, −1 or +1 
               
               
                 x k  = (x k   s x k   p ) 
                 Systematic and parity value sequence for bit d k  at the output of encoder 
               
               
                 y k   s   
                 Received value for systematic bit k at the input of decoder 
               
               
                 y k   p   
                 Received value for parity bit k at the input of decoder 
               
               
                 y k  = (y k   s y k   p ) 
                 Received systematic and parity bit sequence for information bit k 
               
               
                   
                 at the input of decoder 
               
               
                 γ k,i (y k , m′, m″) 
                 Branch transition probability for transit between states m′ and m″, given 
               
               
                   
                 the observation of the received codeword y k , assuming an 
               
               
                   
                 information bit d k  = i (see explanation of Equation 2) 
               
               
                 Γ k (y k , m′, m″) 
                 Logarithm of γ k,i   
               
               
                 α k  (S k ) 
                 Probability measure for being in state S k  for information bit k given 
               
               
                   
                 the received sequence y 1  . . . y k   
               
               
                 β k  (S k ) 
                 Probability measure for being in state S k  for information bit k, 
               
               
                   
                 given the received sequence y k  . . . y K   
               
               
                 L i (x k   s ) 
                 Intrinsic (a-priori) probability log-likelihood ratio which is available 
               
               
                   
                 for bit x k   s   
               
               
                 L e (x k   s ) 
                 Extrinsic probability log-likelihood ratio which is computed for bit 
               
               
                   
                 x k   s   
               
               
                 L(x k   s ) 
                 Decision (a-posteriori) probability log-likelihood ratio which is 
               
               
                   
                 computed for bit x k   s   
               
               
                   
               
             
          
         
       
     
         [0010]    The algorithm has two components commonly referred to as the forward and backward recursion. More specifically, two distributions, α k  and β k  are recursively updated. The quantity α k (S k ) represents the probability measure for being in state S k =m for information bit k, given the received sequence y 1  . . . y k . In a similar manner, β k (S k ) represents the probability measure for being in state S k =m for information bit k, given the received sequence y k  . . . y k . 
         [0011]    Both recursions may be defined based on the so-called branch transition probability γ k,i (y k , m′, m″). This represents the probability to transit between states m′ and m″ given the observation of the received codeword y k , assuming that the information bit causing the transit is d k =i. The branch transition probability can be computed as 
         [0000]      γ k,i (( y   s   k   ,y   p   k ), S   k−1   ,S   k )− q ( d   k   =i|S   k−1   ,S   k )· p ( y   s   k   |d   k   =i )· p ( y   p   k   |d   k   =i,S   k−1   ,S   k )· Pr{S   k   |S   k−1 }  Equation 2 
         [0012]    The value of q(d k =i|S k−1 ,S k ) is either one or zero, depending on whether bit i is associated with the transition from state S k−1  to state S k  or not. Pr{S k |S k−1 } is the a priori probability of the information bit d k . In the context of turbo decoding this probability may be the obtained extrinsic information from another decoder. Other terms can be derived easily by those skilled in the art. For example if no a priori information is available the probabilities may be set equal. 
         [0013]    Equation 2 can be simplified by omitting the index i if it is assumed that the γ values exist only for those transitions where q(d k =i|S k−1 ,S k )=1. Using this assumption the equation can be rewritten as 
         [0000]      γ k (( y   s   k   ,y   p   k ), S   k−1   ,S   k )= p ( y   s   k   |x   s   k )· p ( y   p   k   |x   s   k   ,S   k−1   ,S   k )· Pr{S   k   |S   k−1 }  Equation 3 
         [0014]    Considering the case in which for each information bit d k  at the encoder input, there are two coded bits x k =(x s   k x p   k ) at the output of the encoder, Equation 3 may be further simplified, resulting in a code rate of ½. Furthermore, when considering the binary case, Equation 3 may be further simplified by using logarithmic expressions: 
         [0000]      Γ k (( y   s   k   ,y   p   k ), S   k−1   ,S   k )=1  nγ   k (( y   s   k   ,y   p   k ), S   k−1   ,S   k )  Equation 4 
         [0015]    In case of a binary shift-register code, the number of states M can be computed as 
         [0000]        M= 2 r   Equation 5 
       Initialization 
       [0016]    For each branch transition originating in state S k−1  ending in state S k  the branch transition probability for a BPSK (Binary Phase Shift Keying) AWGN (Additive White Gaussian Noise) case is given by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       Γ 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           ( 
                           
                             
                               y 
                               k 
                               s 
                             
                             , 
                             
                               y 
                               k 
                               p 
                             
                           
                           ) 
                         
                         , 
                         
                           S 
                           
                             k 
                             - 
                             1 
                           
                         
                         , 
                         
                           S 
                           k 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         1 
                         2 
                       
                       · 
                       
                         x 
                         k 
                         s 
                       
                       · 
                       
                         ( 
                         
                           
                             
                               L 
                               i 
                             
                              
                             
                               ( 
                               
                                 x 
                                 k 
                                 s 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               L 
                               c 
                             
                              
                             
                               y 
                               k 
                               s 
                             
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                         1 
                         2 
                       
                        
                       
                         L 
                         c 
                       
                        
                       
                         y 
                         k 
                         p 
                       
                        
                       
                         x 
                         k 
                         p 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   6 
                 
               
             
           
         
       
     
         [0000]    with k running from 1 to K. 
         [0017]    Since the last term is used frequently below, Equation 6 may be rewritten as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             Γ 
                             k 
                           
                            
                           
                             ( 
                             
                               
                                 ( 
                                 
                                   
                                     y 
                                     k 
                                     s 
                                   
                                   , 
                                   
                                     y 
                                     k 
                                     p 
                                   
                                 
                                 ) 
                               
                               , 
                               
                                 S 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 S 
                                 k 
                               
                             
                             ) 
                           
                         
                         = 
                           
                          
                         
                           
                             
                               1 
                               2 
                             
                             · 
                             
                               x 
                               k 
                               s 
                             
                             · 
                             
                               ( 
                               
                                 
                                   
                                     L 
                                     i 
                                   
                                    
                                   
                                     ( 
                                     
                                       x 
                                       k 
                                       s 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     L 
                                     c 
                                   
                                    
                                   
                                     y 
                                     k 
                                     s 
                                   
                                 
                               
                               ) 
                             
                           
                           + 
                         
                       
                     
                   
                   
                     
                       
                           
                          
                         
                           
                             Γ 
                             k 
                             e 
                           
                            
                           
                             ( 
                             
                               
                                 y 
                                 k 
                                 p 
                               
                               , 
                               
                                 S 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                               , 
                               
                                 S 
                                 k 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   7 
                 
               
             
             
               
                 using 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       Γ 
                       k 
                       e 
                     
                      
                     
                       ( 
                       
                         
                           y 
                           k 
                           p 
                         
                         , 
                         
                           S 
                           
                             k 
                             - 
                             1 
                           
                         
                         , 
                         
                           S 
                           k 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       1 
                       2 
                     
                      
                     
                       L 
                       c 
                     
                      
                     
                       y 
                       k 
                       p 
                     
                      
                     
                       x 
                       k 
                       p 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   8 
                 
               
             
           
         
       
     
         [0018]    L c  is a channel scaling factor which may be derived from the signal-to-noise ratio (SNR), and is in this case 
         [0000]    
       
         
           
             
               
                 
                   
                     L 
                     c 
                   
                   = 
                   
                     2 
                     
                       σ 
                       2 
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   9 
                 
               
             
           
         
       
     
         [0000]    with σ 2  representing the channel noise variance. 
         [0019]    The initial values of α k  and β k  may be initialized according to system parameters. For a code which begins and ends in the state m=0, the initializations should be 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                       0 
                     
                      
                     
                       ( 
                       
                         S 
                         0 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               for 
                                
                               
                                   
                               
                                
                               
                                 S 
                                 0 
                               
                             
                             = 
                             0 
                           
                         
                       
                       
                         
                           
                             - 
                             ∞ 
                           
                         
                         
                           else 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   10 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         S 
                         0 
                       
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               for 
                                
                               
                                   
                               
                                
                               
                                 S 
                                 0 
                               
                             
                             = 
                             0 
                           
                         
                       
                       
                         
                           
                             - 
                             ∞ 
                           
                         
                         
                           else 
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   11 
                 
               
             
           
         
       
     
       Forward Recursion 
       [0020]    For each state S k , k running from 1 to K, α k  may be calculated as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                       k 
                     
                      
                     
                       ( 
                       
                         S 
                         k 
                       
                       ) 
                     
                   
                   = 
                   
                     ln 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               S 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             = 
                             1 
                           
                           M 
                         
                          
                         
                             
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   α 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     S 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   Γ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       S 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                     , 
                                     
                                       S 
                                       k 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     S 
                                     k 
                                   
                                   = 
                                   1 
                                 
                                 M 
                               
                                
                               
                                   
                               
                                
                               
                                 
                                   ∑ 
                                   
                                     
                                       S 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                     = 
                                     1 
                                   
                                   M 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   exp 
                                   ( 
                                   
                                     
                                       
                                         α 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           S 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                     + 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Γ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       S 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                     , 
                                     
                                       S 
                                       k 
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   12 
                 
               
             
           
         
       
     
       Backward Recursion 
       [0021]    For each state S k , k running from K−1 to 0, β k  may be calculated as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         S 
                         k 
                       
                       ) 
                     
                   
                   = 
                   
                     ln 
                      
                     
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     S 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                   = 
                                   1 
                                 
                                 M 
                               
                                
                               
                                   
                               
                                
                               
                                 exp 
                                 ( 
                                 
                                   
                                     
                                       β 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         S 
                                         
                                           k 
                                           + 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 ( 
                                 
                                   
                                     y 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                   , 
                                   
                                     S 
                                     k 
                                   
                                   , 
                                   
                                     S 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                 
                                 ) 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     S 
                                     k 
                                   
                                   = 
                                   1 
                                 
                                 M 
                               
                                
                               
                                   
                               
                                
                               
                                 
                                   ∑ 
                                   
                                     
                                       S 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     = 
                                     1 
                                   
                                   M 
                                 
                                  
                                 
                                     
                                 
                                  
                                 
                                   exp 
                                   ( 
                                   
                                     
                                       
                                         β 
                                         
                                           k 
                                           + 
                                           1 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           S 
                                           
                                             k 
                                             + 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                     + 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Γ 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     , 
                                     
                                       S 
                                       k 
                                     
                                     , 
                                     
                                       S 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   13 
                 
               
             
           
         
       
     
       Decoding 
       [0022]    A full decoding process may consist of an application of the forward and backward recursion. After these recursions one can update the soft-output decision (i.e. the posteriori probability) of each information bit: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       L 
                       e 
                     
                      
                     
                       ( 
                       
                         x 
                         k 
                         s 
                       
                       ) 
                     
                   
                   = 
                   
                     ln 
                      
                     
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     ( 
                                     
                                       
                                         m 
                                         ′ 
                                       
                                       , 
                                       
                                         m 
                                         ′′ 
                                       
                                     
                                     ) 
                                   
                                   ∈ 
                                   
                                     S 
                                     + 
                                   
                                 
                               
                                
                               
                                   
                               
                                
                               
                                 exp 
                                 ( 
                                 
                                   
                                     
                                       α 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         m 
                                         ′ 
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     k 
                                     e 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                     , 
                                     
                                       m 
                                       ′′ 
                                     
                                   
                                   ) 
                                 
                                 + 
                                 
                                   
                                     β 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       m 
                                       ′′ 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     ( 
                                     
                                       
                                         m 
                                         ′ 
                                       
                                       , 
                                       
                                         m 
                                         ′′ 
                                       
                                     
                                     ) 
                                   
                                   ∈ 
                                   
                                     S 
                                     - 
                                   
                                 
                               
                                
                               
                                   
                               
                                
                               
                                 exp 
                                 ( 
                                 
                                   
                                     
                                       α 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         m 
                                         ′ 
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     Γ 
                                     k 
                                     e 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                     , 
                                     
                                       m 
                                       ′′ 
                                     
                                   
                                   ) 
                                 
                                 + 
                                 
                                   
                                     β 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       m 
                                       ′′ 
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   14 
                 
               
             
             
               
                 
                   
                     L 
                      
                     
                       ( 
                       
                         d 
                         k 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         L 
                         c 
                       
                       · 
                       
                         y 
                         k 
                         s 
                       
                     
                     + 
                     
                       
                         L 
                         i 
                       
                        
                       
                         ( 
                         
                           x 
                           k 
                           s 
                         
                         ) 
                       
                     
                     + 
                     
                       
                         L 
                         e 
                       
                        
                       
                         ( 
                         
                           x 
                           k 
                           s 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   15 
                 
               
             
           
         
       
     
         [0023]    In the above equation, S +  is the set of ordered pairs (m′,m″) corresponding to all state transitions m′→m″ which are caused by data input d k =1. S −  is similarly defined for d k =0. 
         [0000]    
       
         
           
             
               
                 
                   
                     S 
                     + 
                   
                   = 
                   
                     { 
                     
                       
                         ( 
                         
                           
                             m 
                             ′ 
                           
                           , 
                           
                             m 
                             ′′ 
                           
                         
                         ) 
                       
                        
                       
                         
                           m 
                           ′ 
                         
                          
                         
                           → 
                           
                             
                               d 
                               k 
                             
                             = 
                             1 
                           
                         
                          
                         
                           m 
                           ′′ 
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   16 
                 
               
             
             
               
                 
                   
                     S 
                     - 
                   
                   = 
                   
                     { 
                     
                       
                         ( 
                         
                           
                             m 
                             ′ 
                           
                           , 
                           
                             m 
                             ′′ 
                           
                         
                         ) 
                       
                        
                       
                         
                           m 
                           ′ 
                         
                          
                         
                           → 
                           
                             
                               d 
                               k 
                             
                             = 
                             0 
                           
                         
                          
                         
                           m 
                           ′′ 
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   17 
                 
               
             
           
         
       
     
         [0024]    Using Equation 15 the value of the k th  transmitted bit can be estimated as 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       d 
                       ̑ 
                     
                     k 
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 L 
                                  
                                 
                                   ( 
                                   
                                     d 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                             ≥ 
                             0 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           
                             
                               if 
                                
                               
                                   
                               
                                
                               
                                 L 
                                  
                                 
                                   ( 
                                   
                                     d 
                                     k 
                                   
                                   ) 
                                 
                               
                             
                             &lt; 
                             0 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   18 
                 
               
             
           
         
       
     
         [0025]    It should be noted that the extrinsic quantity L e  obtained in Equation 14 may be used as intrinsic information for a subsequent decoder. Likewise the quantity L i  in Equation 15 may have been obtained as intrinsic information from the extrinsic information of another decoder. 
         [0026]    Those skilled in the art will recognize that both quantities can also be set to proper values in case no information is available from another decoder. Further details about applicability of the algorithm to turbo codes, intrinsic information and extrinsic information are given in Berrou et al., “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo Codes (1)”, Proc. IEEE Int. Conf. On Communications, pp. 1064-1070, May 1993. 
       Max-Log-MAP Algorithm 
       [0027]    To simplify the calculations involved, Equations 12 and 13 may be approximated and substituted by 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                       k 
                     
                      
                     
                       ( 
                       
                         S 
                         k 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         max 
                         
                           
                             S 
                             
                               k 
                               - 
                               1 
                             
                           
                           = 
                           
                             1 
                              
                             … 
                              
                             
                                 
                             
                              
                             M 
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               α 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 S 
                                 
                                   k 
                                   - 
                                   1 
                                 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               Γ 
                               k 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                 , 
                                 
                                   S 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                                 , 
                                 
                                   S 
                                   k 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     
                       
                         
                           
                             max 
                             
                               
                                 S 
                                 k 
                               
                               = 
                               
                                 1 
                                  
                                 … 
                                  
                                 
                                     
                                 
                                  
                                 M 
                               
                             
                           
                         
                       
                       
                         
                           
                             [ 
                             
                               
                                 max 
                                 
                                   
                                     S 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                   = 
                                   
                                     1 
                                      
                                     … 
                                      
                                     
                                         
                                     
                                      
                                     M 
                                   
                                 
                               
                                
                               
                                 ( 
                                 
                                   
                                     
                                       α 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         S 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       Γ 
                                       k 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           y 
                                           k 
                                         
                                         , 
                                         
                                           S 
                                           
                                             k 
                                             - 
                                             1 
                                           
                                         
                                         , 
                                         
                                           S 
                                           k 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   19 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         S 
                         k 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         
                           
                             
                               max 
                               
                                 
                                   S 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 = 
                                 
                                   1 
                                    
                                   … 
                                    
                                   
                                       
                                   
                                    
                                   M 
                                 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   
                                     β 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       S 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   Γ 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               ( 
                               
                                 
                                   y 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 , 
                                 
                                   S 
                                   k 
                                 
                                 , 
                                 
                                   S 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                               
                               ) 
                             
                             ) 
                           
                         
                       
                     
                     
                       
                         
                           
                             
                               max 
                               
                                 
                                   S 
                                   k 
                                 
                                 = 
                                 
                                   1 
                                    
                                   … 
                                    
                                   
                                       
                                   
                                    
                                   M 
                                 
                               
                             
                              
                             
                               [ 
                               
                                 
                                   max 
                                   
                                     
                                       S 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     = 
                                     
                                       1 
                                        
                                       … 
                                        
                                       
                                           
                                       
                                        
                                       M 
                                     
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       
                                         β 
                                         
                                           k 
                                           + 
                                           1 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           S 
                                           
                                             k 
                                             + 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                     + 
                                   
                                 
                               
                             
                           
                         
                       
                       
                         
                           
                             
                               
                                 
                                   Γ 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     , 
                                     
                                       S 
                                       k 
                                     
                                     , 
                                     
                                       S 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               ) 
                             
                             ] 
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   20 
                 
               
             
           
         
       
     
         [0028]    Likewise the decision variable can be obtained by modifying Equation 14 to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       L 
                       e 
                     
                      
                     
                       ( 
                       
                         x 
                         k 
                         s 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         max 
                         
                           
                             ( 
                             
                               
                                 m 
                                 ′ 
                               
                               , 
                               
                                 m 
                                 ″ 
                               
                             
                             ) 
                           
                           ∈ 
                           
                             S 
                             + 
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               α 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 m 
                                 ′ 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               Γ 
                               k 
                               e 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                 , 
                                 
                                   m 
                                   ′ 
                                 
                                 , 
                                 
                                   m 
                                   ″ 
                                 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               β 
                               k 
                             
                              
                             
                               ( 
                               
                                 m 
                                 ″ 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     - 
                     
                       
                         max 
                         
                           
                             ( 
                             
                               
                                 m 
                                 ′ 
                               
                               , 
                               
                                 m 
                                 ″ 
                               
                             
                             ) 
                           
                           ∈ 
                           
                             S 
                             - 
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               α 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 m 
                                 ′ 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               Γ 
                               k 
                               e 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                 , 
                                 
                                   m 
                                   ′ 
                                 
                                 , 
                                 
                                   m 
                                   ″ 
                                 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               β 
                               k 
                             
                              
                             
                               ( 
                               
                                 m 
                                 ″ 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   21 
                 
               
             
           
         
       
     
         [0029]    These approximations may degrade the performance of the decoding however. 
         [0030]    As can be seen from the equations for the forward and backward recursion, the information from numerous values is involved which is ultimately derived from the received vector corresponding to the transmitted codeword. In a noisy channel environment, chances are high that several received values carry wrong information, which implies that wrong information can be inferred from these values and propagate through the decoding iterations. 
       SUMMARY OF THE INVENTION 
       [0031]    It is therefore the object of the present invention is to reduce the influence of such wrong information. 
         [0032]    The object is solved by the subject matters of the independent claims. Advantageous embodiments of the present invention are subject matters to the dependent claims. 
         [0033]    According to one aspect of the present invention not all information in the forward and/or backward recursion is processed, as it would be required by the respective prior-art equations. According to this embodiment of the present invention some of the terms are excluded instead. The decision, which term/s is/are excluded may for example be determined according to its/their reliability. I.e. a term which would produce degrade the decoding performance when employed in determining the forward and/or backward recursion is omitted from the respective equation. 
         [0034]    In one of the different exemplary embodiments of the present invention, a method for decoding at least one codeword, wherein the at least one codeword has been generated by an encoder comprising a structure providing a code representable by a set of branch transitions in a trellis diagram is provided. 
         [0035]    According to this embodiment, the method may comprise the steps of initializing a set of branch transition probabilities in the decoder based on the received codeword and the encoder structure, initializing a first probability distribution and a second probability distribution according to the initial state of the encoder used to encode the at least one codeword, recalculating the values of the first probability distribution based on the initial values of the first probability distribution and the set of branch transition probabilities using a recursive algorithm, recalculating the values of the second probability distribution based on the initial values of the second probability distribution and the set of branch transition probabilities using a recursive algorithm, and reconstructing a decoded codeword based on the received codeword and an extrinsic probability measure calculated based on the set of branch transition probabilities, the first and the second probability distribution. 
         [0036]    In either each of or both steps of recalculating the values of first or second probability distribution a subset of initial values of the first probability distribution or the second probability distribution, respectively, and a subset of the set of branch transition probabilities may be used for recalculating the respective probability distribution. Further, only the values in the subsets fulfilling a predetermined reliability criterion are used. 
         [0037]    In a further embodiment, the encoder may be representable by a shift register structure containing at least one of feed-forward mathematic operations and feed-back mathematic operations. 
         [0038]    Moreover, in another embodiment of the present invention, the code is suitable for decoding by employing a maximum a-posteriori algorithm. 
         [0039]    In a further embodiment of the present invention, the method may further comprise the step of using an intrinsic probability measure to initialize the set of branch transition probabilities. 
         [0040]    Another embodiment of the present invention encompasses the step of using an intrinsic probability measure to reconstruct the decoded codeword. 
         [0041]    In a further variation of this embodiment, a decoder representable by two separate decoder instances is used for decoding the at least one codeword in a first decoding step and the method may further comprise the step of using the extrinsic probability measure of the first decoder instance as the intrinsic probability measure in the second decoder instance. 
         [0042]    In another variation of this embodiment the method further comprises the step of performing a second decoding iteration in the first decoder instance, wherein the decoder instance uses the extrinsic probability measure of the second decoder instance as the intrinsic probability measure. 
         [0043]    According to a further embodiment of the present invention the reliability criterion may be based on at least one of channel estimations of a radio channel via which the at least one codeword has been received, the absolute values of the elements of the first and/or second probability distribution, the number of decoding steps performed and a random process. In another variation the reliability criterion may not be fulfilled by an element of the first or the second probability distribution, if the signal to noise ratio for the element and/or the absolute value of the element is below a predetermined threshold value. 
         [0044]    Moreover, the present invention provides in another embodiment, a decoder for decoding at least one codeword, wherein the at least one codeword has been generated by an encoder comprising a structure providing a code representable by a set of branch transitions in a trellis diagram. 
         [0045]    The decoder may comprise processing means for initializing a set of branch transition probabilities in the decoder based on the received codeword and the encoder structure, initializing a first probability distribution and a second probability distribution according to the initial state of the encoder used to encode the at least one codeword, recalculating the values of the first probability distribution based on the initial values of the first probability distribution and the set of branch transition probabilities using a recursive algorithm, recalculating the values of the second probability distribution based on the initial values of the second probability distribution and the set of branch transition probabilities using a recursive algorithm, and for reconstructing a decoded codeword based on the received codeword and an extrinsic probability measure calculated based on the set of branch transition probabilities, the first and the second probability distribution. 
         [0046]    Moreover, the processing means may be adapted to use in either each of or both steps of recalculating the values of the first and second probability distribution a subset of initial values of the first probability distribution or the second probability distribution, respectively, and a subset of the set of branch transition probabilities for recalculating the respective probability distribution, wherein only values are used that fulfill a predetermined reliability criterion. 
         [0047]    In a further embodiment of the present invention a decoder comprising means adapted to perform any of the above mentioned decoding methods is provided. 
         [0048]    Moreover, another embodiment of the present invention relates to a mobile terminal in a mobile communication system, wherein the mobile terminal may comprise receiving means for receiving at least one codeword, demodulation means for demodulating the at least one received codeword, and a decoder according to one of the embodiments of the present invention. 
         [0049]    In another embodiment, the mobile terminal may further comprise encoding means for encoding data in at least one codeword, and transmission means for transmitting the at least one codeword, wherein the at least one transmitted codeword is suitable for decoding according to a decoding methods outlined above. 
         [0050]    In a further embodiment of the present invention a base station in a mobile communication system is provided, wherein the base station may comprise receiving means for receiving at least one codeword, demodulation means for demodulating the at least one received codeword, and a decoder according to one of the embodiments of the present invention. 
         [0051]    In another embodiment, the base station may further comprise encoding means for encoding data in at least one codeword, and transmission means for transmitting the at least one codeword, wherein the at least one transmitted codeword is suitable for decoding according to a decoding methods outlined above. 
         [0052]    Moreover, the according to an even further embodiment provides a mobile communication system comprising at least one base station according to one of the embodiments of the present invention and at least one mobile terminal according to one of the embodiments of the present invention 
     
     
       BRIEF DESCRIPTION OF THE FIGURES 
         [0053]    In the following the present invention is described in more detail in reference to the attached figures and drawings. Similar or corresponding details in the figures are marked with the same reference numerals. 
           [0054]      FIG. 1  shows an exemplary a shift-register encoder layout for systematic encoding, 
           [0055]      FIG. 2  shows a state transition diagram of the encoder shown in  FIG. 1 , 
           [0056]      FIG. 3  shows a trellis segment description for the encoder shown in  FIG. 1 , 
           [0057]      FIG. 4  shows a trellis segment showing variables for the forward recursion, 
           [0058]      FIG. 5  shows a trellis segment showing variables for the backward recursion, 
           [0059]      FIG. 6  shows a trellis segment showing variables for the decision, 
           [0060]      FIG. 7  shows a flowchart of a decoding process according to one embodiment of the present invention, 
           [0061]      FIGS. 8 &amp; 9  show flowcharts of a decoding process using the turbo principle according to different embodiments of the present invention, 
           [0062]      FIG. 10  shows a transmitter and a receiver unit according to an embodiment of the present invention, 
           [0063]      FIG. 11  shows a mobile terminal according to an embodiment of the present invention comprising the transmitter and the receiver shown in  FIG. 10 , 
           [0064]      FIG. 12  shows a base station according to an embodiment of the present invention comprising the transmitter and the receiver shown in  FIG. 10 , and 
           [0065]      FIG. 13  shows an architectural overview of a communication system according to an embodiment of the present invention comprising a mobile terminal shown in  FIG. 11  and a base station (Node B) shown in  FIG. 12 . 
       
    
    
     DETAILED DESCRIPTION 
       [0066]    In the following paragraphs the expression “xεA\B” denotes “x is element of set A without set B”, which is equivalent to “x is element of set A but not element of set B”. 
         [0067]    As outlined in the previous sections, mathematical equations may be solved in the initialization, forward recursion, backward recursion, and decision step of the maximum a-posteriori algorithm (see for example Equations 6, 12, 13, 14 and 15). 
         [0068]    Generally these equations contain the following terms terms:
       The equation for the initialization contains terms involving y values   The equation for the forward recursion contains terms involving Γ and determined α values   The equation for the backward recursion contains terms involving Γ and determined β values       
 
         [0072]    The numerator of Equation 12 for the forward recursion may be interpreted as a sum of values for state transitions which originate in state S k−1  terminate in state S k =m. Therefore the following “forward set” can be defined: 
         [0000]    
       
         
           
             
               
                 
                   
                     T 
                     
                       k 
                       , 
                       m 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           S 
                           
                             k 
                             - 
                             1 
                           
                         
                         | 
                         
                           
                             S 
                             
                               k 
                               - 
                               1 
                             
                           
                            
                           
                              
                             
                               
                                 d 
                                 k 
                               
                               ∈ 
                               
                                 { 
                                 
                                   0 
                                   , 
                                   1 
                                 
                                 } 
                               
                             
                           
                            
                           
                             S 
                             k 
                           
                         
                       
                       = 
                       m 
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   22 
                 
               
             
           
         
       
     
         [0073]    T k,m  is the set of states S k−1  where transitions from state S k−1  to S k are possible by an information bit d k . 
         [0074]    Therefore 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     log 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               m 
                               ′ 
                             
                             ∈ 
                             
                               T 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   α 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     m 
                                     ′ 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   Γ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                     , 
                                     m 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               m 
                               ″ 
                             
                             = 
                             1 
                           
                           M 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 m 
                                 ′ 
                               
                               ∈ 
                               
                                 T 
                                 
                                   k 
                                   , 
                                   
                                     m 
                                     ″ 
                                   
                                 
                               
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     α 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       m 
                                       ′ 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     Γ 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         y 
                                         k 
                                       
                                       , 
                                       
                                         m 
                                         ′ 
                                       
                                       , 
                                       
                                         m 
                                         ″ 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   23 
                 
               
             
           
         
       
     
         [0075]    Similarly the numerator of Equation 13 for the backward recursion may be interpreted as a sum of values for state transitions which originate in state S k+1  and terminate in state S k =m. Therefore a second “backward set” can be defined: 
         [0000]    
       
         
           
             
               
                 
                   
                     U 
                     
                       k 
                       , 
                       m 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           S 
                           
                             k 
                             + 
                             1 
                           
                         
                         | 
                         
                           S 
                           k 
                         
                       
                       = 
                       
                         m 
                          
                         
                            
                           
                             
                               d 
                               k 
                             
                             ∈ 
                             
                               { 
                               
                                 0 
                                 , 
                                 1 
                               
                               } 
                             
                           
                         
                          
                         
                           S 
                           
                             k 
                             + 
                             1 
                           
                         
                       
                     
                     } 
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   24 
                 
               
             
           
         
       
     
         [0076]    U k,m  is the set of states S k+1  where transitions from state S k to S k+1  are possible by an information bit d k . 
         [0077]    Therefore 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     log 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               m 
                               ″ 
                             
                             ∈ 
                             
                               U 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   β 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     m 
                                     ″ 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   Γ 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                     , 
                                     m 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               m 
                               ′ 
                             
                             = 
                             1 
                           
                           M 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 m 
                                 ″ 
                               
                               ∈ 
                               
                                 U 
                                 
                                   k 
                                   , 
                                   
                                     m 
                                     ′ 
                                   
                                 
                               
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     β 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       m 
                                       ″ 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     Γ 
                                     
                                       k 
                                       + 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         y 
                                         
                                           k 
                                           + 
                                           1 
                                         
                                       
                                       , 
                                       
                                         m 
                                         ′ 
                                       
                                       , 
                                       
                                         m 
                                         ″ 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   25 
                 
               
             
           
         
       
     
         [0078]    According to the present invention, exclusion sets Δ k,m  and Ω k,m  may be additionally defined for the forward and/or backward recursions. 
         [0079]    The exclusion set Δ k,m  may indicate those elements in the forward set T k,m  that do not fulfill a specific reliability criterion and may therefore not be used in the forward recursion step. Likewise, the exclusion set Ω k,m  may indicate those elements in the backward set U k,m  that do not fulfill a specific reliability criterion and may therefore not be used in the backward recursion step. 
         [0080]    Employing the exclusion sets Δ k,m  and Ω k,m , the equations may therefore be modified as follows: 
       New Forward Recursion 
       [0081]    
       
         
           
             
               
                 
                   
                     
                       α 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     log 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               m 
                               ′ 
                             
                             ∈ 
                             
                               
                                 T 
                                 
                                   k 
                                   , 
                                   m 
                                 
                               
                                
                               \ 
                                
                               
                                 Δ 
                                 
                                   k 
                                   , 
                                   m 
                                 
                               
                             
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   α 
                                   
                                     k 
                                     - 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     m 
                                     ′ 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   Γ 
                                   k 
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       k 
                                     
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                     , 
                                     m 
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               m 
                               ″ 
                             
                             = 
                             1 
                           
                           M 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 m 
                                 ′ 
                               
                               ∈ 
                               
                                 
                                   T 
                                   
                                     k 
                                     , 
                                     
                                       m 
                                       ″ 
                                     
                                   
                                 
                                  
                                 \ 
                                  
                                 
                                   Δ 
                                   
                                     k 
                                     , 
                                     
                                       m 
                                       ″ 
                                     
                                   
                                 
                               
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     α 
                                     
                                       k 
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       m 
                                       ′ 
                                     
                                     ) 
                                   
                                 
                                 + 
                                 
                                   
                                     Γ 
                                     k 
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         y 
                                         k 
                                       
                                       , 
                                       
                                         m 
                                         ′ 
                                       
                                       , 
                                       
                                         m 
                                         ″ 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   26 
                 
               
             
           
         
       
     
         [0000]    or alternatively simplified to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       α 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         max 
                         
                           
                             m 
                             ′ 
                           
                           ∈ 
                           
                             
                               T 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                              
                             \ 
                              
                             
                               Δ 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               α 
                               
                                 k 
                                 - 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 m 
                                 ′ 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               Γ 
                               k 
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   k 
                                 
                                 , 
                                 
                                   m 
                                   ′ 
                                 
                                 , 
                                 m 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     
                       
                         max 
                         
                           
                             m 
                             ″ 
                           
                           = 
                           
                             1 
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             M 
                           
                         
                       
                        
                       
                         [ 
                         
                           
                             
                               
                                 max 
                                 
                                   
                                     m 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     
                                       T 
                                       
                                         k 
                                         , 
                                         
                                           m 
                                           ″ 
                                         
                                       
                                     
                                      
                                     \ 
                                      
                                     
                                       Δ 
                                       
                                         k 
                                         , 
                                         
                                           m 
                                           ″ 
                                         
                                       
                                     
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       α 
                                       
                                         k 
                                         - 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         m 
                                         ′ 
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       Γ 
                                       k 
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           y 
                                           k 
                                         
                                         , 
                                         
                                           m 
                                           ′ 
                                         
                                         , 
                                         
                                           m 
                                           ″ 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   27 
                 
               
             
           
         
       
     
       New Backward Recursion 
       [0082]    
       
         
           
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     log 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               m 
                               ″ 
                             
                             ∈ 
                             
                               
                                 U 
                                 
                                   k 
                                   , 
                                   m 
                                 
                               
                                
                               \ 
                                
                               
                                 Ω 
                                 
                                   k 
                                   , 
                                   m 
                                 
                               
                             
                           
                         
                          
                         
                           exp 
                            
                           
                             ( 
                             
                               
                                 
                                   β 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     m 
                                     ″ 
                                   
                                   ) 
                                 
                               
                               + 
                               
                                 
                                   Γ 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                     , 
                                     m 
                                     , 
                                     
                                       m 
                                       ″ 
                                     
                                   
                                   ) 
                                 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               m 
                               ′ 
                             
                             = 
                             1 
                           
                           M 
                         
                          
                         
                           
                             ∑ 
                             
                               
                                 m 
                                 ″ 
                               
                               ∈ 
                               
                                 
                                   U 
                                   
                                     k 
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                   
                                 
                                  
                                 \ 
                                  
                                 
                                   Ω 
                                   
                                     k 
                                     , 
                                     
                                       m 
                                       ′ 
                                     
                                   
                                 
                               
                             
                           
                            
                           
                             exp 
                              
                             
                               ( 
                               
                                 
                                   
                                     
                                       
                                         
                                           β 
                                           
                                             k 
                                             + 
                                             1 
                                           
                                         
                                          
                                         
                                           ( 
                                           
                                             m 
                                             ″ 
                                           
                                           ) 
                                         
                                       
                                       + 
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         Γ 
                                         
                                           k 
                                           + 
                                           1 
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             y 
                                             
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           , 
                                           
                                             m 
                                             ′ 
                                           
                                           , 
                                           
                                             m 
                                             ″ 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   28 
                 
               
             
           
         
       
     
         [0000]    or alternatively simplified to 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       β 
                       k 
                     
                      
                     
                       ( 
                       
                         
                           S 
                           k 
                         
                         = 
                         m 
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         max 
                         
                           
                             m 
                             ″ 
                           
                           ∈ 
                           
                             
                               U 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                              
                             \ 
                              
                             
                               Ω 
                               
                                 k 
                                 , 
                                 m 
                               
                             
                           
                         
                       
                        
                       
                         ( 
                         
                           
                             
                               β 
                               
                                 k 
                                 + 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 m 
                                 ″ 
                               
                               ) 
                             
                           
                           + 
                           
                             
                               Γ 
                               
                                 k 
                                 + 
                                 1 
                               
                             
                              
                             
                               ( 
                               
                                 
                                   y 
                                   
                                     k 
                                     + 
                                     1 
                                   
                                 
                                 , 
                                 m 
                                 , 
                                 
                                   m 
                                   ″ 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                     
                       
                         max 
                         
                           
                             m 
                             ′ 
                           
                           = 
                           
                             1 
                              
                             
                                 
                             
                              
                             … 
                              
                             
                                 
                             
                              
                             M 
                           
                         
                       
                        
                       
                         [ 
                         
                           
                             
                               
                                 max 
                                 
                                   
                                     m 
                                     ″ 
                                   
                                   ∈ 
                                   
                                     
                                       U 
                                       
                                         k 
                                         , 
                                         
                                           m 
                                           ′ 
                                         
                                       
                                     
                                      
                                     \ 
                                      
                                     
                                       Δ 
                                       
                                         k 
                                         , 
                                         
                                           m 
                                           ′ 
                                         
                                       
                                     
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 ( 
                                 
                                   
                                     
                                       β 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         m 
                                         ″ 
                                       
                                       ) 
                                     
                                   
                                   + 
                                   
                                     
                                       Γ 
                                       
                                         k 
                                         + 
                                         1 
                                       
                                     
                                      
                                     
                                       ( 
                                       
                                         
                                           y 
                                           
                                             k 
                                             + 
                                             1 
                                           
                                         
                                         , 
                                         
                                           m 
                                           ′ 
                                         
                                         , 
                                         
                                           m 
                                           ″ 
                                         
                                       
                                       ) 
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   Equation 
                    
                   
                       
                   
                    
                   29 
                 
               
             
           
         
       
     
         [0083]    If both sets Δ k,m  and Ω k,m  are empty, prior art behavior is replicated. If the exclusion set Δ k,m  contains the same elements as the forward set T k,m , then the value of α k (S k =m) may not be determined from the recursion formula. 
         [0084]    In such a case it may be useful to set the corresponding α k (S k =m)=−∞. Likewise β k (S k =m)=−∞ may be set when the exclusion set Ω k,m  contains the same elements as the backward set U k,m . 
         [0085]    In case that for a certain value of k an exclusion set is equal to the forward set for all m=1 . . . M, then α k (m) may be set to −1 nM, which means that all states S k =1 . . . M are equally likely. The same applies to the backward set. 
         [0086]    Generally the exclusion sets may depend for example on the state index m for which an equation is solved, on the information bit index k for which an equation is solved and/or on the iteration number of the decoding procedure (for example in a turbo decoding context). 
       Definition of Exclusion Sets Δ k,m  and Ω k,m    
       [0087]    As outlined above, the exclusion sets Δ k,m  and Ω k,m  may be defined in order to exclude data from the equations (or decoding process) which are assumed to be wrong, or which are highly likely to be wrong. If such data is included, the produced output is likely to be wrong as well. Therefore the present invention proposes to neglect such values from the equations to overcome their negative impacts on the decoding output. 
         [0088]    As mentioned above, the exclusion sets for the new forward recursion step (see Equation 26 or 27) and backward recursion step (see Equation 28 or 29) may be defined such that unreliable messages are excluded from the calculations. In a further embodiment of the present invention the exclusion sets may for example be defined independently from each other, i.e. an element of exclusion set Δ k,m  may not necessarily be element of exclusion set Ω k,m . 
         [0089]    Similarly, in another embodiment of the present invention, the exclusion sets Δ k,m  and Ω k,m  may be set independently in decoding iterations. When increasing the number of iterations, the overall reliability of messages passed may be increased for reasonably good transmission conditions. This may be for example applicable to the decoding of turbo codes, where the extrinsic information exchanged between decoding entities usually-increases in reliability with an increased number of decoding iterations. 
         [0090]    Therefore, when increasing the number of iterations the number of elements of the exclusion sets may be reduced, such that at late stages (in terms of iterations) of decoding the exclusion sets may be empty. 
         [0091]    In another embodiment of the present invention the exclusion sets may for example depend both on the number of iterations processed so far, as well as on the maximum number of decoding iterations, which may be a parameter given by the communication system. This may allow a gradual reduction of elements in the exclusion sets depending on the progress of iteration steps. 
         [0092]    An exemplary list of possible criteria which may be used isolated or in combination for determining the exclusion sets are channel estimation (signal-to-noise ratio), absolute LLR values, iteration number (in turbo decoding context) and/or a random process. 
         [0093]    For example a channel estimation criterion allows the definition of exclusion sets according to the perceived quality of received data. The advantage may be that the channel estimation provides a sort of independent side information known at the decoder to estimate the reliability of received coded information. However, the granularity of a channel estimate may be restricted to a segment which consists of several bits, so this measure alone may not be applicable in all situations to define an exclusion set. 
         [0094]    An absolute LLR value criterion may allow reliability estimation with a fine granularity. Due to the definition of the LLR value, large absolute values represent a high confidence. Conversely a small absolute value represents a low confidence. Therefore a ranking of absolute LLR values may be used to determine the smallest values for a given equation to be part of the exclusion set. For example, a LLR value criterion may be used alone or in combination with other criteria to determine the elements in the exclusion sets. 
         [0095]    A further possible criterion may be a random process criterion. This criterion may be used either alone or in conjunction with other criteria to determine members of the exclusion set. For example, due to channel estimation it may be assumed that 10% of the received information is unreliable. Then for each piece of information there may be a chance of 10% for being member of an exclusion set. 
         [0096]    Next, in reference to  FIGS. 7 ,  8  and  9 , different embodiments of the present invention will be outlined. 
         [0097]      FIG. 7  shows a flowchart of a decoding process according to one embodiment of the present invention. Upon receiving a codeword y k  via the air interface in step  701 , the decoder may generate the exclusion sets Δ k,m  and Ω k,m  in step  702 . 
         [0098]    In order to generate the exclusion sets, several different decision parameters may be used to decide which elements should be excluded from the calculations in the forward recursion and/or backward recursion steps  704 ,  705 . For example, receiving means may provide information on the channel quality for the reception of the codeword or individual bits thereof, or may even provide the exclusion sets Δ k,m  and Ω k,m  to the decoder. 
         [0099]    Further, based on the knowledge of the encoder structure and the received codeword y k  the branch transition probabilities Γ(y k ,S k−1 ,S k ) may be initialized in step  703 . Also the probability distributions α k  and β k  are initialized in step  704 . This may be for example done using the knowledge of the encoder structure used to generate the received codeword y k . 
         [0100]    Having initialized the decoder appropriately, the forward recursion and the backward recursion, as for example defined in Equations 26 to 29, may be performed in steps  705  and  706 . In these recursions the exclusion sets Δ k,m  and Ω k,m  are considered, i.e. only a subset of the values in the distributions α k , β k  and/or Γ(y k ,S k−1 ,S k ) may be used to perform the recursion steps. 
         [0101]    Upon having recalculated the new values of α k  and β k , the codeword may be reconstructed by the decoder. This step may for example include the generation of the extrinsic LLR L e (x s   k ) and an estimation criterion L(d k ) for deciding upon the individual bits of the decoded codeword {circumflex over (d)} k . 
         [0102]    In a further embodiment, it may be further possible to reuse the extrinsic LLR L e (x s   k ) or the estimation criterion L(d k ) as a parameter for the initialization of the branch transition probabilities Γ(y k ,S k−1 ,S k ) of the next decoding procedure for the subsequent codeword. However, this may facilitate the propagation of decoding errors of a previous codeword to the next codeword. 
         [0103]      FIGS. 8 and 9  show flowcharts of a decoding process using the turbo principle according to further exemplary embodiments of the present invention. In these examples multiple decoder instances are used in the decoder. For example, such a structure may be application for use with turbo encoders/decoders. 
         [0104]    The left branch in the  FIGS. 8 and 9  illustrates the operation of a first decoder instance while the right branch illustrates the operation of the second decoder instance. To better differentiate between the parameters of the two different decoder instances, the 1 s and 2 s have been added in superscript or subscript. 
         [0105]    Essentially, the steps performed by both decoder instances are similar to the respective steps outlined with reference to  FIG. 7 . In the following description of  FIGS. 8 and 9 , it will be therefore focused on the changes applied to the decoding process. 
         [0106]    In  FIG. 8 , a receiving means receives a codeword y k in step  801  and may provide same to the first decoder instance. Upon generating or obtaining the exclusions sets Δ 1   k,m  and Ω 1   k,m  (see step  702 ), for example using reception quality indicators for the individual bits of a receiving means, the branch transition probabilities Γ 1 (y k ,S 1   k−1 ,S 1   k ) and the values of α 1   k  and β 1   k  may be initialized (see steps  703  and  704 ). Next, the forward recursion step  705  and the backward recursion step  706  are executed. 
         [0107]    According to this embodiment of the present invention, the first decoder instance may generate extrinsic LLR L e   1 (x s   k ) (or alternatively an estimation criterion L 1 (d k ) based thereon) in step  802  instead of reconstructing the codeword {circumflex over (d)} k . The generated extrinsic LLR L e   1 (x s   k ) (or the estimation criterion L 1 (d k )) may be forwarded to the second decoder instance for use in its decoding process, which will be explained next. 
         [0108]    In step  803  the second decoder instance receives the codeword y k  from the receiving means. Next, it may generate the exclusions sets Δ 2   k,m  and Ω 2   k,m  or may be provided with same. Alternatively, for example, when using the results of the first decoder instance as indicated by the dotted arrow, the exclusions sets Δ 2   k,m  and Ω 2   k,m  will be generated in step  803 . It should be noted that the consideration of the processing results of the first decoder instance is optional in step  803 . 
         [0109]    Next, the second decoder instance may initialize the branch transition probabilities Γ 2 (y k ,S 2   k−1 ,S 2   k ) in step  804 . The extrinsic LLR L e   1 (x s   k ) or the estimation criterion L 1 (d k ) may be used as the intrinsic LLR L 1   2 (x s   k ) in the initialization in the second decoder instance. Further, the values of α 2   k  and β 2   k  are initialized in a similar manner as described for steps  703  and  704 . 
         [0110]    Upon initializing Γ 2 (y k ,S 2   k−1 ,S 2   k ), α 2   k  and β 2   k , the forward recursion step  806  and the backward recursion step  807  are executed in a similar manner as described with reference to steps  705  and  706  of  FIG. 7 . 
         [0111]    After having recalculated the probability distributions α 2   k  and β 2   k  the codeword {circumflex over (d)} k  may be reconstructed. According to the exemplary embodiment of  FIG. 8 , the extrinsic LLR L e   2 (x s   k ) may be generated next in step  808  and based in these values the codeword {circumflex over (d)} k  may be reconstructed in step  809 . 
         [0112]    As has become apparent, the second decoder instance may be operated with a delay relative to the first decoder instance, such that the results of the first decoder instance may be used in the decoding procedure of the second decoder instance. It should also be further noted that in an alternative embodiment the first decoder instance may reconstruct a decoded codeword which may be compared to same obtained from the second decoder instance. In this case, the second decoder may or may not be operated delayed to the first decoder instance. This process will be more closely described in reference to  FIG. 9  in the following. 
         [0113]      FIG. 9  shows a flowchart of a decoding process using the turbo principle according to a further exemplary embodiment of the present invention. The decoding processes in the two decoder instances shown in the left and right branches of  FIG. 9  are almost identical. The first decoding iteration in the first decoder instance is similar to the one explained with reference to  FIG. 8 , i.e. for the first decoding iteration steps  901  and  902  are similar to steps  702  and  703  in  FIGS. 7 and 9 . 
         [0114]    Upon initialization and the calculations of the forward recursion an backward recursion (see steps  704 ,  705 ,  706 ), the first decoder instance generates an extrinsic LLR L e   1 (x s   k ) which is provided to the second encoder instance. Further, the first decoding instance construct the decode codeword {circumflex over (d)} 1   k . 
         [0115]    In parallel or with a delay allowing the use of the results of the first decoder instance in step  804  (and optionally step  803 ), the second decoder instance may perform (steps  803  to  807 ,  809  and  904 ) a similar decoding as the first decoder instance or a decoding iteration as described with reference to the second decoder instance in  FIG. 8 . 
         [0116]    At the end of the first decoding iteration, the second decoding instance generates a reconstructed codeword {circumflex over (d)} 2   k . In step  905 , the two generated codeword {circumflex over (d)} 1   k  and {circumflex over (d)} 2   k  are compared and if found to be equal the decoding process finishes in step  906 . 
         [0117]    If however the decision in step  905  comes to a negative result, a further decoding iteration may be performed. In this case the second decoder instance may provide its extrinsic LLR L e   2 (x s   k ) to the first decoder instance (step  904 ) as indicated by the dotted arrows. Similar to the second decoder instance, the first decoder instance may use this extrinsic information as an intrinsic information, e.g. the intrinsic LLR L i   1 (x s   k ), in the decoding iteration. I.e. the information of the second decoder instance may be used for obtaining a newly initialized set of branch transition probabilities Γ 1 (y k ,S 1   k−1 ,S 1   k ) in step  902  and, optionally, for determining the new exclusion sets Δ 1   k,m  and Ω 1   k,m  in step  901 . 
         [0118]    Thus, the decoder may perform several iterations before obtaining similar reconstructed codewords {circumflex over (d)} 1   k  and {circumflex over (d)} 2   k , which will end the decoding procedure for received codeword y k . Further, in case the reconstructed codewords {circumflex over (d)} 1   k  and {circumflex over (d)} 2   k  do not match after a predetermined number of iterations, the decoding process may be halted and a decoding error may be signaled to the next processing instance. 
         [0119]    Though the exemplary decoding procedure of  FIG. 9  has been described with both decoder instances reconstructing a codeword and comparing same, it should be noted that also a procedure as proposed in the embodiment shown in  FIG. 8  may be employed together with performing several decoding iterations before reconstructing the codeword. 
         [0120]    Next,  FIG. 10  will be discussed in more detail.  FIG. 10  shows a transmitter and a receiver unit according to an embodiment of the present invention. The transmitter  1001  comprises an encoder  1002  and a transmission means  1003 . The transmission means may comprise a modulator for modulating the signals encoded by encoder  1002 . As indicated by the dotted arrow, the encoder  1002  is capable of encoding input data into codeword suitable for decoding according to the various embodiments of the decoding process described above. The modulated data may be transmitted by the transmission means  1003  using an antenna as indicated. 
         [0121]    The receiver  1004  receiving the encoded signals may comprise a receiving means  1006 , which may comprise a demodulator for demodulating the received signals. Upon extracting the y k  values and parameters such as the transmission quality or a reliability criterion for each bit in received codeword y k  in the receiving means  1006 , these data may be provided to a decoder  1005 , which will consider the data to initialize the decoding process as outlined above. 
         [0122]    The decoder  1005  may comprise a processing means  1007 , adapted to decode the received data according to the methods described above to produce reconstructed codewords. 
         [0123]      FIGS. 11 and 12  show a mobile terminal (UE)  1101  and a base station (Node B)  1201  according to different embodiments of the present invention, respectively. The mobile terminal  1101  and the base station may each include a transmitter  1001  and a receiver  1004  as shown in  FIG. 10  to perform communications. 
         [0124]      FIG. 13  shows an architectural overview of a communication system according to an embodiment of the present invention comprising a mobile terminal  1101  shown in  FIG. 11  and a base station (Node B)  1201  shown in  FIG. 12 . 
         [0125]    The overview depicts a UMTS network  1301 , which comprises a core network (CN)  1303  and the UMTS terrestrial radio access network (UTRAN)  1302 . The mobile terminal  1101  may be connected to the UTRAN  1302  via a wireless link to a Node B  1201 . The base stations in the UTRAN  1302  may be further connected to a radio network controller (RNC)  1304 . The CN  1303  may comprise a (Gateway) Mobile Switching Center (MSC) for connecting the CN  1303  to a Public Switched Telephone Network (PSTN). The Home Location Register (HLR) and the Visitor Location Register (VLR) may be used to store user related information. Further, the core network may also provide connection to an Internet Protocol-based (IP-based) network through the Serving GPRS Support Node (SGSN) and the Gateway GPRS Support Node (GGSN). 
         [0126]    Though exemplary reference to a mobile communication system has been made above, those skilled in the art will notice that the present invention may also be applicable for use in wireless (data) networks, as for example IEEE 802.11, digital video broadcasting, such as DVB, or digital audio broadcasting, as for example DAB or DRM.