© 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 Communications
Volume 50 Number 1, January 2002

Table of Contents for this issue

Complete paper in PDF format

On (n,n-1) Convolutional Codes With Low Trellis Complexity

Hung-Hua Tang and Mao-Chao Lin

Page 37.

Abstract:

We show that the state complexity profile of a convolutional code C is the same as that of the reciprocal of the dual code of C in case that minimal encoders for both codes are used. Then, we propose an optimum permutation for any given (n, n-1) binary convolutional code that will yield an equivalent code with the lowest state complexity. With this permutation, we are able to find many (n, n-1) binary convolutional codes which are better than punctured convolutional codes of the same code rate and memory size by either lower decoding complexity or better weight spectra.

References

  1. 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.
  2. J. B. Cain, G. C. Clark Jr and J. M. Geist, "Punctured convolutional codes of rate (n, n-1 ) and simplified maximum likelihood decoding", IEEE Trans. Inform. Theory, vol. 25, pp.  97-100, Jan.  1979 .
  3. P. J. Lee, "Constructions of rate (n-1)/n punctured convolutional codes with minimal required SNR criterion", IEEE Trans. Commun., vol. 36, pp.  1171-1173, Oct.  1988 .
  4. D. Haccoun and G. Begin, "High rate punctured convolutional codes for Viterbi and sequential decoding", IEEE Trans. Commun., vol. 37, pp.  1113-1125, Nov.  1989.
  5. G. Begin and D. Haccoun, "High rate punctured convolutional codes: Structure properties and construction construction technique", IEEE Trans. Commun., vol. 37, pp.  1381-1385, Dec.  1989.
  6. M.-G. Kim, "On systematic punctured convolutional codes", IEEE Trans. Commun., vol. 45, pp.  133-139, Feb.  1997.
  7. I. E. Bocharova and B. D. Kudryashov, "Rational rate punctured convolutional codes for soft-decision Viterbi decoding", IEEE Trans. Inform. Theory, vol. 43, pp.  1305-1313, July  1997.
  8. G. D. Forney Jr, "Coset codes-Part II: Binary lattices and related codes", IEEE Trans. Inform. Theory, vol. 34, pp.  1152-1187,  Sept.  1988.
  9. D. J. Muder, "Minimal trellises for block codes", IEEE Trans. Inform. Theory, vol. 34, pp.  1049-1053, Sept.  1988.
  10. L. R. Bahl, J. Cocke, F. Jelinek and J. Raviv, "Optimal decoding of linear codes for minimizing symbol error rate", IEEE Trans. Inform. Theory, vol. IT-20, pp.  284-287,  Mar.  1974.
  11. J. L. Massey, "Foundation and methods of channel encoding", in Proc. Int. Conf. Information Theory and Systems, vol. 65, Berlin, Germany, 1978, pp.  148-157. 
  12. A. D. Kot and C. Leung, "On the construction and dimensionality of linear block code trellises", in IEEE Int. Symp. Inform. Theory, San Antonio, TX, 1993.
  13. G. D. Forney Jr, "Dimension/length profiles and trellis complexity of linear block codes", IEEE Trans. Inform. Theory, vol. 40, pp.  1741-1752, Nov.  1994.
  14. R. J. McEliece, "On the BCJR trellis for linear block codes", IEEE Trans. Inform. Theory, vol. 42, pp.  1072 -1092, July  1996.
  15. A. Vardy and F. R. Kschischang, "Proof of a conjecture of McEliece regarding the expansion index of the minimal trellis", IEEE Trans. Inform. Theory, vol. 42, pp.  2027-2034, Nov.  1996.
  16. V. Sidorenko and V. Zyablov, "Decoding of convolutional codes using a syndrome trellis", IEEE Trans. Inform. Theory, vol. 40, pp.  1663 -1666, Sept.  1994.
  17. R. J. McEliece and W. Lin, "The trellis complexity of convolutional codes", IEEE Trans. Inform. Theory, vol. 42, pp.  1855 -1864, Nov.  1996.
  18. P. Piret, Convolutional Codes, Cambridge, MA: MIT Press, 1988.
  19. G. D. Forney Jr, "Convolutional codes I: Algebraic structure", IEEE Trans. Inform. Theory, vol. IT-16, pp.  720 -738, Nov.  1970.
  20. M. Cedervall and R. Johannesson, "A fast algorithm for computing distance spectrum of convolutional codes", IEEE Trans. Inform. Theory, vol. 35, pp.  1146-1159, Nov.  1989.