Asymptotic Distribution of Absorbing Sets and Fully Absorbing Sets for Regular Sparse Code Ensembles

被引:16
作者
Amiri, Behzad [1 ]
Lin, Chi-Wei [1 ]
Dolecek, Lara [1 ]
机构
[1] Univ Calif Los Angeles, Los Angeles, CA 90024 USA
关键词
Absorbing sets; graph-based codes; regular ensembles; iterative decoding; PARITY-CHECK CODES; LDPC CODES; TRAPPING SETS; ERROR FLOOR;
D O I
10.1109/TCOMM.2012.120512.110605
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.
引用
收藏
页码:455 / 464
页数:10
相关论文
共 32 条
[1]   Enumerators for Protograph-Based Ensembles of LDPC and Generalized LDPC Codes [J].
Abu-Surra, Shadi ;
Divsalar, Dariush ;
Ryan, William E. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (02) :858-886
[2]  
[Anonymous], 1963, Low-Density Parity-Check Codes
[3]  
[Anonymous], P 2010 INF THEOR APP
[4]   Lowering the Error Floor of LDPC Codes Using Cyclic Liftings [J].
Asvadi, Reza ;
Banihashemi, Amir H. ;
Ahmadian-Attari, Mahmoud .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (04) :2213-2224
[5]  
Bender E. A., 1974, Discrete Mathematics, V10, P217, DOI 10.1016/0012-365X(74)90118-6
[6]   Asymptotic enumeration methods for analyzing LDPC codes [J].
Burshtein, D ;
Miller, G .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2004, 50 (06) :1115-1131
[7]  
Cole C.A., 2006, GEN METHOD FINDING L
[8]  
Di CY, 2002, IEEE T INFORM THEORY, V48, P1570, DOI 10.1109/TIT.2002.1003839
[9]   Analysis of Absorbing Sets and Fully Absorbing Sets of Array-Based LDPC Codes [J].
Dolecek, Lara ;
Zhang, Zhengya ;
Anantharam, Venkat ;
Wainwright, Martin J. ;
Nikolic, Borivoje .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (01) :181-201
[10]   Eliminating trapping sets in low-density parity-check codes by using Tanner graph covers [J].
Ivkovic, Milos ;
Chilappagari, Shashi Kiran ;
Vasic, Bane .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (08) :3763-3768