research-article

Performance bounds for nonbinary linear block codes over memoryless symmetric channels

Authors:

Shlomo ShamaiAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 55, Issue 3

Pages 977 - 996

Published: 01 March 2009 Publication History

Abstract

The performance of nonbinary linear block codes is studied in this paper via the derivation of new upper bounds on the block error probability under maximum-likelihood (ML) decoding. The transmission of these codes is assumed to take place over a memoryless and symmetric channel. The new bounds, which are based on the Gallager bounds and their variations, are applied to the Gallager ensembles of nonbinary and regular low-density parity-check (LDPC) codes. These upper bounds are also compared with sphere-packing lower bounds. This study indicates that the new upper bounds are useful for the performance evaluation of coded communication systems which incorporate nonbinary coding techniques.

References

[1]

I. Sason and S. Shamai, "Performance analysis of linear codes under maximum-likelihood decoding: A tutorial," Foundations and Trends in Communications and Information Theory, vol. 3, no. 1-2, pp. 1-222, Jun. 2006.

Digital Library

[2]

R. G. Gallager, "A simple derivation of the coding theorem and some applications," IEEE Trans. Inf. Theory, vol. IT-11, no. 1, pp. 3-18, Jan. 1965.

[3]

T. M. Duman, "Turbo Codes and Turbo-Coded Modulation Systems: Analysis and Performance Bounds," Ph.D. dissertation, Elect. Comput. Eng. Dep., Northeastern Univ., Boston, MA, May 1998.

Digital Library

[4]

T. M. Duman and M. Salehi, "New peformance bounds for turbo codes," IEEE Trans. Commun., vol. 46, no. 6, pp. 717-723, Jun. 1998.

[5]

S. Shamai (Shitz) and I. Sason, "Variations on the Gallager bounds, connections, and applications," IEEE Trans. Inf. Theory, vol. 48, no. 12, pp. 3029-3051, Dec. 2002.

Digital Library

[6]

D. Divsalar, "A Simple Tight Bound on Error Probability of Block Codes With Application to Turbo Codes," JPL, Pasadena, CA, Telecommunications and Mission Operations (TMO) Progress Report 42-139, Nov. 15, 1999, pp. 1-35 {Online}. Available: http://tmo.jpl.nasa.gov/progress_report/42-139/139L.pdf

[7]

X. Wu, H. Xiang, and C. Ling, "New Gallager bounds in block-fading channels," IEEE Trans. Inf. Theory, vol. 53, no. 2, pp. 684-694, Feb. 2007.

Digital Library

[8]

I. Sason and S. Shamai (Shitz), "On improved bounds on the decoding error probability of block codes over interleaved fading channels, with applications to turbo-like codes," IEEE Trans. Inf. Theory, vol. 47, no. 6, pp. 2275-2299, Sep. 2001.

Digital Library

[9]

I. Sason, S. Shamai (Shitz), and D. Divsalar, "Tight exponential upper bounds on the MLdecoding error probability of block codes over fully-interleaved fading channels," IEEE Trans. Commun., vol. 51, no. 8, pp. 1296-1305, Aug. 2003.

[10]

N. Shulman and M. Feder, "Random coding techniques for nonrandom codes," IEEE Trans. Inf. Theory, vol. 45, no. 6, pp. 2101-2104, Sep. 1999.

Digital Library

[11]

A. Bennatan and D. Burshtein, "On the application of LDPC codes to arbitrary discrete-memoryless channels," IEEE Trans. Inf. Theory, vol. 50, no. 3, pp. 417-438, Mar. 2004.

Digital Library

[12]

A. Bennatan and D. Burshtein, "Design and analysis of nonbinary LDPC codes for arbitrary discrete memoryless channels," IEEE Trans. Inf. Theory, vol. 52, no. 2, pp. 549-583, Feb. 2006.

Digital Library

[13]

R. G. Gallager, Information Theory and Reliable Communication. New York: Wiley, 1968.

Digital Library

[14]

H. Herzberg and G. Poltyrev, "Techniques of bounding the probability of decoding error for block coded modulation structures," IEEE Trans. Inf. Theory, vol. 40, no. 3, pp. 903-911, May 1994.

Digital Library

[15]

U. Erez and G. Miller, "The ML decoding performance of LDPC ensembles over Z_q," IEEE Trans. Inf. Theory, vol. 51, no. 5, pp. 1871-1879, May 2005.

Digital Library

[16]

