Fast Decoding of Expander Codes

5 years ago

Fast Decoding of Expander Codes

Michael Dowling, , Shuhong Gao

Expander codes are Tanner codes defined on sparse graphs that have good expansion properties. Sipser and Spielman (1996) showed that there is a linear-time decoding algorithm for expander codes when the vertex expansion is at least 3/4 and the number of errors corrected is a constant fraction of the code length. Later, Feldman et al. (2007) gave a decoding algorithm that allows the expansion to be 2/3 + 1/(3c), where

$c$

is the left degree of the underlying bipartite graph, at the expense of polynomial-time decoding complexity. Recently, Viderman (2013) further improved the expansion parameter to

$2/3 - 1/(6c)$

, and the decoding algorithm runs in linear time. These results are for expander codes whose inner codes are parity-check codes. By using stronger inner codes, Chilappagari et al. (2010) showed that there is a linear-time decoding algorithm for every vertex expansion greater than 1/2. In this paper, it is shown that for every vertex expansion, there is a linear-time decoding algorithm for expander codes (using inner codes with minimum distance depending on the vertex expansion), and that the number of errors corrected is a constant fraction of the code length.

Publisher URL: http://ieeexplore.ieee.org/document/7976348

DOI: 7976348