More Web Proxy on the site http://driver.im/

article

Low-floor decoders for LDPC codes

Authors:

William E. RyanAuthors Info & Claims

IEEE Transactions on Communications, Volume 57, Issue 6

Pages 1663 - 1673

https://doi.org/10.1109/TCOMM.2009.06.070325

Published: 01 June 2009 Publication History

Abstract

One of the most significant impediments to the use of LDPC codes in many communication and storage systems is the error-rate floor phenomenon associated with their iterative decoders. The error floor has been attributed to certain subgraphs of an LDPC code's Tanner graph induced by so-called trapping sets. We show in this paper that once we identify the trapping sets of an LDPC code of interest, a sum-product algorithm (SPA) decoder can be custom-designed to yield floors that are orders of magnitude lower than floors of the the conventional SPA decoder. We present three classes of such decoders: (1) a bi-mode decoder, (2) a bit-pinning decoder which utilizes one or more outer algebraic codes, and (3) three generalized-LDPC decoders. We demonstrate the effectiveness of these decoders for two codes, the rate-1/2 (2640,1320) Margulis code which is notorious for its floors and a rate-0.3 (640,192) quasi-cyclic code which has been devised for this study. Although the paper focuses on these two codes, the decoder design techniques presented are fully generalizable to any LDPC code.

References

[1]

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

[2]

Y. Kou, S. Lin, and M. Fossorier, "Low-density parity-check codes based on finite geometries: a rediscovery and new results," IEEE Trans. Inform. Theory, vol. 47, pp. 2711-2736, Nov. 2001.

Digital Library

[3]

X.-Y. Hu, E. Eleftheriou, and D.-M. Arnold, "Progressive edge-growth Tanner graphs," in Proc. IEEE GlobeCom, vol. 2, pp. 995-1001, Nov. 2001.

[4]

T. Tian, C. Jones, J. D. Villasenor, and R. D. Wesel, "Construction of irregular LDPC codes with low error floors," in Proc. IEEE International Conf. Commun., vol. 5, pp. 3125-3129, May 2003.

[5]

J. Xu, L. Chen, I. Djurdjevic, S. Lin, and K. Abdel-Ghaffar, "Construction of regular and irregular LDPC codes: geometry decomposition and masking," IEEE Trans. Inform. Theory, vol. 53, no. 1, pp. 121-134, Jan. 2007.

Digital Library

[6]

A. Abbasfar, D. Divsalar, and K. Yao, "Accumulate repeat accumulate codes," in Proc. IEEE GlobeCom, vol. 1, pp. 509-513, Nov. 2004.

[7]

D. Divsalar, S. Dolinar, and J. Thorpe, "Accumulate-repeat-accumulate-accumulate-codes," in Proc. 60th Veh. Technol. Conf., vol. 3, pp. 2292- 2296, Sept. 2004.

[8]

W.-Y. Weng, A. Ramamoorthy, and R. D. Wesel, "Lowering the error floors of irregular high-rate LDPC codes by graph condition," in Proc. 60th Veh. Technol. Conf., vol. 4, pp. 2549-2553, Sept. 2004.

[9]

D. Divsalar and C. Jones, "Protograph based low error floor LDPC coded modulation," in Proc. IEEE Military Commun. Conf., vol. 1, pp. 378-385, Oct. 2005.

[10]

Y. Zhang and W. E. Ryan, "Structured IRA codes: performance analysis and construction," IEEE Trans. Commun., to appear.

[11]

Y. Zhang and W. E. Ryan, "Toward low LDPC-code floors: a case study," submitted to IEEE Trans. Commun., Feb. 2007.

Digital Library

[12]

J. Lu and J. M. F. Moura, "Structured LDPC codes for high-density recording: large girth and low error floor," IEEE Trans. Magnetics, vol. 42, pp. 208-213, Feb. 2006.

[13]

S. K. Chilappagari, S. Sankaranarayanan, and B. Vasic, "Error floors of LDPC codes on the binary symmetric channel," IEEE International Conf. Commun., June 2006.

[14]

H. Xiao and A. H. Banihashemi, "Graph-based message-passing schedules for decoding LDPC codes," IEEE Trans. Commun., vol. 52, no. 12, pp. 2098-2105, Dec. 2004.

[15]