R. Liu, P. Spasojevic, and E. Soljanin, "Reliable channel regions for good binary codes transmitted over parallel channels," IEEE Trans. Inf. Theory, vol. 52, no. 4, pp. 1405-1424, Apr. 2006.

Digital Library

[17]

I. Sason and I. Goldenberg, "Coding for parallel channels: Gallager bounds and applications to turbo-like codes," IEEE Trans. Inf. Theory, vol. 53, no. 7, pp. 2394-2428, Jul. 2007.

Digital Library

[18]

C. E. Shannon, "Probability of error for optimal codes in a Gaussian channel," Bell Syst. Tech. J., vol. 38, pp. 611-656, May 1959.

[19]

C. Shannon, R. Gallager, and E. Berlekamp, "Lower bounds to error probability for decoding on discrete memoryless channels," Inf. Contr., vol. 10, pt. 1, pp. 65-103, Feb./May 1967, and Part 2: pp. 522-552.

[20]

A. Valembois and M. Fossorier, "Sphere-packing bounds revisited for moderate block length," IEEE Trans. Inf. Theory, vol. 50, no. 12, pp. 2998-3014, Dec. 2004.

Digital Library

[21]

G. Wiechman and I. Sason, "An improved sphere-packing bound for finite-length codes on symmetric memoryless channels," IEEE Trans. Inf. Theory, vol. 54, no. 5, pp. 1962-1990, May 2008.

Digital Library

[22]

R. G. Gallager, Low-Density Parity-Check Codes. Cambridge, MA: MIT Press, 1963.

[23]

C. C. Wang, S. R. Kulkarni, and H. V. Poor, "Finite-dimensional bounds on Z_m and binary LDPC codes with belief propagation decoders," IEEE Trans. Inf. Theory, vol. 53, no. 1, pp. 56-81, Jan. 2007.

Digital Library

[24]

V. Rathi and R. Urbanke, "Density evolution, stability condition, thresholds for non-binary LDPC codes," IEE Commun. Proc., vol. 152, no. 6, pp. 1069-1074, Dec. 2005.

[25]

M. C. Davey and D. J. C. Mackay, "Low-density parity check codes over GF(q)," IEEE Commun. Lett., vol. 2, no. 6, pp. 165-167, Jun. 1998.

[26]

B. Zhou, L. Zhang, J. Kang, Q. Huang, S. Lin, and M. Xu, "Non-binary LDPC codes vs. Reed-Solomon codes," in Proc. 2008 Information Theory and Applications (ITA) Workshop, San Diago, CA, Jan./Feb. 2008 {Online}. Available: http://ita.ucsd.edu/workshop/08/files/paper/ paper_151.pdf

[27]

P. Robertson and T. Woerz, "Bandwidth-efficient turbo trellis-coded modulation using punctured component codes," IEEE J. Sel. Areas Commun., vol. 16, no. 2, pp. 206-218, Feb. 1998.

Digital Library

[28]

S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, "Bandwidth efficient parallel concatenated coding schemes," IEE Electron. Lett., vol. 31, no. 24, pp. 2067-2069, 1995.

[29]

T. Duman and M. Salehi, "Performance bounds for turbo-coded modulation systems," IEEE Trans. Commun., vol. 47, no. 4, pp. 511-521, Apr. 1999.

[30]

U. Wachsmann, R. F. Fischer, and J. B. Huber, "Multilevel codes: Theoretical concepts and practical design rules," IEEE Trans. Inf. Theory, vol. 45, no. 5, pp. 1361-1391, Jul. 1999.

Digital Library

[31]

R. Liu, J. Luo, and P. Spasojevic, "Adaptive transmission with variable-rate turbo bit-interleaved coded modulation," IEEE Trans. Wireless Commun., vol. 6, no. 11, pp. 3926-3936, Nov. 2007.

Digital Library

[32]

S. Tong, "Tangential-sphere bounds on the ensemble performance of ML decoded Gallager codes via their exact ensemble distance spectrum," in Proc. 2008 IEEE Int. Conf. Communications (ICC 2008), Beijing, China, May 2008, pp. 1150-1154.

[33]

D. Burshtein and G. Miller, "Asymptotic enumeration methods for analyzing LDPC codes," IEEE Trans. Inf. Theory, vol. 50, no. 6, pp. 1115-1131, Jun. 2004.

Digital Library

[34]

A. J. Viterbi and J. K. Omura, Principle of Digital Communication and Coding. New York: McGraw-Hill, 1979.

Digital Library

[35]

