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].

Parents

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 [19].

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 [20].
Repeat-accumulate (RA) code — There exist quasi-cyclic versions of RA codes [21].
Finite-geometry LDPC (FG-LDPC) code — Many FG-LDPC codes can be put into quasi-cyclic form [22,23][24; pg. 286].
Quantum low-density parity-check (QLDPC) code — QC-LDPC codes can be used to make QLDPC codes using various non-CSS constructions [25].
EA quasi-cyclic QLDPC code
Abelian LP code — QC-LDPC codes can be lifted to yield various Abelian LP codes [26–28]. Conversely, the Abelian LP construction yiels notable families of QC-LDPC codes [29].

References

[1]: R. Gallagher, 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 et al., “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 et al., “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 et al., “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) (2020) DOI
[14]: LDPC coding for OFDMA PHY. 802.16REVe Sponsor Ballot Recirculation comment, July 2004. IEEE C802.16e04/141r2
[15]: T. Brack et al., “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 et al., “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 et al., “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 et al., “LDPC Block and Convolutional Codes Based on Circulant Matrices”, IEEE Transactions on Information Theory 50, 2966 (2004) DOI
[20]: R. M. Tanner et al., “LDPC Block and Convolutional Codes Based on Circulant Matrices”, IEEE Transactions on Information Theory 50, 2966 (2004) DOI
[21]: 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.
[22]: 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
[23]: Heng Tang et al., “Codes on finite geometries”, IEEE Transactions on Information Theory 51, 572 (2005) DOI
[24]: “Latin Squares and their Applications”, (2015) DOI
[25]: P. Tan and J. Li, “Efficient Quantum Stabilizer Codes: LDPC and LDPC-Convolutional Constructions”, IEEE Transactions on Information Theory 56, 476 (2010) DOI
[26]: N. Raveendran et al., “Finite Rate QLDPC-GKP Coding Scheme that Surpasses the CSS Hamming Bound”, Quantum 6, 767 (2022) arXiv:2111.07029 DOI
[27]: S. Miao et al., “A Joint Code and Belief Propagation Decoder Design for Quantum LDPC Codes”, (2024) arXiv:2401.06874
[28]: T. R. Scruby, T. Hillmann, and J. Roffe, “High-threshold, low-overhead and single-shot decodable fault-tolerant quantum memory”, (2024) arXiv:2406.14445
[29]: F. G. Jeronimo et al., “Explicit Abelian Lifts and Quantum LDPC Codes”, (2021) arXiv:2112.01647

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.