© 2001 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 49 Number 5, May 2001

Table of Contents for this issue

Complete paper in PDF format

List Viterbi Algorithms for Continuous Transmission

Brian Chen, Member, IEEE and Carl-Erik W. Sundberg Fellow, IEEE

Page 784.

Abstract:

The conventional list Viterbi algorithm (LVA) produces a list of the L best output sequences over a certain block length in decoding a terminated convolutional code. We show in this paper that the LVA with a sufficiently long list is an optimum maximum-likelihood decoder for the concatenated pair of a convolutional code and a cyclic redundancy check (CRC) block code with error detection. The CRC is used to select the output. New LVAs for continuous transmission are proposed and evaluated, where no termination bits are required for the convolutional code for every CRC block. We also present optimum and suboptimum LVAs for tailbiting convolutional codes. Convolutional codes with Viterbi decoding were proposed for so-called hybrid in band on channel (hybrid IBOC) systems for digital audio broadcasting compatible with the frequency modulation band. For high-quality audio signals, it is beneficial to use error concealment/error mitigation techniques to avoid the worst type of channel errors. This requires a reliable error flag mechanism (error detection feature) in the channel decoder. A CRC on a block of audio information bits provides this mechanism. We demonstrate how the LVA can significantly reduce the flag rate compared to the regular Viterbi algorithm (VA) for the same transmission parameters. At the expense of complexity, a receiver optional LVA can reduce the flag rate by more than an order of magnitude. The difference in audio quality is dramatic. The LVA is backward compatible with a VA.

References

  1. S. Lin and D. J. Costello Jr., Error Control Coding: Fundamentals and Applications, Englewood Cliffs, NJ: Prentice-Hall, 1983.
  2. N. Seshadri and C.-E. W. Sundberg, "List Viterbi decoding algorithms with applications", IEEE Trans. Commun., vol. 42, pp.  311-323, Feb./Mar./Apr.  1994.
  3. C. Nill and C.-E. W. Sundberg, "List and soft symbol output Viterbi algorithms: Extensions and comparisons", IEEE Trans. Commun., vol. 43, pp.  277-287, Feb./Mar./Apr.  1995.
  4. B. Chen and C.-E. W. Sundberg, "An integrated error correction and detection system for digital audio broadcasting", IEEE Trans. Broadcast. , vol. 46, pp.  68-78, Mar.  2000.
  5. in"2nd Int. Symp. Digital Audio Broadcasting", vol. 1-2, Toronto, ON, Canada, Mar. 1994.
  6. N. S. Jayant and E. Y. Chen, "Audio compression: Technology and applications", AT&T Tech. J., vol. 74, pp.  23-34, Mar./Apr.   1995.
  7. J. D. Johnston, D. Sinha, S. Dorward and S. R. Quackenbush, "AT&T perceptual audio coding (PAC),"in Audio Engineering Society (AES) Collected Papers on Digital Audio Bit Rate Reduction, N. Gilchrist, and C. Grewin, Eds. New York: AES, 1996, pp.  73-82. 
  8. J. A. C. Bingham, "In-band digital audio radio: An update on AT&T Amati PAC/DMT solution", in Proc. Int. Symp. Digital Audio Broadcasting , Toronto, ON, Canada,Mar. 1994, pp.  270-277. 
  9. N. S. Jayant, E. Y. Chen, J. D. Johnston, S. R. Quackenbush, S. M. Dorward, K. Thompson, R. L. Cupo, J.-D. Wang, C.-E. W. Sundberg and N. Seshadri, "The AT&T in-band adjacent channel system for digital audio broadcasting", in Proc. Int. Symp. Digital Audio Broadcasting , Toronto, ON, Canada,Mar. 1994, pp.  254-267. 
  10. B. W. Kroeger and A. J. Vigil, "Improved IBOC DAB technology for AM and FM broadcasting", in Proc. NAB, Las Vegas, NV, Oct. 1996, pp.  1-10. 
  11. C.-E. W. Sundberg, "Digital audio broadcasting in the FM band", in Proc. ISIE'97, Guimaraes, Portugal,July 1997, pp.  SS37-SS41. 
  12. B. Chen and C.-E. W. Sundberg, "Complementary punctured-pair convolutional codes for digital audio broadcasting", IEEE Trans. Commun., vol. 48, pp.  1829-1839, Nov.  2000.
  13. S. Kallel, "Complementary punctured convolutional (CPC) codes and their applications", IEEE Trans. Commun., vol. 43, pp.  2005-2009, June  1995.
  14. B. Kroeger and D. Cammarata, "Complementary punctured convolutional codes with application to IBOC DAB", June 1997
  15. G. C. Clark Jr. and J. B. Cain, Error-Correction Coding for Digital Communications, New York: Plenum, 1981.
  16. J. Hagenauer, "Rate-compatible punctured convolutional codes (RCPC codes) and their applications", IEEE Trans. Commun., vol. 36, pp.  389-400, Apr.  1988.
  17. R. V. Cox, J. Hagenauer, N. Seshadri and C.-E. W. Sundberg, "Subband speech coding and matched convolutional channel coding for mobile radio channels", IEEE Trans. Signal Processing, vol. 39, pp.  1717-1731, Aug.  1991.
  18. J. Hagenauer, N. Seshadri and C.-E. W. Sundberg, "The performance of rate-compatible punctured convolutional codes for digital mobile radio", IEEE Trans. Commun. , vol. 38, pp.  966-980, July  1990.
  19. D. Sinha and C.-E. W. Sundberg, "Unequal error protection (UEP) for perceptual audio coders", in Proc. ICASSP'99, Phoenix, AZ, Apr. 1999.
  20. Y. Yasuda, K. Kashiki and Y. Hirata, "High-rate punctured convolutional codes for soft decision Viterbi decoding", IEEE Trans. Commun., vol. COM-32, pp.  315-319, Mar.  1984.
  21. M. Sandell, C.-E. W. Sundberg and R.-H. Yan, "List Viterbi algorithms for GSM with enhanced full-rate speech coder", in Proc. Radiovetenskap och Kommunikation (RVK'99), Karlskrona, Sweden,June 1999, pp.  426-430. 
  22. K. R. Narayanan and G. L. Stüber, "Turbo decoding for packet data systems", in Proc. IEEE Global Telecommunications Conf. (GLOBECOM'97), Phoenix, AZ, Nov. 1997, pp.  44-48. 
  23. J. S. Sadowsky, "A maximum likelihood decoding algorithm for turbo codes", in Proc. IEEE Global Telecommunications Conf. (GLOBECOM'97) , Phoenix, AZ, Nov. 1997, pp.  929-933. 
  24. J. M. Wozencraft and I. M. Jacobs, Principles of Communication Engineering, New York: Wiley, 1965.
  25. R. V. Cox and C.-E. W. Sundberg, "An efficient adaptive circular Viterbi algorithm for decoding generalized tailbiting convolutional codes", IEEE Trans. Veh. Technol., vol. 43, pp.  57-68, Feb.  1994.