Quasi-cyclic LDPC (QC-LDPC) code

Quasi-cyclic LDPC (QC-LDPC) code[2–8][1; Appx. C]

Description

LDPC code that can be put into quasi-cyclic form. Its parity check matrix can be put into the form of a block matrix consisting of either circulant permutation sub-matrices or the zero sub-matrix. Such codes are often constructed by lifting certain protographs into such block matrices [9]. Their simple structure makes them useful for several wireless communication standards.

Protection

Minimum-distance upper bounds exist [10,11].

Realizations

5G NR cellular communication for the traffic channel [12,13].Wireless communication: WiMAX (IEEE 802.16e) [14–16], WiFi 4 (IEEE 802.11n) [17], and WPAN (IEEE 802.15.3c) [18].

Cousins

LDPC convolutional code (LDPC-CC)— QC-LDPC codes can be unwrapped to obtain LDPC-CCs by expressing each circulant matrix block as a power of some generating circulant matrix and replacing that generating matrix by the shift operator of the convolutional code [19].
Repeat-accumulate (RA) code— There exist quasi-cyclic versions of RA codes [20].
Finite-geometry LDPC (FG-LDPC) code— Many FG-LDPC codes can be put into quasi-cyclic form [21,22][23; pg. 286].
Quantum LDPC (QLDPC) code— QC-LDPC codes can be used to make qubit QLDPC codes using various non-CSS constructions [24].
Quasi-cyclic QLDPC (QC-QLDPC) code
EA QC-QLDPC code
La-cross code— La-cross codes are constructed using a hypergraph product a cyclic LDPC code with itself.
Abelian LP code— QC-LDPC codes can be lifted to yield various Abelian LP codes [25–27]. Conversely, the Abelian LP construction yiels notable families of QC-LDPC codes [28].

Member of code lists

Primary Hierarchy

Classical Domain

Binary Kingdom

Binary codeECC

Binary group-orbit codeECC

Linear binary codeLinear \(q\)-ary 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

Quasi-cyclic codeECC

Quasi-cyclic LDPC (QC-LDPC) code

Children

Array-based LDPC (AB-LDPC) code

Block LDPC (B-LDPC) code

Difference-set cyclic (DSC) code

Cycle LDPC code

Cycle LDPC codes form a class of regular QC LDPC codes [29].

References