A. I. Vila Casado, M. Griot, and R. Wesel, "Informed dynamic scheduling for belief-propagation decoding of LDPC codes," in Proc. IEEE ICC'07, Glasgow, Scotland, June 2007.

[16]

E. Cavus and B. Daneshrad, "A performance improvement and error floor avoidance technique for belief propagation decoding of LDPC codes," in Proc. 16th IEEE International Symp. Personal, Indoor Mobile Radio Commun., vol. 4, pp. 2386-2390, Sept. 2005.

[17]

S. Lander and O. Milenkovic, "Algorithmic and combinatorial analysis of trapping sets in structured LDPC codes," in Proc. 2005 International Conf. Wireless Networks, Commun. Mobile Computing, vol. 1, pp. 630- 635, June 2005.

[18]

M. Chertkov, "Reducing the error floor," 2007 Information Theory Workshop, Lake Tahoe, CA, Sept. 2007.

[19]

Z. Zhang, L. Dolecek, B. Nikolic, V. Anantharam, and M. Wainwright, "Investigation of error floors of structured low-density parity-check codes by hardware emulation," 2006 IEEE GlobeCom Conf., Nov. 2006.

[20]

T. Richardson, "Error floors of LDPC codes," in Proc. 41st Allerton Conf. Commun., Control, Computing, Allerton House, Monticello, IL, USA, Oct. 2003.

[21]

D. MacKay and M. Postol, "Weaknesses of margulis and ramanujan-margulis low-density parity-check codes," Electronic Notes Theoretical Computer Science, vol. 74, 2003.

[22]

G. A. Margulis, "Explicit constructions of graphs without short cycles and low-density codes," Combinatorica vol 2, no. 1, pp. 71-78, 1982.

[23]

J. Rosenthal and P. O. Vontobel, "Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis," in Proc. 38th Annual Allerton Conf. Commun., Control, Computing, pp. 248-257, 2000.

[24]

B. Xia and W. E. Ryan, "On importance sampling for linear block codes," in Proc. 2003 IEEE International Conf. Commun., vol. 4, pp. 2904-2908, May 2003.

[25]

E. Cavus, C. Haymes, and B. Baneshrad, "A highly efficient importance sampling method for LDPC codes using trapping sets," submitted to IEEE Trans. Commun..

[26]

C. A. Cole, S. G. Wilson, E. K. Hall, and T. R. Giallorenzi, "A general method for finding low error rates of LDPC codes," submitted to IEEE Trans. Inform. Theory, June 2006.

[27]

L. Dolecek, Z. Zhang, M. Wainwright, V. Anantharam, and B. Nikoli'c, "Evaluation of the low frame error rate performance of LDPC codes using importance sampling," 2007 IEEE Inform. Theory Workshop, Sept. 2-6, 2007.

[28]

R. Koetter and P. Vontobel, "Graph-covers and iterative decoding of finite length codes," Turbo Conference, Brest 2003.

[29]

O. Milenkovic, E. Soljanin, and P. Whiting, "Asymptotic spectra of trapping sets in regular and irregular LDPC code ensembles," IEEE Trans. Inform. Theory, vol. 53, pp. 39-55, Jan. 2007.

Digital Library

[30]

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. 20, pp. 284-287, Mar. 1974.

Digital Library

[31]

R. McEliece, "On the BCJR trellis for linear block codes," IEEE Trans. Inf. Theory, pp. 1072-1092, July 1996.

Digital Library

[32]

R. Pyndiah, "Near optimum decoding of product codes: block turbo codes," IEEE Trans. Commun., vol. 46, no. 8, pp. 1003-1010, Aug. 1998.

[33]

J. Hagenauer and P. Hoeher, "A Viterbi algorithm with soft-decision outputs and its applications," in Proc. IEEE GlobeCom, vol. 3, pp. 1680- 1686, Nov. 1989.

[34]

C. Jones, S. Dolinar, K. Andrews, D. Divsalar, Y. Zhang, and W. Ryan, "Functions and architectures for LDPC decoding," IEEE Inform. Theory Workshop'07, Lake Tahoe, CA, Sept. 2007.

[35]

R. Michael Tanner, "On quasi-cyclic repeat-accumulate codes," in Proc. 37th Allerton Conf. Commun., Control, Computing, Sept. 1999.

[36]

