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 [24].

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 [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].

Realizations

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

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

Cousins

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

Your contribution is welcome!

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

edit on this site

Zoo Code ID: regular_binary_tanner

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

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.