Abstract:
A wireless device, including: an antenna configured to receive a reception signal, a processor configured to convert the reception signal into a first signal that includes a product of an upper triangular matrix and a transmission signal, to detect a first region, to which the first signal belongs, on an IQ plane, a memory configured to store a symbol ranking table that stores symbol candidates in an order of shorter distance from a region center, up to an order that is equal to a rank upper limit value that is set to be lower than a modulation multi-level number of the transmission signal, wherein the processor is further configured to select a first symbol candidate based on the first region and the symbol ranking table.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
     This application is based upon and claims the benefit of priority of the prior Japanese Patent Application No. 2012-061205, filed on Mar. 16, 2012, the entire contents of which are incorporated herein by reference. 
     FIELD 
     The embodiments discussed herein are related to a wireless device and a wireless communication method. 
     BACKGROUND 
     In recent years, multiple input multiple output (MIMO) technique has been studied as a next-generation communication technique. In the MIMO system, a transmitter which is provided with a plurality of transmission antennas (for example, M antennas) transmits a plurality of data streams and a receiver which is provided with a plurality of reception antennas (for example, N antennas) receives the plurality of data streams in a separate manner. Here, M≦N holds. 
     For the sake of expediency in description, a case where a transmitter transmits M data streams which are equal to the number of transmission antennas is described as an example, here. A receiver receives N reception signals. Here, when a data stream is denoted as a vector x in the M-th row and the first column, a channel matrix in the N-th row and M-th column which has a propagation path gain hij between the j-th transmission antenna and the i-th reception antenna as an element is denoted as H, a reception signal is denoted as a vector y in the N-th row and first column, and a noise is denoted as a vector n in the N-th row and first column, expression (1) is obtained. 
     
       
         
           
             
               
                 
                   y 
                   = 
                   
                     
                       Hx 
                       + 
                       
                         n 
                         ⁢ 
                         
                           
 
                         
                         ( 
                         
                           
                             
                               
                                 y 
                                 1 
                               
                             
                           
                           
                             
                               
                                 y 
                                 2 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 y 
                                 N 
                               
                             
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               
                                 
                                   h 
                                   11 
                                 
                               
                               
                                 
                                   h 
                                   12 
                                 
                               
                               
                                 ⋯ 
                               
                               
                                 
                                   h 
                                   
                                     1 
                                     , 
                                     M 
                                   
                                 
                               
                             
                             
                               
                                 
                                   h 
                                   21 
                                 
                               
                               
                                 
                                   h 
                                   22 
                                 
                               
                               
                                 ⋯ 
                               
                               
                                 
                                   h 
                                   
                                     2 
                                     , 
                                     M 
                                   
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                               
                                 ⋮ 
                               
                               
                                 ⋱ 
                               
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   h 
                                   
                                     N 
                                     , 
                                     1 
                                   
                                 
                               
                               
                                 
                                   h 
                                   
                                     N 
                                     , 
                                     2 
                                   
                                 
                               
                               
                                 ⋯ 
                               
                               
                                 
                                   h 
                                   
                                     N 
                                     , 
                                     M 
                                   
                                 
                               
                             
                           
                           ) 
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               
                                 
                                   x 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   x 
                                   2 
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   x 
                                   M 
                                 
                               
                             
                           
                           ) 
                         
                       
                       + 
                       
                         ( 
                         
                           
                             
                               
                                 n 
                                 1 
                               
                             
                           
                           
                             
                               
                                 n 
                                 2 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 n 
                                 N 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     Examples of a stream separation method on the reception side include minimum mean square error (MMSE) and maximum likelihood detection (MLD). In MLD, metrics such as a squared Euclidean distance are calculated with respect to all symbol replica candidate combinations of a plurality of stream signals so as to set a combination, which has the minimum sum metric, as a signal after stream separation. In MLD, a superior reception performance is obtained compared to a linear separation method such as MMSE. However, when a modulation multi-level number of the l-th transmission signal is denoted as m l  (for example, m=4 in a case of QPSK, m=16 in a case of 16QAM, and m=64 in a case of 64QAM), a combination number is expressed as expression (2). 
     
       
         
           
             
               
                 
                   
                     ∏ 
                     
                       k 
                       = 
                       1 
                     
                     M 
                   
                   ⁢ 
                   
                     m 
                     k 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     As expressed in expression (2), as a modulation multi-level number and the number of transmission streams are increased, the number of times of metric calculation is increased in an exponential fashion, causing an enormous amount of processing disadvantageously. Therefore, various types of arithmetic amount reduction type MLD have been proposed. 
     In related art, QRM-MLD in which QR decomposition and M algorithm are combined with each other has been proposed. In QRM-MLD, metrics such as a squared Euclidean distance from all symbol replica candidates are calculated with respect to surviving symbol replica candidates on the previous stage. When k=1, . . . , and the number of surviving candidates on the M-th stage is denoted as S k , the number of times of metric calculation becomes as expression (3). 
     
       
         
           
             
               
                 
                   
                     S 
                     1 
                   
                   + 
                   
                     
                       ∑ 
                       
                         k 
                         = 
                         2 
                       
                       M 
                     
                     ⁢ 
                     
                       
                         m 
                         k 
                       
                       ⁢ 
                       
                         S 
                         
                           k 
                           - 
                           1 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     In related art, a method of adaptive selection of surviving symbol replica candidates based on the maximum reliability (ASESS) in which a method for reducing the number of times of metric calculation is further applied to QRM-MLD has been proposed. Symbol replica candidates on respective stages are ranked through region detection and metric calculation is performed as many times as the number of surviving symbol replica candidates, with respect to symbol replicas in an ascending order of cumulative values of metrics. When k=1, . . . , and the number of surviving candidates on the M-th stage is denoted as S k , the number of times of metric calculation is expressed as expression (4). 
     
       
         
           
             
               
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     M 
                   
                   ⁢ 
                   
                     S 
                     k 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     In ASESS method, the number of times of metric calculation is linearly increased with respect to the number of transmission streams. Further, Japanese Laid-open Patent Publication No. 2006-270430 has disclosed a method in which ranking of symbol candidates is applied to the list sphere decoding (LSD) method. 
     The ASESS method is described in detail. In order to simplify the description, a case of M=N is taken as an example. In the ASESS method, a channel matrix H is QR-decomposed into a unitary matrix Q and an upper triangular matrix R as expression (5). 
     
       
         
           
             
               
                 
                   H 
                   = 
                   
                     QR 
                     = 
                     
                       
                         ( 
                         
                           
                             
                               
                                 q 
                                 11 
                               
                             
                             
                               
                                 q 
                                 12 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   1 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                 q 
                                 21 
                               
                             
                             
                               
                                 q 
                                 22 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   2 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                             
                               ⋮ 
                             
                             
                               ⋱ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   1 
                                 
                               
                             
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   2 
                                 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   N 
                                 
                               
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             
                               
                                 r 
                                 11 
                               
                             
                             
                               
                                 r 
                                 12 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 r 
                                 
                                   1 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                 r 
                                 22 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 r 
                                 
                                   2 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                   
                               
                             
                             
                               ⋱ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               O 
                             
                             
                               
                                   
                               
                             
                             
                               
                                 r 
                                 
                                   N 
                                   , 
                                   N 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     O denotes a zero matrix. In the ASESS method, multiplication of a reception signal y by Hermitian conjugates of the unitary matrix Q from the left enables orthogonalization as expression (6). 
     
       
         
           
             
               
                 
                   
                     
                       
                         z 
                         = 
                           
                         ⁢ 
                         
                           
                             Q 
                             H 
                           
                           ⁢ 
                           y 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               Q 
                               H 
                             
                             ⁢ 
                             QRx 
                           
                           + 
                           
                             
                               Q 
                               H 
                             
                             ⁢ 
                             n 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           Rx 
                           + 
                           
                             
                               n 
                               ′ 
                             
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     
                                       z 
                                       1 
                                     
                                   
                                 
                                 
                                   
                                     
                                       z 
                                       2 
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       z 
                                       N 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                         ⁢ 
                         
                           
                             
                               ( 
                               
                                 
                                   
                                     
                                       r 
                                       11 
                                     
                                   
                                   
                                     
                                       r 
                                       12 
                                     
                                   
                                   
                                     ⋯ 
                                   
                                   
                                     
                                       r 
                                       
                                         1 
                                         , 
                                         N 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                       r 
                                       22 
                                     
                                   
                                   
                                     ⋯ 
                                   
                                   
                                     
                                       r 
                                       
                                         2 
                                         , 
                                         N 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     ⋱ 
                                   
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     O 
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                       r 
                                       
                                         N 
                                         , 
                                         N 
                                       
                                     
                                   
                                 
                               
                               ) 
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   
                                     
                                       x 
                                       1 
                                     
                                   
                                 
                                 
                                   
                                     
                                       x 
                                       2 
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       x 
                                       N 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                           + 
                           
                             ( 
                             
                               
                                 
                                   
                                     n 
                                     1 
                                     ′ 
                                   
                                 
                               
                               
                                 
                                   
                                     n 
                                     2 
                                     ′ 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     n 
                                     N 
                                     ′ 
                                   
                                 
                               
                             
                             ) 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     In the ASESS method, region detection on the lowest stage is performed by expression (7) so as to determine a region number ε (1)  of a region to which u N  belongs, on the first stage.
 
 u   N   =z   N   /r   N,N   (7)
 
     In the ASESS method, region detection includes the N div  times of quadrant detection and the N div −1 times of origin movement, and a region to which u N  belongs among 2 2Ndiv  regions is detected. In the ASESS method, a symbol ranking table Ω is referred to and as many candidate replicas as S 1 , the number of surviving candidates from the higher ranking, are set as surviving paths of the first stage so as to calculate a metric such as a squared Euclidean distance. When a surviving path is expressed as expression (8) and a metric is a squared Euclidean distance, the metric is expressed as expression (9).
 
Π 1   (1) ( i )=Ω (m     N     ) (ε, i )  (8)
 
 d   1 (Π 1   (1) ( i ))=| z   N   −r   N,N   c   N,Π     1       (1)     (i) | 2   , i= 1, 2 , . . . , S   1   (9)
 
     Here, Ω (4) , Ω (16) , and Ω (64)  respectively represent symbol ranking tables with respect to QPSK, 16QAM, and 64QAM. Expression (10) expresses the symbol number of the i-th order in ranking with respect to a region number ε (1)  which is stored in the symbol ranking table.
 
Ω (m     N     ) (ε (1)   ,i )  (10)
 
     In the ASESS method, region detection by expression (11) in which candidate replicas of S 1  surviving paths, which are survived on the first stage, are respectively cancelled from a reception signal z N−1  which is the second lowest signal is performed so as to determine a region number ε (1) (i) of a region to which u expressed as expression (12) belongs, on the second stage.
 
 u   N−1 (Π 1   (1) ( i ))=( z   N−1   −r   N−1,N   c   N,Π     1       (1)     (i) )/ r   N−1,N−1   , i= 1, 2 , . . . , S   1   (11)
 
 u   N−1 (Π 1   (1) ( i ))  (12)
 
     In the ASESS method, a surviving path on the second stage is adaptively selected as following. In the ASESS method, a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the first stage are first initialized so as to obtain expression (13), expression (14), and expression (15).
 
 E ( i ):= d   1 (Π 1   (1) ( i ))  (13)
 
ρ( i ):=1  (14)
 
q:=1  (15)
 
     In the ASESS method, a candidate replica on the ρ(i min )-th order in the ranking of i min  at which ρ(i)≦m N  is satisfied and E(i) has the minimum value is selected from the symbol ranking table and the q-th surviving path on the second stage is expressed as expression (16) and expression (17). 
     
       
         
           
             
               
                 
                   
                     
                       
                         ∏ 
                         1 
                         
                           ( 
                           2 
                           ) 
                         
                       
                       ⁢ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         ∏ 
                         1 
                         
                           ( 
                           1 
                           ) 
                         
                       
                       ⁢ 
                       
                         ( 
                         
                           i 
                           
                             m 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             n 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         ∏ 
                         2 
                         
                           ( 
                           2 
                           ) 
                         
                       
                       ⁢ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         Ω 
                         
                           ( 
                           
                             m 
                             
                               N 
                               - 
                               1 
                             
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             
                               ɛ 
                               
                                 ( 
                                 2 
                                 ) 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 
                                   m 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                               ) 
                             
                           
                           , 
                           
                             ρ 
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 
                                   m 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   16 
                   ) 
                 
               
             
             
               
                 
                   
                     i 
                     
                       m 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       i 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       n 
                     
                   
                   = 
                   
                     
                       arg 
                       
                         
                           ρ 
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ≤ 
                         
                           m 
                           
                             N 
                             - 
                             1 
                           
                         
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         min 
                         ⁡ 
                         
                           [ 
                           
                             e 
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ] 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   17 
                   ) 
                 
               
             
           
         
       
     
     A cumulative metric is calculated as expression (18).
 
 d   2 (Π (2) ( q ))= d   1 (Π 1   (1) ( i   min ))+| z   N−1   −r   N−1,N   c   N,Π     1       (1)     (i     min     )   −r   N−1,N−1   c   N−1,Π     2       (2)     (q) | 2   (18)
 
     Then, in the ASESS method, the cumulative metric is updated as expression (19), expression (20), and expression (21).
 
 E ( i   min ):= d   2 (Π (2) ( q ))  (19)
 
ρ( i   min ):=ρ( i   min )+1  (20)
 
 q:=q+ 1  (21)
 
     In the ASESS method, the above-mentioned processing is performed until q reaches the number S 2  of surviving paths of the second stage. In the ASESS method, region detection by expression (22) in which candidate replicas of S k−1  surviving paths, which are survived on the k−1-th stage, are respectively cancelled from a reception signal z N−k+1  which is the k-th lowest signal is performed so as to determine a region number ε (k)  of a region to which u expressed as expression (23) belongs, on the following k-th stage. 
     
       
         
           
             
               
                 
                   
                     
                       
                         u 
                         
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                           , 
                           i 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           
                             z 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 p 
                                 = 
                                 1 
                               
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 r 
                                 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 c 
                                 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     
                                       Π 
                                       p 
                                       
                                         ( 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                       / 
                       
                         r 
                         
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                           , 
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                         
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     i 
                     = 
                     1 
                   
                   , 
                   2 
                   , 
                   … 
                   ⁢ 
                   
                       
                   
                   , 
                   
                     S 
                     
                       k 
                       - 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       u 
                       
                         
                           N 
                           - 
                           k 
                           + 
                           1 
                         
                         , 
                         i 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           Π 
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           i 
                           ) 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
           
         
       
     
     In the ASESS method, a surviving path on the k-th stage is adaptively selected as following. In the ASESS method, a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage are first initialized so as to obtain expression (24), expression (25), and expression (26).
 
 E ( i ):= d   k−1 (Π (k−1) ( i ))  (24)
 
ρ( i ):=1  (25)
 
q:=1  (26)
 
     In the ASESS method, a candidate replica on the ρ(i min )-th order in the ranking of i min  at which ρ(i)≦m N−k+1  is satisfied and E(i) has the minimum value is selected from the symbol ranking table and the q-th surviving path on the k-th stage is expressed as expression (27) and expression (28). 
     
       
         
           
             
               
                 
                   
                     
                       
                         Π 
                         
                           
                             1 
                             ~ 
                             k 
                           
                           - 
                           1 
                         
                         
                           ( 
                           k 
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         Π 
                         
                           ( 
                           
                             k 
                             - 
                             1 
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           
                             m 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             i 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             n 
                           
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         Π 
                         k 
                         
                           ( 
                           k 
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         Ω 
                         
                           ( 
                           
                             m 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             
                               ɛ 
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 
                                   m 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                               ) 
                             
                           
                           , 
                           
                             ρ 
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 
                                   m 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   i 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   n 
                                 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
             
               
                 
                   
                     i 
                     
                       m 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       i 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       n 
                     
                   
                   = 
                   
                     
                       arg 
                       
                         
                           ρ 
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ≤ 
                         
                           m 
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                         
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         min 
                         ⁡ 
                         
                           [ 
                           
                             E 
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ] 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     A cumulative metric is calculated as expression (29). 
     
       
         
           
             
               
                 
                   
                     
                       d 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           Π 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         d 
                         
                           k 
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             
                               i 
                               
                                 m 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 i 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 n 
                               
                             
                             ) 
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                          
                         
                           
                             z 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 p 
                                 = 
                                 1 
                               
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                               
                                 r 
                                 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 c 
                                 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     
                                       Π 
                                       p 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       q 
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                           - 
                           
                             
                               r 
                               
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                                 , 
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               c 
                               
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                                 , 
                                 
                                   
                                     Π 
                                     k 
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     q 
                                     ) 
                                   
                                 
                               
                             
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
           
         
       
     
     Then, in the ASESS method, the cumulative metric is updated as expression (30), expression (31), and expression (32), and the above-mentioned processing is performed until q reaches the number S k  of surviving paths of the k-th stage.
 
 E ( i   min ):= d   k (Π (k) ( q ))  (30)
 
ρ( i   min ):=ρ( i   min )+1  (31)
 
 q:=q+ 1  (32)
 
     The followings are examples of related art. 
     K. J. Kim and J. Yue, “Joint channel estimation and data detection algorithms for MIMO-OFDM systems,” in Proc. Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, pp. 1857-1861, November 2002 
     K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection of Surviving Symbol Replica Candidates Based on Maximum Reliability in QRM-MLD for OFCDM MIMO Multiplexing,” Proc. of IEEE Globecom 2004, pp. 2480-2486, November 2004 
     K. Higuchi, H. Kawai, N. Maeda and M. Sawahashi, “Adaptive Selection Algorithm of Surviving Symbol Replica Candidates in QRM-MLD for MIMO Multiplexing Using OFCDM Wireless Access”, RCS2004-69, May 2004 
     SUMMARY 
     According to an aspect of the invention, a wireless device, including: an antenna configured to receive a reception signal, a processor configured to convert the reception signal into a first signal that includes a product of an upper triangular matrix and a transmission signal, to detect a first region, to which the first signal belongs, on an IQ plane, a memory configured to store a symbol ranking table that stores symbol candidates in an order of shorter distance from a region center, up to an order that is equal to a rank upper limit value that is set to be lower than a modulation multi-level number of the transmission signal, wherein the processor is further configured to select a first symbol candidate based on the first region and the symbol ranking table. 
     The object and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the claims. 
     It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory and are not restrictive of the invention, as claimed. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIGS. 1A to 1C  illustrate a CCDF of a current rank of each surviving path in a stage end. 
         FIG. 2  illustrates the configuration of a MIMO system. 
         FIG. 3  illustrates a configuration example of a MIMO stream separation unit of Embodiment 1. 
         FIG. 4  is a flowchart of region detection. 
         FIG. 5  illustrates an example of region detection in QPSK (N div =1). 
         FIG. 6  illustrates an example of a size reduction type symbol ranking table in QPSK and N div =1. 
         FIG. 7  illustrates an example of region detection in QPSK (N div =2). 
         FIG. 8  illustrates an example of a size reduction type symbol ranking table in QPSK and N div =2. 
         FIG. 9  illustrates an example in 16QAM (N div =2). 
         FIG. 10  illustrates an example of a size reduction type symbol ranking table in 16QAM (N div =2). 
         FIG. 11  illustrates an example in 16QAM (N div =3). 
         FIG. 12  illustrates an example of a size reduction type symbol ranking table in 16QAM (N div =3). 
         FIG. 13  illustrates an example in 64QAM (N div =3). 
         FIG. 14  illustrates an example of a size reduction type symbol ranking table in 64QAM and N div =3. 
         FIGS. 15A to 15C  illustrate an example of region detection. 
         FIG. 16  is a flowchart of Embodiment 1. 
         FIG. 17  is a flowchart of first stage processing. 
         FIG. 18  is a flowchart of surviving symbol selection of the first stage processing. 
         FIG. 19  is a flowchart of k-th stage processing. 
         FIG. 20  is a flowchart of surviving symbol selection of the k-th stage processing. 
         FIG. 21  illustrates an outline of a second aspect. 
         FIG. 22  illustrates a configuration example of MIMO stream separation unit of Embodiment 2. 
         FIGS. 23A and 23B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table in QPSK and N div =2. 
         FIGS. 24A and 24B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table in 16QAM and N div =3. 
         FIG. 25  illustrates an example of a symbol higher order ranking table in 64QAM and N div =3. 
         FIG. 26  illustrates an example of a symbol lower order ranking table in 64QAM and N div =3. 
         FIG. 27  is a flowchart of surviving symbol selection of first stage processing of Embodiment 2. 
         FIG. 28  is a flowchart of k-th stage processing of Embodiment 2. 
         FIG. 29  is a flowchart of surviving symbol selection of the k-th stage processing of Embodiment 2. 
         FIG. 30  illustrates a configuration example of a MIMO stream separation unit of Embodiment 3. 
         FIGS. 31A to 31C  respectively illustrate examples of a symbol higher order ranking table, a symbol intermediate order ranking table, and a symbol lower order ranking table. 
         FIG. 32  is a flowchart of surviving symbol selection of first stage processing of Embodiment 3. 
         FIG. 33  is a flowchart of surviving symbol selection of k-th stage processing of Embodiment 3. 
         FIGS. 34A and 34B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table. 
         FIG. 35  is a flowchart of first stage processing of Embodiment 5. 
         FIGS. 36A and 36B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table for the first stage processing of Embodiment 5. 
         FIG. 37  illustrates the configuration of a MIMO stream separation unit of Embodiment 6. 
         FIG. 38  is a flowchart of Embodiment 6. 
         FIG. 39  illustrates the configuration of a MIMO stream separation unit of Embodiment 7. 
         FIG. 40  is a flowchart of Embodiment 7. 
         FIG. 41  illustrates an example of a symbol ranking table in QPSK and N div =1. 
         FIG. 42  illustrates an example of a symbol ranking table in QPSK and N div =2. 
         FIG. 43  illustrates an example of a symbol ranking table in 16QAM and N div =2. 
         FIG. 44  illustrates an example of a symbol ranking table in 16QAM and N div =3. 
         FIG. 45  illustrates an example of a symbol ranking table in 64QAM and N div =3. 
         FIG. 46  illustrates sizes of symbol ranking tables. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     As described above, in the ASESS method, region detection of a signal which is obtained by cancelling a symbol candidate of each surviving path up to a previous stage, from a reception signal is performed. Then, in the ASESS method, a symbol candidate on a current rank of a surviving path having the minimum representative cumulative metric is set as a surviving candidate by using a symbol ranking table, so as to reduce the processing amount. The symbol ranking table is a table which stores a result obtained by ranking symbol candidates in the order of shorter distance from a region center to a symbol candidate, for each prepared region. 
     In the ASESS method, a symbol ranking table on the k-th stage become to be a table of which the number of words is equal to expression (33) and the bit width per word is equal to expression (34), in each modulation method. However, m denotes a modulation multi-level number of a modulation method.
 
2 2N     div   ×min( S   k   ,m )  (33)
 
log 2    m   (34)
 
     Here, examples of symbol ranking tables in related art are illustrated in  FIGS. 41 to 45 . Further, sizes of symbol ranking tables are illustrated in  FIG. 46 . Here, examples of symbol ranking tables having different N div  in the same modulation method are illustrated, but it is sufficient to obtain a symbol ranking table of at least one type of N div  in the same modulation method. 
     As illustrated in  FIGS. 41 to 46 , the size of a symbol ranking table is increased as the modulation multi-level number and the number of regions are increased. When the size of a symbol ranking table is increased, memory capacity of a device is increased. 
     The technique disclosed herein has made in view of the above description, and it is desirable to provide a wireless device, a wireless device control method, and a wireless device control program that realize reduction of the size of a symbol ranking table. 
     Embodiments of a wireless device, a wireless device control method, and a wireless device control program according to the present disclosure will be described in detail below with reference to the accompanying drawings. However, the present disclosure is not limited by these embodiments. 
     (Solving Aspect 1) 
     A basic idea of a first solving aspect of the present disclosure is first described. A current rank of each surviving path according to a related art example is first considered.  FIGS. 1A to 1C  illustrate a complementary cumulative distribution function (CCDF) of current ranks of respective surviving paths at stage end. More specifically,  FIGS. 1A to 1C  illustrate a CCDF of current ranks for every surviving path at the stage end when the number of transmission antennas is 4, the number of reception antennas is 4, a modulation method of transmission data of each of the transmission antennas is 64QAM, and the number of surviving candidates is S 1 =S 2 =S 3 =S 4 =64. However, only 10 surviving paths are illustrated in an ascending order of cumulative metrics up to a previous stage because a current rank of a surviving path of which a cumulative metric up to the previous stage is smaller tends to be larger. From  FIGS. 1A to 1C , it is understood that there is a small probability that a current rank has a large value. 
     Accordingly, in the first aspect, a surviving path of which a current rank is equal to or lower than a predetermined rank upper limit value MAX_RANK (&lt;m) and a representative cumulative metric has the minimum value is selected. Accordingly, the current rank of the surviving path is less than or equal to the MAX_RANK thereby satisfying the expression (35) for the number of words of a symbol ranking table. Therefore, according to the first aspect, it is possible to reduce the size of a symbol ranking table.
 
2 2N     div   ×MAX_RANK  (35)
 
     (Embodiment 1) 
     Embodiment 1 is an embodiment to which the first aspect is applied.  FIG. 2  illustrates the configuration of a MIMO system. As depicted in  FIG. 2 , the MIMO system includes a transmitter  100  and a receiver  200 . The transmitter  100  includes an error correction encode unit  102 , a modulation unit  104 , a plurality of transmission units  106 , and a plurality of transmission antennas  108 . 
     The error correction encode unit  102  performs error-correction-encode of transmission data. The modulation unit  104  performs modulation such as QPSK, 16QAM, and 64QAM so as to separate transmission data into streams. The transmission unit  106  up-converts a signal obtained by the modulation of the modulation unit  104  into a signal of a wireless frequency and simultaneously transmits the signal from the transmission antenna  108 . 
     The receiver  200  includes a plurality of reception antennas  202 , reception units  204 , a demodulation unit  208 , an error correction decode unit  214 , a central processing unit (CPU)  260 , and a memory  262 . The demodulation unit  208  includes a channel estimation unit  210  and a MIMO stream separation unit  212 . 
     The reception unit  204  converts a signal which is received at the reception antenna  202  into a baseband signal. The channel estimation unit  210  receives a pilot signal or the like which is transmitted from the transmitter  100 , so as to estimate a propagation path. The MIMO stream separation unit  212  performs stream separation processing by using a reception signal and a channel estimation value. The error correction decode unit  214  performs error-correction-decode of a separated stream. 
     The memory  262  includes a read only memory (ROM) which stores data for executing various functions of the receiver  200  and various types of programs for executing various functions of the receiver  200 . The memory  262  further includes a random access memory (RAM) which stores a program which is to be executed among the various types of programs which are stored in the ROM. 
     The CPU  260  is an arithmetic processing unit which executes various types of programs which are stored in the memory  262 . The CPU  260  executes the various types of programs which are stored in the memory  262 , so as to control the receiver  200 . Here, programs which are executed in the CPU  260  are not only stored in the memory  262  but also may be recorded in a distributable storage medium such as a compact disc (CD)-ROM and a memory medium so as to be read out of the storage medium and executed. Further, programs may be stored in a server which is connected via a network and the program may be set to be operated on the server, so as to provide a service to the receiver  200  which is connected via the network, depending on a request from the receiver  200  which is a request source. 
       FIG. 3  illustrates a configuration example of the MIMO stream separation unit of Embodiment 1. As depicted in  FIG. 3 , the MIMO stream separation unit  212  includes a QR decomposition unit  216 , a MIMO demodulation unit  222 , and a log likelihood ratio (LLR) calculation unit  254 . The QR decomposition unit  216  includes a QR decomposition processing unit  218  and a reception signal conversion unit  220 . The MIMO demodulation unit  222  includes a first stage processing unit  224 , a second stage processing unit  234 , . . . , and an N-th stage processing unit  244 . 
     The first stage processing unit  224  includes a region detection unit  226 , a surviving symbol selection unit  228 , a metric calculation unit  230 , and a symbol ranking table  232 . The second stage processing unit  234  includes a region detection unit  236 , a surviving symbol selection unit  238 , a metric calculation unit  240 , and a size reduction type symbol ranking table  242 . The N-th stage processing unit  244  includes a region detection unit  246 , a surviving symbol selection unit  248 , a metric calculation unit  250 , and a size reduction type symbol ranking table  252 . 
     The QR decomposition unit  216  performs QR decomposition to decompose a channel matrix into a unitary matrix Q and an upper triangular matrix R, as expressed in expression (36). 
     
       
         
           
             
               
                 
                   H 
                   = 
                   
                     QR 
                     = 
                     
                       
                         ( 
                         
                           
                             
                               
                                 q 
                                 11 
                               
                             
                             
                               
                                 q 
                                 12 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   1 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                 q 
                                 21 
                               
                             
                             
                               
                                 q 
                                 22 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   2 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                             
                               ⋮ 
                             
                             
                               ⋱ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   1 
                                 
                               
                             
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   2 
                                 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 q 
                                 
                                   N 
                                   , 
                                   N 
                                 
                               
                             
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         ( 
                         
                           
                             
                               
                                 r 
                                 11 
                               
                             
                             
                               
                                 r 
                                 12 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 r 
                                 
                                   1 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                 r 
                                 22 
                               
                             
                             
                               ⋯ 
                             
                             
                               
                                 r 
                                 
                                   2 
                                   , 
                                   N 
                                 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                   
                               
                             
                             
                               ⋱ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               O 
                             
                             
                               
                                   
                               
                             
                             
                               
                                 r 
                                 
                                   N 
                                   , 
                                   N 
                                 
                               
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   36 
                   ) 
                 
               
             
           
         
       
     
     Here, it is possible to set a diagonal element of the matrix R to a positive real number by appropriately selecting a unitary matrix Q. A unitary conversion unit multiplies a reception signal vector y by a Hermitian conjugate of the unitary matrix Q so as to obtain a unitary conversion vector z expressed as expression (37).
 
z=Q H y  (37)
 
     At this time, a relationship of expression (38) is established between the unitary conversion vector z and a transmission stream vector x. 
     
       
         
           
             
               
                 
                   
                     u 
                     N 
                   
                   = 
                   
                     
                       z 
                       N 
                     
                     
                       r 
                       
                         N 
                         , 
                         N 
                       
                     
                   
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
           
         
       
     
     The region detection unit  226  of the first stage performs region detection of the lowest stage by expression (39) so as to determine a region number ε (1)  of a region to which u N  belongs. 
     
       
         
           
             
               
                 
                   
                     u 
                     N 
                   
                   = 
                   
                     
                       z 
                       N 
                     
                     
                       r 
                       
                         N 
                         , 
                         N 
                       
                     
                   
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
           
         
       
     
     The surviving symbol selection unit  228  refers to a symbol ranking table Ω which stores a result of ranking of symbol candidates which are preliminarily ranked in the order of shorter distance from a region center to each symbol candidate c N,i  (i=1, 2, . . . , m N ) of a transmission signal x N , for each region number. Then, the surviving symbol selection unit  228  sets as many candidate replicas as S 1 , the number of surviving candidates from the upper order of the ranking, as surviving paths of the first stage. The surviving symbol selection unit  228  sets the surviving path as expression (40).
 
Π 1   (1) ( i )=Ω (m     N     ) (ε, i ),  i= 1, 2 , . . . , S   1   (40)
 
     Here, Π(k)(i) represents the i-th surviving path on the k-th stage. Π j   (k) (i) denotes a path on the j-th stage (=1, 2, . . . , k) of the i-th surviving path on the k-th stage. Further, Π a˜b   (k) (i) (a&lt;b) represents a partial path from the a-th stage to the b-th stage of the i-th surviving path on the k-th stage. For example, expression (42), expression (43), and expression (44) are obtained in a case of expression (41).
 
Π (4) ={(0,1,2,3),(0,2,1,1),(1,2,3,0),(2,0,0,1)}  (41)
 
Π (4) (2)=(0,2,1,1)  (42)
 
Π 3   (4) (3)=3  (43)
 
Π 1˜3 (1)=(0,1,2)  (44)
 
     The metric calculation unit  230  calculates a metric such as a squared Euclidean distance. In a case of a squared Euclidean distance, expression (45) is obtained. Here, Ω (4) , Ω (16) , and Ω (64)  respectively represent symbol ranking tables with respect to QPSK, 16QAM, and 64QAM.
 
 d   1 (Π 1   (1) ( i ))=| z   N   −r   N,N   c   N,Π     1       (1)     (i) | 2   , i= 1, 2 , . . . , S   1   (45)
 
     Expression (46) expresses a symbol number, which is stored in the symbol ranking table, on the i-th order of the ranking with respect to the region number ε (1) . Here, c N,i  denotes a signal point of a modulation method which is used in transmission of a transmission stream x N . Typical examples of the modulation method include QPSK, 16QAM, and 64QAM, but the embodiment is not limited to a specific modulation method.
 
Ω (m     N     ) (ε (1)   ,i )  (46)
 
     Processing on the following k-th stage (for example, the second stage) is described. The region detection unit on the k-th stage performs region detection by expression (47) in which respective candidate replicas of S k−1  surviving paths, which are survived on the k−1-th stage, are respectively cancelled from a reception signal Z N−k+1  which is the k-th lowest signal, so as to determine a region number ε (k) (i) of a region to which u expressed as expression (48) belongs. 
     
       
         
           
             
               
                 
                   
                     
                       
                         u 
                         
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                           , 
                           i 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ) 
                       
                     
                     = 
                     
                       
                         ( 
                         
                           
                             z 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 p 
                                 = 
                                 1 
                               
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 r 
                                 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 c 
                                 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     
                                       Π 
                                       p 
                                       
                                         ( 
                                         
                                           k 
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                         
                         ) 
                       
                       / 
                       
                         r 
                         
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                           , 
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                         
                       
                     
                   
                   , 
                 
               
               
                 
                   ( 
                   47 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         i 
                         = 
                         1 
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         S 
                         
                           k 
                           - 
                           1 
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         u 
                         
                           
                             N 
                             - 
                             k 
                             + 
                             1 
                           
                           , 
                           i 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   48 
                   ) 
                 
               
             
           
         
       
     
     A surviving symbol selection unit (for example, the surviving symbol selection unit  238 ) adaptively selects a surviving path on the k-th stage as following. The surviving symbol selection unit first initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage so as to obtain expression (49), expression (50), and expression (51).
 
 E ( i ):= d   k−1 (Π (k−1) ( i ))  (49)
 
ρ( i ):=1  (50)
 
q:=1  (51)
 
     The surviving symbol selection unit selects a candidate replica on the ρ(i min )-th order of the ranking of i min  at which ρ(i)≦MAX_RANK k  is satisfied and E(i) has the minimum value, from the size reduction type symbol ranking table. The surviving symbol selection unit sets the q-th surviving path on the k-th stage as expression (52) and expression (53). 
     
       
         
           
             
               
                 
                   
                     
                       
                         Π 
                         
                           
                             l 
                             ~ 
                             k 
                           
                           - 
                           1 
                         
                         
                           ( 
                           k 
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         Π 
                         
                           ( 
                           
                             k 
                             - 
                             1 
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           i 
                           min 
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         Π 
                         k 
                         
                           ( 
                           k 
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         q 
                         ) 
                       
                     
                     = 
                     
                       
                         Ω 
                         
                           ( 
                           
                             m 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           ) 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             
                               ɛ 
                               
                                 ( 
                                 k 
                                 ) 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 min 
                               
                               ) 
                             
                           
                           , 
                           
                             ρ 
                             ⁡ 
                             
                               ( 
                               
                                 i 
                                 min 
                               
                               ) 
                             
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   52 
                   ) 
                 
               
             
             
               
                 
                   
                     i 
                     min 
                   
                   = 
                   
                     
                       arg 
                       
                         
                           ρ 
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ≤ 
                         
                           
                             MAX 
                             ⁢ 
                             _ 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             RANK 
                             k 
                           
                         
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         min 
                         ⁡ 
                         
                           [ 
                           
                             E 
                             ⁡ 
                             
                               ( 
                               i 
                               ) 
                             
                           
                           ] 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   53 
                   ) 
                 
               
             
           
         
       
     
     Here, MAX_RANK k  is a predetermined rank upper limit value of the k-th stage. MAX_RANK k  may be set to have a different value for every modulation method of the k-th stage. Further, it is assumed that S k−1 ×MAX_RANK k ≧S k  is satisfied so as to enable selection of S k  surviving candidates. 
     A metric calculation unit (for example, the metric calculation unit  240 ) calculates a cumulative metric as expression (54). 
     
       
         
           
             
               
                 
                   
                     
                       d 
                       k 
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           Π 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       
                         d 
                         
                           k 
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               
                                 k 
                                 - 
                                 1 
                               
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             
                               i 
                               min 
                             
                             ) 
                           
                         
                         ) 
                       
                     
                     + 
                     
                       
                          
                         
                           
                             z 
                             
                               N 
                               - 
                               k 
                               + 
                               1 
                             
                           
                           - 
                           
                             
                               ∑ 
                               
                                 p 
                                 = 
                                 1 
                               
                               
                                 k 
                                 - 
                                 1 
                               
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 r 
                                 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                 
                               
                               ⁢ 
                               
                                 c 
                                 
                                   
                                     N 
                                     - 
                                     p 
                                     + 
                                     1 
                                   
                                   , 
                                   
                                     
                                       Π 
                                       p 
                                       
                                         ( 
                                         k 
                                         ) 
                                       
                                     
                                     ⁡ 
                                     
                                       ( 
                                       q 
                                       ) 
                                     
                                   
                                 
                               
                             
                           
                           - 
                           
                             
                               r 
                               
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                                 , 
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                               
                             
                             ⁢ 
                             
                               c 
                               
                                 
                                   N 
                                   - 
                                   k 
                                   + 
                                   1 
                                 
                                 , 
                                 
                                   
                                     Π 
                                     k 
                                     
                                       ( 
                                       k 
                                       ) 
                                     
                                   
                                   ⁡ 
                                   
                                     ( 
                                     q 
                                     ) 
                                   
                                 
                               
                             
                           
                         
                          
                       
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   54 
                   ) 
                 
               
             
           
         
       
     
     Then, the metric calculation unit updates the cumulative metric as expression (55), expression (56), and expression (57).
 
 E ( i   min ):= d   k (Π (k) ( q ))  (55)
 
