The search functionality is under construction.

The search functionality is under construction.

In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.

- Publication
- IEICE TRANSACTIONS on Communications Vol.E101-B No.10 pp.2230-2238

- Publication Date
- 2018/10/01

- Publicized
- 2018/04/09

- Online ISSN
- 1745-1345

- DOI
- 10.1587/transcom.2017EBP3336

- Type of Manuscript
- PAPER

- Category
- Wireless Communication Technologies

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Zhi QUAN, Ting TIAN, "DCD-Based Branch and Bound Detector with Reduced Complexity for MIMO Systems" in IEICE TRANSACTIONS on Communications,
vol. E101-B, no. 10, pp. 2230-2238, October 2018, doi: 10.1587/transcom.2017EBP3336.

Abstract: In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.

URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.2017EBP3336/_p

Copy

@ARTICLE{e101-b_10_2230,

author={Zhi QUAN, Ting TIAN, },

journal={IEICE TRANSACTIONS on Communications},

title={DCD-Based Branch and Bound Detector with Reduced Complexity for MIMO Systems},

year={2018},

volume={E101-B},

number={10},

pages={2230-2238},

abstract={In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.},

keywords={},

doi={10.1587/transcom.2017EBP3336},

ISSN={1745-1345},

month={October},}

Copy

TY - JOUR

TI - DCD-Based Branch and Bound Detector with Reduced Complexity for MIMO Systems

T2 - IEICE TRANSACTIONS on Communications

SP - 2230

EP - 2238

AU - Zhi QUAN

AU - Ting TIAN

PY - 2018

DO - 10.1587/transcom.2017EBP3336

JO - IEICE TRANSACTIONS on Communications

SN - 1745-1345

VL - E101-B

IS - 10

JA - IEICE TRANSACTIONS on Communications

Y1 - October 2018

AB - In many communications applications, maximum-likelihood decoding reduces to solving an integer least-squares problem, which is NP-hard in the worst case. It has recently been shown that over a wide range of dimensions and SNRs, the branch and bound (BB) algorithm can be used to find the exact solution with an expected complexity that is roughly cubic in the dimension of the problem. However, the computational complexity becomes prohibitive if the SNR is too low and/or the dimension of the problem is too large. The dichotomous coordinate descent (DCD) algorithm provides low complexity, but its detection performance is not as good as that of the BB detector. Two methods are developed to bound the optimal detector cost to reduce the complexity of BB in this paper. These methods are DCD-based detectors for MIMO and multiuser detection in the scenario of a large number of transmitting antennas/users. First, a combined detection technique based on the BB and DCD algorithms is proposed. The technique maintains the advantages of both algorithms and achieves a good trade-off between performance and complexity compared to using only the BB or DCD algorithm. Second, since the first feasible solution obtained from the BB search is the solution of the decorrelating decision feedback (DF) method and because DCD results in better accuracy than the decorrelating DF solution, we propose that the first feasible solution of the BB algorithm be obtained by the box-constrained DCD algorithm rather than the decorrelating DF detector. This method improves the precision of the initial solution and identifies more branches that can be eliminated from the search tree. The results show that the DCD-based BB detector provides optimal detection with reduced worst-case complexity compared to that of the decorrelating DF-based BB detector.

ER -