Efficient soft-input soft-output tree detection via an improved path metric

Jun Won Choi; Byonghyo Shim; Andrew C. Singer

doi:10.1109/TIT.2011.2177590

Efficient soft-input soft-output tree detection via an improved path metric

Jun Won Choi, Byonghyo Shim, Andrew C. Singer

Department of Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

19 Citations (Scopus)

Abstract

Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems.

Original language	English
Article number	6157084
Pages (from-to)	1518-1533
Number of pages	16
Journal	IEEE Transactions on Information Theory
Volume	58
Issue number	3
DOIs	https://doi.org/10.1109/TIT.2011.2177590
Publication status	Published - 2012 Mar

Bibliographical note

Funding Information:
Manuscript received April 15, 2010; revised August 04, 2011; accepted September 22, 2011. Date of current version February 29, 2012. The work of B. Shim was supported by the Basic Science Research Program through the NRF funded by the Ministry of Education, Science and Technology (MEST) (No. 2011-0012525) and the second Brain Korea 21 project. J. W. Choi is with Qualcomm, Inc., San Diego, CA 92121 USA (e-mail: jun-wonc@qualcomm.com). B. Shim is with the School of Information and Communication, Korea University, Seoul, Korea (e-mail: bshim@korea.ac.kr). A. C. Singer is with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail:ac-singer@illinois.edu). Communicated by F. R. Kschischang, Associate Editor for the Special Issue on “Facets of Coding Theory: From Algorithms to Networks.” Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2011.2177590

Keywords

Iterative detection and decoding (IDD)
M-algorithm
k-best search
list sphere decoding
look-ahead path metric
soft-input soft-output detection
tree detection
turbo principle

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Library and Information Sciences

Access to Document

10.1109/TIT.2011.2177590

Cite this

@article{98144b02182d4823987d136d21ee9dbf,

title = "Efficient soft-input soft-output tree detection via an improved path metric",

abstract = "Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems.",

keywords = "Iterative detection and decoding (IDD), M-algorithm, k-best search, list sphere decoding, look-ahead path metric, soft-input soft-output detection, tree detection, turbo principle",

author = "Choi, {Jun Won} and Byonghyo Shim and Singer, {Andrew C.}",

note = "Funding Information: Manuscript received April 15, 2010; revised August 04, 2011; accepted September 22, 2011. Date of current version February 29, 2012. The work of B. Shim was supported by the Basic Science Research Program through the NRF funded by the Ministry of Education, Science and Technology (MEST) (No. 2011-0012525) and the second Brain Korea 21 project. J. W. Choi is with Qualcomm, Inc., San Diego, CA 92121 USA (e-mail: jun-wonc@qualcomm.com). B. Shim is with the School of Information and Communication, Korea University, Seoul, Korea (e-mail: bshim@korea.ac.kr). A. C. Singer is with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail:ac-singer@illinois.edu). Communicated by F. R. Kschischang, Associate Editor for the Special Issue on “Facets of Coding Theory: From Algorithms to Networks.” Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2011.2177590",

year = "2012",

month = mar,

doi = "10.1109/TIT.2011.2177590",

language = "English",

volume = "58",

pages = "1518--1533",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "3",

}

TY - JOUR

T1 - Efficient soft-input soft-output tree detection via an improved path metric

AU - Choi, Jun Won

AU - Shim, Byonghyo

AU - Singer, Andrew C.

N1 - Funding Information: Manuscript received April 15, 2010; revised August 04, 2011; accepted September 22, 2011. Date of current version February 29, 2012. The work of B. Shim was supported by the Basic Science Research Program through the NRF funded by the Ministry of Education, Science and Technology (MEST) (No. 2011-0012525) and the second Brain Korea 21 project. J. W. Choi is with Qualcomm, Inc., San Diego, CA 92121 USA (e-mail: jun-wonc@qualcomm.com). B. Shim is with the School of Information and Communication, Korea University, Seoul, Korea (e-mail: bshim@korea.ac.kr). A. C. Singer is with the Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (e-mail:ac-singer@illinois.edu). Communicated by F. R. Kschischang, Associate Editor for the Special Issue on “Facets of Coding Theory: From Algorithms to Networks.” Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TIT.2011.2177590

PY - 2012/3

Y1 - 2012/3

N2 - Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems.

AB - Tree detection techniques are often used to reduce the complexity of a posteriori probability (APP) detection in multiantenna wireless communication systems. In this paper, we introduce an efficient soft-input soft-output tree detection algorithm that employs a new type of look-ahead path metric in the process of branch pruning (or sorting). While conventional path metrics depend only on symbols on a visited path, the new path metric accounts for unvisited parts of the tree in advance through an unconstrained linear estimator and adds a bias term that reflects the contribution of as-yet undecided symbols. By applying the linear estimate-based look-ahead path metric to an M-algorithm that selects the best M paths for each level of the tree, we develop a new soft-input soft-output tree detector, called an improved soft-input soft-output M-algorithm (ISS-MA). Based on an analysis of the probability of correct path loss, we show that the improved path metric offers substantial performance gain over the conventional path metric. We also demonstrate through simulations that the proposed ISS-MA can be a promising candidate for soft-input soft-output detection in high-dimensional systems.

KW - Iterative detection and decoding (IDD)

KW - M-algorithm

KW - k-best search

KW - list sphere decoding

KW - look-ahead path metric

KW - soft-input soft-output detection

KW - tree detection

KW - turbo principle

UR - http://www.scopus.com/inward/record.url?scp=84863229398&partnerID=8YFLogxK

U2 - 10.1109/TIT.2011.2177590

DO - 10.1109/TIT.2011.2177590

M3 - Article

AN - SCOPUS:84863229398

SN - 0018-9448

VL - 58

SP - 1518

EP - 1533

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 3

M1 - 6157084

ER -

Efficient soft-input soft-output tree detection via an improved path metric

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this