ρ( i   min ):=ρ( i   min )+1  (56)
 
 q:=q+ 1  (57)
 
     The metric calculation unit performs the above-mentioned processing until q reaches the number S k  of surviving paths of the k-th stage. Each stage processing unit performs similar processing up to the N-th stage. 
     Region detection and a size reduction type symbol ranking table are now described in detail. The symbol ranking table of the first stage processing unit may sufficiently have only a sub-set part of S 1  columns on the left side of the symbol ranking tables depicted on  FIGS. 41 to 45 . 
     A size reduction type symbol ranking table of the k-th stage and region detection are described in detail below. As a setting value of MAX_RANK k , examples of expression (58), expression (59), and expression (60) are illustrated. Here, an example of N=4 is illustrated. Further, this parameter is merely an example and other setting values may be used.
 
MAX_RANK 2   (QPSK) =MAX_RANK 3   (QPSK) =MAX_RANK 4   (QPSK) =3  (58)
 
MAX_RANK 2   (16QAM) =MAX_RANK 3   (16QAM) =MAX_RANK 4   (16QAM) =8  (59)
 
MAX_RANK 2   (64QAM) =MAX_RANK 3   (64QAM) =MAX_RANK 4   (64QAM) =16  (60)
 
     Description of region detection here is common in every stage, so that an index of a signal for performing region detection is omitted and a signal is denoted as u.  FIG. 4  is a flowchart of region detection. The region detection unit first sets t to 2 and sets χmod as expression (61) (S 101 ). 
     
       
         
           
             
               
                 
                   
                     χ 
                     mod 
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             / 
                             
                               
                                 2 
                                 , 
                               
                             
                           
                         
                         
                           
                             for 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             QPSK 
                           
                         
                       
                       
                         
                           
                             
                               2 
                               / 
                               
                                 10 
                               
                             
                             , 
                           
                         
                         
                           
                             for 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             16 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             QAM 
                           
                         
                       
                       
                         
                           
                             
                               4 
                               / 
                               
                                 42 
                               
                             
                             , 
                           
                         
                         
                           
                             for 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             64 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             QAM 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   61 
                   ) 
                 
               
             
           
         
       
     
     Further, the region detection unit determines positive/negative of a real part and an imaginary part of u (1) =u (positive/negative of an IQ component) so as to determine which quadrant u belongs to, in the first-time detection (S 102 ). The region detection unit determines whether t&gt;N div  is satisfied or not (S 103 ). When t&gt;N div  is satisfied (S 103 , Yes), the region detection unit determines a region number (S 104 ). When t&gt;N div  is not satisfied (S 103 , No), the region detection unit moves an origin to a center (expression (62)) of the quadrant which is determined on the first-time detection (S 105 ). Further, the region detection unit performs quadrant detection of u (2)  which is obtained by moving the origin to the center (expression (62)) of the quadrant which is determined on the first-time detection, in the second-time detection (S 106 ). Here, sign(x) is expressed as expression (63). 
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       sign 
                       ⁢ 
                       
                         
                           { 
                           
                             Re 
                             ⁡ 
                             
                               ( 
                               u 
                               ) 
                             
                           
                           } 
                         
                         · 
                         
                           χ 
                           mod 
                         
                       
                     
                     , 
                     
                       sign 
                       ⁢ 
                       
                         
                           { 
                           
                             Im 
                             ⁡ 
                             
                               ( 
                               u 
                               ) 
                             
                           
                           } 
                         
                         · 
                         
                           χ 
                           mod 
                         
                       
                     
                   
                   ) 
                 
               
               
                 
                   ( 
                   62 
                   ) 
                 
               
             
             
               
                 
                   
                     sign 
                     ⁡ 
                     
                       ( 
                       x 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             1 
                             , 
                           
                         
                         
                           
                             x 
                             ≥ 
                             0 
                           
                         
                       
                       
                         
                           
                             
                               - 
                               1 
                             
                             , 
                           
                         
                         
                           
                             x 
                             &lt; 
                             0 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   63 
                   ) 
                 
               
             
           
         
       
     
     Subsequently, the region detection unit increments t and sets χmod to χmod/2 (S 107 ). Then, the region detection unit determines whether t≦N div  is satisfied or not (S 108 ). When t≦N div  is satisfied (S 108 , Yes), the region detection unit returns to S 105  and repeats the processing. Here, on t-th time detection, the region detection unit performs quadrant detection of u (t)  which is obtained by moving the origin to a center (expression (64)) of a quadrant which is determined on the t−1-th time detection. 
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         ∑ 
                         
                           p 
                           = 
                           1 
                         
                         
                           t 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         sign 
                         ⁢ 
                         
                           
                             { 
                             
                               Re 
                               ⁡ 
                               
                                 ( 
                                 
                                   u 
                                   
                                     ( 
                                     p 
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             } 
                           
                           · 
                           
                             
                               χ 
                               mod 
                             
                             / 
                             
                               2 
                               
                                 p 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                     , 
                     
                       
                         ∑ 
                         
                           p 
                           = 
                           1 
                         
                         
                           t 
                           - 
                           1 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         sign 
                         ⁢ 
                         
                           
                             { 
                             
                               Im 
                               ⁡ 
                               
                                 ( 
                                 
                                   u 
                                   
                                     ( 
                                     p 
                                     ) 
                                   
                                 
                                 ) 
                               
                             
                             } 
                           
                           · 
                           
                             
                               χ 
                               mod 
                             
                             / 
                             
                               2 
                               
                                 p 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   ) 
                 
               
               
                 
                   ( 
                   64 
                   ) 
                 
               
             
           
         
       
     
     When t≦N div  is not satisfied (S 108 , No), the region detection unit determines a region number (S 109 ). That is, the region detection unit repeats the above-mentioned processing N div  times in sequence so as to determine which region u belongs to among regions the number of which is expressed by expression (65).
 
 N   area =2 2N     div     (65)
 
     Here, an example of a way of assigning a region number of N div =1 in QPSK is described.  FIG. 5  illustrates an example of region detection in QPSK (N div =1). Further,  FIG. 6  illustrates an example of a size reduction type symbol ranking table in QPSK and N div =1. 
     Symbol numbers are held for every region in the order of shorter distances between a representative point of a region (a symbol position included in a region) and a symbol. A representative point is expressed by expression (66) by using a region number E. Here, bit(ε,n) in expression (67) denotes a bit value on the N-th (1 to 2N div ) bit from MSB of ε which is expressed by a bit width of 2N div [bit]. In this case, a representative point of each region is same as a symbol position which belongs to each region. 
     
       
         
           
             
               
                 
                   ( 
                   
                     
                       
                         ∑ 
                         
                           p 
                           = 
                           1 
                         
                         
                           N 
                           div 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         bit_sign 
                         ⁢ 
                         
                           
                             ( 
                             
                               ɛ 
                               , 
                               
                                 
                                   2 
                                   ⁢ 
                                   p 
                                 
                                 - 
                                 1 
                               
                             
                             ) 
                           
                           · 
                           
                             
                               χ 
                               mod 
                             
                             / 
                             
                               2 
                               
                                 p 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                     , 
                     
                       
                         ∑ 
                         
                           p 
                           = 
                           1 
                         
                         
                           N 
                           div 
                         
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         bit_sign 
                         ⁢ 
                         
                           
                             ( 
                             
                               ɛ 
                               , 
                               
                                 2 
                                 ⁢ 
                                 p 
                               
                             
                             ) 
                           
                           · 
                           
                             
                               χ 
                               mod 
                             
                             / 
                             
                               2 
                               
                                 p 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                     
                   
                   ) 
                 
               
               
                 
                   ( 
                   66 
                   ) 
                 
               
             
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       bit_sign 
                       ⁢ 
                       
                         ( 
                         
                           ɛ 
                           , 
                           n 
                         
                         ) 
                       
                     
                     = 
                     
                       { 
                       
                         
                           
                             
                               1 
                               , 
                             
                           
                           
                             
                               
                                 bit 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ɛ 
                                     , 
                                     n 
                                   
                                   ) 
                                 
                               
                               = 
                               0 
                             
                           
                         
                         
                           
                             
                               
                                 - 
                                 1 
                               
                               , 
                             
                           
                           
                             
                               
                                 bit 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ɛ 
                                     , 
                                     n 
                                   
                                   ) 
                                 
                               
                               = 
                               1 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   67 
                   ) 
                 
               
             
           
         
       
     
     Here, MAX_RANK (QPSK)   k =3 is set, so that only symbol numbers up to the third order in the ranking are held. Therefore, as depicted in  FIG. 6 , the number of words of the table is 4 (the number of regions)×3(MAX_RANK (QPSK)   k )=12. Thus, the table size is ¾ times as large as that of related art. Here, in a case of N div =1, it is difficult to discriminate between a symbol which is the second closest to a representative point of a region and a symbol which is the third closest to the representative point. For example, in a case of a region  0 , it is difficult to determine which of 10 (decimal: 2) and 01 (decimal: 1) is closer, so that a table may be arbitrarily formed in advance to determine which goes to the second order or the third order. Further, the way of assigning a region number is an example and a region number may be arbitrarily assigned. In this case, rows of the size reduction type symbol ranking table depicted in  FIG. 6  are merely exchanged. The same goes for the following examples. 
     Here, in the example in QPSK and N div =1, it is difficult to discriminate between a symbol which is the second closest to a representative point of a region and a symbol which is the third closest to the representative point, so that a table may be arbitrarily formed to determine which goes to the second order or the third order. Further, accuracy of the ranking may be improved by increasing the number N div  of times of quadrant detection, as well. 
     An example in N div =2 in QPSK is described.  FIG. 7  illustrates an example of region detection in QPSK (N div =2). In this case, a representative point of each region is any one of (±{1,3}/2√2, ±{1,3}/2√2). 
     Further, a size reduction type symbol ranking table is described.  FIG. 8  illustrates an example of a size reduction type symbol ranking table in QPSK and N div =2. In regions  1 ,  2 ,  4 ,  7 ,  8 ,  11 ,  13 , and  14 , a symbol which is the second closest to a representative point of a region and a symbol which is the third closest to the representative point are discriminated from each other. Thus, accuracy of the size reduction type symbol ranking table is improved. Further, MAX_RANK (QPSK)   k =3 is set, so that only symbol numbers up to the third order in the ranking are held. 
     A way of assigning a region number and an example of a size reduction type symbol ranking table in 16QAM and N div =2 are now described. 
       FIG. 9  illustrates an example of 16QAM (N div =2).  FIG. 10  illustrates an example of a size reduction type symbol ranking table in 16QAM (N div =2). 
     Outline digits in symbols in  FIG. 9  represent symbol numbers (obtained by converting bit columns into decimal numbers). In this case, a representative point of each region is same as a symbol position which is included in the region. As depicted in  FIG. 10 , MAX_RANK (16QAM)   k =8 is set, so that the size reduction type symbol ranking table holds only symbol numbers up to the eighth order of the ranking. 
     A way of assigning a region number and an example of a size reduction type symbol ranking table in 16QAM and N div =3 are now described.  FIG. 11  illustrates an example of 16QAM (N div =3).  FIG. 12  illustrates an example of a size reduction type symbol ranking table in 16QAM (N div =3). 
     In this case, a representative point of each region is any one of (±{1,3,5,7}/2√10, ±{1,3,5,7}/2√10). As depicted in  FIG. 12 , MAX_RANK (16QAM)   k =8 is set, so that the size reduction type symbol ranking table holds only symbol numbers up to the eighth order of the ranking. 
     A way of assigning a region number and an example of a size reduction type symbol ranking table in 64QAM and N div =3 are now described.  FIG. 13  illustrates an example of 64QAM (N div =3).  FIG. 14  illustrates an example of a size reduction type symbol ranking table in 64QAM and N div =3. 
     In this case, a representative point of each region is same as a symbol position which is included in the region. As depicted in  FIG. 14 , MAX_RANK (16QAM)   k =32 is set, so that the size reduction type symbol ranking table holds only symbol numbers up to the 32nd order of the ranking. 
     As described above, it is understood that it is sufficient for the size reduction type symbol ranking table to have only a sub-set part of MAX_RANK k  columns on the left side of the symbol ranking tables depicted in  FIGS. 41 to 45 . That is, it is understood that the size reduction type symbol ranking table may be easily applied to a case of a setting value which is different from a setting value example of MAX_RANK k  illustrated in this example. 
     A concrete example of region detection is now described by taking a case of 64QAM as an example.  FIGS. 15A to 15C  illustrate an example of region detection. In the example of  FIGS. 15A to 15C , u are denoted by a star and N div =3 holds. As the lower left of  FIGS. 15A to 15C , a region is divided into 64 regions and region numbers are assigned to the regions as numbers of the upper left in the regions. Since both of a real part and an imaginary part are negative in positive/negative determination in the first-time quadrant detection, it is determined that u belongs to the fourth quadrant. Then, since it is determined that u belongs to the fourth quadrant in the first-time quadrant detection, an origin is moved to (−4/√42, −4/√42). Expression (68) is obtained by subtracting a coordinate which is to be the next origin from u.
 
 u   (2)   ={Re ( u )+4/√{square root over (42)}}+ j{Im ( u )+4/√{square root over (42)}}  (68)
 
     Positive/negative determination of a real part and an imaginary part of u (2)  is performed similarly in the second-time quadrant detection, and the first quadrant is detected as a result of the determination. The origin is moved to (−2/√42, −2/√42) as is the case with the first-time quadrant detection. The third-time quadrant detection is performed and the third quadrant is detected. As a result, it is determined that u belongs to a region of region number  50 . 
     Returning to the description of  FIG. 3 , the LLR calculation unit  254  calculates a bit LLR for every transmission stream. The LLR calculation unit  254  first searches the minimum value of a cumulative metric so as to set a surviving path of which a cumulative metric has the minimum value, as a combination of maximum likelihood symbols. A bit LLR of the N-th bit of the first stream x l  is difference between a sum metric with respect to the maximum likelihood symbol combination and the minimum value of a cumulative metric with respect to a symbol having a reversal value of the N-th bit of the maximum likelihood symbol. Specifically, a bit LLR is expressed as expression (72) under conditions of expression (69), expression (70), and expression (71). 
     
       
         
           
             
               
                 
                   
                     Π 
                     
                       
                         ( 
                         N 
                         ) 
                       
                       , 
                       ML 
                     
                   
                   = 
                   
                     arg 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       min 
                       [ 
                       
                         
                           d 
                           N 
                         
                         ( 
                         
                           
                             Π 
                             
                               ( 
                               N 
                               ) 
                             
                           
                           ⁡ 
                           
                             ( 
                             i 
                             ) 
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   69 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       d 
                       
                         l 
                         , 
                         min 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           b 
                           n 
                         
                         = 
                         
                           bit 
                           ( 
                           
                             
                               Π 
                               l 
                               
                                 
                                   ( 
                                   N 
                                   ) 
                                 
                                 , 
                                 ML 
                               
                             
                             , 
                             n 
                           
                           ) 
                         
                       
                       ) 
                     
                   
                   = 
                   
                     d 
                     ⁡ 
                     
                       ( 
                       
                         Π 
                         
                           
                             ( 
                             N 
                             ) 
                           
                           , 
                           ML 
                         
                       
                       ) 
                     
                   
                 
               
               
                 
                   ( 
                   70 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       d 
                       
                         l 
                         , 
                         min 
                       
                     
                     ⁡ 
                     
                       ( 
                       
                         
                           b 
                           n 
                         
                         = 
                         
                           invbit 
                           ⁡ 
                           
                             ( 
                             
                               
                                 Π 
                                 l 
                                 
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                   , 
                                   ML 
                                 
                               
                               , 
                               n 
                             
                             ) 
                           
                         
                       
                       ) 
                     
                   
                   = 
                   
                     
                       min 
                       
                         
                           bit 
                           ⁡ 
                           
                             ( 
                             
                               
                                 Π 
                                 1 
                                 
                                   ( 
                                   N 
                                   ) 
                                 
                               
                               , 
                               n 
                             
                             ) 
                           
                         
                         = 
                         
                           invbit 
                           ⁡ 
                           
                             ( 
                             
                               
                                 Π 
                                 l 
                                 
                                   
                                     ( 
                                     N 
                                     ) 
                                   
                                   , 
                                   ML 
                                 
                               
                               , 
                               n 
                             
                             ) 
                           
                         
                       
                     
                     ⁢ 
                     
                       [ 
                       
                         d 
                         ⁡ 
                         
                           ( 
                           
                             Π 
                             l 
                             
                               ( 
                               N 
                               ) 
                             
                           
                           ) 
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   71 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       LLR 
                       l 
                     
                     ⁡ 
                     
                       ( 
                       n 
                       ) 
                     
                   
                   = 
                   
                     
                       
                         d 
                         
                           l 
                           , 
                           min 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             b 
                             n 
                           
                           = 
                           1 
                         
                         ) 
                       
                     
                     - 
                     
                       
                         d 
                         
                           l 
                           , 
                           min 
                         
                       
                       ⁡ 
                       
                         ( 
                         
                           
                             b 
                             n 
                           
                           = 
                           0 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   ( 
                   72 
                   ) 
                 
               
             
           
         
       
     
     Here, l denotes a stream number, and bit(x,n) and invbit(x,n) respectively denote the N-th bit value and the N-th reversal bit value of x. Though a bit LLR is difference of metrics in the above description, a bit LLR may be expressed as expression (73) by square roots.
 
LLR l ( n )=√{square root over ( d   l,min ( b   n =1))}−√{square root over ( d   l,min ( b= 0))}  (73)
 
     A flowchart of the MIMO stream separation unit of Embodiment 1 is now described.  FIG. 16  is a flowchart of Embodiment 1. As depicted in  FIG. 16 , the QR decomposition processing unit  218  performs QR decomposition (S 201 ). Subsequently, the reception signal conversion unit  220  performs reception signal conversion and calculates a unitary conversion vector z (S 202 ). Then, the first stage processing unit  224  performs first stage processing (S 203 ). The first stage processing will be described in detail later. 
     Subsequently, the MIMO demodulation unit  222  sets k to 2 (S 204 ). Then, the k-th stage processing unit performs k-th stage processing (S 205 ). The k-th stage processing will be described in detail later. Subsequently, the MIMO demodulation unit  222  increments k (S 206 ) so as to determine whether k≦N is satisfied or not (S 207 ). 
     When k≦N is satisfied (S 207 , Yes), the MIMO demodulation unit  222  returns to S 205  and repeats the processing. On the other hand, when k≦N is not satisfied (S 207 , No), the LLR calculation unit  254  calculates a LLR as described above (S 208 ). 
     A flowchart of the first stage processing is now described.  FIG. 17  is a flowchart of the first stage processing. As depicted in  FIG. 17 , the region detection unit  226  detects a region of u N  (S 301 ). Subsequently, the first stage processing unit  224  sets q to 1 (S 302 ). Then, the surviving symbol selection unit  228  selects a surviving symbol (S 303 ). The selection of a surviving symbol will be described later. 
     Subsequently, the metric calculation unit  230  calculates a metric as described above (S 304 ). Then, the first stage processing unit  224  increments q (S 305 ) so as to determine whether q≦S 1  is satisfied or not (S 306 ). When q≦S 1  is satisfied (S 306 , Yes), the first stage processing unit  224  returns to S 303  and repeats the processing. On the other hand, when q≦S 1  is not satisfied (S 306 , No), the first stage processing unit  224  ends the processing. 
     A flowchart of surviving symbol selection of the first stage processing is now described.  FIG. 18  is a flowchart of the surviving symbol selection of the first stage processing. As depicted in  FIG. 18 , the surviving symbol selection unit  228  selects a symbol in the ε (1) -th row and q-th column of a symbol ranking table Ω (mk)  so as to set the symbol as a surviving path (S 401 ). 
     A flowchart of the k-th stage processing is now described.  FIG. 19  is flowchart of the k-th stage processing. As depicted in  FIG. 19 , the k-th stage processing unit sets i to 1 (S 501 ). Subsequently, the region detection unit performs region detection as expression (47) (S 502 ). Then, the region detection unit increments i (S 503 ). After that, the region detection unit determines whether i≦S k−1  is satisfied or not (S 504 ). When i≦S k−1  is satisfied (S 504 , Yes), the region detection unit returns to S 502  and repeats the processing. 
     On the other hand, when i≦S k−1  is not satisfied (S 504 , No), the surviving symbol selection unit initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived in the k−1-th stage as expression (49), expression (50), and expression (51) (S 505 ). Subsequently, the surviving symbol selection unit selects i min  at which ρ(i)≦MAX_RANK k  is satisfied and the representative cumulative metric E(i) has the minimum value (S 506 ). 
     Then, the surviving symbol selection unit selects a surviving symbol (S 507 ). The selection of a surviving symbol will be described later. Subsequently, the metric calculation unit calculates a cumulative metric as expression (54) (S 508 ). Then, the metric calculation unit updates the cumulative metric as expression (55), expression (56), and expression (57) (S 509 ). 
     Subsequently, the metric calculation unit determines q≦S k  is satisfied or not (S 510 ). When q≦S k  is satisfied (S 510 , Yes), the surviving symbol selection unit returns to S 506  and repeats the processing. On the other hand, when q≦S k  is not satisfied (S 510 , No), the metric calculation unit ends the processing. 
     A flowchart of the surviving symbol selection in the k-th stage processing is now described.  FIG. 20  is a flowchart of the surviving symbol selection in the k-th stage processing. As depicted in  FIG. 20 , the surviving symbol selection unit adds a symbol in the ε (k) (i min )-th row and ρ(i min )-th column of the size reduction type symbol ranking table Ω to surviving paths (S 601 ). 
     As described above, according to Embodiment 1, a current rank of each surviving path does not become larger than the predetermined rank upper limit value MAX_RANK, so that it is sufficient for the symbol ranking table to hold only symbol candidates which are equal to or smaller than the MAX_RANK. As a result, according to Embodiment 1, it is possible to reduce the size of a symbol ranking table compared to related art. Here, MAX_RANK, and N div  are not limited to the example described in the embodiment. 
     (Solving Aspect 2) 
     A basic idea of a second solving aspect of the present disclosure is now described. In the second aspect, a symbol ranking table is separated into a symbol higher order ranking table which holds symbol candidates which are placed on rank orders higher than a certain rank order ρ th  in ranking and a symbol lower order ranking table which holds symbol candidates which are placed on rank orders equal to or lower than ρ th  in the ranking. Further, in the second aspect, the symbol lower order ranking table holds symbol candidates in the order of shorter distances from a representative point of N adj  regions which are adjacent to each other. Accordingly, it is possible to reduce the number of words of the symbol lower order ranking table and thus reduce the table size. 
       FIG. 21  schematically illustrates the second aspect. As depicted in  FIG. 21 , in a case where the number of regions is 64 in 16QAM, for example, higher order symbol candidates on the first to eighth orders are common in regions  0 ,  1 ,  2 , and  3 , and lower order symbol candidates on the eighth to 16th orders are also common. In the second aspect, regarding symbol candidates on higher orders, symbol candidates which are ranked for respective regions are held in the symbol higher order ranking table in order to maintain ranking accuracy. Further, in the second aspect, regarding symbol candidates on lower orders, ranking accuracy is reduced and symbol candidates are held in the symbol lower order ranking table in the order of shorter distances from a representative point of adjacent regions for every group of adjacent regions. 
     (Embodiment 2) 
     Embodiment 2 is an embodiment to which the second aspect is applied.  FIG. 22  illustrates a configuration example of a MIMO stream separation unit of Embodiment 2. As depicted in  FIG. 22 , a MIMO stream separation unit  312  includes a QR decomposition unit  316 , a MIMO demodulation unit  322 , and a LLR calculation unit  354 . The QR decomposition unit  316  includes a QR decomposition processing unit  318  and a reception signal conversion unit  320 . The MIMO demodulation unit  322  includes a first stage processing unit  324 , a second stage processing unit  334 , . . . , and an N-th stage processing unit  344 . 
     The first stage processing unit  324  includes a region detection unit  326 , a surviving symbol selection unit  328 , a metric calculation unit  330 , a symbol higher order ranking table  331 , and a symbol lower order ranking table  332 . The second stage processing unit  334  includes a region detection unit  336 , a surviving symbol selection unit  338 , a metric calculation unit  340 , a symbol higher order ranking table  341 , and a symbol lower order ranking table  342 . The N-th stage processing unit  344  includes a region detection unit  346 , a surviving symbol selection unit  348 , a metric calculation unit  350 , a symbol higher order ranking table  351 , and a symbol lower order ranking table  352 . 
     As depicted in  FIG. 22 , Embodiment 2 is different from Embodiment 1 in that the symbol ranking table  232  and the size reduction type symbol ranking tables  242  and  252  of Embodiment 1 are exchanged into the symbol higher order ranking tables  331 ,  341 , and  351  and the symbol lower order ranking tables  332 ,  342 , and  352 . Accordingly, description of configurations same as those of Embodiment 1 is arbitrarily omitted and the configuration different from Embodiment 1 is mainly described. 
     The surviving symbol selection unit  328  refers to the symbol higher order ranking table  331  (Ω 1 ) or the symbol lower order ranking table  332  (Ω 2 ) and sets as many candidate replicas as S 1 , the number of surviving candidates from the higher order in the ranking, as surviving paths of the first stage. The surviving path is expressed by expression (74). 
     
       
         
           
             
               
                 
                   
                     
                       Π 
                       1 
                       
                         ( 
                         1 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   Ω 
                                   1 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ɛ 
                                     , 
                                     i 
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               ≤ 
                               
                                 ρ 
                                 th 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Ω 
                                   2 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       ⌊ 
                                       
                                         ɛ 
                                         / 
                                         
                                           N 
                                           adj 
                                         
                                       
                                       ⌋ 
                                     
                                     , 
                                     
                                       i 
                                       - 
                                       
                                         ρ 
                                         th 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               &gt; 
                               
                                 ρ 
                                 th 
                               
                             
                           
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                         i 
                         = 
                         1 
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         S 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   74 
                   ) 
                 
               
             
           
         
       
     
     A surviving symbol selection unit of a k-th stage processing unit adaptively selects a surviving path on the k-th stage as following. The surviving symbol selection unit first initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage so as to obtain expression (75), expression (76), and expression (77).
 
 E ( i ):= d   k−1 (Π (k−1) ( i ))  (75)
 
ρ( i ):=1  (76)
 
q:=1  (77)
 
     The surviving symbol selection unit selects a candidate replica on the ρ(i min )-th order in the ranking of i min  at which ρ(i)≦m N−k+1  is satisfied and E(i) has the minimum value, from the symbol higher order ranking table Ω 1  or the symbol lower order ranking table Ω 2 . Then, the surviving symbol selection unit sets the q-th surviving path on the k-th stage as expression (78). 
     
       
         
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         
                           Π 
                           
                             
                               l 
                               ~ 
                               k 
                             
                             - 
                             1 
                           
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         
                           Π 
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             i 
                             min 
                           
                           ) 
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         
                           Π 
                           k 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         { 
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         1 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             
                                               ɛ 
                                               
                                                 ( 
                                                 k 
                                                 ) 
                                               
                                             
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                           , 
                                           
                                             ρ 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     ≤ 
                                     
                                       ρ 
                                       th 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         2 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ⌊ 
                                             
                                               
                                                 
                                                   ɛ 
                                                   
                                                     ( 
                                                     k 
                                                     ) 
                                                   
                                                 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     i 
                                                     min 
                                                   
                                                   ) 
                                                 
                                               
                                               / 
                                               
                                                 N 
                                                 adj 
                                               
                                             
                                             ⌋ 
                                           
                                           , 
                                           
                                             
                                               ρ 
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   i 
                                                   min 
                                                 
                                                 ) 
                                               
                                             
                                             - 
                                             
                                               ρ 
                                               th 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     &gt; 
                                     
                                       ρ 
                                       th 
                                     
                                   
                                 
                               
                             
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               i 
                               min 
                             
                           
                           = 
                           
                             
                               arg 
                               
                                 
                                   ρ 
                                   ⁡ 
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                                 ≤ 
                                 
                                   m 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 min 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     E 
                                     ⁡ 
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                   ] 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   78 
                   ) 
                 
               
             
           
         
       
     
     The symbol higher order ranking table and the symbol lower order ranking table are now described in detail. In a case of QPSK and N div =2, as depicted in  FIGS. 42 and 7 , symbol candidates included from the first order to the third order of the ranking are common among four regions which are adjacent to each other and it is apparent that symbol candidates on the fourth order are common in four regions which are adjacent to each other as well. Therefore, an example of a case in ρ th =3 and N adj =4 is illustrated in  FIGS. 23A and 23B .  FIGS. 23A and 23B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table in QPSK and N djv =2. As depicted in  FIGS. 23A and 23B , it is understood that the total number of words of the symbol higher order ranking table and the symbol lower order ranking table is 16×3+4×1=52 and the table size is 52/64 compared to the related art example. 
     A table example and a table designing method when ρ th =8 and N adj =4 in a case of 16QAM and N div =3 is now described. First, regions  0 ,  1 ,  2 , and  3  are considered. Referring to  FIG. 44 , symbol candidates included from the first order to the eighth order in the ranking are common. Further, symbol candidates included from the ninth order to the 16th order in the ranking are also common. The symbol lower order ranking table is designed in the order of shorter distances from a representative point (a position of a symbol number  3 ) of four regions (regions  0 ,  1 ,  2 ,  3 ) which are adjacent to each other. 
     Subsequently, regions  4 ,  5 ,  6 , and  7  are considered. Referring to  FIG. 44 , symbol candidates included from the first order to the eighth order in the ranking of each region are; 
     region  4 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  7 ,  8 ), 
     region  5 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  5 ,  6 ,  7 ), 
     region  6 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 ,  9 ), and 
     region  7 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  7 ,  8 ). 
     Since symbol candidates are not completely common among regions unlike the case of the regions  0 ,  1 ,  2 , and  3 , two numbers among symbol numbers  5 ,  7 ,  8 , and  9  have to be migrated into the symbol lower order ranking table so as to make symbol candidates common. In this example, a square error with respect to an order in an original symbol ranking table ( FIG. 44 ) is reduced. 
     When it is assumed that a symbol number has become to be placed on the ninth order which is the highest order of the symbol lower order ranking table by migrating the symbol numbers into the symbol lower order ranking table, (9-8)^2=1 is obtained because the symbol number  5  of the region  5  is placed on the eighth order. The symbol number  7  of the region  4  is placed on the seventh order, the symbol number  7  of the region  5  is placed on the seventh order, and the symbol number  7  of the region  7  is placed on the eighth order, so that (9-7)^2+(9-7)^2+(9-8)^2=9 is obtained. 
     The symbol number  8  of the region  4  is placed on the eighth order, the symbol number  8  of the region  5  is placed on the ninth order, and the symbol number  8  of the region  7  is placed on the seventh order, so that (9-8)^2+(9-9)^2+(9-7)^2=5 is obtained. The symbol number  9  of the region  6  is placed on the eighth order, so that (9-8)^2=1 is obtained. 
     In order to reduce a square error, it is favorable that the symbol numbers  7  and  8  are left in the symbol higher order ranking table and the symbol numbers  5  and  9  are migrated into the symbol lower order ranking table. Accordingly, tables are designed such that the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  7 , and  8  are held in the symbol higher order ranking table in the order of shorter distance from a representative point of each region and symbol numbers other than the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  7 , and  8  are held in the symbol lower order ranking table in the order of shorter distance from a representative point (symbol number  2 ) of the four regions (regions  4 ,  5 ,  6 , and  7 ) which are adjacent to each other. 
     In a similar manner, regarding the regions  8 ,  9 ,  10 , and  11 , symbol numbers included from the first order to the eighth order in the ranking are; 
     region  8 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  8 ,  9 ,  11 ), 
     region  9 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 ,  9 ), 
     region  10 : symbol number ( 0 ,  1 ,  2 ,  3 ,  8 ,  9 ,  10 ,  11 ), and 
     region  11 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  8 ,  9 ,  11 ). 
     Therefore, two symbol numbers among the symbol numbers  4 ,  6 ,  10 , and  11  have to be migrated into the symbol lower order ranking table. In a similar manner, 
     symbol number  4 : (9-7)^2+(9-7)^2+(9-7)^2=12, 
     symbol number  6 : (9-8)^2=1, 
     symbol number  10 : (9-8)^2=1, and 
     symbol number  11 : (9-8)^2+(9-7)^2+(9-8)^2=6 are obtained. 
     Therefore, the symbol numbers  6  and  10  are migrated into the symbol lower order ranking table. Accordingly, tables are designed such that the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  8 ,  9 , and  11  are held in the symbol higher order ranking table in the order of shorter distance from a representative point of each region and symbol numbers other than the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  8 ,  9 , and  11  are held in the symbol lower order ranking table in the order of shorter distance from a representative point (symbol number  1 ) of the four regions (regions  8 ,  9 ,  10 , and  11 ) which are adjacent to each other. 
     Regarding the regions  12 ,  13 ,  14 , and  15 , symbol numbers included from the first order to the eighth order in the ranking are; 
     region  12 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 ,  9 ), 
     region  13 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 ,  12 ), 
     region  14 : symbol number ( 0 ,  1 ,  2 ,  3 ,  4 ,  8 ,  9 ,  12 ), and 
     region  15 : symbol number ( 0 ,  1 ,  2 ,  4 ,  6 ,  8 ,  9 ,  12 ). 
     Therefore, one symbol number among the symbol numbers  3 ,  6 ,  9 , and  12  has to be migrated into the symbol lower order ranking table. In a similar manner, 
     symbol number  3 : (9-4)^2+(9-7)^2+(9-7)^2=33, 
     symbol number  6 : (9-7)^2+(9-4)^2+(9-8)^2=30, 
     symbol number  9 : (9-8)^2+(9-4)^2+(9-7)^2=30, and 
     symbol number  12 : (9-8)^2+(9-8)^2+(9-4)^2=27 are obtained. 
     Therefore, the symbol number  12  is migrated into the symbol lower order ranking table. Accordingly, tables are designed such that the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 , and  9  are held in the symbol higher order ranking table in the order of shorter distance from a representative point of each region and symbol numbers other than the symbol numbers  0 ,  1 ,  2 ,  3 ,  4 ,  6 ,  8 , and  9  are held in the symbol lower order ranking table in the order of shorter distance from a representative point (symbol number  1 ) of the four regions (regions  8 ,  9 ,  10 , and  11 ) which are adjacent to each other. 
     A symbol higher order ranking table and a symbol lower order ranking table which are a result of similar processing with respect to regions  13  to  63  are illustrated in  FIGS. 24A and 24B .  FIGS. 24A and 24B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table in 16QAM and N div =3. Apparent from  FIGS. 24A and 24B , the total number of words of the symbol higher order ranking table and the symbol lower order ranking table is expressed as expression (79).
 
