Improved Linear-Time Decoding of Generalized Expander Codes

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$ . Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that $δ>3/4$ is sufficient; later Viderman (ACM-TOCT'13) improved this to $δ>2/3-Ω(1)$ and he also showed that $δ>1/2$ is necessary. For general linear code $C_0$ , the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$ . In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph $G$ together with a linear inner code $C_0$. Expander codes are Tanner codes whose defining bipartite graph $G$ has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that $δ$ and $d_0$ must satisfy, so that \textit{every} bipartite expander $G$ with vertex expansion ratio $δ$ and \textit{every} linear inner code $C_0$ with minimum distance $d_0$ together define an expander code that corrects $Ω(n)$ errors in $O(n)$ time? For $C_0$ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that $δ>3/4$ is sufficient; later Viderman (ACM-TOCT'13) improved this to $δ>2/3-Ω(1)$ and he also showed that $δ>1/2$ is necessary. For general linear code $C_0$, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that $d_0=Ω(cδ^{-2})$ is sufficient, where $c$ is the left-degree of $G$. In this paper, we give a near-optimal solution to the above question for general $C_0$ by showing that $δd_0>3$ is sufficient and $δd_0>1$ is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.

arXiv:2312.16087Leibniz international proceedings in informaticsDec 26, 20230 citations

A decoding algorithm for linear codes

Martin Bossert, F. Hergert

Lecture notes in computer scienceJan 1, 19862 citations

Generalized minimum distance iterative decoding of expander codes

Vitaly Skachek, Ron M. Roth

Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.Recently, G. Zemor (see IEEE Trans. Inf. Theory, vol.47, p.835-7, 2001) proposed an improvement on the Sipser-Spielman analysis of expander codes (Sipser, M. and Spielman, D.A., IEEE Trans. Inf. Theory, vol.42 , p.1710-22, 1996) and presented a linear-time iterative decoder that can correct a number of errors up to approximately 1/4 the known lower bound on the minimum distance of the code. We propose an improvement on Zemor's decoder for F=GF(2), with the number of correctable errors becoming close to half the lower bound on the minimum distance. The improvement is obtained by inserting into the decoding algorithm features akin to generalized minimum distance decoding of concatenated codes.

IEEE Information Theory Workshop (ITW)Mar 1, 200427 citations

Linear-Time Erasure List-Decoding of Expander Codes

Noga Ron‐Zewi, Mary K. Wootters, Gilles Zémor

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner codeC0of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the codeC=C(G,C0) of length nd from approximately δδrnd erasures in time n·poly (d2r/δ), where δ and δrare the relative distance and the r'th generalized relative distance ofC0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters.

arXiv:2002.08579IEEE International Symposium on Information Theory (ISIT)Jun 1, 20206 citations

Decoding Methods for Linear Codes

Kenny Barrese

Jun 4, 20080 citations

Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph

G

together with a linear inner code

C_0

. Expander codes are Tanner codes whose defining bipartite graph

G

has good expansion property. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that

δ

and

d_0

must satisfy, so that \textit{every} bipartite expander

G

with vertex expansion ratio

δ

and \textit{every} linear inner code

C_0

with minimum distance

d_0

together define an expander code that corrects

Ω(n)

errors in

O(n)

time? For

C_0

being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that

δ>3/4

is sufficient; later Viderman (ACM-TOCT'13) improved this to

δ>2/3-Ω(1)

and he also showed that

δ>1/2

is necessary. For general linear code

C_0

, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that

d_0=Ω(cδ^{-2})

is sufficient, where

c

is the left-degree of

G

. In this paper, we give a near-optimal solution to the above question for general

C_0

by showing that

δd_0>3

is sufficient and

δd_0>1

is necessary, thereby also significantly improving Dowling-Gao's result. We present two novel algorithms for decoding expander codes, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius.