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

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 [12] and LTCs [13].
  • 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 [12] and LTCs [13].
  • Expander LP code — Expander lifted-product codes are products of regular \(q\)-ary Tanner codes defined on expander graphs [14].

References

[1]
R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981) DOI
[2]
N. Wiberg, H.-A. 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]
P. Panteleev and G. Kalachev, “Maximally Extendable Sheaf Codes”, (2024) arXiv:2403.03651
[13]
U. A. First and T. Kaufman, “Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query LTCs and Lifted Codes”, (2024) arXiv:2403.19388
[14]
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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: tanner

Cite as:
“Tanner code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/tanner
BibTeX:
@incollection{eczoo_tanner, title={Tanner code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/tanner} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/tanner

Cite as:

“Tanner code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/tanner

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