2 2N     div   ×ρ th +2 2N     div   ×( m−ρ   th )/ N   adj =64×8+64×(16−8)/4=640  (79)
 
     Accordingly, the size of the symbol higher order ranking table and the symbol lower order ranking table is 62.5% of the size of a symbol ranking table of related art. Examples of a symbol higher order ranking table and a symbol lower order ranking table, which are designed by using a similar method to 16QAM described above, in a case of ρ th =32 and N adj =4 in 64QAM and N div =3 are respectively illustrated in  FIGS. 25 and 26 .  FIG. 25  illustrates an example of a symbol higher order ranking table in 64QAM and N div =3.  FIG. 26  illustrates an example of a symbol lower order ranking table in 64QAM and N div =3. The total number of words in the symbol higher order ranking table and the symbol lower order ranking table is 2560. Thus, the size of the symbol higher order ranking table and the symbol lower order ranking table is 62.5% of the size of a symbol ranking table of related art. 
     An example in ρ th  and N adj  has been described here, but it is possible to design a symbol higher order ranking table and a symbol lower order ranking table in ρ th  and N adj  which have different values as well, by using the table designing method which is described above in detail. 
     Further, in the above description, when symbols included from the first order to the ρ th -th order in the ranking are not common, symbol numbers are selected in an evaluation standard of a smaller square error. However, other methods may be used. For example, in a case of the regions  4 ,  5 ,  6 , and  7 , it is sufficient to select two symbol numbers among the symbol numbers  5 ,  7 ,  8 , and  9 . In this case, two symbol numbers may be arbitrarily selected without using the evaluation standard of a square error and the like. 
     Processing in each stage in Embodiment 2 is now described. Description of processing same as that of Embodiment 1 is omitted. A flowchart of surviving symbol selection in first stage processing of Embodiment 2 is first described.  FIG. 27  is a flowchart of the surviving symbol selection in the first stage processing of Embodiment 2. 
     As depicted in  FIG. 27 , the surviving symbol selection unit  328  determines whether q≦ρ th  is satisfied or not (S 701 ). When q≦ρ th  is satisfied (S 701 , Yes), the surviving symbol selection unit  328  adds a symbol in the ε (1) -th row and q-th column of the symbol higher order ranking table  331  to surviving paths (S 702 ). On the other hand, when q≦ρ th  is not satisfied (S 701 , No), the surviving symbol selection unit  328  adds a symbol number in the floor(ε (1) /N adj )-th row and q−ρ th -th column of the symbol lower order ranking table  332  to surviving paths (S 703 ). 
     A flowchart of k-th stage processing is now described.  FIG. 28  is a flowchart of the k-th stage processing of Embodiment 2. As depicted in  FIG. 28 , the k-th stage processing unit sets i to 1 (S 801 ). Subsequently, the region detection unit performs region detection as expression (47) (S 802 ). Then, the region detection unit increments i (S 803 ). After that, the region detection unit determines whether i≦S k−1  is satisfied or not (S 804 ). When i≦S k−1  is satisfied (S 804 , Yes), the region detection unit returns to S 802  and repeats the processing. 
     On the other hand, when i≦S k−1  is not satisfied (S 804 , No), the surviving symbol selection unit initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage as expressed in expression (49), expression (50), and expression (51) (S 805 ). Subsequently, the surviving symbol selection unit selects i min  at which ρ(i)≦m N−k+1  is satisfied and a representative cumulative metric E(i) has the minimum value (S 806 ). 
     Then, the surviving symbol selection unit selects a surviving symbol (S 807 ). The selection of a surviving symbol will be described later. Subsequently, the metric calculation unit calculates a cumulative metric as expression (54) (S 808 ). Then, the metric calculation unit updates the cumulative metric as expression (55), expression (56), and expression (57) (S 809 ). 
     Subsequently, the metric calculation unit determines whether q≦S k  is satisfied or not (S 810 ). When q≦S k  is satisfied (S 810 , Yes), the surviving symbol selection unit returns to S 806  and repeats the processing. On the other hand, when q≦S k  is not satisfied (S 810 , No), the metric calculation unit ends the processing. 
     A flowchart of surviving symbol selection in the k-th stage processing is now described.  FIG. 29  is a flowchart of the surviving symbol selection in the k-th stage processing of Embodiment 2. As depicted in  FIG. 29 , the surviving symbol selection unit determines whether ρ(i min )≦ρ th  is satisfied or not (S 901 ). 
     When ρ(i min )≦ρ th  is satisfied (S 901 , Yes), the surviving symbol selection unit adds a symbol in the ε (k) (i min )-th row and ρ(i min )-th column of the symbol higher order ranking table to surviving paths (S 902 ). 
     On the other hand, when ρ(i min )≦ρ th  is not satisfied (S 901 , No), the surviving symbol selection unit adds a symbol number in the floor(ε (k) (i min )/N adj )-th row and ρ(i min )−ρ th -th column of the symbol lower order ranking table to surviving paths (S 903 ). 
     (Embodiment 3) 
     Embodiment 3 is now described. In Embodiment 2, an example that a symbol ranking table is separated into two levels of tables, that is, a symbol higher order ranking table and a symbol lower order ranking table at ρ th  as a boundary is described. However, a symbol ranking table may be separated into three or more levels of tables. In this embodiment, an example that a symbol ranking table is separated into three levels of tables is described. 
       FIG. 30  illustrates a configuration example of a MIMO stream separation unit of Embodiment 3. As depicted in  FIG. 30 , Embodiment 3 is different from Embodiments 1 and 2 in that a symbol intermediate order ranking table is added. Description of configurations same as those of Embodiments 1 and 2 is omitted and the configuration different from that of Embodiments 1 and 2 is mainly described. 
     A surviving symbol selection unit  428  of a first stage processing unit refers to a symbol higher order ranking table  421  (Ω 1 ), a symbol intermediate order ranking table  422  (Ω 2 ), or a symbol lower order ranking table  433  (Ω 3 ) and sets as many candidate replicas as S 1 , the number of surviving candidates from the higher order in the ranking, as surviving paths of the first stage. The surviving symbol selection unit  428  sets the surviving path as expression (80). 
     
       
         
           
             
               
                 
                   
                     
                       Π 
                       1 
                       
                         ( 
                         1 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   Ω 
                                   1 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ɛ 
                                     , 
                                     i 
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               ≤ 
                               
                                 ρ 
                                 
                                   th 
                                   , 
                                   1 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Ω 
                                   2 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       ⌊ 
                                       
                                         ɛ 
                                         / 
                                         
                                           N 
                                           
                                             adj 
                                             , 
                                             1 
                                           
                                         
                                       
                                       ⌋ 
                                     
                                     , 
                                     
                                       i 
                                       - 
                                       
                                         ρ 
                                         
                                           th 
                                           , 
                                           1 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               
                                 ρ 
                                 
                                   th 
                                   , 
                                   1 
                                 
                               
                               &lt; 
                               i 
                               ≤ 
                               
                                 ρ 
                                 
                                   th 
                                   , 
                                   2 
                                 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Ω 
                                   3 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       ⌊ 
                                       
                                         ɛ 
                                         / 
                                         
                                           N 
                                           
                                             adj 
                                             , 
                                             2 
                                           
                                         
                                       
                                       ⌋ 
                                     
                                     , 
                                     
                                       i 
                                       - 
                                       
                                         ρ 
                                         
                                           th 
                                           , 
                                           2 
                                         
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               &gt; 
                               
                                 ρ 
                                 
                                   th 
                                   , 
                                   2 
                                 
                               
                             
                           
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                         i 
                         = 
                         1 
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         S 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   80 
                   ) 
                 
               
             
           
         
       
     
     A surviving symbol selection unit of a k-th stage processing unit adaptively selects a surviving path on the k-th stage as following. The surviving symbol selection unit first initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage so as to obtain expression (81), expression (82), and expression (83).
 
 E ( i ):= d   k−1 (Π (k−1) ( i ))  (81)
 
