Abstract:
The present invention discloses a candidate list augmentation apparatus with dynamic compensation in the coded MIMO systems. The proposed path augmentation technique in the present invention can expand the candidate paths derived from the detector to a distinct and larger list before computing the soft value of each bit. Consequently, the detector is allowed to deliver a smaller list, leading to reduction in computation complexity. Moreover, an additive correction term is introduced to dynamically compensate the approximation inaccuracy in the soft value generation, which improves the efficiency and performance of the coded MIMO systems.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The invention relates to a candidate list augmentation apparatus and method for channel coding system, and more particularly, a candidate list augmentation apparatus which is able to detect signal with dynamic compensation in the multi-input multi-output (MIMO) channel coding systems. 
         [0003]    2. Description of the Related Art 
         [0004]    Multiple input multiple output (MIMO) technology draws great attention due to its ability to improve transmission efficiency. Among several MIMO detection schemes, maximum likelihood (ML) detection is one of the most well known in the art which is being commonly used to fully utilize the diversity gain. With an additive white Gaussian channel noise assumption, ML detection can be reduced to a closest-point-search problem in a given lattice. Moreover, although MIMO system performance is boosted by the diversity gain, channel coding is often employed to provide extra coding gain such that systems are allowed to perform better in case of lower signal-to-noise-ratio (SNR). Since exhaustive search is infeasible for large number of antennas or high level signal modulation, sphere decoding has been proposed to perform exhaustive search after confining the search range by a radius. With properly chosen radius, sphere decoding has been proved to approach the performance of ML detection. 
         [0005]    Please refer to  FIG. 1  for a block diagram schematically showing a conventional MIMO system  100  with channel coding schemes. The conventional MIMO system  100  includes a channel encoder  102 , a spatial mapping device  104 , a transmit device  106 , a receive device  108 , a sphere decoder  110 , and a channel decoder  112 . Assume that the transmit device  106  includes N t  transmit antennas and the receive device  108  includes N r  antennas. The channel encoder  102  is utilized to channel code the original signal u and generate the coded bits x=[x (1) , x (2) , . . . , x (L) ] T . The spatial mapping device  104  then modulates the coded bits x through L time slots. Here, Each vector x (t) =[x 1   (t) , x 2   (t) , . . . , x Nt×2Mc   (t) ] with the time index t is mapped to the transmitted vector {tilde over (s)} (1) =[{tilde over (s)} 1   (t) ,{tilde over (s)} 2   (t)  . . . {tilde over (s)} Nt   (t) ] T  by {tilde over (M)}(•), which maps 2M c  bits to a complex signal. For simplicity, the spatial mapping in the spatial mapping device  104  refers to direct spatial multiplexing, and M 2 -QAM-mapped signals are considered henceforth. 
         [0006]    After mapping the signal, the transmit device  106  transmits through the complex signal based on the transmitted vector {tilde over (s)} (t)  and the receive device  108  receives the real signal according to the received vector {tilde over (y)} (t) . The relation between the transmitted vector {tilde over (s)} (t)  and the received vector {tilde over (y)} (t)  can be expressed by: 
         [0000]        {tilde over (y)}   (t)   ={tilde over (H)}   (t)   {tilde over (s)}   (t)   +ñ   (t)    (1) 
         [0000]    where the channel {tilde over (H)} (t)  is an N r ×N t  matrix of independent and identically distributed (i.i.d.) complex Gaussian random variables; ñ (t)  is an N r ×1 i.i.d. complex Gaussian noise vector. The complex model in the equation (1) can be further rewritten as: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           y 
                           
                             ( 
                             t 
                             ) 
                           
                         
                         = 
                         
                           [ 
                           
                             
                               
                                 
                                   R 
                                    
                                   
                                     { 
                                     
                                       
                                         y 
                                         ~ 
                                       
                                       
                                         ( 
                                         t 
                                         ) 
                                       
                                     
                                     } 
                                   
                                 
                               
                             
                             
                               
                                 
                                   L 
                                    
                                   
                                     { 
                                     
                                       
                                         y 
                                         ~ 
                                       
                                       
                                         ( 
                                         t 
                                         ) 
                                       
                                     
                                     } 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         R 
                                          
                                         
                                           { 
                                           
                                             
                                               y 
                                               ~ 
                                             
                                             
                                               ( 
                                               t 
                                               ) 
                                             
                                           
                                           } 
                                         
                                       
                                       , 
                                     
                                   
                                   
                                     
                                       
                                         - 
                                         L 
                                       
                                        
                                       
                                         { 
                                         
                                           
                                             H 
                                             ~ 
                                           
                                           
                                             ( 
                                             t 
                                             ) 
                                           
                                         
                                         } 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         L 
                                          
                                         
                                           { 
                                           
                                             
                                               H 
                                               ~ 
                                             
                                             
                                               ( 
                                               t 
                                               ) 
                                             
                                           
                                           } 
                                         
                                       
                                       , 
                                     
                                   
                                   
                                     
                                       R 
                                        
                                       
                                         { 
                                         
                                           
                                             y 
                                             ~ 
                                           
                                           
                                             ( 
                                             t 
                                             ) 
                                           
                                         
                                         } 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                              
                             
                               [ 
                               
                                 
                                   
                                     
                                       R 
                                        
                                       
                                         { 
                                         
                                           
                                             s 
                                             ~ 
                                           
                                           
                                             ( 
                                             t 
                                             ) 
                                           
                                         
                                         } 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       L 
                                        
                                       
                                         { 
                                         
                                           
                                             s 
                                             ~ 
                                           
                                           
                                             ( 
                                             t 
                                             ) 
                                           
                                         
                                         } 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           + 
                           
                             [ 
                             
                               
                                 
                                   
                                     R 
                                      
                                     
                                       { 
                                       
                                         
                                           n 
                                           ~ 
                                         
                                         
                                           ( 
                                           t 
                                           ) 
                                         
                                       
                                       } 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     L 
                                      
                                     
                                       { 
                                       
                                         
                                           n 
                                           ~ 
                                         
                                         
                                           ( 
                                           t 
                                           ) 
                                         
                                       
                                       } 
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               H 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                              
                             
                               s 
                               
                                 ( 
                                 t 
                                 ) 
                               
                             
                           
                           + 
                           
                             n 
                             
                               ( 
                               t 
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where R{•} and L{•} refer to the real and the imaginary parts, respectively, of the complex signal s (t) . Thus, the Nt-dimensional complex M2-QAM signals s (t)  are transformed into 2Nt-dimensional real M-PAM signals y (t) . For simpler notation, the time index t will be omitted hereafter. 
         [0007]    Based on the equation (2), ML solution can be derived by searching all over the 2N t -dimensional constellation space Ω 2Nt  for the minimizer: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       s 
                       ^ 
                     
                     ML 
                   
                   = 
                   
                     
                       arg 
                     
                      
                     
                       
                         max 
                         
                           
                             s 
                             ′ 
                           
                           ∈ 
                           
                             Ω 
                             
                               2 
                                
                               
                                 N 
                                 t 
                               
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             y 
                             - 
                             
                               Hs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where the cost function ∥•∥ 2  refers to Euclidean norm. As shown in the equation (3), the exhaustive search for the minimizer ŝ ML  becomes infeasible since the computation grows exponentially with N t  and L. Therefore, the sphere decoder  110  in the conventional MIMO system utilizes sphere decoding algorithm as a means to solve the closest-lattice-point searching problem. 
         [0008]    The sphere decoder  110  first confines the search range by a predefined radius r; and only the path metric of the s′ in the hypersphere ∥y−Hs′∥ 2 ≦r 2  will be compared. That is, the equation (2) can be computed by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         s 
                         ^ 
                       
                       ML 
                     
                     ≈ 
                     
                       
                         s 
                         ^ 
                       
                       SD 
                     
                   
                   = 
                   
                     
                       arg 
                     
                      
                     
                       
                         max 
                         
                           
                             
                               s 
                               ′ 
                             
                             ∈ 
                             
                               Ω 
                               
                                 2 
                                  
                                 
                                   N 
                                   t 
                                 
                               
                             
                           
                           , 
                           
                             
                               
                                  
                                 
                                   y 
                                   - 
                                   
                                     Hs 
                                     ′ 
                                   
                                 
                                  
                               
                               2 
                             
                             ≤ 
                             
                               r 
                               2 
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             y 
                             - 
                             
                               Hs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0009]    Here, if the radius r is chosen properly such that at least one path s′ satisfies the radius constraint. 
         [0010]    Next, the sphere decoder  110  will preprocess on y to transform the equation (4) into a tree-search problem. By QR-decomposition, for instance, the channel matrix is decomposed by H=QR where Q T Q=I 2Nr , an identity matrix of size 2N r , and R is a 2N t ×2N t  upper triangular matrix. By multiplying y with Q T , the sphere decoder  110  can transformed the equation (4) into: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       s 
                       ^ 
                     
                     ML 
                   
                   = 
                   
                     
                       arg 
                     
                      
                     
                       
                         min 
                         
                           
                             s 
                             ′ 
                           
                           ∈ 
                           
                             Ω 
                             
                               2 
                                
                               
                                 N 
                                 t 
                               
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             q 
                             - 
                             
                               Rs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where q=[q 1 , q 2 , . . . , q 2Nt ]=Q T y. Each s′ in Ω 2Nt  is defined as a “path” that traverses from the root to the leaf of the search tree. Every path consists of 2N t  nodes representing the 2N t  points of the 2N t -layered tree. Moreover, the cost function of each path, i.e. ∥q−Rs′∥ 2 , will be referred to “path metric” and can be calculated by: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                        
                       
                         q 
                         - 
                         
                           Rs 
                           ′ 
                         
                       
                        
                     
                     2 
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           2 
                            
                           Nt 
                         
                       
                        
                       
                         
                           ( 
                           
                             
                               q 
                               i 
                             
                             - 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   i 
                                 
                                 
                                   2 
                                    
                                   Nt 
                                 
                               
                                
                               
                                 
                                   R 
                                   
                                     i 
                                     , 
                                     j 
                                   
                                 
                                  
                                 
                                   s 
                                   j 
                                 
                               
                             
                           
                           ) 
                         
                         2 
                       
                     
                     = 
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           2 
                            
                           Nt 
                         
                       
                        
                       
                         e 
                          
                         
                           ( 
                           
                             s 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where s (i)  represents the i-th to 2Nt-th elements of s′, that is, s (i) =[s i , s i+1 , . . . , s 2Nt ] T . Moreover, the partial Euclidean distance (PED) of s (i) , T(s (i) ), is defined by: 
         [0000]    
       
         
           
             
               
                 
                   
                     T 
                      
                     
                       ( 
                       
                         s 
                         
                           ( 
                           i 
                           ) 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         ∑ 
                         
                           i 
                           = 
                           1 
                         
                         
                           2 
                            
                           Nt 
                         
                       
                        
                       
                         
                           ( 
                           
                             
                               q 
                               
                                 i 
                                 ′ 
                               
                             
                             - 
                             
                               
                                 ∑ 
                                 
                                   j 
                                   = 
                                   
                                     i 
                                     ′ 
                                   
                                 
                                 
                                   2 
                                    
                                   Nt 
                                 
                               
                                
                               
                                 
                                   R 
                                   
                                     
                                       i 
                                       ′ 
                                     
                                     , 
                                     j 
                                   
                                 
                                  
                                 
                                   s 
                                   j 
                                 
                               
                             
                           
                           ) 
                         
                         2 
                       
                     
                     = 
                     
                       
                         T 
                          
                         
                           ( 
                           
                             s 
                             
                               ( 
                               
                                 i 
                                 + 
                                 1 
                               
                               ) 
                             
                           
                           ) 
                         
                       
                       + 
                       
                         e 
                          
                         
                           ( 
                           
                             s 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ) 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0011]    Based on this conventional sphere decoding algorithm, the minimizer ŝ ML  can be found as long as each path has been searched. However, the traditional sphere decoding algorithm remains a major challenge in acquiring accurate probabilistic information. Limited by the complex computation of sphere decoding, and inconstant decoding throughput could cause inefficient VLSI implementation. 
         [0012]    Different from the sphere decoding algorithm that outputs only the ML path, the conventional MIMO system utilizes the modified list sphere decoding algorithm to deliver a candidate list L that consists of the most reliable paths. Please refer to  FIG. 2  for a block diagram schematically showing another conventional MIMO system  200  with list sphere coding schemes. The conventional MIMO system  200  includes a channel encoder  202 , a spatial mapping device  204 , a transmit device  206 , a receive device  208 , a list sphere decoder  210 , and a channel decoder  216 . Since the elements of the same name in the  FIG. 1  and  FIG. 2  have the same function and operation, detailed description is omitted for the sake of brevity. The main different between the MIMO systems  100  and  200  is that the MIMO systems  200  further includes the list sphere decoder  210 . The list sphere decoder  210  includes a candidate list generation device  212  and a soft value generation device  214 . The candidate list generation device  212  is utilized to generate a candidate list L. Assume that |L| is the list size. Based on the system model in the equation (2), the most reliable |L| paths are equivalent to the paths corresponding to the least |L| path metrics. After generating the candidate list L, the soft value generation device  214  then computes the soft input signal from the list L for the subsequent channel decoder  216 . Different soft input signal can result in different error correcting capability for the following channel decoding. The operation of the candidate list generation device  212  and the soft value generation device  214  are further detailed as follows. 
         [0013]    Let M(•) denote the M-PAM mapping function such that s k =M(x k,1 , x k,2 , . . . , x k,Mc ). For any path s′ε L, the soft value of x k,j  is defined by its “a posteriori” probabilities: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           L 
                            
                           
                             ( 
                             
                               x 
                               
                                 k 
                                 , 
                                 j 
                               
                             
                             ) 
                           
                         
                         = 
                         
                           log 
                            
                           
                             
                               Pr 
                                
                               
                                 ( 
                                 
                                   
                                     x 
                                     
                                       k 
                                       , 
                                       j 
                                     
                                   
                                   = 
                                   
                                     0 
                                     | 
                                     y 
                                   
                                 
                                 ) 
                               
                             
                             
                               Pr 
                                
                               
                                 ( 
                                 
                                   
                                     x 
                                     
                                       k 
                                       , 
                                       j 
                                     
                                   
                                   = 
                                   
                                     1 
                                     | 
                                     y 
                                   
                                 
                                 ) 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             log 
                              
                             
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     
                                       x 
                                       
                                         k 
                                         , 
                                         j 
                                       
                                     
                                     = 
                                     0 
                                   
                                   ) 
                                 
                               
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     
                                       x 
                                       
                                         k 
                                         , 
                                         j 
                                       
                                     
                                     = 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                           + 
                           
                             log 
                              
                             
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       | 
                                       
                                         x 
                                         
                                           k 
                                           , 
                                           j 
                                         
                                       
                                     
                                     = 
                                     0 
                                   
                                   ) 
                                 
                               
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     
                                       y 
                                       | 
                                       
                                         x 
                                         
                                           k 
                                           , 
                                           j 
                                         
                                       
                                     
                                     = 
                                     1 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   
                     
                       
                         ( 
                         8 
                         ) 
                       
                     
                   
                   
                     
                       
                           
                       
                     
                   
                   
                     
                       
                         ( 
                         9 
                         ) 
                       
                     
                   
                 
               
             
           
         
       
     
         [0000]    The first term in the equation (9), which is the “a priori” information, is zero for the ML detection or can be computed by the extrinsic information provided by the channel decoder in an iterative detection decoding process. The second term in the equation (9) can be computed by: 
         [0000]    
       
         
           
             
               
                 
                   
                     log 
                      
                     
                       
                         Pr 
                          
                         
                           ( 
                           
                             
                               y 
                               | 
                               
                                 x 
                                 
                                   k 
                                   , 
                                   j 
                                 
                               
                             
                             = 
                             0 
                           
                           ) 
                         
                       
                       
                         Pr 
                          
                         
                           ( 
                           
                             
                               y 
                               | 
                               
                                 x 
                                 
                                   k 
                                   , 
                                   j 
                                 
                               
                             
                             = 
                             1 
                           
                           ) 
                         
                       
                     
                   
                   = 
                   
                     log 
                      
                     
                       
                         
                           ∑ 
                           
                             
                               s 
                               ′ 
                             
                             ∈ 
                             
                               Ω 
                               
                                 j 
                                 , 
                                 0 
                               
                             
                           
                         
                          
                         
                           Pr 
                            
                           
                             ( 
                             
                               y 
                               | 
                               
                                 s 
                                 ′ 
                               
                             
                             ) 
                           
                         
                       
                       
                         
                           ∑ 
                           
                             
                               s 
                               ′ 
                             
                             ∈ 
                             
                               Ω 
                               
                                 j 
                                 , 
                                 1 
                               
                             
                           
                         
                          
                         
                           Pr 
                            
                           
                             ( 
                             
                               y 
                               | 
                               
                                 s 
                                 ′ 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   ≈ 
                   
                     
                       1 
                       
                         2 
                          
                         
                           σ 
                           2 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             min 
                             
                               
                                 s 
                                 ′ 
                               
                               ∈ 
                               
                                 Ω 
                                 
                                   j 
                                   , 
                                   1 
                                 
                               
                             
                           
                            
                           
                             
                                
                               
                                 y 
                                 - 
                                 
                                   Hs 
                                   ′ 
                                 
                               
                                
                             
                             2 
                           
                         
                         - 
                         
                           
                             min 
                             
                               
                                 s 
                                 ′ 
                               
                               ∈ 
                               
                                 Ω 
                                 
                                   j 
                                   , 
                                   0 
                                 
                               
                             
                           
                            
                           
                             
                                
                               
                                 y 
                                 - 
                                 
                                   Hs 
                                   ′ 
                                 
                               
                                
                             
                             2 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
             
               
                 
                   ≈ 
                   
                     
                       1 
                       
                         2 
                          
                         
                           σ 
                           2 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           
                             min 
                             
                               
                                 s 
                                 ′ 
                               
                               ∈ 
                               
                                 
                                   Ω 
                                   
                                     j 
                                     , 
                                     1 
                                   
                                 
                                 ⋂ 
                                 L 
                               
                             
                           
                            
                           
                             
                                
                               
                                 y 
                                 - 
                                 
                                   Hs 
                                   ′ 
                                 
                               
                                
                             
                             2 
                           
                         
                         - 
                         
                           
                             min 
                             
                               
                                 s 
                                 ′ 
                               
                               ∈ 
                               
                                 
                                   Ω 
                                   
                                     j 
                                     , 
                                     0 
                                   
                                 
                                 ⋂ 
                                 L 
                               
                             
                           
                            
                           
                             
                                
                               
                                 y 
                                 - 
                                 
                                   Hs 
                                   ′ 
                                 
                               
                                
                             
                             2 
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Where σ 2  is the noise variance, and Ω j,b  is the set of all path s′ having x k,j =b for b=0, 1. That is, Ω j,0  represents the set of all s′ having x k,j =0, and Ω j,0  represents the set of all s′ having x k,j =1. Usually, the candidate list generation device  212  will generate a sufficiently large list to ensure a high probability in finding the true minimizer in the equation (11) with (12). With preprocessing, the equation (12) will be replaced by: 
         [0000]    
       
         
           
             
               
                 
                   
                     1 
                     
                       2 
                        
                       
                         σ 
                         2 
                       
                     
                   
                    
                   
                     ( 
                     
                       
                         
                           min 
                           
                             
                               s 
                               ′ 
                             
                             ∈ 
                             
                               
                                 Ω 
                                 
                                   j 
                                   , 
                                   1 
                                 
                               
                               ⋂ 
                               L 
                             
                           
                         
                          
                         
                           
                              
                             
                               q 
                               - 
                               
                                 Rs 
                                 ′ 
                               
                             
                              
                           
                           2 
                         
                       
                       - 
                       
                         
                           min 
                           
                             
                               s 
                               ′ 
                             
                             ∈ 
                             
                               
                                 Ω 
                                 
                                   j 
                                   , 
                                   0 
                                 
                               
                               ⋂ 
                               L 
                             
                           
                         
                          
                         
                           
                              
                             
                               q 
                               - 
                               
                                 Rs 
                                 ′ 
                               
                             
                              
                           
                           2 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
           
         
       
     
         [0014]    However, when one of the sets Ω j,0  and Ω j,0  can not find the path s′ in the list L (i.e. Ω j,0 ∩L=0 or Ω j,1 ∩L=0), it is impossible to find the minimizer in an empty set, and the minima is often approximated by a predefined large constant. Being the soft input signals to the subsequent channel decoder  216 , the additional interference resulted from the approximation inaccuracy can degrade the error performance. Although the degradation can be mitigated by increasing the list size to reduce the probability of Ω j,0 ∩L (or Ω j,1 ∩L), being an empty set, the computation complexity in generating the candidate list also increases. 
         [0015]    Therefore, to solve the above-mentioned problems, the present invention proposes a novel candidate list augmentation apparatus for channel coding system and method thereof along with dynamic compensation to improve the efficiency and performance of the coded MIMO systems. 
       SUMMARY OF THE INVENTION 
       [0016]    It is therefore one of the many objectives of the claimed invention to provide candidate list augmentation apparatus and method thereof along with dynamic compensation to improve the efficiency and performance of the coded MIMO systems. 
         [0017]    According to the claimed invention, a candidate list augmentation device is disclosed. The candidate list augmentation device includes a candidate list generation device for receiving an input signal within a coded MIMO system and generating a candidate list according to said input signal; a path augmentation device, coupled to said candidate list generation device, for augmenting paths in the candidate list according to said candidate list and generate an augmented list; and a soft value generation device, coupled to said candidate list generation device and said path augmentation device, for comparing said input signal and said augmented list and generating a soft value according to said input signal, said candidate list and said augmented list, wherein said soft value is utilized for error correcting in decoding said input signal. 
         [0018]    Also according to the claimed invention, a candidate list augmentation method with low-complexity soft value generation for the coded MIMO systems is disclosed. The candidate list augmentation method includes (1) receiving an input signal and generating a candidate list according to said input signal; (2) generating an augmented list according to said candidate list; and (3) comparing said input signal and said augmented list and generating a soft value according to said input signal, said candidate list and said augmented list, wherein said soft value is utilized for error correcting in decoding said input signal. 
         [0019]    Below, the embodiments of the present invention are described in detail in cooperation with the attached drawings to make easily understood the objectives, technical contents, characteristics and accomplishments of the present invention. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0020]      FIG. 1  is a block diagram schematically showing a conventional MIMO system with channel coding schemes; 
           [0021]      FIG. 2  is a block diagram schematically showing another conventional MIMO system with list sphere coding schemes; 
           [0022]      FIG. 3  is a block diagram schematically showing a MIMO system with candidate list augmentation scheme according to the present invention; 
           [0023]      FIG. 4  is diagram schematically showing an example of the operation of the path augmentation device according to the present invention; and 
           [0024]      FIG. 5  is a diagram schematically showing a simulation result according to the present invention. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]    The present invention provides a candidate list augmentation device and method thereof for channel coding systems with dynamic compensation to improve the efficiency and performance of the channel coding system especially coded MIMO systems 
         [0026]    Please refer to  FIG. 3  for a block diagram schematically showing a MIMO system  300  with candidate list augmentation scheme according to the present invention. The MIMO system  300  includes a channel encoder  302 , a spatial mapping device  304 , a transmit device  306 , a receive device  308 , a list sphere decoder  310 , and a channel decoder  318 . The list sphere decoder  310  includes a candidate list generation device  312 , a soft value generation device  314 , and a path augmentation device  316 . The candidate list generation device  312  is mainly responsible for receiving an input signal within the coded MIMO system and generating a candidate list according to this input signal. As for the path augmentation device  316  which is coupled to the candidate list generation device  312 , it is responsible for augmenting paths in the candidate list according to the candidate list and then generate an augmented list. The soft value generation device  314  which is coupled to the candidate list generation device  312  and the path augmentation device  316  provides comparison for the input signal and the augmented list, and then generates a soft value according to the input signal, the candidate list and the augmented list, wherein said soft value is utilized for error correcting in decoding the input signal. Since the elements of the same name in the  FIG. 2  and  FIG. 3  have the same function and operation, detailed description is omitted for the sake of brevity. In the present invention, the path augmentation device  316  is applied to equivalently provide a larger candidate list, and the probability of failing to find the minimizer in the augmented list is reduced accordingly. That is, the path augmentation device  316  can be treated as an enhancement; no modifications are required for the candidate list generation device  312  and the soft value generation device  314  based on the conventional schemes. 
         [0027]    For the soft value L(x k,j ) computation, the path augmentation device  316  will expand each path s′ in L to M paths by first duplicating s′ M−1 times. Next, each the k-th element of the M identical paths is replaced by a distinct ω j  from Ω={ω j |j=0, 1, . . . ,M−1}, the M symbols of M-PAM constellation. This duplicating-and-replacing procedure continues until all the paths in L are examined. As a result, L is expended to L k  and |L k |=M×|L|. Although identical paths may be found in L k , Ω j,0 ∩L k  or Ω j,1 ∩L k  will never be empty sets since the augmented list contains all constellation points at the k-th layer. Besides, the paths in L are believed to be more reliable, and the augmented list is supposed to be reliable as well. It can be inferred that: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         min 
                         
                           
                             s 
                             ′ 
                           
                           ∈ 
                           
                             Ω 
                             
                               j 
                               , 
                               0 
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             y 
                             - 
                             
                               Hs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                     ≈ 
                     
                       
                         min 
                         
                           
                             s 
                             ′ 
                           
                           ∈ 
                           
                             
                               Ω 
                               
                                 j 
                                 , 
                                 0 
                               
                             
                             ⋂ 
                             
                               L 
                               K 
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             y 
                             - 
                             
                               Hs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   And 
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       min 
                       
                         
                           s 
                           ′ 
                         
                         ∈ 
                         
                           Ω 
                           
                             j 
                             , 
                             1 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           y 
                           - 
                           
                             Hs 
                             ′ 
                           
                         
                          
                       
                       2 
                     
                   
                   ≈ 
                   
                     
                       min 
                       
                         
                           s 
                           ′ 
                         
                         ∈ 
                         
                           
                             Ω 
                             
                               j 
                               , 
                               1 
                             
                           
                           ⋂ 
                           
                             L 
                             K 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           y 
                           - 
                           
                             Hs 
                             ′ 
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   15 
                   ) 
                 
               
             
           
         
       
     
         [0000]    Moreover, the path metric of the j-th expanded path from s′ can be computed by 
         [0000]        T ( s′ )+(Δ i   R   i,i ) 2 +2( y   i   −Σ   j=i   2N     t     R   i,j   S   j ) R   i,i Δ i    (16) 
         [0000]    where Δ j =s k −ω j  for j=0, 1, . . . , M−1. 
         [0028]    For example, please refer to  FIG. 4  for a diagram schematically showing an example of the operation of the path augmentation device  316  according to the present invention. Assume that the path augmentation device  316  is used for computing L(x 5,0 ) and L(x 5,1 ) in a 16-QAM 4×4 MIMO system. The equivalent 4-PAM 8-layered tree can be represented by an 8-stage trellis diagram. Each path s′ in L corresponds to a path in the trellis. In this example, s′={+1,−1,−1,+1,+3,−1,−3,−1}, M=4, and Ω={−3,−1,+1,+3}. The path augmentation device  316  can expand the path s′ to the four distinct path that contains all constellation points of s 5  for computing L(x 5,0 ) and L(x 5,1 ) by the duplicating-and-replacing procedure. As shown in  FIG. 4 , the solid lines are for Ω j,0  and the dashed lines are for Ω j,1 . 
         [0029]    The above-mentioned procedure needs to be performed 2N t  times for decoding s, and the equation (16) is the major computation overhead. Note that Δ j  have limited values and ranges, and they can be realized by a simple look up table or a decoder. Please note that, in this embodiment, the path s′ can be expanded to unlimited M paths. However, considering the overhead from the path augmentation device  316 , L k  can also be augmented partially. That is, the soft values can be generated by the |L|×M most reliable paths for 0&lt;M&lt;1. The value M can provide a tradeoff between complexity and error performance. 
         [0030]    Moreover, the path augmentation device  316  in the present invention can further perform the dynamic compensation by introducing an additive correction term to improve the approximation accuracy of the channel decoder  318  and to improve the error performance. Here, let n 0  and n 1  denote the sizes of Ω j,0 ∩L k  and Ω j,1 ∩L k  respectively, and n 0 +n 1 =|L|. Moreover, let 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       m 
                       0 
                     
                     = 
                     
                       
                         min 
                         
                           
                             s 
                             ′ 
                           
                           ∈ 
                           
                             Ω 
                             
                               j 
                               , 
                               0 
                             
                           
                         
                       
                        
                       
                         
                            
                           
                             q 
                             - 
                             
                               Rs 
                               ′ 
                             
                           
                            
                         
                         2 
                       
                     
                   
                    
                   
                     
 
                   
                    
                   And 
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
             
               
                 
                   
                     m 
                     1 
                   
                   = 
                   
                     
                       min 
                       
                         
                           s 
                           ′ 
                         
                         ∈ 
                         
                           Ω 
                           
                             j 
                             , 
                             1 
                           
                         
                       
                     
                      
                     
                       
                          
                         
                           q 
                           - 
                           
                             Rs 
                             ′ 
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   18 
                   ) 
                 
               
             
           
         
       
     
         [0000]    And the path augmentation device  316  can express the equation (10) in the conventional list sphere decoding algorithm as follows: 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           log 
                            
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     s 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     Ω 
                                     
                                       j 
                                       , 
                                       0 
                                     
                                   
                                 
                               
                                
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     y 
                                     | 
                                     
                                       s 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 ∑ 
                                 
                                   
                                     s 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     Ω 
                                     
                                       j 
                                       , 
                                       1 
                                     
                                   
                                 
                               
                                
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     y 
                                     | 
                                     
                                       s 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         = 
                         
                           log 
                            
                           
                             
                               
                                 ∑ 
                                 
                                   
                                     s 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     Ω 
                                     
                                       j 
                                       , 
                                       0 
                                     
                                   
                                 
                               
                                
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     q 
                                     | 
                                     
                                       s 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                             
                             
                               
                                 ∑ 
                                 
                                   
                                     s 
                                     ′ 
                                   
                                   ∈ 
                                   
                                     Ω 
                                     
                                       j 
                                       , 
                                       1 
                                     
                                   
                                 
                               
                                
                               
                                 Pr 
                                  
                                 
                                   ( 
                                   
                                     q 
                                     | 
                                     
                                       s 
                                       ′ 
                                     
                                   
                                   ) 
                                 
                               
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               ( 
                               
                                 
                                   m 
                                   1 
                                 
                                 - 
                                 
                                   m 
                                   0 
                                 
                               
                               ) 
                             
                             
                               2 
                                
                               
                                 σ 
                                 2 
                               
                             
                           
                           + 
                           
                             log 
                              
                             
                               
                                 1 
                                 + 
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     
                                       
                                         n 
                                         0 
                                       
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         
                                           - 
                                           1 
                                         
                                         
                                           2 
                                            
                                           
                                             σ 
                                             2 
                                           
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             a 
                                             i 
                                           
                                           - 
                                           
                                             m 
                                             0 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                               
                                 1 
                                 + 
                                 
                                   
                                     ∑ 
                                     
                                       i 
                                       = 
                                       1 
                                     
                                     
                                       
                                         n 
                                         1 
                                       
                                       - 
                                       1 
                                     
                                   
                                    
                                   
                                      
                                     
                                       
                                         
                                           - 
                                           1 
                                         
                                         
                                           2 
                                            
                                           
                                             σ 
                                             2 
                                           
                                         
                                       
                                        
                                       
                                         ( 
                                         
                                           
                                             b 
                                             i 
                                           
                                           - 
                                           
                                             m 
                                             1 
                                           
                                         
                                         ) 
                                       
                                     
                                   
                                 
                               
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   19 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where {m 0 , a 1 , a 2 , . . . , a n0−1 }={T(s′)}|∀s′εΩ j,0 ∩L}, and {m 1 , b 1 , b 2 , . . . , b n1−1 }={T(s′)}|∀s′εΩ j,1 ∩L}. For sufficiently large list size, 
         [0000]    
       
         
           
             
               
                 log 
                  
                 
                     
                 
                  
                 
                   
                     n 
                     0 
                   
                   
                     n 
                     1 
                   
                 
               
               ≈ 
               
                 
                   Pr 
                    
                   
                     ( 
                     
                       
                         x 
                         j 
                       
                       = 
                       0 
                     
                     ) 
                   
                 
                 
                   Pr 
                    
                   
                     ( 
                     
                       
                         x 
                         j 
                       
                       = 
                       1 
                     
                     ) 
                   
                 
               
             
             , 
           
         
       
     
         [0000]    which is the intrinsic information required by an maximum “a posteriori” (MAP) detector.
 