J. Xu, L. Chen, L. Zeng, L. Lan, and S. Lin, "Construction of low-density parity-check codes by superposition," IEEE Trans. Commun., vol. 53, pp. 243-251, Feb. 2005.

[37]

T. J. Richardson and R. L. Urbanke, "Multi-edge type LDPC codes," to appear, IEEE Trans. Inform. Theory. {Online}. Available: http://lthcwww.epfl.ch/

[38]

J. Thorpe, "Low-Density Parity-Check (LDPC) codes constructed from protographs," JPL INP, Tech. Rep., pp. 42-154, Aug. 2003.

[39]

European TeleCommun. Standards Institute. "Digital video broadcasting (DVB) second generation farming structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broadband satellite applications," DRAFT EN 302 307 DVBS2- 74r15, 2003.

[40]

Y. Han and W. E. Ryan, "Pinning techniques for low-floor detection/decoding of LDPC-coded partial response channels," in Proc. 2008 5th International Symposium on Turbo Codes and Related Topics, pp. 49-54, Sept. 2008.

[41]

F. Kschischang, B. Frey, and H.-A. Loeliger, "Factor graphs and the sum-product algorithm," IEEE Trans. Inform. Theory, pp. 498-519, Feb. 2001.

Digital Library

Cited By

Battaglioni MChiaraluce FBaldi MPacenti MMitchell D(2023)Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objectsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-023-02273-02023:1Online publication date: 25-Jul-2023
https://dl.acm.org/doi/10.1186/s13638-023-02273-0
Hatami HMitchell DCostello DFuja T(2019)A Modified Min-Sum Algorithm for Quantized LDPC Decoders2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849308(2434-2438)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1109/ISIT.2019.8849308
Kumar SMotwani R(2017)An Upper Bounding Technique on the Error Floor Performance of LDPC CodesGLOBECOM 2017 - 2017 IEEE Global Communications Conference10.1109/GLOCOM.2017.8254151(1-4)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.1109/GLOCOM.2017.8254151
Show More Cited By

Recommendations

Toward low LDPC-code floors: a case study

While LDPC codes have been widely acclaimed in recent years for their near-capacity performance, they have not found their way into many important applications. For some cases, this is due to their increased decoding complexity relative to the classical ...
Instanton-based techniques for analysis and reduction of error floors of LDPC codes
Special issue on capaciyy approaching codes

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding ...
Design of LDPC decoders for improved low error rate performance: quantization and algorithm choices

Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Communications

IEEE Transactions on Communications Volume 57, Issue 6

June 2009

334 pages

ISSN:0090-6778

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 June 2009

Revised: 22 January 2008

Received: 04 July 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Battaglioni MChiaraluce FBaldi MPacenti MMitchell D(2023)Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objectsEURASIP Journal on Wireless Communications and Networking10.1186/s13638-023-02273-02023:1Online publication date: 25-Jul-2023
https://dl.acm.org/doi/10.1186/s13638-023-02273-0
Hatami HMitchell DCostello DFuja T(2019)A Modified Min-Sum Algorithm for Quantized LDPC Decoders2019 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2019.8849308(2434-2438)Online publication date: 7-Jul-2019
https://dl.acm.org/doi/10.1109/ISIT.2019.8849308
Kumar SMotwani R(2017)An Upper Bounding Technique on the Error Floor Performance of LDPC CodesGLOBECOM 2017 - 2017 IEEE Global Communications Conference10.1109/GLOCOM.2017.8254151(1-4)Online publication date: 4-Dec-2017
https://dl.acm.org/doi/10.1109/GLOCOM.2017.8254151
Ravanmehr VKhatami MDeclercq DVasic B(2016)Check-hybrid GLDPC codesTransactions on Emerging Telecommunications Technologies10.1002/ett.312227:12(1679-1692)Online publication date: 1-Dec-2016
https://dl.acm.org/doi/10.1002/ett.3122
Han YRyan W(2010)Low-floor detection/decoding of LDPC-coded partial response channelsIEEE Journal on Selected Areas in Communications10.5555/1734877.173489128:2(252-260)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.5555/1734877.1734891
Bocharova IKudryashov BSkachek VYakimenka Y(undefined)Low complexity algorithm approaching the ML decoding of binary LDPC codes2016 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT.2016.7541790(2704-2708)
https://dl.acm.org/doi/10.1109/ISIT.2016.7541790

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents