© 2002 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Transactions on Wireless Communications
Volume 1 Number 1, January 2002

Table of Contents for this issue

Complete paper in PDF format

Complexity Reduction of the MLSD/MLSDE Receiver Using the Adaptive State Allocation Algorithm

Hossein Zamiri-Jafarian, Member IEEE and Subbarayan Pasupathy Fellow, IEEE

Page 101.

Abstract:

The idea of adaptive state allocation (ASA) algorithm is used in this paper to substantially reduce the computational complexity of the maximum-likelihood sequence detection and estimation (MLSD/MLSDE) receiver without a significant degradation in its performance. In the ASA algorithm, the total number of states assigned to the trellis and the number of states selected from the entire set are changed adaptively based on the short-term power of the channel impulse response (CIR) or its estimate.

The ASA algorithm is a combination of two methods: adaptive threshold (AT) and adaptive state partitioning (AP). In the AT method, a threshold value is formulated based on the probability of removing the correct state in the trellis diagram. At each time, only the paths whose costs are less than the minimum cost (corresponding to the best survivor path) plus the threshold value are retained and are extended to the next trellis stage. The AT method significantly reduces the computational complexity of the regular MLSDE mostly at high signal-to-noise ratio (SNR) with a negligible loss in performance. Simulation results for fading channels show that the AT method typically selects one trellis state (the minimum possible number of states) at high SNRs. In the AP method, the branch metrics are fused and diffused adaptively by using the Kullback-Leibler (KL) distance metric invoked for quantifying the differences between the probability density functions of the correct and incorrect branch metrics in the trellis. The adaptation is done such that the channel coefficients with short-term power less than a threshold are assumed to be zero in computing the branch metrics. The AP method decreases the computational complexity of the regular MLSDE at low SNRs.

References

  1. G. D. Forney, "Maximum-likelihood sequence estimation of digital sequences in presence of intersymbol interference", IEEE Trans. Inform. Theory, vol. IT-18, pp.  363-378, May  1972.
  2. H. Zamiri-Jafarian and S. Pasupathy, "Adaptive MLSDE using the EM algorithm", IEEE Trans. Commun., vol. 47, pp.  1181-1193, Aug.  1999.
  3. D. D. Falconer and F. R. Magee, "Adaptive channel memory truncation for maximum-likelihood sequence estimation", Bell Syst. Tech. J., vol. 9, pp.  1541-1562, Nov.  1973.
  4. K. Wesolowski, "An efficient DFE and ML suboptimum receiver for data transmission over dispersive channels using two-dimensional signal constellations", IEEE Trans. Commun., vol. COM-35, pp.  336-339, Mar.   1987.
  5. M. V. Eyuboglu and S. U. H. Qureshi, "Reduced-state sequence estimation with set partitioning and decision feedback", IEEE Trans. Commun., vol. COM-36, pp.  13-20, Jan.  1988.
  6. J. B. Anderson and S. Mohan, "Sequential coding algorithm: A survey and cost analysis", IEEE Trans. Commun., vol. COM-32, pp.  169-176, Feb.  1984.
  7. S. J. Simmons, "Breadth-first trellis decoding with adaptive effort", IEEE Trans. Commun., vol. 38, pp.  3-12, Jan.  1990.
  8. H. Zamiri-Jafarian and S. Pasupathy, "Adaptive state allocation algorithm in mlsd receiver for multipath fading channels: Structure and strategy", IEEE Trans. Veh. Technol., vol. 48, pp.  174-187, Jan.  1999 .
  9. N. McGinty and R. Kennedy, "Reduced-state sequence estimator with reverse-time structure", IEEE Trans. Commun. , vol. 45, pp.  265-268, March  1997.
  10. J. Belzile and D. Haccoun, "Bidirectional breadth-first algorithms for the decoding of convolutional codes", IEEE Trans. Commun., vol. 41, pp.  370-380, Feb.  1993.
  11. N. Seshadri, "Joint data and channel estimation using blind trellis search techniques", IEEE Trans. Commun., pp.  1000-1011, Feb.  1994.
  12. J. P. Seymour and M. P. Fitz, "Near-optimal symbol-by-symbol detection schemes for flat Rayleigh fading", IEEE Trans. Commun., vol. 43, pp.  1525-1533, Feb./Mar./Apr.  1995.
  13. H. Zamiri-Jafarian and S. Pasupathy, "Adaptive T-algorithm in MLSD/MLSDE receivers for fading channels", in Proc. ICC'99, vol. I, Vancouver, Canada,June, pp.  539- 543. 
  14. H. Zamiri-Jafarian, "Adaptive MLSDE Receivers for Wireless Communications", Ph.D., Dept. Elec. Comput. Eng., Univ. Toronto, Toronto, Canada, 1998.
  15. E. A. Lee and D. G. Messerschmitt, Digital Communications, 2nd ed.   Boston, MA: Kluwer Academic, 1994 .
  16. T. L. M. Longo and R. M. Gray, "Quantization for decentralized hypothesis testing under communication constraints", IEEE Trans. Inform. Theory, vol. IT-36, pp.  241-255, Mar.  1990 .
  17. V. Krishnamurthy and J. B. Moore, "On-line estimation of hidden markov model parameters based on the Kullback-Leibler information measure", IEEE Trans. Signal Processing, pp.  2557-2573, Aug.  1993 .
  18. V. Krishnamurthy, "On-line estimation of dynamic shock-error models based on the Kullback-Leibler information measure", IEEE Trans. Automat. Contr., pp.  1129 -1135, May  1994.
  19. T. M. Cover and J. A. Thomas, Elements of Information Theory, New York: Wiley, 1991.
  20. R. Raheli and A. Polydoros, "Per-survivor processing: A general approach to MLSE in uncertain environments", IEEE Trans. Commun., vol. 43, pp.  354-364, Feb./Mar./Apr.  1995.
  21. R. H. Clarke, "A statistical theory of mobile-radio reception", Bell Syst. Tech. J., pp.  957-1000, July-Aug.  1968.
  22. K. Pahlavan and A. H. Levesque, Wireless Information Networks, New York: Wiley, 1995.
  23. W. H. A. Guston and E. H. Walker, "A multipath fading simulator for radio", IEEE Trans. Veh. Technol., pp.  241-244, Nov  1973.