A Comparison of Minimum Distance Bounds on Tanner/Expander Codes

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that $\delta d_{0}>2$ , corrects up to $\alpha n$ errors for a Tanner code $T\left(G, C_{0}\right)$ , where $G$ is a ( $c, d, \alpha, \delta$ ) bipartite expander with $n$ left vertices, and $C_{0} \subseteq \mathbb{F}_{2}^{d}$ is a linear inner code with minimum distance $d_{0}$ . This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required $\delta d_{0}>3$ . We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of $\alpha n$ , compared with the previous radius of $\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n$ . Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code $T\left(G, C_{0}\right)$ is approximately $f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$ , where $f_{\delta}(\cdot)$ is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from $\alpha n$ to approximately $f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$ .In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that$\delta d_{0}>2$, corrects up to$\alpha n$errors for a Tanner code$T\left(G, C_{0}\right)$, where$G$is a ($c, d, \alpha, \delta$) bipartite expander with$n$left vertices, and$C_{0} \subseteq \mathbb{F}_{2}^{d}$is a linear inner code with minimum distance$d_{0}$. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required$\delta d_{0}>3$. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of$\alpha n$, compared with the previous radius of$\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n$. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code$T\left(G, C_{0}\right)$is approximately$f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n$, where$f_{\delta}(\cdot)$is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from$\alpha n$to approximately$f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n$.

arXiv:2501.12293IEEE International Symposium on Information Theory (ISIT)Jun 22, 20252 citations

Eigenvalue bounds on the pseudocodeword weight of expander codes

Christine A. Kelley, Deepak Sridhara

Four different ways of obtaining low-density parity-check codesfrom expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimumdistance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.Four different ways of obtaining low-density parity-check codesfrom expander graphs are considered. For each case, lower bounds on the minimum stopping set size and the minimum pseudocodeword weight of expander (LDPC) codes are derived. These bounds are compared with the known eigenvalue-based lower bounds on the minimum distance of expander codes. Furthermore, Tanner's parity-oriented eigenvalue lower bound on the minimumdistance is generalized to yield a new lower bound on the minimum pseudocodeword weight. These bounds are useful in predicting the performance of LDPC codes under graph-based iterative decoding and linear programming decoding.

arXiv:0708.2462Advances in Mathematics of CommunicationsJan 1, 200711 citations

An Improvement to Generalized-Minimum-Distance Decoding

Steven S. Pietrobon, Robert Huijie Deng, A. Lafanechere +1 more

Jan 1, 19910 citations

Bounds for error-correcting codes (Corresp.)

W. W. Peterson

IEEE Transactions on Information TheoryJan 1, 19622 citations

In this paper, we present improved decoding algorithms for expander-based Tanner codes. We begin by developing a randomized linear-time decoding algorithm that, under the condition that

\delta d_{0}>2

, corrects up to

\alpha n

errors for a Tanner code

T\left(G, C_{0}\right)

, where

G

is a (

c, d, \alpha, \delta

) bipartite expander with

n

left vertices, and

C_{0} \subseteq \mathbb{F}_{2}^{d}

is a linear inner code with minimum distance

d_{0}

. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which required

\delta d_{0}>3

. We further derandomize the algorithm to obtain a deterministic linear-time decoding algorithm with the same decoding radius. Our algorithm improves upon the previous deterministic algorithm of Cheng et al. by achieving a decoding radius of

\alpha n

, compared with the previous radius of

\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} n

. Additionally, we investigate the size-expansion trade-off introduced by the recent work of Chen, Cheng, Li, and Ouyang (IEEE TIT 2023), and use it to provide new bounds on the minimum distance of Tanner codes. Specifically, we prove that the minimum distance of a Tanner code

T\left(G, C_{0}\right)

is approximately

f_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha n

, where

f_{\delta}(\cdot)

is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms from

\alpha n

to approximately

f_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha n