© 1999 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 Communications
Volume 47 Number 2, February 1999

Table of Contents for this issue

Complete paper in PDF format

Breadth-First Maximum Likelihood Sequence Detection: Basics

Tor M. Aulin, Fellow, IEEE

Page 208.

Abstract:

The problem of performing breadth-first maximum likelihood sequence detection (MLSD) under given structural and complexity constraints is solved and results in a family of optimal detectors. Given a trellis with S states, these are partitioned into C classes where B paths into each class are selected recursively in each symbol interval. The derived result is to retain only those paths which are closest to the received signal in the Euclidean (Hamming) distance sense. Each member in the SA(B, C) family of sequence detectors (SA denotes search algorithm) performs complexity constrained MLSD for the additive white Gaussian noise (AWGN) (BSC) channel. The unconstrained solution is the Viterbi Algorithm (VA). Analysis tools are developed for each member of the SA(B, C) class and the asymptotic (SNR) probability of losing the correct path is associated with a new Euclidean distance measure for the AWGN case, the vector Euclidean distance (VED). The traditional Euclidean distance is a scalar special case of this,termed the scalar Euclidean distance (SED). The generality of this VED is pointed out. Some general complexity reductions exemplify those associated with the VA approach.

References

  1. G. D. Forney, Jr. "The Viterbi algorithm," Proc. IEEE, vol. 61, pp. 268-278, Mar. 1973.
  2. J. K. Omura "Optimum receiver design for convolutional codes and channels with memory via control theoretical concepts," Inform. Sci., vol. 3, pp. 243-266, 1971.
  3. J. M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering.New York: Wiley, 1965.
  4. F. Jelinek, "A fast sequential decoding algorithm using a stack," IBM J. Res. Develop., vol. 13, pp. 675-685 Nov. 1969.
  5. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms.Rockville, MD: Computer Sci. Press, 1978.
  6. A. J. Viterbi "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm," IEEE Trans. Inform. Theory, vol. IT-13, pp. 260-269, Apr. 1967.
  7. T. Aulin, "Breadth first maximum likelihood sequence detection," Chalmers Univ. Technol., Comput. Eng., Telecommun. Theory, Göteborg, Sweden, Oct. 1992, Tech. Rep., Apr. 1992.
  8. F. L. Vermeulen, "Low complexity decoders for channels with intersymbol interference," Ph.D. dissertation, Dep. Elect. Eng., Stanford Univ., Aug. 1975.
  9. F. L. Vermeulen and M. E. Hellman, "Reduced state Viterbi decoders for channels with intersymbol interference,' in IEEE Int. Conf. Communications Conf. Rec. ICC'74, Minneapolis, MN, June 1974,
  10. R. R. Anderson and G. J. Foschini, "The minimum distance for MLSE digital data systems of limited complexity," IEEE Trans. Inform. Theory, vol. IT-21, pp. 544-551, Sept. 1975.
  11. S. J. Simmons and P. H. Wittke, "Low complexity decoders for constant envelope digital modulations," IEEE Trans. Commun., vol. COM-31, pp. 1273-1280, Dec. 1983.
  12. T. Aulin, "Study of a new trellis decoding algorithm and its applications," Final Rep., ESTEC Contract 6039/84/NL/DG, European Space Agency, Noordwijk, The Netherlands, Dec. 1985.
  13. --, "A fractional Viterbi-type trellis decoding algorithm," in IEEE Int. Symp. Information Theory, ISIT'86, Ann Arbor, MI, Oct. 6-9, 1986, Abstracts of Papers, p. 41.
  14. T. Hashimoto, "A list-type reduced-constraint generalization of the Viterbi algorithm," IEEE Trans. Inform. Theory, vol. IT-33, pp. 866-876, Nov. 1987.
  15. M. V. Eyuboglu and S. U. Qureshi, "Reduced-state sequence estimation with set partitioning and decision feedback," IEEE Trans. Commun., vol. 36, pp. 13-20, Jan. 1988.
  16. A. Duel-Hallen and C. Heegard, "Delayed decision-feedback sequence estimation," IEEE Trans. Commun., vol. 37, pp. 428-436, May 1989.
  17. P. R. Chevillat and E. Eleftheriou, "Decoding of trellis-encoded signals in the presence of intersymbol interference and noise," IEEE Trans. Commun., vol. 37, pp. 669-676, July 1989.
  18. J. B. Anderson, "Limited search trellis decoding of convolutional codes," IEEE Trans. Inform. Theory, vol. IT-35, pp. 944-955, Sept. 1989.
  19. T. Larsson, "A trellis partitioning technique for reduced-state sequence detection," in IEEE Int. Symp. Information Theory, ISIT'90, San Diego, CA, Jan. 14-19, 1990, p. 22.
  20. S. J. Simmons, "Breadth-first trellis decoding with adaptive effort," IEEE Trans. Commun., vol. 38, pp. 3-12, Jan. 1990.
  21. T. Aulin, "An efficiency evaluation of different simplified sequence detection algorithms," Tech. Rep. no. 106, Dept. Telecommun. Theory, Chalmers Univ. Technol., Göteborg, Sweden, Mar. 1991.
  22. T. Larsson and T. Aulin, "Structural optimization of reduced-state detectors for trellis coded modulation," in Proc. IEEE Int. Symp. Inform. Theory, ISIT'91, Budapest, Hungary, June 24-28, 1991, p. 147.
  23. T. Aulin, "Asymptotically optimal joint channel equalization, demodulation and channel decoding with minimal complexity and delay," in Proc. 5th Tirrenia Int. Workshop on Digital Communications, Coded Modulation and Bandwidth-Efficient Transmission, Tirrenia, Pisa, Italy, Sept. 8-12, 1991, pp. 423-436.
  24. T. Larsson, "A state-space partitioning approach to trellis decoding," Ph.D. dissertation, Chalmers Univ. Technol., Göteborg, Sweden, Dec. 5, 1991.
  25. T. Aulin, "Application of the SA(B) detection algorithm to coded-PSK modulation," Final Report, ESTEC Contract 7108/87/NL/PR, European Space Agency, Noordwijk, The Netherlands, Dec. 1991.
  26. T. Larsson, "Optimal design of CPM decoders based on state-space partitioning," in Proc. IEEE Int. Conf. Communications, ICC'93, Geneva, Switzerland, May 1993, pp. 123-127.
  27. T. Aulin, "Optimal trellis decoding at given complexity," in Proc. IEEE Int. Symp. Information Theory, ISIT'93, San Antonio, TX, Jan. 17-22, 1993, p. 272.
  28. T. Aulin and C.-E. Sundberg, "Continuous phase modulation, Part I: Full response signaling," IEEE Trans. Commun., vol. COM-29, pp. 196-209, Mar. 1981.
  29. T. Aulin, N. Rydbeck, and C.-E. Sundberg, "Continuous phase modulation, Part II: Partial response signaling," IEEE Trans. Commun., vol. COM-29, pp. 210-225, Mar. 1981.
  30. N. Seshadri and C.-E. Sundberg, "List Viterbi decoding algorithms with applications," IEEE Trans. Commun., vol. 42, pp. 313-323, Feb./Mar./Apr. 1994.
  31. K. R. Narayanan and G. L. Stüber, "List decoding of turbo codes," IEEE Trans. Commun., vol. 46, pp. 754-762, June 1998.