Spatially coupled LDPC (SC-LDPC) code

Spatially coupled LDPC (SC-LDPC) code[1–5]

Description

An LDPC code whose parity-check matrix is constructed by “spatially” coupling several copies of a regular LDPC parity-check matrix in chain-like fashion (or, more generally, in grid-like fashion) to yield a band matrix. A finite-length chain is then capped by imposing either open boundary conditions (yielding non-tail-biting SC-LDPC codes) or periodic boundary conditions (yielding tail-biting SC-LDPC codes); sometimes extra terminating vertices are added to the ends of the chain. Matrices corresponding to translationally invariant chains are called time-invariant, and otherwise are called time-varying. These codes can be constructed, e.g., using the lifting procedure or using edge-cutting vectors [6]. Spatial coupling can also be applied to MN-LDPC and HA-LDPC protographs, yielding bounded-density SC-MN and SC-HA families [7].

Protection

SC-LDPCs sometimes outperform other LDPC constructions [8,9].

Rate

Spatial coupling of LDPC codes can increase the achievable rate against BEC, coming close to the capacity [1,4,10]. SC-LDPC codes achieve capacity of the binary memoryless symmetric (BMS) channel [11,12]. Spatial coupling of MN-LDPC and HA-LDPC codes yields bounded-density SC-MN and SC-HA families whose BEC BP thresholds are empirically close to the Shannon limit [7].

Cousins

LDPC convolutional code (LDPC-CC)— Infinite-block versions of SC-LDPC are LDPC-CCs.
MacKay-Neal LDPC (MN-LDPC) code— Spatial coupling of MN-LDPC protographs yields bounded-density SC-MN codes with BEC BP thresholds close to the Shannon limit [7].
Hsu-Anastasopoulos LDPC (HA-LDPC) code— Spatial coupling of HA-LDPC protographs yields bounded-density SC-HA codes with BEC BP thresholds close to the Shannon limit [7].
Quantum spatially coupled (SC-QLDPC) code— SC-QLDPC code stabilizer-generator matrices have similar block form as the parity-check matrices of SC-LDPC codes.

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Binary group-orbit codeECC

Linear binary codeLinear \(q\)-ary Linear code over \(\mathbb{Z}_q\) ECC

Low-density parity-check (LDPC) code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC

Multi-edge LDPC code

Protograph LDPC code\(q\)-ary LDPC Tanner Linear \(q\)-ary LRC Distributed-storage ECC

Parents

Protograph LDPC code

SC-LDPC codes can be interpreted as protograph LDPC codes [13].

Spatially coupled LDPC (SC-LDPC) code

References

[1]: A. Jimenez Felstrom and K. S. Zigangirov, “Time-varying periodic convolutional codes with low-density parity-check matrix”, IEEE Transactions on Information Theory 45, 2181 (1999) DOI
[2]: K. Engdahl and K. Sh. Zigangirov, “To the Theory of Low-Density Convolutional Codes. I”, Problemy Peredachi Informatsii, 35:4 (1999), 12–28; Problems of Information Transmission, 35:4 (1999), 295–310
[3]: M. Lentmaier, D. V. Truhachev, and K. Sh. Zigangirov, Problems of Information Transmission 37, 288 (2001) DOI
[4]: S. Kudekar, T. J. Richardson, and R. L. Urbanke, “Threshold Saturation via Spatial Coupling: Why Convolutional LDPC Ensembles Perform So Well over the BEC”, IEEE Transactions on Information Theory 57, 803 (2011) DOI
[5]: S. Kudekar, T. Richardson, and R. L. Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation”, IEEE Transactions on Information Theory 59, 7761 (2013) DOI
[6]: H. Esfahanizadeh, A. Hareedy, and L. Dolecek, “Finite-Length Construction of High Performance Spatially-Coupled Codes via Optimized Partitioning and Lifting”, IEEE Transactions on Communications 67, 3 (2019) DOI
[7]: K. KASAI and K. SAKANIWA, “Spatially-Coupled MacKay-Neal Codes and Hsu-Anastasopoulos Codes”, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A, 2161 (2011) arXiv:1102.4612 DOI
[8]: N. ul Hassan, M. Lentmaier, and G. P. Fettweis, “Comparison of LDPC block and LDPC convolutional codes based on their decoding latency”, 2012 7th International Symposium on Turbo Codes and Iterative Information Processing (ISTC) 225 (2012) DOI
[9]: D. J. Costello, A. E. Pusane, C. R. Jones, and D. Divsalar, “A Comparison of ARA- and Protograph-Based LDPC Block and Convolutional Codes”, 2007 Information Theory and Applications Workshop 111 (2007) DOI
[10]: M. Lentmaier, A. Sridharan, K. Sh. Zigangirov, and D. J. Costello, “Terminated LDPC convolutional codes with thresholds close to capacity”, Proceedings. International Symposium on Information Theory, 2005. ISIT 2005. 1372 (2005) arXiv:cs/0508030 DOI
[11]: S. Kudekar, T. Richardson, and R. Urbanke, “Spatially Coupled Ensembles Universally Achieve Capacity under Belief Propagation”, (2012) arXiv:1201.2999
[12]: S. Kumar, A. J. Young, N. Macris, and H. D. Pfister, “Threshold Saturation for Spatially Coupled LDPC and LDGM Codes on BMS Channels”, IEEE Transactions on Information Theory 60, 7389 (2014) arXiv:1309.7543 DOI
[13]: A. Beemer, S. Habib, C. A. Kelley, and J. Kliewer, “A Generalized Algebraic Approach to Optimizing SC-LDPC Codes”, (2017) arXiv:1710.03619

Page edit log

Victor V. Albert (2023-05-04) — most recent

Cite as:

“Spatially coupled LDPC (SC-LDPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/sc_ldpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/regular_tanner/regular_ldpc/sc_ldpc.yml.