Regular binary Tanner code

Regular binary Tanner code[1]

Also known as Regular binary GLDPC code.

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

Minimum-distance bounds in terms of graph and short-code parameters include the bit-oriented or parity-oriented bounds [2] along with others [2–4].

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 GV 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 [5].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 [5].A modified construction yields codes that may be encoded in linear time yet maintain similar performance [6].

Decoding

Parallel decoding algorithm corrects a fraction \(\delta_0^2/48\) of errors for Tanner codes [7]. A modification of said algorithm improves the fraction to \(\delta_0^2/4\) with no extra cost to complexity [8].Soft-decision linear-time decoder correcting errors almost up to half of the Blokh-Zyablov bound [9].

Realizations

First hardware implementation was done using a semi-systolic decoding architecture [10].

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]: A. Barg and G. Zemor, “Concatenated Codes: Serial and Parallel”, IEEE Transactions on Information Theory 51, 1625 (2005) DOI
[10]: 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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/tanner/regular_tanner/regular_binary_tanner.yml.