A Caltech Library Service

Sphere-constrained ML detection for frequency-selective channels

Vikalo, H. and Hassibi, B. and Mitra, U. (2006) Sphere-constrained ML detection for frequency-selective channels. IEEE Transactions on Communications, 54 (7). pp. 1179-1183. ISSN 0090-6778. doi:10.1109/TCOMM.2006.877946.

See Usage Policy.


Use this Persistent URL to link to this item:


The maximum-likelihood (ML) sequence detection problem for channels with memory is investigated. The Viterbi algorithm (VA) provides an exact solution. Its computational complexity is linear in the length of the transmitted sequence, but exponential in the channel memory length. On the other hand, the sphere decoding (SD) algorithm also solves the ML detection problem exactly, and has expected complexity which is a low-degree polynomial (often cubic) in the length of the transmitted sequence over a wide range of signal-to-noise ratios. We combine the sphere-constrained search strategy of SD with the dynamic programming principles of the VA. The resulting algorithm has the worst-case complexity determined by the VA, but often significantly lower expected complexity.

Item Type:Article
Related URLs:
URLURL TypeDescription
Additional Information:© Copyright 2006 IEEE. Reprinted with permission. Paper approved by B. Hochwald, the Editor for MIMO Techniques of the IEEE Communications Society. Manuscript received April 2, 2004; revised December 14, 2004. [Posted online: 2006-07-17] This work was supported in part by the National Science Foundation under Grant CCR-0133818, and in part by the Office of Naval Research under Grant N00014-02-1-0578. This paper was presented in part at the 37th Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, November 2003, and in part at the IEEE International Conference on Acoustics, Speech, and Signal Processing, Hong Kong, April 2003.
Subject Keywords:Expected complexity, frequency-selective channels, maximum-likelihood (ML) sequence detection, sphere decoding, Viterbi algorithm (VA)
Issue or Number:7
Record Number:CaltechAUTHORS:VIKieeetc06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4432
Deposited By: Archive Administrator
Deposited On:22 Aug 2006
Last Modified:08 Nov 2021 20:17

Repository Staff Only: item control page