\(q\)-ary LDPC code

\(q\)-ary LDPC code[1]

Alternative names: Non-binary LDPC (NBDPC) code.

Description

A \(q\)-ary linear code with a sparse parity-check matrix. Alternatively, a member of an infinite family of \([n,k,d]_q\) codes for which the number of nonzero entries in each row and column of the parity-check matrix are both bounded above by a constant as \(n\to\infty\).

A parity check is performed by taking the inner product of a row of the parity-check matrix with a codeword that has been affected by a noise channel. A parity check yields either zero (no error) or a nonzero field element (error). Despite the fact that there is more than one nonzero outcome, \(q>2g\)-ary linear codes with sparse parity-check matrices are also called LDPC codes.

Protection

Non-binary cycle LDPC codes for \(q\geq 32\) can exhibit good performance [2–4].

Rate

Asymptotically good non-binary expander codes can be constructed [6][5; Thm. 7.16] by generalizing the originally binary expander constructions [7,8].

Cousins

\(q\)-ary LDGM code— The dual of a \(q\)-ary LDPC code has a sparse generator matrix and is called a \(q\)-ary LDGM code.
Dual linear code— The dual of a \(q\)-ary LDPC code has a sparse generator matrix and is called a \(q\)-ary LDGM code.
Expander code— Asymptotically good non-binary expander codes can be constructed [6][5; Thm. 7.16] by generalizing the originally binary expander constructions [7,8].

Member of code lists

Primary Hierarchy

Classical Domain

Galois-field Kingdom

\(q\)-ary codeECC

Additive \(q\)-ary codeECC

Linear \(q\)-ary codeECC

Tanner codeECC

Parents

Tanner code

\(q\)-ary LDPC codes are \(q\)-ary Tanner codes on sparse bipartite graphs whose constraint nodes represent \(q\)-ary parity-check codes.

Locally recoverable code (LRC)Distributed-storage ECC

LDPC codes are linear LRCs whose locality is the maximum number of nonzero entries in a row of the parity-check matrix [9].

\(q\)-ary LDPC code

Children

Low-density parity-check (LDPC) code

\(q\)-ary protograph LDPC code

References

[1]: M. C. Davey and D. J. C. MacKay, “Low density parity check codes over GF(q)”, 1998 Information Theory Workshop (Cat. No.98EX131) DOI
[2]: X.-Yu. Hu and E. Eleftheriou, “Binary representation of cycle Tanner-graph GF(2/sup b/) codes”, 2004 IEEE International Conference on Communications (IEEE Cat. No.04CH37577) 528 (2004) DOI
[3]: R.-H. Peng and R.-R. Chen, “Design of Nonbinary Quasi-Cyclic LDPC Cycle Codes”, 2007 IEEE Information Theory Workshop 13 (2007) DOI
[4]: C. Poulliat, M. Fossorier, and D. Declercq, “Design of regular (2,d/sub c/)-LDPC codes over GF(q) using their binary images”, IEEE Transactions on Communications 56, 1626 (2008) DOI
[5]: Jeronimo, Fernando Granha. “Fast decoding of explicit almost optimal ε-balanced q-ary codes and fast approximation of expanding k-CSPs.” Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2023.
[6]: Rao, Anup. “Lecture 6: Expander Codes: Tanner Codes.” Coding Theory lecture notes, 14 Oct. 2019, University of Washington
[7]: M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996) DOI
[8]: G. Zemor, “On expander codes”, IEEE Transactions on Information Theory 47, 835 (2001) DOI
[9]: L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653

Page edit log

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

Cite as:

“\(q\)-ary LDPC code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/q-ary_ldpc

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/tanner/q-ary_ldpc.yml.