On Tanner codes: Minimum distance and decoding (Q1566399)

A result of Zémor on the edge density of a subgraph of a \(d\)-regular graph is generalized to give a bound on the minimum distance of Tanner codes. This is the only bound on the minimum distance of Tanner codes obtained from arbitrary \((c,d)\)-regular bipartite graphs. Also the bound on the minimum distance of expander codes of \textit{M. Sipser} and \textit{D. Spielman} [IEEE Trans. Inf. Theory 42, 1710-1722 (1996; Zbl 0943.94543)] is obtained. An algorithm for decoding Tanner codes is presented, and its complexity and error-correcting capabilities using the generalized result are analyzed. The algorithm can be implemented using the same complexity as that of Zémor and has a similar error-correction capability. Explicit families of Tanner codes are presented for which the decoding algorithm is applicable, and asymptotic results and applications are discussed.