Tanner code[1]
Also known as Generalized LDPC (GLDPC) code.
Description
A linear \(q\)-ary code defined on a bipartite graph similar to a Tanner graph. This generalized Tanner graph consists of variable nodes and constraint nodes, with the generalization being that the constraint nodes of degree \(r\) now represent a linear codes of length \(r\).
A string is in the Tanner code if all substrings satisfy their corresponding constraints, i.e., all substrings are members of the linear codes represented on the constraint nodes.
A code is called regular if the corresponding bipartite graph is regular. Expansion properties of the underlying graph can yield efficient decoding algorithms.
Decoding
Min-sum and sum-product iterative decoders for binary Tanner codes [2,3]; see also [4,5]. These decoders can be improved using a probabilistic message-passing schedule [6].Any code can be put into normal form without significantly altering the underlying graph or the decoding complexity [7]. For an algebraic viewpoint on decoding, see [8].Iterative decoding is optimal for Tanner graphs that are free of cycles [3]. However, codes that admit cycle-free representations have bounds on their distances [1,9]; see [10,11].
Parents
- Linear \(q\)-ary code
- Parallel concatenated code — Tanner codes are examples of parallel concatenation [12].
Children
- Regular binary Tanner code — Regular binary Tanner codes are binary Tanner codes defined on regular sparse bipartite graphs, with the inner code being the same for all vertices.
- \(q\)-ary LDPC code — \(q\)-ary LDPC codes are \(q\)-ary Tanner codes on sparse bipartite graphs whose constraint nodes represent \(q\)-ary parity-check codes.
Cousins
- Generalized homological-product CSS code — Tanner codes can be generalized to sheaf codes, whose local codes satisfy a certain hierarchy. This allows for a way to formulate and understand many generalized homological-product CSS codes [13] and LTCs [14].
- Locally testable code (LTC) — Tanner codes can be generalized to sheaf codes, whose local codes satisfy a certain hierarchy. This allows for a way to formulate and understand many generalized homological-product CSS codes [13] and LTCs [14].
- Expander LP code — Expander lifted-product codes are products of regular \(q\)-ary Tanner codes defined on expander graphs [15].
References
- [1]
- R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981) DOI
- [2]
- N. Wiberg, H. Loeliger, and R. Kotter, “Codes and iterative decoding on general graphs”, European Transactions on Telecommunications 6, 513 (1995) DOI
- [3]
- Niclas Wiberg, Codes and decoding on general graphs. 1996. PhD thesis, Linköping University, Linköping, Sweden
- [4]
- Brendan J. Frey. Graphical models for machine learning and digital communication. MIT press, 1998.
- [5]
- R. McEliece, The Theory of Information and Coding (Cambridge University Press, 2002) DOI
- [6]
- Yongyi Mao and A. H. Banihashemi, “Decoding low-density parity-check codes with probabilistic schedule”, 2001 IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (IEEE Cat. No.01CH37233) DOI
- [7]
- G. D. Forney, “Codes on graphs: normal realizations”, 2000 IEEE International Symposium on Information Theory (Cat. No.00CH37060) DOI
- [8]
- E. Soljanin and E. Offer, “LDPC codes: a group algebra formulation”, Electronic Notes in Discrete Mathematics 6, 148 (2001) DOI
- [9]
- T. Etzion, A. Trachtenberg, and A. Vardy, “Which codes have cycle-free Tanner graphs?”, IEEE Transactions on Information Theory 45, 2173 (1999) DOI
- [10]
- C. A. Kelley, "Codes over Graphs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [11]
- D. K. Kythe and P. K. Kythe, “Algebraic and Stochastic Coding Theory”, (2017) DOI
- [12]
- A. Barg and G. Zemor, “Concatenated Codes: Serial and Parallel”, IEEE Transactions on Information Theory 51, 1625 (2005) DOI
- [13]
- P. Panteleev and G. Kalachev, “Maximally Extendable Sheaf Codes”, (2024) arXiv:2403.03651
- [14]
- U. A. First and T. Kaufman, “Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes”, (2024) arXiv:2403.19388
- [15]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
Page edit log
- Victor V. Albert (2023-05-04) — most recent
Cite as:
“Tanner code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/tanner