ρ( i ):=1  (82)
 
q:=1  (83)
 
     The surviving symbol selection unit selects a candidate replica on the ρ(i min )-th order in the ranking of i min  at which ρ(i)≦m N−k+1  is satisfied and E(i) has the minimum value, from the symbol higher order ranking table Ω 1 , the symbol intermediate order ranking table Ω 2 , or the symbol lower order ranking table Ω 3 . The surviving symbol selection unit sets the q-th surviving path on the k-th stage as expression (84). 
     
       
         
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         
                           Π 
                           
                             
                               l 
                               ~ 
                               k 
                             
                             - 
                             1 
                           
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         
                           Π 
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             i 
                             min 
                           
                           ) 
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         
                           Π 
                           k 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         { 
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         1 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             
                                               ɛ 
                                               
                                                 ( 
                                                 k 
                                                 ) 
                                               
                                             
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                           , 
                                           
                                             ρ 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     ≤ 
                                     
                                       ρ 
                                       
                                         th 
                                         , 
                                         1 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         2 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ⌊ 
                                             
                                               
                                                 
                                                   ɛ 
                                                   
                                                     ( 
                                                     k 
                                                     ) 
                                                   
                                                 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     i 
                                                     min 
                                                   
                                                   ) 
                                                 
                                               
                                               / 
                                               
                                                 N 
                                                 
                                                   adj 
                                                   , 
                                                   1 
                                                 
                                               
                                             
                                             ⌋ 
                                           
                                           , 
                                           
                                             
                                               ρ 
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   i 
                                                   min 
                                                 
                                                 ) 
                                               
                                             
                                             - 
                                             
                                               ρ 
                                               
                                                 th 
                                                 , 
                                                 1 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       
                                         th 
                                         , 
                                         1 
                                       
                                     
                                     &lt; 
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     ≤ 
                                     
                                       ρ 
                                       
                                         th 
                                         , 
                                         2 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         3 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ⌊ 
                                             
                                               
                                                 
                                                   ɛ 
                                                   
                                                     ( 
                                                     k 
                                                     ) 
                                                   
                                                 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     i 
                                                     min 
                                                   
                                                   ) 
                                                 
                                               
                                               / 
                                               
                                                 N 
                                                 
                                                   adj 
                                                   , 
                                                   2 
                                                 
                                               
                                             
                                             ⌋ 
                                           
                                           , 
                                           
                                             
                                               ρ 
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   i 
                                                   min 
                                                 
                                                 ) 
                                               
                                             
                                             - 
                                             
                                               ρ 
                                               
                                                 th 
                                                 , 
                                                 2 
                                               
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     &gt; 
                                     
                                       ρ 
                                       
                                         th 
                                         , 
                                         2 
                                       
                                     
                                   
                                 
                               
                             
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               i 
                               min 
                             
                           
                           = 
                           
                             
                               arg 
                               
                                 
                                   ρ 
                                   ⁡ 
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                                 ≤ 
                                 
                                   m 
                                   
                                     N 
                                     - 
                                     k 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 min 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     e 
                                     ⁡ 
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                   ] 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   84 
                   ) 
                 
               
             
           
         
       
     
     The symbol higher order ranking table  421 , the symbol intermediate order ranking table  422 , and the symbol lower order ranking table  433  are now described in detail.  FIGS. 31A to 31C  respectively illustrate examples of a symbol higher order ranking table, a symbol intermediate order ranking table, and a symbol lower order ranking table which are designed when ρ th,1 =4, ρ th,2 =12, ρ adj,1 =4, and ρ adj,2 =16 in a case in 16QAM and N div =3. 
     As depicted in  FIG. 31A , the symbol higher order ranking table holds symbol numbers in the order of shorter distance from a region center for every region, from the first order to fourth order. As depicted in  FIG. 31B , the symbol intermediate order ranking table holds symbol numbers in the order of shorter distance from a representative point of four regions, which are adjacent to each other, for every four adjacent regions, from the fourth order to the 12th order. As depicted in  FIG. 31C , the symbol lower order ranking table holds symbol numbers in the order of shorter distance from a representative point of eight regions, which are adjacent to each other, for every 16 adjacent regions (four groups from region  0  to region  15 , from region  16  to region  31 , from region  32  to region  47 , and from region  48  to region  63 ), from the 12th order to 16th order. 
     Processing on each stage in Embodiment 3 is now described. Description of processing same as that of Embodiments 1 and 2 is omitted. A flowchart of surviving symbol selection in first stage processing of Embodiment 3 is first described.  FIG. 32  is a flowchart of the surviving symbol selection in the first stage processing of Embodiment 3. 
     As depicted in  FIG. 32 , the surviving symbol selection unit  428  determines whether q≦ρ th,1  is satisfied or not (S 1001 ). When q≦ρ th,1  is satisfied (S 1001 , Yes), the surviving symbol selection unit  428  adds a symbol in the ε (1) -th row and q-th column of the symbol higher order ranking table  421  to surviving paths (S 1002 ). 
     On the other hand, when q≦ρ th,1  is not satisfied (S 1001 , No), the surviving symbol selection unit  428  determines whether q≦ρ th,2  is satisfied or not (S 1003 ). When q≦ρ th,2  is satisfied (S 1003 , Yes), the surviving symbol selection unit  428  adds a symbol number in the floor(ε (1) /N adj1 )-th row and q−ρ th,1 -th column of the symbol intermediate order ranking table  422  to surviving paths (S 1004 ). 
     On the other hand, when q≦ρ th,2  is not satisfied (S 1003 , No), the surviving symbol selection unit  428  adds a symbol number in the floor(ε (1) /N adj2 )-th row and q−ρ th,2 -th column of the symbol lower order ranking table to surviving paths (S 1005 ). 
     A flowchart of surviving symbol selection in k-th stage processing is now described.  FIG. 33  is a flowchart of the surviving symbol selection in the k-th stage processing of Embodiment 3. As depicted in  FIG. 33 , the surviving symbol selection unit determines whether ρ(i min )≦ρ th,1  is satisfied or not (S 1101 ). 
     When ρ(i min )≦ρ th,1  is satisfied (S 1101 , Yes), the surviving symbol selection unit adds a symbol in the ε (k) (i min )-th row and ρ(i min )-th column of the symbol higher order ranking table to surviving paths (S 1102 ). 
     On the other hand, when ρ(i min )≦ρ th,1  is (i not satisfied (S 1101 , No), the surviving symbol selection unit determines whether ρ(i min )≦ρ th,2  is satisfied or not (S 1103 ). When ρ(i min )≦ρ th,2  is satisfied (S 1103 , Yes), the surviving symbol selection unit adds a symbol number in the floor (ε (k) (i min )/N adj1 )-th row and ρ(i min )−ρ th,1 -th column of the symbol intermediate order ranking table to surviving paths (S 1104 ). 
     On the other hand, when ρ(i min )−ρ th,2  is not satisfied (S 1103 , No), the surviving symbol selection unit adds a symbol number in the floor(ε (k) (i min )/N adj2 )-th row and ρ(i min )−ρ th,2 -th column of the symbol lower order ranking table to surviving paths (S 1105 ). 
     In Embodiment 3, only the symbol higher order ranking table, the symbol intermediate order ranking table, and the symbol lower order ranking table in a specific parameter example of 16QAM are illustrated. However, the embodiment is not limited to this example. For example, a table may be designed by using the designing method described in Embodiments 2 and 3, even in cases of other modulation methods and other parameters. Further, a table may be designed in a manner to be separated into four or more levels. 
     (Embodiment 4) 
     Embodiment 4 is now described. Embodiment 4 is an embodiment which is obtained by combining the above-mentioned solving aspect 1 and solving aspect 2. Any processing of Embodiments 1, 2, and 3 may be used as processing of the first stage. A surviving symbol selection unit of a k-th stage processing unit adaptively selects a surviving path on the k-th stage as following. The surviving symbol selection unit first initializes a representative cumulative metric value E(i) and a current rank ρ(i) of each surviving path which is survived on the k−1-th stage so as to obtain expression (85), expression (86), and expression (87).
 
 E ( i ):= d   k−1 (Π (k−1) ( i ))  (85)
 
ρ( i ):=1  (86)
 
q:=1  (87)
 
     The surviving symbol selection unit selects a candidate replica on the ρ(i min )-th order in the ranking of i min  at which ρ(i)≦MAX_RANK k  is satisfied and E(i) has the minimum value, from a symbol higher order ranking table Ω 1  or a symbol lower order ranking table Ω 2 . The surviving symbol selection unit sets the q-th surviving path on the k-th stage as expression (88). 
     
       
         
           
             
               
                 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         
                           Π 
                           
                             
                               l 
                               ~ 
                               k 
                             
                             - 
                             1 
                           
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         
                           Π 
                           
                             ( 
                             
                               k 
                               - 
                               1 
                             
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           
                             i 
                             min 
                           
                           ) 
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         
                           Π 
                           k 
                           
                             ( 
                             k 
                             ) 
                           
                         
                         ⁡ 
                         
                           ( 
                           q 
                           ) 
                         
                       
                       = 
                       
                         { 
                         
                           
                             
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         1 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             
                                               ɛ 
                                               
                                                 ( 
                                                 k 
                                                 ) 
                                               
                                             
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                           , 
                                           
                                             ρ 
                                             ⁡ 
                                             
                                               ( 
                                               
                                                 i 
                                                 min 
                                               
                                               ) 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     ≤ 
                                     
                                       ρ 
                                       th 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       
                                         Ω 
                                         2 
                                         
                                           ( 
                                           
                                             m 
                                             
                                               N 
                                               - 
                                               k 
                                               + 
                                               1 
                                             
                                           
                                           ) 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             ⌊ 
                                             
                                               
                                                 
                                                   ɛ 
                                                   
                                                     ( 
                                                     k 
                                                     ) 
                                                   
                                                 
                                                 ⁡ 
                                                 
                                                   ( 
                                                   
                                                     i 
                                                     min 
                                                   
                                                   ) 
                                                 
                                               
                                               / 
                                               
                                                 N 
                                                 adj 
                                               
                                             
                                             ⌋ 
                                           
                                           , 
                                           
                                             
                                               ρ 
                                               ⁡ 
                                               
                                                 ( 
                                                 
                                                   i 
                                                   min 
                                                 
                                                 ) 
                                               
                                             
                                             - 
                                             
                                               ρ 
                                               th 
                                             
                                           
                                         
                                         ) 
                                       
                                     
                                     , 
                                   
                                 
                                 
                                   
                                     
                                       ρ 
                                       ⁡ 
                                       
                                         ( 
                                         
                                           i 
                                           min 
                                         
                                         ) 
                                       
                                     
                                     &gt; 
                                     
                                       ρ 
                                       th 
                                     
                                   
                                 
                               
                             
                             ⁢ 
                             
                               
 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               i 
                               min 
                             
                           
                           = 
                           
                             
                               arg 
                               
                                 
                                   ρ 
                                   ⁡ 
                                   
                                     ( 
                                     i 
                                     ) 
                                   
                                 
                                 ≤ 
                                 
                                   
                                     MAX 
                                     ⁢ 
                                     _ 
                                   
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     RANK 
                                     k 
                                   
                                 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 min 
                                 ⁡ 
                                 
                                   [ 
                                   
                                     E 
                                     ⁡ 
                                     
                                       ( 
                                       i 
                                       ) 
                                     
                                   
                                   ] 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   88 
                   ) 
                 
               
             
           
         
       
     
     A flowchart of the k-th stage is same as that of Embodiment 1. A flowchart of surviving symbol selection on the k-th stage is same as that of Embodiment 2, so that description thereof is omitted. 
     Here, table examples of a case of 16QAM, N div =3, MAX_RANK (16QAM)   k =8, ρ th =4, and N adj =4 are described.  FIGS. 34A and 34B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table. In Embodiment 4, only the symbol higher order ranking table and the symbol lower order ranking table in a specific parameter example of 16QAM are illustrated. However, the embodiment is not limited to this example. For example, a table may be designed by using the designing method described in Embodiments 1 and 2, even in cases of other modulation methods and other parameters. Further, a table for MAX_RANK k  or lower may be designed in a manner to be separated into three or more levels. 
     (Embodiment 5) 
     Embodiment 5 is now described. An example of a symbol ranking table suitable for first stage processing is described in Embodiment 5. In the first stage processing, accuracy in lower orders is demanded in a symbol ranking table compared to accuracy in higher orders in order to leave symbol candidates of metrics which are as small as possible. Contrary to above-described solving aspect 2 and Embodiments 2, 3, and 4, a symbol higher order ranking table is designed in the order of shorter distance from a representative point of regions, which are adjacent to each other, and a symbol lower order ranking table is designed in the order of shorter distance from a representative point for each region. 
     A surviving symbol selection unit of a first stage processing unit refers to a symbol higher order ranking table Ω 1  or a symbol lower order ranking table Ω 2  and sets as many candidate replicas as S 1 , the number of surviving candidates from the higher order in the ranking, as surviving paths of the first stage. The surviving symbol selection unit sets the surviving path as expression (89). 
     
       
         
           
             
               
                 
                   
                     
                       Π 
                       1 
                       
                         ( 
                         1 
                         ) 
                       
                     
                     ⁡ 
                     
                       ( 
                       i 
                       ) 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           
                             
                               
                                 
                                   Ω 
                                   1 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       ⌊ 
                                       
                                         ɛ 
                                         / 
                                         
                                           N 
                                           adj 
                                         
                                       
                                       ⌋ 
                                     
                                     , 
                                     i 
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               ≤ 
                               
                                 ρ 
                                 th 
                               
                             
                           
                         
                         
                           
                             
                               
                                 
                                   Ω 
                                   2 
                                   
                                     ( 
                                     
                                       m 
                                       N 
                                     
                                     ) 
                                   
                                 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     ɛ 
                                     , 
                                     
                                       i 
                                       - 
                                       
                                         ρ 
                                         th 
                                       
                                     
                                   
                                   ) 
                                 
                               
                               , 
                             
                           
                           
                             
                               i 
                               ≥ 
                               
                                 ρ 
                                 th 
                               
                             
                           
                         
                       
                       , 
                       
                         
 
                       
                       ⁢ 
                       
                         i 
                         = 
                         1 
                       
                       , 
                       2 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         S 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   89 
                   ) 
                 
               
             
           
         
       
     
     A flowchart of the first stage processing is same as that of Embodiment 1, so that description thereof is omitted. A flowchart of surviving symbol selection of the first stage processing is described.  FIG. 35  is a flowchart of first stage processing of Embodiment 5. 
     As depicted in  FIG. 35 , the surviving symbol selection unit determines whether q≦ρ th  is satisfied or not (S 1201 ). When q≦ρ th  is satisfied (S 1201 , Yes), the surviving symbol selection unit adds a symbol in the floor(ε (1) /N adj )-th row and q-th column of the symbol higher order ranking table to surviving paths (S 1202 ). On the other hand, when q≦ρ th  is not satisfied (S 1201 , No), the surviving symbol selection unit adds a symbol number in the ε (1) -th row and q−ρ th -th column of the symbol lower order ranking table to surviving paths (S 1203 ). 
     A table of a case of ρ th =8 and N adj =4 in 16QAM and N div =3 is now described.  FIGS. 36A and 36B  respectively illustrate examples of a symbol higher order ranking table and a symbol lower order ranking table for the first stage processing of Embodiment 5. Here, in Embodiment 5, any of the configurations described in Embodiments 1 to 4 may be used as the configurations on and after the second stage. Further, a symbol ranking table may be separated into three levels of tables as Embodiment 3. Further, only an example of a table in 16QAM is illustrated in Embodiment 5, but it is apparent that a table in 64QAM is applicable as well. 
     (Embodiment 6) 
     Embodiment 6 is now described. Embodiment 6 is an embodiment in which the above-mentioned solving aspect 1 is applied to the LSD method. The configuration of a MIMO stream separation unit of Embodiment 6 is first described.  FIG. 37  illustrates the configuration of a MIMO stream separation unit of Embodiment 6. Description of the configurations same as those of Embodiments 1 to 5 is omitted. 
     As depicted in  FIG. 37 , a MIMO stream separation unit  512  includes a QR decomposition unit  516 , a MIMO demodulation unit  522 , and a LLR calculation unit  554 . The QR decomposition unit  516  includes a QR decomposition processing unit  518  and a reception signal conversion unit  520 . The MIMO demodulation unit  522  includes a LSD processing unit  524 . 
     The LSD processing unit  524  includes a region detection unit  526 , a surviving symbol selection unit  528 , a metric calculation unit  530 , and a size reduction type symbol ranking table  532 . 
     Processing of the MIMO demodulation unit  522  of Embodiment 6 is now described.  FIG. 38  is a flowchart of Embodiment 6. As depicted in  FIG. 38 , the region detection unit  526  performs region detection as expression (47) (S 1301 ). Subsequently, the LSD processing unit  524  sets ρ(k) to 1 (S 1302 ). Then, the surviving symbol selection unit  528  selects a symbol in the ε (k) -th row and ρ(k)-th column of the size reduction type symbol ranking table Ω (S 1303 ). 
     Subsequently, the metric calculation unit  530  calculates a cumulative metric as expression (54) (S 1304 ). Then, the metric calculation unit  530  determines whether the cumulative metric≦threshold is satisfied or not (S 1305 ). When the cumulative metric≦threshold is not satisfied (S 1305 , No), the metric calculation unit  530  returns to the k−1-th stage (S 1306 ). 
     On the other hand, when the cumulative metric≦threshold is satisfied (S 1305 , Yes), the metric calculation unit  530  determines whether the current stage is the N-th stage or not (S 1307 ). When the current stage is not the N-th stage (S 1307 , No), the metric calculation unit  530  goes to the k+1-th stage (S 1308 ). 
     On the other hand, when the current stage is the N-th stage (S 1307 , Yes), the metric calculation unit  530  adds a symbol candidate to a list (S 1309 ). Subsequently, the metric calculation unit  530  determines whether ρ(k)≦MAX_RANK k , is satisfied or not (S 1310 ). 
     When ρ(k)≦MAX_RANK k  is not satisfied (S 1310 , No), the metric calculation unit  530  returns to the k−1-th stage (S 1311 ). On the other hand, when ρ(k)≦MAX_RANK k  is satisfied (S 1310 , Yes), the metric calculation unit  530  increments ρ(k) (S 1312 ) and returns to S 1303 . 
     (Embodiment 7) 
     Embodiment 7 is now described. Embodiment 7 is an embodiment in which the above-mentioned solving aspect 2 is applied to the LSD method. The configuration of a MIMO stream separation unit of Embodiment 7 is first described.  FIG. 39  illustrates the configuration of a MIMO stream separation unit of Embodiment 7. Description of the configurations same as those of Embodiments 1 to 6 is omitted. 
     As depicted in  FIG. 39 , a MIMO stream separation unit  612  includes a QR decomposition unit  616 , a MIMO demodulation unit  622 , and a LLR calculation unit  654 . The QR decomposition unit  616  includes a QR decomposition processing unit  618  and a reception signal conversion unit  620 . The MIMO demodulation unit  622  includes a LSD processing unit  624 . 
     The LSD processing unit  624  includes a region detection unit  626 , a surviving symbol selection unit  628 , a metric calculation unit  630 , a symbol higher order ranking table  631 , and a symbol lower order ranking table  632 . 
     Processing of the MIMO demodulation unit  622  of Embodiment 7 is now described.  FIG. 40  is a flowchart of Embodiment 7. As depicted in  FIG. 40 , the region detection unit  626  performs region detection as expression (47) (S 1401 ). Subsequently, the LSD processing unit  624  sets ρ(k) to 1 (S 1402 ). Then, the surviving symbol selection unit  628  determines whether ρ(k)≦ρ th  is satisfied or not (S 1403 ). 
     Subsequently, when ρ(k)≦ρ th  is satisfied (S 1403 , Yes), the surviving symbol selection unit  628  selects a symbol in the ε (k) -th row and ρ(k)-th column of the symbol higher order ranking table  631  (S 1404 ). On the other hand, when ρ(k)≦ρ th  is not satisfied (S 1403 , No), the surviving symbol selection unit  628  selects a symbol in the floor(ε (k) /N adj )-th row and ρ(k)−ρ th -th column of the symbol lower order ranking table  632  (S 1405 ). 
     Subsequently, the metric calculation unit  630  calculates a cumulative metric as expression (54) (S 1406 ). Then, the metric calculation unit  630  determines whether the cumulative metric≦threshold is satisfied or not (S 1407 ). When the cumulative metric≦threshold is not satisfied (S 1407 , No), the metric calculation unit  630  returns to the k−1-th stage (S 1408 ). 
     On the other hand, when the cumulative metric≦threshold is satisfied (S 1407 , Yes), the metric calculation unit  630  determines whether the current stage is the N-th stage or not (S 1409 ). When the current stage is not N-th stage (S 1409 , No), the metric calculation unit  630  goes to the k+1-th stage (S 1410 ). 
     On the other hand, when the current stage is the N-th stage (S 1409 , Yes), the metric calculation unit  630  adds a symbol candidate to a list (S 1411 ). Subsequently, the metric calculation unit  630  determines whether ρ(k)≦m N−k+1  is satisfied or not (S 1412 ). 
     When ρ(k)≦m N−k+1  is not satisfied (S 1412 , No), the metric calculation unit  630  returns to the k−1-th stage (S 1413 ). On the other hand, when ρ(k)≦m N−k+1  is satisfied (S 1412 , Yes), the metric calculation unit  630  increments ρ(k) (S 1414 ) and returns to S 1403 . 
     An example in which a symbol ranking table is separated into two levels of tables is illustrated in Embodiment 7, but, not limited to this example, a symbol ranking table may be separated into three or more levels of tables as Embodiment 3. Further, as Embodiment 4, Embodiment 7 may be combined with Embodiment 6. 
     Seven embodiments have been described thus far, but the embodiments of the present disclosure are not limitedly applied only to ASESS method and LSD method. The embodiments are applicable to all MLD methods in which region detection is performed and a symbol ranking table is provided. 
     All examples and conditional language recited herein are intended for pedagogical purposes to aid the reader in understanding the invention and the concepts contributed by the inventor to furthering the art, and are to be construed as being without limitation to such specifically recited examples and conditions, nor does the organization of such examples in the specification relate to a showing of the superiority and inferiority of the invention. Although the embodiments of the present invention have been described in detail, it should be understood that the various changes, substitutions, and alterations could be made hereto without departing from the spirit and scope of the invention.