[1]: R. Gallager, Low-density parity check codes. 1963. PhD thesis, MIT Cambridge, MA.
[2]: H. Jin, T. Richardson, V. Novichkov, "Error Correction of Algebraic Block Codes". U.S. Patent, Number US8751902B2 2002
[3]: A. Yahya, O. Sidek, M. F. M. Salleh, and F. Ghani, “A new Quasi-Cyclic low density parity check codes”, 2009 IEEE Symposium on Industrial Electronics & Applications (2009) DOI
[4]: Tanner, R. Michael, Deepak Sridhara, and Tom Fuja. "A class of group-structured LDPC codes." Proc. ISTA. 2001.
[5]: B. Vasic, “Combinatorial constructions of low-density parity check codes for iterative decoding”, Proceedings IEEE International Symposium on Information Theory, DOI
[6]: I. Djurdjevic, Jun Xu, K. Abdel-Ghaffar, and Shu Lin, “A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols”, IEEE Communications Letters 7, 317 (2003) DOI
[7]: T. Okamura, “Designing LDPC codes using cyclic shifts”, IEEE International Symposium on Information Theory, 2003. Proceedings. (2003) DOI
[8]: M. P. C. Fossorier, “Quasi-Cyclic Low-Density Parity-Check Codes From Circulant Permutation Matrices”, IEEE Transactions on Information Theory 50, 1788 (2004) DOI
[9]: I. E. Bocharova, F. Hug, R. Johannesson, B. D. Kudryashov, and R. V. Satyukov, “Searching for Voltage Graph-Based LDPC Tailbiting Codes With Large Girth”, IEEE Transactions on Information Theory 58, 2265 (2012) arXiv:1108.0840 DOI
[10]: D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, Codes, Systems, and Graphical Models 113 (2001) DOI
[11]: R. Smarandache and P. O. Vontobel, “Quasi-Cyclic LDPC Codes: Influence of Proto- and Tanner-Graph Structure on Minimum Hamming Distance Upper Bounds”, IEEE Transactions on Information Theory 58, 585 (2012) DOI
[12]: T. Richardson and S. Kudekar, “Design of Low-Density Parity Check Codes for 5G New Radio”, IEEE Communications Magazine 56, 28 (2018) DOI
[13]: M. V. Patil, S. Pawar, and Z. Saquib, “Coding Techniques for 5G Networks: A Review”, 2020 3rd International Conference on Communication System, Computing and IT Applications (CSCITA) 208 (2020) DOI
[14]: LDPC coding for OFDMA PHY. 802.16REVe Sponsor Ballot Recirculation comment, July 2004. IEEE C802.16e04/141r2
[15]: T. Brack, M. Alles, F. Kienle, and N. Wehn, “A Synthesizable IP Core for WIMAX 802.16E LDPC Code Decoding”, 2006 IEEE 17th International Symposium on Personal, Indoor and Mobile Radio Communications (2006) DOI
[16]: G. Falcão, V. Silva, L. Sousa, and J. Marinho, “High coded data rate and multicodeword WiMAX LDPC decoding on Cell/BE”, Electronics Letters 44, 1415 (2008) DOI
[17]: Xiao Han, Kai Niu, and Zhiqiang He, “Implementation of IEEE 802.11n LDPC codes based on general purpose processors”, 2013 15th IEEE International Conference on Communication Technology (2013) DOI
[18]: W. Zhang, S. Chen, X. Bai, and D. Zhou, “A full layer parallel QC-LDPC decoder for WiMAX and Wi-Fi”, 2015 IEEE 11th International Conference on ASIC (ASICON) (2015) DOI
[19]: R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, “LDPC Block and Convolutional Codes Based on Circulant Matrices”, IEEE Transactions on Information Theory 50, 2966 (2004) DOI
[20]: M. R. Tanner, "On quasi-cyclic repeat-accumulate codes." PROCEEDINGS OF THE ANNUAL ALLERTON CONFERENCE ON COMMUNICATION CONTROL AND COMPUTING. Vol. 37. The University; 1998, 1999.
[21]: Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: a rediscovery and new results”, IEEE Transactions on Information Theory 47, 2711 (2001) DOI
[22]: Heng Tang, Jun Xu, S. Lin, and K. A. S. Abdel-Ghaffar, “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
[23]: “Latin Squares and their Applications”, (2015) DOI
[24]: P. Tan and J. Li, “Efficient Quantum Stabilizer Codes: LDPC and LDPC-Convolutional Constructions”, IEEE Transactions on Information Theory 56, 476 (2010) DOI
[25]: N. Raveendran, N. Rengaswamy, F. Rozpędek, A. Raina, L. Jiang, and B. Vasić, “Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound”, Quantum 6, 767 (2022) arXiv:2111.07029 DOI
[26]: S. Miao, J. Mandelbaum, H. Jäkel, and L. Schmalen, “A Joint Code and Belief Propagation Decoder Design for Quantum LDPC Codes”, (2024) arXiv:2401.06874
[27]: T. R. Scruby, T. Hillmann, and J. Roffe, “High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory”, (2024) arXiv:2406.14445
[28]: F. G. Jeronimo, T. Mittal, R. O’Donnell, P. Paredes, and M. Tulsiani, “Explicit Abelian Lifts and Quantum LDPC Codes”, (2021) arXiv:2112.01647
[29]: R. M. Tanner, D. Sridhara, A. Sridharan, T. E. Fuja, and D. J. Costello, “LDPC Block and Convolutional Codes Based on Circulant Matrices”, IEEE Transactions on Information Theory 50, 2966 (2004) DOI

Page edit log

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

Cite as:

“Quasi-cyclic LDPC (QC-LDPC) code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/qc_ldpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/qc/qc_ldpc.yml.