Journal of Communications and Networks

The Korean Institute of Commucations and Information Sciences (한국통신학회)
권호 표지

Upper Bounds for the Performance of Turbo-Like Codes and Low Density Parity Check Codes

  • Chung, Kyu-Hyuk (Division of Information and Computer Science, School of Natural Sciences, Dankook University) ;
  • Heo, Jun (School of Electrical Engineering, Korea University)
  • Published : 2008.03.31
Download PDF
⟨ Previous Next ⟩

Abstract

Researchers have investigated many upper bound techniques applicable to error probabilities on the maximum likelihood (ML) decoding performance of turbo-like codes and low density parity check (LDPC) codes in recent years for a long codeword block size. This is because it is trivial for a short codeword block size. Previous research efforts, such as the simple bound technique [20] recently proposed, developed upper bounds for LDPC codes and turbo-like codes using ensemble codes or the uniformly interleaved assumption. This assumption bounds the performance averaged over all ensemble codes or all interleavers. Another previous research effort [21] obtained the upper bound of turbo-like code with a particular interleaver using a truncated union bound which requires information of the minimum Hamming distance and the number of codewords with the minimum Hamming distance. However, it gives the reliable bound only in the region of the error floor where the minimum Hamming distance is dominant, i.e., in the region of high signal-to-noise ratios. Therefore, currently an upper bound on ML decoding performance for turbo-like code with a particular interleaver and LDPC code with a particular parity check matrix cannot be calculated because of heavy complexity so that only average bounds for ensemble codes can be obtained using a uniform interleaver assumption. In this paper, we propose a new bound technique on ML decoding performance for turbo-like code with a particular interleaver and LDPC code with a particular parity check matrix using ML estimated weight distributions and we also show that the practical iterative decoding performance is approximately suboptimal in ML sense because the simulation performance of iterative decoding is worse than the proposed upper bound and no wonder, even worse than ML decoding performance. In order to show this point, we compare the simulation results with the proposed upper bound and previous bounds. The proposed bound technique is based on the simple bound with an approximate weight distribution including several exact smallest distance terms, not with the ensemble distribution or the uniform interleaver assumption. This technique also shows a tighter upper bound than any other previous bound techniques for turbo-like code with a particular interleaver and LDPC code with a particular parity check matrix.

Keywords