M. F. Flanagan, V. Skachek, E. Byrne, and M. Greferath, "Linear-programming decoding of non-binary linear codes," in Proc. 7th Int. ITG Conf. Source and Channel Coding (SCC 2008), Ulm, Germany, Jan. 2008.

Digital Library

[36]

M. Flanagan, "Codeword-independent performance of nonbinary linear codes under linear-programming and sum-product decoding," in Proc. 2008 IEEE Int. Symp. Information Theory (ISIT'08), Toronto, ON, Canada, Jul. 2008, pp. 1503-1507.

[37]

D. Divsalar and E. Biglieri, "Upper bounds to error probabilities of coded systems beyond the cutoff rate," IEEE Trans. Commun., vol. 51, no. 12, pp. 2011-2018, Dec. 2003.

[38]

G. Miller and D. Burshtein, "Bounds on the maximum-likelihood decoding error probability of low-density-parity-check codes," IEEE Trans. Inf. Theory, vol. 47, no. 7, pp. 2696-2710, Nov. 2001.

Digital Library

[39]

I. Sason and S. Shamai (Shitz), "Improved upper bounds on the ensemble performance of ML decoded low-density parity-check codes," IEEE Commun. Lett., vol. 4, no. 3, pp. 89-91, Mar. 2000.

[40]

G. Poltyrev, "Bounds on the decoding error probability of binary linear codes via their spectra," IEEE Trans. Inf. Theory, vol. 40, no. 4, pp. 1284-1292, Jul. 1994.

Digital Library

[41]

D. E. Knuth, The Art of Computer Programming: Seminumerical Algorithms, 3rd ed. Reading, MA: Addison-Wesley, 1998, vol. 2, p. 461.

Digital Library

[42]

R. M. Roth, Introduction to Coding Theory. Cambridge, U.K.: Cambridge Univ. Press, 2006.

Digital Library

[43]

L. M. G. M. Tolhuizen, "On maximum distance separable codes over alphabets of arbitrary size," in Proc. 1994 IEEE Int. Symp. Information Theory (ISIT'94), Trondheim, Norway, Jun. 1994, p. 431.

Cited By

Hof ESason IShamai S(2010)Performance bounds for erasure, list and decision feedback schemes with linear block codesIEEE Transactions on Information Theory10.1109/TIT.2010.205079756:8(3754-3778)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1109/TIT.2010.2050797
Flanagan MSkachek VByrne EGreferath M(2009)Linear-programming decoding of nonbinary linear codesIEEE Transactions on Information Theory10.1109/TIT.2009.202557155:9(4134-4154)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1109/TIT.2009.2025571

Performance bounds for nonbinary linear block codes over memoryless symmetric channels
1. Mathematics of computing
  1. Information theory
2. Security and privacy
  1. Cryptography

Recommendations

Parity-Check Density Versus Performance of Binary Linear Block Codes: New Bounds and Applications

The moderate complexity of low-density parity-check (LDPC) codes under iterative decoding is attributed to the sparseness of their parity-check matrices. It is therefore of interest to consider how sparse parity-check matrices of binary linear block ...
Tightened Upper Bounds on the ML Decoding Error Probability of Binary Linear Block Codes

The performance of maximum-likelihood (ML) decoded binary linear block codes is addressed via the derivation of tightened upper bounds on their decoding error probability. The upper bounds on the block and bit error probabilities are valid for any ...
Deriving Good LDPC Convolutional Codes from LDPC Block Codes

Low-density parity-check (LDPC) convolutional codes are capable of achieving excellent performance with low encoding and decoding complexity. In this paper, we discuss several graph-cover-based methods for deriving families of time-invariant and time-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Information Theory

IEEE Transactions on Information Theory Volume 55, Issue 3

March 2009

511 pages

ISSN:0018-9448

Issue’s Table of Contents

Copyright © 2009.

Publisher

IEEE Press

Publication History

Published: 01 March 2009

Revised: 15 October 2008

Received: 23 April 2008

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hof ESason IShamai S(2010)Performance bounds for erasure, list and decision feedback schemes with linear block codesIEEE Transactions on Information Theory10.1109/TIT.2010.205079756:8(3754-3778)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1109/TIT.2010.2050797
Flanagan MSkachek VByrne EGreferath M(2009)Linear-programming decoding of nonbinary linear codesIEEE Transactions on Information Theory10.1109/TIT.2009.202557155:9(4134-4154)Online publication date: 1-Sep-2009
https://dl.acm.org/doi/10.1109/TIT.2009.2025571

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents