Tanner code

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

Tanner Codes protect against noise on classical bit strings. If \(C_0\) is an \([d, d-t,d'> d(\gamma_0 +\frac{\lambda}{d})]_2\) code and G is an \((N, M, 2, d, \rho,\alpha)\)- expander where \(\rho = \gamma_0 (\gamma_0 +\frac{\lambda}{d})\), then the Tanner Code \(T(G, C_0)\) has rate \(1-\frac{M}{N}t\) and relative distance \(\geq \gamma_0(\gamma_0+\frac{\lambda}{d})\).

Rate

For a short code \(C_0\) with rate \(R_0\), the Tanner code has rate \(R \geq 2R_0-1\). If \(C_0\) satisfies the Gilbert-Varshamov bound, the rate \(R \geq \delta = 1-2h(\delta_0)\), where \(\delta\) (\(\delta_0\)) is the relative distance of the Tanner code (\(C_0\)), and \(h\) is the binary entropy function.

Encoding

Quadratic algorithm: This technique works for all linear block codes and encodes using matrix multiplication [2].Using the non-Abelian Fast Fourier Transform and exploiting the symmetry of the underlying graph, an encoding algorithm that requires \(O(n^{4/3})\) has been devised in [2].A modified construction yields codes that may be encoded in linear time yet maintain similar performance [3].

Decoding

Parallel decoding algorithm corrects a fraction \(\delta_0^2/48\) of errors for Tanner codes [4]. A modification of said algorithm improves the fraction to \(\delta_0^2/4\) with no extra cost to complexity [5].

Parents

Child

Expander code

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)

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.