Abstract:
A disclosed receiver in a MIMO multiplexing communication system, in which plural signals are simultaneously transmitted from plural transmitting antenna branches using the same frequency, and the transmitted signals are retrieved by receiving signals at plural receiving antennas, separating the received signals and searching for proper symbol metrics for each branch, comprises a QR decomposer for QR decomposing the received signals to orthogonalize the transmitted signals; a symbol replica candidate ranking unit for subtracting surviving symbol replica candidates from the QR decomposed received signals to get remaining received signals and rank the remaining signals in the increasing order of expected branch metrics of the remaining received signals; a symbol replica candidate selector for selecting symbol replica candidates in the ranked order; a branch metric calculator for calculating the branch metrics of the selected symbol replica candidates; and a threshold comparator for comparing the calculated branch metrics with a predetermined threshold; wherein if a calculated branch metric is larger than the predetermined threshold, the branch metric and successive branch metrics are deleted without further searching.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to receivers in MIMO multiplexing communication system and signal separation methods, and especially relates to such a receiver and method employing LSD (List Sphere Decoding) method with adaptive selection of surviving symbol replica candidates. 
     2. Description of the Related Art 
     MIMO (Multiple Input Multiple Output) spatial multiplexing is one technology to realize large capacity and high speed data communications.  FIG. 1  schematically illustrates a general structure of a MIMO multiplexing system  10 . In the MIMO multiplexing system  10 , a transmitter  100  transmits plural different signals or data via plural different antenna branches  101 ,  102 , . . . , using the same frequency, time and/or code. A receiver  200  receives spatially multiplexed plural different signals via antennas  201 ,  202 , . . . , and separates the received signals to retrieve the transmitted signals or data. Since the MIMO multiplexing system can transmit and receive different data simultaneously, it can drastically increase information bit rate. 
     Some signal separation schemes have been proposed for the MIMO multiplexing. Among them, the maximum likelihood of detection (MLD) method is desirable, because the MLD method has excellent signal separation characteristics, and can reduce a required signal energy per bit-to-noise power spectrum density ratio (E b /N o ) and therefore realize high throughput. In the MLD method, however, it is necessary to calculate the branch metrics (squared Euclidean distances) of all possible symbol replica candidates with respect to all the transmission branches (transmitted signals), and therefore the calculation amount and complexity is extremely large. In the MLD, the transmitted signals can be retrieved on the assumption that a combination of symbol replica candidates giving the minimum branch metrics is the correct combination of the transmitted signals. It is desired to reduce the calculation amount and complexity for the actual implementation of the MLD method. 
     As one promising approach that reduces the calculation amount in the MLD method, the List Sphere Decoding (LSD) method has been proposed. In the LSD method, the QR decomposition technique is used to orthogonalize the transmitted signals (into a condition where each received signal includes only a specific transmitted signal component(s) but not other transmitted signal components, as shown in  FIG. 2 ). A suitable threshold is previously established. The transmitted signals or transmission branches are sorted or ranked in the decreasing order of their received SINRs (Signal to Interference plus Noise power Ratios). The branch metrics of symbol replica candidates with respect to the transmission branches are compared with the threshold, in the decreasing order of their received SINRs. In accordance with a result of the comparison, the symbol replica candidates with respect to the lower ranked transmitted signals (See Non-Patent Document #1) are deleted. 
     The QR decomposition is described below in more detail. Assuming that the transmitted signals are represented by x (x 1 , x 2 , x 3  and x 4  where four transmission antenna branches are used) and the received signals are represented by y (y 1 , y 2 , y 3  and y 4  where four receiving antennas are used), the received signals can be represented by the following equation (1).
 
y=Hx  (1)
 
     H is a channel matrix that can be obtained by performing channel estimation in the receiver using known orthogonal pilot signals multiplexed with the transmission signals. The orthogonal pilot signals are multiplexed to the transmitted signal by any of or a combination of time division multiplexing, frequency division multiplexing, and code division multiplexing. 
     A unitary matrix Q and an upper triangular matrix R satisfying the following equation (2) are determined.
 
H=QR  (2)
 
     The above equation (1) can be represented by the following equation (3) using QR.
 
y=Hx=QRx  (3)
 
     The Hermitian transposed matrix Q H  of the matrix Q is multiplied to both sides of the equation (3) from the left to get the following equation (4).
 
Q H y=Q H Q R x=Rx  (4)
 
     An equation shown in  FIG. 2  indicates the components x 1 , x 2 , x 3  and x 4  of the transmitted signals x and the components z 1 , z 2 , z 3  and z 4  of the received signals Q H y obtained by orthogonalizing the transmitted signals x. For example, since the component z 1 =r 44 x 1 , it includes only the component x 1  but not other components of x. The component z 2  includes only the components x 1  and x 2 . This condition is referred to as “orthogonal” herein. 
     As for the received signals z by thus orthogonalizing the transmitted signals x using the upper triangular matrix R, the branch metric with respect to each symbol replica candidate (S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , . . . ) for each transmitted signal (x 1 , x 2 , x 3 , x 4 ) transmitted at the antenna branch  101  is compared with the threshold by turns. In accordance with the comparison result (e.g. a solid line white circle S 1  for x 1  at stage  1  shown in  FIG. 3  is larger than the threshold), lower ranked symbol replica candidates (e.g. the following symbol replica candidates represented by four dotted line white circles at stage  2 ) for the transmitted signals (e.g. x 2  at stage  2  shown in  FIG. 3 ) are deleted to reduce the calculation amount. Each stage corresponds to each transmitting antenna branch, therefore to each transmitted signal. By deciding symbol replica candidates at each stage, the transmitted signal is retrieved at each antenna branch. 
       FIG. 3  schematically illustrates the branch metric calculation and comparison procedure of the above described LSD method under a condition where the QPSK (Quadrature Phase Shift Keying) modulation and 2×2 MIMO multiplexing are employed. Solid and dotted line white circles represent symbol replica candidates that have been deleted according to the comparison with the threshold. Black circles represent surviving symbol replica candidates. In this example, the calculation and comparison procedure starts at step S 1 , goes through steps S 2 , S 3 , S 4 , S 5 , S 6 , S 7 , S 8 , S 9 , S 10  and S 13 , and ends at step S 12 . 
     [Non-patent Document #1] 
     B. M. Hochwald, et al., “Achieving near-capacity on multiple-antenna channel,” IEEE Trans. Commun., vol. 51, no. 3, pp. 389-399, March 2003. 
     Description of the Invention 
     Problem(s) to be Solved by the Invention 
     The conventional LSD method performs the above explained operation, and can reduce the calculation amount compared with the MLD method. The LSD method, however, has a problem that its calculation amount is still large for the actual implementation. That is, all symbol replica candidates (e.g. S 3 , S 4 , S 5 , S 6 , S 9 , S 10 , S 13 , S 12 ) added at the next stage need branch metric calculations, and therefore there has been a limitation in reducing the calculation amount. 
       FIG. 4  illustrates a branch metric calculation and comparison procedure at a stage m+1 in the conventional LSD method in case of 16QAM (Quadrature Amplitude Modulation). At the stage m+1, all 16 symbol replica candidates need their branch metric calculations. Although some symbol replica candidates (represented by white circles, S 1 , S 3 , . . . ) should be deleted as a result of comparisons with the threshold, the branch metric calculation should be performed even for such symbol replica candidates to be deleted, and therefore the calculation amount cannot be effectively further reduced. 
     SUMMARY OF THE INVENTION 
     The present invention provides a receiver in a MIMO multiplexing communication system and a signal separation method based on the LSD method that can further reduce the calculation amount. 
     Features of the present invention are set forth in the description that follows, and in part will become apparent from the description and the accompanying drawings, or may be learned by practice of the invention according to the teachings provided in the description. Problem solutions provided by the present invention will be realized and attained by a method and system particularly pointed out in the specification in such full, clear, concise, and exact terms as to enable a person having ordinary skill in the art to practice the invention. 
     To achieve these solutions and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention provides a specific method and system as follows. 
     Means for Solving the Problem 
     An aspect of the present invention provides a receiver in a MIMO multiplexing communication system in which plural signals are simultaneously transmitted from plural transmitting antenna branches using the same frequency, and the transmitted signals are retrieved by receiving the signals at plural receiving antennas, separating the received signals and searching for proper symbol metrics for each branch, comprising: a QR decomposer for QR decomposing the received signals to orthogonalize the transmitted signals; a symbol replica candidate ranking unit for subtracting surviving symbol replica candidates from the QR decomposed received signals to get remaining received signals and rank the remaining signals in the increasing order of expected branch metrics of the remaining received signals; a symbol replica candidate selector for selecting symbol replica candidates in the ranked order; a branch metric calculator for calculating the branch metrics of the selected symbol replica candidates; and a threshold comparator for comparing the calculated branch metrics with a predetermined threshold; wherein if a calculated branch metric is larger than the predetermined threshold, the branch metric and successive branch metrics are deleted without further searching. 
     In the receiver, the symbol replica candidate ranking unit may perform quadrant detection by determining in which quadrant of an orthogonal coordinate of a signal layout the remaining signal exists, repeating the determination by narrowing an area of the quadrant detection, getting a spatial relationship of the remaining signal in the signal layout and determining branch metric size based on the spatial relationship. 
     According to another aspect of the invention, when it is determined that a branch metric is larger than the threshold, further searching for a predetermined number of candidates is performed rather than terminating immediately. 
     According to another aspect of the invention, symbol replica candidates whose branch metrics are smaller than the threshold are input into a list, and after the list is full, a new symbol replica candidate to be added to the list is compared with the symbol replica candidate in the list having the largest branch metric, and if the former is smaller than the latter then the former replaces the latter and the threshold is revised to the largest branch metric. 
     According to another aspect of the invention, symbol replica candidates whose branch metrics are smaller than the threshold are input into a list, and after the list is full, a new symbol replica candidate to be added to the list is compared with the symbol replica candidate in the list having the largest branch metric, and if the former is smaller than the latter then the former replaces the latter and a predetermined number of the replaced candidates are still held in the list. 
     According to another aspect of the invention, the searching for symbol replica candidates is terminated when a predetermined calculation amount is reached. 
     According to another aspect of the invention, the receiver further comprises: a channel estimator for performing channel estimation based on orthogonal pilot signals contained in the received signals; a transmitted signal ranking unit for ranking the transmitted signals in the decreasing order of their received SINR based on the channel estimation. 
     According to another aspect of the invention, the orthogonal pilot signals are multiplexed with the transmitted signal by any of or a combination of time division multiplexing, frequency division multiplexing, and code division multiplexing. 
     According to another aspect of the invention, a signal separation method in a MIMO multiplexing communication system, in which plural signals are simultaneously transmitted from plural transmitting antenna branches using the same frequency, and the transmitted signals are retrieved by receiving signals at plural receiving antennas, separating the received signals and searching for proper symbol metrics for each branch, comprises the steps of: QR decomposing the received signals to orthogonalize the transmitted signals; subtracting surviving symbol replica candidates from the QR decomposed received signals to get remaining received signals; ranking the remaining signals in the increasing order of expected branch metrics of the remaining received signals; selecting symbol replica candidates in the ranked order; calculating the branch metrics of the selected symbol replica candidates; and comparing the calculated branch metrics with a predetermined threshold; wherein if a calculated branch metric is larger than the predetermined threshold, the branch metric and successive branch metrics are deleted without further searching. 
     Advantage of the Invention 
     According to embodiments of the present invention, it is possible to further reduce the calculation amount. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  schematically illustrates a general structure of a MIMO multiplexing system; 
         FIG. 2  depicts an example of orthogonalizing transmitted signals using the QR decomposition; 
         FIG. 3  schematically illustrates a branch metric calculation and comparison procedure in a conventional LSD method; 
         FIG. 4  schematically illustrates a branch metric calculation and comparison procedure at a stage m+1 in a conventional LSD method; 
         FIG. 5  schematically illustrates a general structure of a MIMO multiplexing communication system according to one embodiment of the present invention; 
         FIG. 6  illustrates three example ways for multiplexing pilot signals; 
         FIG. 7  illustrates a structure example of an LSD processing unit according to the embodiment of the present invention; 
         FIG. 8  is a flowchart showing one example procedure in the LSD processing unit; 
         FIG. 9  schematically illustrates a branch metric calculation and comparison procedure at a stage m+1 according to the embodiment of the present invention; 
         FIG. 10  illustrates an example of ranking symbol replica candidates based on quadrant detection; 
         FIG. 11  shows an example of the same ranking in the quadrant detection; 
         FIG. 12  is a flowchart showing another example procedure in the LSD processing unit; 
         FIG. 13  schematically illustrates a branch metric calculation and comparison procedure taking account of the same ranking; 
         FIG. 14  shows an example list holding symbol replica candidates surviving at the last stage; 
         FIG. 15  is a flowchart showing further another example procedure in the LSD processing unit; 
         FIG. 16  shows another example list holding symbol replica candidates surviving at the last stage; 
         FIG. 17  is a flowchart showing further another example procedure in the LSD processing unit; 
         FIG. 18  schematically illustrates widths of variations in calculation amounts; and 
         FIG. 19  is a flowchart showing further another example procedure in the LSD processing unit. 
     
    
    
       100  transmitter 
       101 ˜ 104  antenna 
       111 ˜ 114  orthogonal pilot signal multiplexer 
       200  receiver 
       201 ˜ 204  antenna 
       210  channel estimator 
       220  transmitted signal ranking unit 
       230  QR decomposer 
       240  Q H  multiplier 
       250  LSD processor 
       251  symbol replica candidate ranking unit 
       252  symbol replica candidate selector 
       253  branch metric calculator 
       254  threshold comparator 
       260  list 
     P 1 ˜P 4  pilot signals 
       30  signal point layout for signal point detection in quadrant detection method 
       31  surviving received signal 
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     In the following, preferred embodiments of the present invention are explained below. 
       FIG. 5  schematically illustrates a general structure of a MIMO multiplexing communication system  50  according to one embodiment of the present invention. The MIMO multiplexing communication system  50  has four antennas in both transmitting side and receiving side, but the number of antennas is not limited to four. 
     A transmitter  100  shown in  FIG. 5  includes orthogonal pilot signal multiplexers  111 ˜ 114  that multiplex data #1˜#4 to be transmitted and orthogonal pilot signals. The transmitter  100  further includes four antennas  101 ˜ 104  connected to the orthogonal pilot signal multiplexers  111 ˜ 114 , respectively. 
     A receiver  200  includes antennas  201 ˜ 204  for receiving signals, and a channel estimator  210  for performing channel estimation (generating a channel matrix) based on orthogonal pilot signals contained in the received signals. The receiver  200  further includes a transmitted signal ranking unit  220  that ranks or sorts the transmitted signals by their received SINRs, based on channel estimation results. The transmitted signals are ranked from one with the highest received SINR to one with the lowest received SINR. The receiver  200  further includes a QR decomposer  230  that performs the QR decomposition to orthogonalize the transmitted signals, a Q H  multiplier  240  that multiplies the Hermitian transposed matrix Q H  with the signals received by the antennas  201 ˜ 204 , and an LSD processor  250  that performs signal separation on the received signals multiplied by QH, based on the LSD method. The ranking process in the transmitted signal ranking unit  220  is performed so that the received SINR of each antenna is compared with the others and the row components of the channel matrix are sorted or reordered from lower received SINR to higher received SINR. By searching for symbol replica candidates using thus ranked transmitted signals, the probability of searching for and finding symbol replica candidates whose branch metrics are larger than a threshold is reduced, and therefore the calculation amount can be reduced. 
       FIG. 6  illustrates three example ways for multiplexing pilot signals.  FIG. 6(   a ) shows an example way in which pilot signals P 1 ˜P 4  are time multiplexed.  FIG. 6(   b ) shows an example way in which pilot signals P 1 ˜P 4  are frequency multiplexed. 
       FIG. 6(   c ) shows an example way in which pilot signals P 1 ˜P 4  are code multiplexed. A combination of these multiplexing ways can be also employed. 
       FIG. 7  illustrates a structural example for one stage provided with the LSD processor  250  included in the receiver  200  shown in  FIG. 5 . Plural functions as shown in  FIG. 7  can be provided exclusively for plural stages, respectively. Alternatively, only one function can be provided and can be shared among the stages by varying parameters. 
     The LSD processor  250  shown in  FIG. 7  includes a symbol replica candidate ranking unit  251 , in which from the received signals (received signals after multiplying by Q H ) obtained by orthogonalizing the transmitted signals by the QR decomposition, the signal components of the surviving symbol replica candidates are subtracted, to obtain remaining received signals, and the remaining received signals are ranked or sorted by their expected branch metrics, from smaller branch metric to larger branch metric. 
     The LSD processor  250  further includes a symbol replica candidate selector  252 , in which symbol replica candidates are selected with respect to the sorted received signals in the order from the highest ranked received signal (with the smallest expected branch metric) to the lowest ranked received signal (with the largest expected branch metric). 
     The LSD processor  250  further includes a branch metric calculator  253 , in which the branch metrics of the selected symbol replica candidates are calculated. 
     The LSD processor  250  further includes a threshold comparator  254 , in which the calculated branch metrics are compared with a predetermined threshold. 
     If the comparison in the threshold comparator  254  results in the branch metric of a symbol replica candidate being smaller than the predetermined threshold, the procedure moves to the next stage (corresponding to the next transmitting branch). On the other hand, if the branch metric of a symbol replica candidate is larger than the predetermined threshold, no further searching with respect to this symbol replica candidate is performed, all the symbol replica candidates after the present stage are deleted, and the procedure goes back to the previous stage to try a fresh combination of symbol replica candidates. 
       FIG. 8  is a flowchart showing one example procedure in the LSD processor  250 , whose operation is explained below with reference to  FIG. 8 . 
     At stage m after coming from the previous stage m−1, first, the ranking of all the symbol replica candidates in the stage m is performed at step S 101 . Next, symbol replica selection is performed from the first ranked symbol replica candidate at step S 102 , and the branch metric of the selected symbol replica candidate is calculated at step S 103 . 
     Then, the calculated branch metric is compared with a threshold and it is determined whether the calculated branch metric is smaller than the threshold at step S 104 . If it is determined that the calculated branch metric is larger than the threshold, the procedure goes back to stage m−1. On the other hand, if it is determined that the calculated brand metric is smaller than the threshold, the procedure moves to step S 105  where it is determined whether the present stage is the final stage. If the present stage is not the final one, the procedure moves to the next stage m+1. 
     If the present stage is the last one, the symbol replica candidates are input to a list at step S 106 . The list holds some symbol replica candidates to perform soft-decision turbo decoding later. Then, it is determined whether all the symbol replica candidates have been searched for and found at the present stage m at step S 107 . If not, the procedure goes back to the symbol replica candidate selection at step S 102 . If all the symbol replica candidates have been searched for and found at the present stage m, the procedure goes back to previous stage m−1. 
       FIG. 9  schematically illustrates ranking, branch metric calculation and comparison procedures at stage m+1 according to the embodiment of the present invention in case of 16QAM. At stage m+1, the procedure goes to step S 1  where the branch metric calculation and the threshold comparison are performed, goes to step S 2  where the branch metric calculation and the threshold comparison are performed, and goes to step S 3 . If it is determined that the calculated branch metric is larger than the threshold at step S 3 , it is possible to omit the following steps S 4 ˜ 16 , that drastically reduce the calculation amount. 
     Next,  FIG. 10  illustrates an example of tanking symbol replica candidates based on quadrant detection according to another embodiment of the present invention. This ranking is performed in the symbol replica candidate ranking unit  251  shown in  FIG. 7 . Marks x shown in  FIG. 10  represent constellations corresponding to symbol replica candidates. Sixteen constellations are shown in the case of 16QAM. 
     First, as shown in  FIG. 10(   a ), a detection region is defined as the whole region of a signal layout  30  comprising all quadrants of the complex plane. Assuming orthogonal coordinates whose origin  32  coincides with the center of the signal layout  30 , it is determined in which quadrant a remaining received signal  31  exists. Since the quadrant detection is achieved by checking the signs of the I and Q components of the remaining received signal, this process can be much less complex than calculating the squared Euclidian distance. In this example shown in  FIG. 10(   a ), it is determined that the remaining received signal  31  exists in the first quadrant  33 . 
     Next, a new detection region is defined as the determine d first quadrant  33 . Orthogonal coordinates are placed so that their origin  34  coincides with the center of the determined first quadrant  33  as shown in  FIG. 10(   b ). It is determined in which quadrant of the determined first quadrant  33  the remaining received signal  31  exists. In this example, it is determined that the remaining received signal  31  exists in the third quadrant  35 . 
     Similarly, a new detection region is defined as the determined third quadrant  35 . Orthogonal coordinates are placed so that their origin  36  coincides with the center of the determined first quadrant  35  as shown in  FIG. 10(   c ). It is determined in which quadrant of the determined third quadrant  35  the remaining received signal  31  exists. In this example, it is determined that the remaining received signal  31  exists in the third quadrant  37 . 
     Finally, as shown in  FIG. 10(   d ), the region  38  where the remaining received signal  31  is located is identified or specified. Each constellation, that is, each symbol replica candidate is ranked based on a spatial relationship with the identified region  38 . 
     The detection regions and how to place orthogonal coordinates can be varied in the scope of the present invention. 
     In this manner, it is possible to perform ranking only by simply checking the signs of the I and Q components of the remaining received complex signals. 
     Next,  FIGS. 11˜13  illustrate an improvement feature for dealing with the same ranking. In  FIG. 11 , although two symbol replica candidates  39  encircled by dotted lines on the signal layout  30  rank “2” and “3”, they should have substantially the same ranking because they have the same spatial relationship with the remaining received signal  31 . In this case, according to the procedure shown in  FIGS. 8 and 9 , the branch metric for the symbol replica candidate ranking “2” is calculated and compared with the threshold, and if the branch metric is determined to be larger than the threshold, the next symbol replica candidate ranking “3” is deleted. However, the symbol replica candidate ranking “3” may be smaller than the threshold in which case it should survive. In that case, deletion of such a symbol replica candidate may cause the degradation of successive decoding characteristics. In order to solve this problem, a scheme shown in  FIGS. 12 and 13  is proposed. 
       FIG. 12  is a flowchart showing another example procedure in the LSD processing unit  250 . In this example, there is a new determination step S 108  through which the procedure passes on the way to stage (m−1) after leaving step S 104 . At step S 108 , it is determined how many branch metrics have been compared since it has been first determined a branch metric is larger than the threshold. At step S 10 , it is determined whether the present branch metric is the αth one since it has been first determined a branch metric is larger than the threshold. If the present branch metric reaches the αth one, the procedure goes back to stage m−1. If not, the procedure goes to step S 102 , where a symbol replica candidate is selected. 
       FIG. 13  schematically illustrates a branch metric calculation and comparison procedure at stage m+1 according to the above example, wherein the 16QAM is employed and α=2. The procedure goes from step S 1 , S 2 , . . . for each of 16 symbol replica candidates at stage m+1. Even if it is determined that the branch metric is larger than the threshold, the searching is not terminated then. At the next step S 4 , a branch metric calculation and comparison with the threshold are performed for the next symbol replica candidate. If it is determined at step S 4  that the branch metric is larger than the threshold, the branch metric at step S 4  should be αth one since it has been first determined that the branch metric (at step S 3 ) is larger than the threshold, and therefore the following steps are omitted. 
     In this manner, by performing branch metric calculation and comparison with some margin or redundancy, it is possible to prevent deleting a potentially effective symbol replica candidate and degrading the characteristics, at the cost of a small increase in the calculation amount. 
     Next,  FIGS. 14 and 15  relate to an improved feature of the management mechanism of the list that holds some symbol replica candidates to perform soft-decision turbo decoding later. In the above examples, when adding a new symbol replica candidate to the list at the final stage, the new symbol replica candidate is added to the list if the list is not full. On the other hand, if the list is full, the new symbol replica candidate is compared with the maximum branch metric in the list. Only if the new symbol replica candidate is smaller than the maximum branch metric in the list does the new symbol replica candidate replace the symbol replica candidate with the maximum branch metric. Accordingly under the situation where the list is already filled with symbol replica candidates with small branch metrics, performing new branch metric calculations and comparisons may be time-consuming and useless because they might not be added to the list. In order to solve this time-consuming problem, a scheme is proposed in which the threshold is revised when the list becomes full. 
       FIG. 14  shows a list  260  that holds the remaining symbol replica candidates at the final stage.  FIG. 15  is a flowchart showing further another example procedure in the LSD processing unit  250 . In  FIG. 15 , a new step S 109  is added after step S 106  where the symbol replica candidates are input to the list. At step S 109 , if the list is filled with symbol replica candidates, the threshold is changed to the maximum branch metric held in the list  260 . 
     In this manner, by revising the threshold to the maximum branch metric in the list, it is possible to eliminate branch metric calculations and comparisons for symbol replica candidates that cannot be input on the list, reducing the calculation amount. 
       FIGS. 16 and 17  show another improvement in the managing mechanism of the list  260 . In the above example, when adding a new symbol replica candidate to the list at the final stage, the symbol replica candidate is simply added if the list is not full. On the other hand, if the list is already full, the new symbol replica candidate is compared with the maximum symbol replica candidate in the list. If it is determined that the new symbol replica candidate is smaller than the maximum symbol replica candidate in the list, the maximum symbol replica candidate is replaced by the new symbol replica candidate. The replaced symbol replica candidate is thrown away. The thrown away symbol replica candidate cannot be used any longer in a later decoding process, even if the candidate may be effective for improving signal separation characteristics and for reducing the calculation amount. 
     In this example shown in  FIGS. 16 and 17 , all the replaced symbol replica candidates are not thrown away, and a certain number of such candidates are held for possible use. 
       FIG. 16  shows an example of the list  260  that holds the symbol replica candidates remaining at the final stage. The list  260  shown in  FIG. 16  is provided with entries for the replaced N cand     —     max  symbol replica candidates in addition to entries #1˜#N cand  for the normal symbol replica candidates. 
       FIG. 17  is a flowchart showing a procedure in the LSD processing unit  250  in this example. There is provided a new step S 110  after step S 106  where symbol replica candidates are input to the list  260 . At step S 110 , if the list is filled with symbol replica candidates, the replaced symbol replica candidates are held up to N cand     —     max  replaced candidates. 
       FIGS. 18 and 19  relate to an improvement in the total calculation amount. In the prior art, as shown in  FIG. 18(   a ), searches are done for all symbol replica candidates whose branch metrics are smaller than the threshold. Therefore, an average calculation amount and the maximum calculation amount are much different from each other and there is a large variation width (gap) between them. Calculation time required until finishing the symbol search widely varies as shown in  FIG. 18(   a ) depending on reception condition, and that is a problem. One scheme to solve this problem is to define an upper limit in the calculation amount at a level lower than the maximum calculation amount to reduce the variation width. 
       FIG. 19  is a flowchart showing further another example procedure in the LSD processing unit  250 . There is provided a new step S 111  after step S 102  where symbol replica candidate selection is performed. At step S 111 , it is determined whether the number of all branch metric calculations through all stages exceeds a predetermined value. If the number of all branch metric calculations through all stages exceeds the predetermined value, the searching procedure is terminated. 
     In this manner, by terminating the searching procedure when the predetermined value is reached, the calculation amount does not vary depending on reception condition. 
     The present invention is not limited to these embodiments, but variations and modifications may be made without departing from the scope of the present invention. 
     The present application is based on Japanese Priority Application No. 2005-84697 filed on Mar. 23, 2005 with the Japanese Patent Office, the entire contents of which are hereby incorporated by reference.