# Regular binary Tanner code[1]

## Description

A binary Tanner code defined on a regular bipartite graph, with the inner code being the same for all vertices.

An alternative definition maps the variable nodes of the generalized Tanner graph to edges of a regular graph \(G\) and the constraint nodes to vertices of \(G\). Bits are placed on edges of \(G\) such that each subsequence of bits corresponding to edges in the neighborhood any vertex belong to some short binary linear code \(C_0\).

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\} ~, \tag*{(1)}\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

## Realizations

## Parents

- Linear binary code
- 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.

## Children

- Generalized Gallager code
- Regular LDPC code — Regular LDPC codes are regular binary Tanner codes defined on sparse graphs whose constraint nodes represent parity-check codes.

## Cousins

- Dinur-Hsieh-Lin-Vidick (DHLV) code — Regular binary Tanner codes are used in constructing quantum DHLV codes.
- Quantum Tanner code — Regular binary 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]
- R. M. Tanner, “Minimum-distance bounds by graph analysis”, IEEE Transactions on Information Theory 47, 808 (2001) DOI
- [3]
- C. A. Kelley, “Minimum distance and pseudodistance lower bounds for generalised LDPC codes”, International Journal of Information and Coding Theory 1, 313 (2010) DOI
- [4]
- C. A. Kelley and D. Sridhara, “Eigenvalue bounds on the pseudocodeword weight of expander codes”, (2007) arXiv:0708.2462
- [5]
- 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
- [6]
- D. A. Spielman, “Linear-time encodable and decodable error-correcting codes”, IEEE Transactions on Information Theory 42, 1723 (1996) DOI
- [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]
- K. Karplus and H. Krit, “A semi-systolic decoder for the PDSC-73 error-correcting code”, Discrete Applied Mathematics 33, 109 (1991) 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:

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