Tanner code[1]
Description
Binary linear code defined on edges on a regular graph \(G\) such that each subsequence of bits corresponding to edges in the neighborhood any vertex belong to some short binary linear code \(C_0\). Expansion properties of the underlying graph can yield efficient decoding algorithms.
More technically, let \(G(V,E)\) be a \(\Delta\)-regular (not necessarily bipartite) graph with number of vertices \(|V| = n \) and number of edges \(|E| = N = n\Delta/2\). Let \(C_0\) be a linear binary code of length \(\Delta\) and rate \(R_0\). The Tanner code \(T(G,C_0)\), whose bits are placed on edges of the graph, consists of the following codewords: \begin{align} \left\{ c \in GF(2)^{n}\,\text{s.t. }\forall v\in V,\left.c\right|_{N(v)}\in C_{0}\right\} ~, \end{align} where \(\left.c\right|_{N(v)}\) is the subsequence formed by the \(\Delta\) bits located on the neighbors \(N(v)\) of the vertex \(v\). The dimension of \(T\) is at least \(N -n(\Delta -\Delta R_0) = N(2R_0-1)\geq 0\) whenever \(R_0 \geq \frac{1}{2}\).
Protection
Rate
Encoding
Decoding
Parents
Child
Cousins
- Dinur-Hsieh-Lin-Vidick (DHLV) code — Tanner codes are used in constructing quantum DHLV codes.
- Expander lifted-product code — Expander lifted-product codes are products of \(q\)-ary Tanner codes defined on expander graphs.
- Quantum Tanner code — Tanner codes are used in constructing quantum Tanner codes.
References
- [1]
- R. Tanner, “A recursive approach to low complexity codes”, IEEE Transactions on Information Theory 27, 533 (1981). DOI
- [2]
- J. D. Lafferty and D. N. Rockmore, “Spectral techniques for expander codes”, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 (1997). DOI
- [3]
- D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory 42, 1723 (1996). DOI
- [4]
- M. Sipser and D. A. Spielman, “Expander codes”, IEEE Transactions on Information Theory 42, 1710 (1996). DOI
- [5]
- G. Zemor, “On expander codes”, IEEE Transactions on Information Theory 47, 835 (2001). DOI
Page edit log
- Victor V. Albert (2022-04-21) — most recent
- Xiaozhen Fu (2022-03-30)
- Victor V. Albert (2021-11-29)
Zoo code information
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/tree/main/codes/classical/bits/tanner.yml.