References

  1. R. Gallager, Low Density Parity Check Codes. MIT press, 1963.
  2. D. J. C. MacKay, 'Good error-correcting codes based on very sparse matrices,' Electronic Lett., vol. 33, pp. 457-458, Mar. 1997 https://doi.org/10.1049/el:19970362
  3. C. Berrou and A. Glavieux, 'Near optimum error correcting coding and decoding: Turbo-codes' IEEE Trans. Commun., vol. 44, no. 10, pp. 1261-1271, Oct. 1996 https://doi.org/10.1109/26.539767
  4. S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, 'Serial concatenation of interleaved codes: Performance analysis, design, and iterative decoding,' IEEE Trans. Inf. Theory, vol. 44, no. 3, pp. 909-926, May 1998 https://doi.org/10.1109/18.669119
  5. L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, 'Optimal decoding of linear codes for minimizing symbol error rate,' IEEE Trans. Inf. Theory, vol. 20, pp. 284-287 Mar. 1974
  6. N. Wiberg, 'Codes and decoding on general graphs (Ph.D. thesis),' Linkoping University (Sweden), 1996
  7. D. Divsalar and F. Pollara, 'Turbo codes for deep-space communications,' TDA Progress Rep., vol. 42-120, pp. 29-39, Feb. 1995
  8. S. Benedetto and G. Montorsi, 'Design of parallel concatenated convolutional codes,' IEEE Trans. Commun., vol. 44, pp. 591-600, May 1996 https://doi.org/10.1109/26.494303
  9. S. Benedetto and G. Montorsi, 'Unveiling turbo codes: Some results on parallel concatenated coding schemes,' IEEE Trans. Inf. Theory, vol. 42, no. 2, pp. 408-428, Mar. 1996
  10. T. J. Richardson and R. L. Urbanke, 'The capacity of low-density paritycheck codes under message-passing decoding,' IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 599-618, Feb. 2001 https://doi.org/10.1109/18.910577
  11. T. J. Richardson, M. A. Shokrollahi, and R. L. Urbanke, 'Design of capacity-approaching irregular low-density parity-check codes,' IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 619-637, 2001 https://doi.org/10.1109/18.910578
  12. S. Y. Chung, T. J. Richardson, and R. L. Urbanke, 'Analyisis of sumproduct decoding of low-density parity-check codes using a Gaussian approximation,' IEEE Trans. Inf. Theory, vol. 47, no. 2, pp. 657-670, 2001 https://doi.org/10.1109/18.910580
  13. ] S. Y. Chung, G. D. Forney, T. J. Richardson, and R. L. Urbanke, 'On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit,' Commun. Lett., vol. 5, no. 2, pp. 58-60, 2001 https://doi.org/10.1109/4234.905935
  14. T. M. Duman and M. Salehi, 'New performance bounds for turbo codes,' IEEE Trans. Commun., vol. 46, pp. 565-567, May 1998 https://doi.org/10.1109/26.668715
  15. T. M. Duman and M. Salehi, 'Performance bounds for turbo-coded modulation systems,' IEEE Trans. Commun., vol. 47, pp. 511-521, Apr. 1999 https://doi.org/10.1109/26.764924
  16. G. Poltyrev, 'Bounds on the decoding error probability of binary linear codes via their spectra,' IEEE Trans. Inf. Theory, vol. 40, pp. 1284-1292, July 1994 https://doi.org/10.1109/18.335935
  17. I. Sason and S. Shamai, 'Improved upper bounds on the decoding error probability of parallel and serial concatenated turbo codes via their ensemble distance spectrum,' IEEE Trans. Inf. Theory, vol. 46, pp. 24-47, Jan. 2000 https://doi.org/10.1109/18.817506
  18. A. M. Viterbi and A. J. Viterbi, 'Improved union bound on linear codes for the input-binary AWGN channel with applications to turbo codes,' in Proc. IEEE ISIT, 1998, p. 29
  19. D. Divsalar, S. Dolinar, and F. Pollara, 'Transfer function bounds on the performance of turbo codes,' Jet Propulsion Lab., TDA Progress Rep. vol. 42-122, Aug. 1995
  20. D. Divsalar, 'A simple tight bound on error probability of block codes with application to turbo codes,' Jet Propulsion Lab., TMO Progress Rep. vol. 42-139, Nov. 1999
  21. R. Garello, P. Pierleoni, and S. Benedetto, 'Computing the free distance of turbo codes and serially concatenated codes with interleavers: Algorithms and applications,' IEEE J. Sel. Areas Commun., vol. 19, no. 5, pp. 800- 812, May 2001 https://doi.org/10.1109/49.924864
  22. L. Perez, J. Seghers, and D. Costello, 'A distance spectrum interpretation of turbo codes,' IEEE Trans. Inf. Theory, vol. 42, pp. 1698-1709, Nov. 1996 https://doi.org/10.1109/18.556666
  23. K. Chung and J. Heo, 'Valid code word search algorithms for computing free distance of RA code,' in Proc. ITC-CSCC , 2006, pp. 281-285
  24. S. Crozier, 'New high-spread high-distance interleavers for turbo-codes,' in Proc. 20th Biennial Symp. Commun., May 2000, pp. 3-7
  25. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms. Computer Science Press, 1978
  26. S. Benedetto, L. Gaggero, R. Garello, and G. Montorsi, 'On the design of binary serially concatenated convolutional codes,' in Proc. Int. Conf. Commun. Theory Mini-Conf., 1999, pp. 32-36