Sphere decoding with a probabilistic tree pruning

Byonghyo Shim, Insung Kang

Research output: Contribution to journalArticlepeer-review

92 Citations (Scopus)


In this paper, we present a near ML-achieving sphere decoding algorithm that reduces the number of search operations in the sphere-constrained search. Specifically, by adding a probabilistic noise constraint on top of the sphere constraint, a more stringent necessary condition is provided, particularly at an early stage, and, hence, branches unlikely to be survived are removed in the early stage of sphere search. The tradeoff between the performance and complexity is easily controlled by a single parameter, so-called pruning probability. Through the analysis and simulations, we show that the complexity reduction is significant while maintaining the negligible performance degradation.

Original languageEnglish
Pages (from-to)4867-4878
Number of pages12
JournalIEEE Transactions on Signal Processing
Issue number10 I
Publication statusPublished - 2008

Bibliographical note

Funding Information:
Manuscript received March 28, 2007; revised February 24, 2008. Current version published September 17, 2008. The associate editor coordinating the review of this paper and approving it for publication was Dr. Zhi Tian. This work was supported in part by a Grant from Korea University (K0800061) and the Second BK 21 project.


  • Lattice
  • Maximum likelihood decoding
  • Multiple-input-multiple-output (MIMO) system
  • Probabilistic noise constraint
  • Probabilistic tree pruning
  • Sphere constraint
  • Sphere decoding (SD)

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering


Dive into the research topics of 'Sphere decoding with a probabilistic tree pruning'. Together they form a unique fingerprint.

Cite this