Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objects
Authors: 
Massimo Battaglioni, Franco Chiaraluce, Marco Baldi, Michele Pacenti, David G. M. MitchellAuthors Info & Claims
Abstract
It is well known that some harmful objects in the Tanner graph of low-density parity-check (LDPC) codes have a negative impact on their error correction performance under iterative message-passing decoding. Depending on the channel and the decoding algorithm, these harmful objects are different in nature and can be stopping sets, trapping sets, absorbing sets, or pseudocodewords. Differently from LDPC block codes, the design of spatially coupled LDPC codes must take into account the semi-infinite nature of the code, while still reducing the number of harmful objects as much as possible. We propose a general procedure, based on edge spreading, enabling the design of good quasi-cyclic spatially coupled LDPC (QC-SC-LDPC) codes. These codes are derived from quasi-cyclic LDPC (QC-LDPC) block codes and contain a considerably reduced number of harmful objects with respect to the original QC-LDPC block codes. We use an efficient way of enumerating harmful objects in QC-SC-LDPCCs to obtain a fast algorithm that spans the search space of potential candidates to select those minimizing the multiplicity of the target harmful objects. We validate the effectiveness of our method via numerical simulations, showing that the newly designed codes achieve better error rate performance than codes presented in previous literature.
References
[1]
Jiménez Felström A and Zigangirov KS Time-varying periodic convolutional codes with low-density parity-check matrix IEEE Trans. Inf. Theory 1999 45 6 2181-2191
[2]
R.G. Gallager, Low-density parity-check codes. IRE Trans. Inform. Theory IT-8, 21–28 (1962)
[3]
Yang Z, Fang Y, Zhang G, Lau FCM, Mumtaz S, and da Costa DB Analysis and optimization of tail-biting spatially coupled protograph LDPC codes for BICM-ID systems IEEE Trans. Veh. Technol. 2020 69 1 390-404
[4]
Wang Q, Cai S, Lin W, Zhao S, Chen L, and Ma X Spatially coupled LDPC codes via partial superposition and their application to HARQ IEEE Trans. Veh. Technol. 2021 70 4 3493-3504
[5]
Richardson TJ and Urbanke RL The capacity of low-density parity-check codes under message-passing decoding IEEE Trans. Inf. Theory 2001 47 2 599-618
[6]
Lentmaier M, Sridharan A, Costello DJ, and Zigangirov KS Iterative decoding threshold analysis for LDPC convolutional codes IEEE Trans. Inf. Theory 2010 56 10 5274-5289
[7]
Kudekar S, Richardson TJ, and Urbanke RL Threshold saturation via spatial coupling: why convolutional LDPC ensembles perform so well over the BEC IEEE Trans. Inf. Theory 2011 57 2 803-834
[8]
Kudekar S, Richardson TJ, and Urbanke RL Spatially coupled ensembles universally achieve capacity under belief propagation IEEE Trans. Inf. Theory 2013 59 12 7761-7813
[9]
Tanner R A recursive approach to low complexity codes IEEE Trans. Inf. Theory 1981 27 5 533-547
[10]
Di C, Proietti D, Telatar IE, Richardson TJ, and Urbanke RL Finite-length analysis of low-density parity-check codes on the binary erasure channel IEEE Trans. Inf. Theory 2002 48 6 1570-1579
[11]
T. Richardson, Error floors of LDPC codes, in Proceedings of 41st Annual Allerton Conference, Monticello, IL (2003)
[12]
Dolecek L, Zhang Z, Anantharam V, Wainwright MJ, and Nikolic B Analysis of absorbing sets and fully absorbing sets of array-based LDPC codes IEEE Trans. Inf. Theory 2010 56 1 181-201
[13]
Hashemi Y and Banihashemi A On characterization of elementary trapping sets of variable-regular LDPC codes IEEE Trans. Inf. Theory 2014 60 9 5188-5203
[14]
Hashemi Y and Banihashemi A New characterization and efficient exhaustive search algorithm for leafless elementary trapping sets of variable-regular LDPC codes IEEE Trans. Inf. Theory 2016 62 12 6713-6736
[15]
Tao X, Li Y, Liu Y, and Hu Z On the construction of LDPC codes free of small trapping sets by controlling cycles IEEE Commun. Lett. 2018 22 1 9-12
[16]
Asvadi R, Banihashemi AH, and Ahmadian-Attari M Lowering the error floor of LDPC codes using cyclic liftings IEEE Trans. Inf. Theory 2011 57 4 2213-2224
[17]
Nguyen DV, Chilappagari SK, Marcellin MW, and Vasic B On the construction of structured LDPC codes free of small trapping sets IEEE Trans. Inf. Theory 2012 58 4 2280-2302
[18]
Han Y and Ryan WE Low-floor decoders for LDPC codes IEEE Trans. Commun. 2009 57 6 1663-1673
[19]
Kang J, Huang Q, Lin S, and Abdel-Ghaffar K An iterative decoding algorithm with backtracking to lower the error-floors of LDPC codes IEEE Trans. Commun. 2011 59 1 64-73
[20]
Kang S, Moon J, Ha J, and Shin J Breaking the trapping sets in LDPC codes: check node removal and collaborative decoding IEEE Trans. Commun. 2016 64 1 15-26
[21]
Mitchell DGM, Lentmaier M, and Costello DJ Jr Spatially coupled LDPC codes constructed from protographs IEEE Trans. Inf. Theory 2015 61 9 4866-4889
[22]
Tanner RM, Sridhara D, Sridharan A, Fuja TE, and Costello DJ LDPC block and convolutional codes based on circulant matrices IEEE Trans. Inf. Theory 2004 50 12 2966-2984
[23]
Pradhan AK, Thangaraj A, and Subramanian A Construction of near-capacity protograph LDPC code sequences with block-error thresholds IEEE Trans. Commun. 2016 64 1 27-37
[24]
Fang Y, Liew SC, and Wang T Design of distributed protograph LDPC codes for multi-relay coded-cooperative networks IEEE Trans. Wireless Commun. 2017 16 11 7235-7251
[25]
Fang Y, Chen P, Cai G, Lau FCM, Liew SC, and Han G Outage-limit-approaching channel coding for future wireless communications: Root-protograph low-density parity-check codes IEEE Veh. Technol. Mag. 2019 14 2 85-93
[26]
Amiri B, Reisizadehmobarakeh A, Esfahanizadeh H, Kliewer J, and Dolecek L Optimized design of finite-length separable circulant-based spatially-coupled codes: an absorbing set-based analysis IEEE Trans. Commun. 2016 64 3 918-931
[27]
D.G.M. Mitchell, L. Dolecek, D.J. Costello, Absorbing set characterization of array-based spatially coupled LDPC codes, in Proceedings of IEEE ISIT 2014, Honolulu, HI, USA, pp. 886–890 (2014)
[28]
D.G.M. Mitchell, E. Rosnes, Edge spreading design of high rate array-based SC-LDPC codes, in Proceedings of IEEE ISIT 2017, Aachen, Germany, pp. 2940–2944 (2017)
[29]
H. Esfahanizadeh, A. Hareedy, L. Dolecek, A novel combinatorial framework to construct spatially-coupled codes: minimum overlap partitioning, in Proceedings of IEEE ISIT 2017, Aachen, Germany, pp. 1693–1697 (2017)
[30]
A. Beemer, S. Habib, C.A. Kelley, J. Kliewer, A generalized algebraic approach to optimizing SC-LDPC codes, in Proceedings of 55th Annual Allerton Conference, Monticello, IL, pp. 672–679 (2017)
[31]
Esfahanizadeh H, Hareedy A, and Dolecek L Finite-length construction of high performance spatially-coupled codes via optimized partitioning and lifting IEEE Trans. Commun. 2019 67 1 3-16
[32]
Hareedy A, Wu R, and Dolecek L A channel-aware combinatorial approach to design high performance spatially-coupled codes IEEE Trans. Inf. Theory 2020 66 8 4834-4852
[33]
Mo S, Chen L, Costello DJ, Mitchell DGM, Smarandache R, and Qiu J Designing protograph-based quasi-cyclic spatially coupled LDPC codes with large girth IEEE Trans. Commun. 2020 68 9 5326-5337
[34]
L. Schmalen, V. Aref, F. Jardel, Non-uniformly coupled LDPC codes: Better thresholds, smaller rate-loss, and less complexity, in 2017 IEEE International Symposium on Information Theory (ISIT), pp. 376–380 (2017).
[35]
Yang S, Hareedy A, Calderbank R, and Dolecek L Breaking the computational bottleneck: Probabilistic optimization of high-memory spatially-coupled codes IEEE Trans. Inf. Theory 2023 69 2 886-909
[36]
M. Battaglioni, F. Chiaraluce, M. Baldi, D.G.M. Mitchell, Efficient search and elimination of harmful objects for the optimization of QC-SC-LDPC codes, in Proceedings of IEEE GLOBECOM 2019, Waikoloa, Hawaii, USA (2019)
[37]
Sadeghi M-R and Amirzade F Edge-coloring technique to analyze elementary trapping sets of spatially-coupled LDPC convolutional codes IEEE Commun. Lett. 2020 24 4 711-715
[38]
J.L. Fan, Array codes as low-density parity-check codes, in Proceedings of 2nd Interenational Symposium Turbo Codes, Brest, France, pp. 543–546 (2000)
[39]
H. Zhou, N. Goertz, Unavoidable cycles in polynomial-based time-invariant LDPC convolutional codes, in Proceedings of Wireless Conference on Sustainable Wireless Technology 2011, Vienna, Austria, pp. 1–6 (2011)
[40]
Wang Y, Draper SC, and Yedidia JS Hierarchical and high-girth QC LDPC codes IEEE Trans. Inf. Theory 2013 59 7 4553-4583
[41]
Fossorier MPC Quasi-cyclic low-density parity-check codes from circulant permutation matrices IEEE Trans. Inf. Theory 2004 50 8 1788-1793
[42]
Battaglioni M, Chiaraluce F, Baldi M, and Lentmaier M Girth analysis and design of periodically time-varying SC-LDPC codes IEEE Trans. Inf. Theory 2021 67 4 2217-2235
[43]
G. Liva, M. Chiani, Protograph LDPC codes design based on EXIT analysis, in IEEE GLOBECOM 2007—IEEE Global Telecommunications Conference, pp. 3250–3254 (2007).
[44]
Battaglioni M, Tasdighi A, Cancellieri G, Chiaraluce F, and Baldi M Design and analysis of time-invariant SC-LDPC convolutional codes with small constraint length IEEE Trans. Commun. 2018 66 3 918-931
[45]
Dijkstra EW A note on two problems in connexion with graphs Numer. Math. 1959 1 1 269-271
[46]
S. Zhang, C. Schlegel, Causes and dynamics of LDPC error floors on AWGN channels, in Proceedings of 49th Annual Allerton Conference, Monticello, IL, pp. 1025–1032 (2011)
[47]
A. Beemer, C.A. Kelley, Avoiding trapping sets in SC-LDPC codes under windowed decoding, in Proceedings of ISITA 2016, Monterey, CA, pp. 206–210 (2016)
[48]
L. Schmalen, D. Suikat, V. Aref, D. Roesener, On the design of capacity-approaching unit-memory spatially coupled LDPC codes for optical communications, in ECOC 2016; 42nd European Conference on Optical Communication, pp. 1–3 (2016)
[49]
K. Klaiber, S. Cammerer, L. Schmalen, S.t. Brink, Avoiding burst-like error patterns in windowed decoding of spatially coupled LDPC codes, in 2018 IEEE 10th International Symposium on Turbo Codes & Iterative Information Processing (ISTC), pp. 1–5 (2018).
[50]
Zhang G, Sun R, and Wang X Several explicit constructions for (3, L) QC-LDPC codes with girth at least eight IEEE Commun. Lett. 2013 17 9 1822-1825
[51]
Majdzade M and Gholami M On the class of high-rate QC-LDPC codes with girth 8 from sequences satisfied in GCD condition IEEE Commun. Lett. 2020 24 7 1391-1394
[52]
Zhang G, Hu Y, Fang Y, and Ren D Relation between GCD constraint and full-length row-multiplier QC-LDPC codes with girth eight IEEE Commun. Lett. 2021 25 9 2820-2823
[53]
Hashemi Y and Banihashemi AH Characterization and efficient search of non-elementary trapping sets of LDPC codes with applications to stopping sets IEEE Trans. Inf. Theory 2019 65 2 1017-1033
Index Terms
- Optimizing quasi-cyclic spatially coupled LDPC codes by eliminating harmful objects
Index terms have been assigned to the content through auto-classification.
Recommendations
Instanton-based techniques for analysis and reduction of error floors of LDPC codes
Special issue on capaciyy approaching codesWe 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 ...
Spatially Coupled LDPC Codes Constructed From Protographs
In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single coupled chain. By varying L , we obtain a flexible family ...
High Rate APPS and Bi-APPS LDPC Codes Design with Low Error Floor and Large Girth
In this paper, two new methods to construct low-density parity-check (LDPC) codes with low error floor and large girth are proposed. The first one is APPS-LDPC codes based on Arithmetic Progression theory and cycle classification, whose girth is at ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s) 2023.
Publisher
Hindawi Limited
London, United Kingdom
Publication History
Published: 25 July 2023
Accepted: 06 July 2023
Received: 26 September 2022
Author Tags
Qualifiers
- Research-article
Funding Sources
- Division of Human Resource Development
- Division of Computing and Communication Foundations
- Division of Electrical, Communications and Cyber Systems
- Division of Computing and Communication Foundations
- Jet Propulsion Laboratory
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 17 Jan 2025