The second term in (19) and the intrinsic information can be combined as
 
         [0000]    
       
         
           
             
               
                 
                   
                     β 
                      
                     
                         
                     
                      
                     log 
                      
                     
                       
                         1 
                         + 
                         
                           n 
                           0 
                         
                       
                       
                         1 
                         + 
                         
                           n 
                           1 
                         
                       
                     
                   
                   ≅ 
                   
                     
                       log 
                        
                       
                         
                           ( 
                           
                             1 
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 
                                   
                                     n 
                                     0 
                                   
                                   - 
                                   1 
                                 
                               
                                
                               
                                  
                                 
                                   
                                     1 
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         a 
                                         i 
                                       
                                       - 
                                       
                                         m 
                                         0 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ) 
                         
                         
                           ( 
                           
                             1 
                             + 
                             
                               
                                 ∑ 
                                 
                                   i 
                                   = 
                                   1 
                                 
                                 
                                   
                                     n 
                                     1 
                                   
                                   - 
                                   1 
                                 
                               
                                
                               
                                  
                                 
                                   
                                     
                                       - 
                                       1 
                                     
                                     
                                       2 
                                        
                                       
                                         σ 
                                         2 
                                       
                                     
                                   
                                    
                                   
                                     ( 
                                     
                                       
                                         b 
                                         i 
                                       
                                       - 
                                       
                                         m 
                                         1 
                                       
                                     
                                     ) 
                                   
                                 
                               
                             
                           
                           ) 
                         
                       
                     
                     + 
                     
                       log 
                        
                       
                         
                           Pr 
                            
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               0 
                             
                             ) 
                           
                         
                         
                           Pr 
                            
                           
                             ( 
                             
                               
                                 x 
                                 j 
                               
                               = 
                               1 
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   20 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where 
         [0000]    
       
         
           
             
               n 
               0 
             
             
               n 
               1 
             
           
         
       
     
         [0000]    is modified to 
         [0000]    
       
         
           
             
               1 
               + 
               
                 n 
                 0 
               
             
             
               1 
               + 
               
                 n 
                 1 
               
             
           
         
       
     
         [0000]    to avoid logarithm of zero or infinity. Ultimately, the soft value generated by the soft value generation device  314  will be: 
         [0000]    
       
         
           
             
               
                 
                   
                     L 
                      
                     
                       ( 
                       
                         x 
                         
                           k 
                           , 
                           j 
                         
                       
                       ) 
                     
                   
                   ≈ 
                   
                     
                       
                         - 
                         1 
                       
                       
                         2 
                          
                         
                           σ 
                           2 
                         
                       
                     
                      
                     
                       ( 
                       
                         
                           m 
                           1 
                         
                         - 
                         
                           m 
                           0 
                         
                         + 
                         
                           β 
                            
                           
                               
                           
                            
                           log 
                            
                           
                             
                               1 
                               + 
                               
                                 n 
                                 0 
                               
                             
                             
                               1 
                               + 
                               
                                 n 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   21 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                    
                   
                     ≈ 
                     
                       ( 
                       
                         
                           m 
                           1 
                         
                         - 
                         
                           m 
                           0 
                         
                         + 
                         
                           βlog 
                            
                           
                             
                               1 
                               + 
                               
                                 n 
                                 0 
                               
                             
                             
                               1 
                               + 
                               
                                 n 
                                 1 
                               
                             
                           
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where β is a normalization factor, and n 1 =|L|−n 0 . From the equation (21), the computation overhead resulted from the dynamic compensation 
         [0000]    
       
         
           
             β 
              
             
                 
             
              
             log 
              
             
               
                 1 
                 + 
                 
                   n 
                   0 
                 
               
               
                 1 
                 + 
                 
                   n 
                   1 
                 
               
             
           
         
       
     
         [0000]    are one multiplication, two logarithms, and at most |L|+1 additions for accumulating n 0 . Moreover, m 0  (or m 1 ) will be estimated by the maximum path metric in L if Ω j,0 ∩L k  (or Ω j,1 ∩L k ) is empty set. Please note that, in this embodiment, the calculation of the soft value L(x k,j ) in the equation (21) and (22) is the estimated value suitable for current model. However, the calculation of the soft value L(x k,j ) is not limited to the above definition. That is, in other embodiments, the soft value L(x k,j ) can be assigned by different conditions depending on design requirements. For example, for simplicity, the soft value generation device  314  can alternatively generate the soft value L(x k,j ) by: 
         [0000]        L ( x   k,j ) ≈m   1   −m   2    (23) 
         [0031]    Please refer to  FIG. 5  for a diagram schematically showing a simulation result according to the present invention. The simulation is based on a 4×4 MIMO system wherein (648,324) and (1944, 972) LDPC codes of IEEE802.11n is applied as channel coding schemes. The candidate list generation is realized by the K-best algorithm. To achieve the BER lower than 10 −5 ,  FIG. 5  shows that the conventional LSDs should have the list size K larger than 128. However, as shown in  FIG. 5 , the proposed candidate list augmentation scheme (A-LSD) in the present invention can achieve SNR improvement from 0.3 dB to 1 dB, depending on K value, and the improvement becomes more apparent when K value is smaller. That is, the path augmentation algorism in the present invention results in equivalently more available candidates, and therefore 64-best A-LSD has the lowest error floor. 
         [0032]    Based on the present invention, the path augmentation algorithm in the present invention guarantees a low probability of failing to find the minimizers. Actually, the computation overhead from list expansion by the path augmentation device  316  is usually smaller as compared to direct generation of a larger candidate list in the conventional MIMO system. Moreover, the path augmentation algorithm in the present invention can be applied in different decoding algorithm, for instance, sphere decoding, list decoding, M-algorithm, T-algorithm, or K-best algorithm. Besides, an additive correction term is introduced to dynamically compensate the approximation loss in the conventional list sphere decoding scheme. Combining the two proposed schemes, the MIMO system with candidate list augmentation scheme in the present invention significantly reduce the calculation complex and perceive improvement in error performance. 
         [0033]    Those described above are only the preferred embodiments to exemplify the present invention but not to limit the scope of the present invention. Any equivalent modification or variation according to the shapes, structures, features and spirit disclosed in the specification is to be also included within the scope of the present invention.