Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Algebra and Its Applications

Linear-time decoding from a constant fraction of errors for irregular expander codes

Rutuja Kshirsagar, Gretchen L. Matthews

Published Apr 16, 2025• 0 citations
Publisher

Abstract

In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.

DOI
10.1142/s0219498825410270

Related papers

Fast Decoding of Expander Codes

Michael C. 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.

IEEE Transactions on Information Theory•Jul 12, 2017•4 citations

When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Yuanting Shen, Chong Shangguan, Minghui Ouyang +1 more

Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being 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 codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.

IEEE Transactions on Information Theory•Jul 7, 2025•0 citations

When Can an Expander Code Correct Ω(n) Errors in O(n) Time?

Kuan Cheng, Minghui Ouyang, Chong Shangguan +1 more

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.16087•Leibniz international proceedings in informatics•Dec 26, 2023•0 citations

Linear time decoding of regular expander codes

Michael Viderman

Sipser and Spielman (IEEE IT, [1996]) showed that any c , d )-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, [2007]) proved that expansion parameter >⅔ + 1/3c is sufficient to correct a constant fraction of errors in polynomial time using LP decoding. In this work, we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in linear time and works for any expansion parameter >⅔ − 1/6c. We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.

Conference on Innovations in Theoretical Computer Science•Jan 8, 2012•8 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.

IEEE Information Theory Workshop (ITW)•Mar 1, 2004•27 citations

On expander codes

Gilles Zémor

Sipser and Spielman (see ibid., vol.42, p.1717-22, Nov. 1996) have introduced a constructive family of asymptotically good linear error-correcting codes-expander codes-together with a simple parallel algorithm that will always remove a constant fraction of errors. We introduce a variation on their decoding algorithm that, with no extra cost in complexity, provably corrects up to 12 times more errors.

IEEE Transactions on Information Theory•Jan 1, 2001•137 citations
In this paper, we present a linear-time decoding algorithm for expander codes based on irregular graphs of any positive vertex expansion factor [Formula: see text] and inner codes with a minimum distance of at least [Formula: see text], where [Formula: see text] is the maximum right degree. The algorithm corrects a constant fraction of errors. It builds on two thrusts. The first is a series of works starting with that of Sipser and Spielman [Expander codes, IEEE Trans. Inf. Theory 42(6) (1996) 1710–1722] demonstrating that an asymptotically good family of error-correcting codes that can be decoded in linear time even from a constant fraction of errors in a received word provided [Formula: see text] is at least [Formula: see text] and continuing to the results of Gao and Dowling [Fast decoding of expander codes, IEEE Trans. Inf. Theory 64(2) (2018) 972–978], which only require [Formula: see text] provided the inner code minimum distance is sufficiently large. The second is the improved performance of LDPC codes based on irregular graphs demonstrated by Luby et al. [Improved low- density parity-check codes using irregular graphs, IEEE Trans. Inf. Theory 47(2) (2001) 585–598] and Richardson et al. [Design of capacity- approaching irregular low-density parity-check codes, IEEE Trans. Inf. Theory 47(2) (2001) 619–637]. The algorithm presented in this paper allows for irregular or regular graph-based constructions and uses inner codes of appropriate lengths as checks rather than simple parity-checks.
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 ccc 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)2/3 - 1/(6c)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.
Tanner codes are error-correcting codes built from a bipartite graphGand a short inner codeC0. Expander codes are a special type of Tanner code, where the graph is highly interconnected, ensuring stronger error correction capabilities. This paper is motivated by the following natural and fundamental problem in decoding expander codes: What are the sufficient and necessary conditions that δ ∈ [0, 1] andd0∈ N must satisfy, so thateverybipartite expanderGwith vertex expansion ratio δ andeverylinear inner codeC0with minimum distanced0together define an expander code that corrects Ω(n) errors inO(n) time? ForC0being 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 codeC0, the previously best-known result of Dowling and Gao (IEEE-TIT’18) showed thatd0= Ω(cδ-2) is sufficient, wherecis the left-degree ofG. We present a near-optimal solution to the above problem for generalC0by showing that δd0> 3 is sufficient and δd0> 1 is necessary, thereby significantly improving Dowling-Gao’s result. To prove the sufficient condition, we present two novel algorithms for decoding arbitrary expander codes withδd0> 3, where the first algorithm is deterministic, and the second one is randomized and has a larger decoding radius. To prove the necessary condition, we generalize the aforementioned necessary result of Viderman, and construct for every pair of δ,d0with δd0=1, an expander code with constant distance, that only corrects a constant number of errors.
Tanner codes are graph-based linear codes whose parity-check matrices can be characterized by a bipartite graph GGG together with a linear inner code C0C_0C0​. Expander codes are Tanner codes whose defining bipartite graph GGG 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 d0d_0d0​ must satisfy, so that \textit{every} bipartite expander GGG with vertex expansion ratio δδδ and \textit{every} linear inner code C0C_0C0​ with minimum distance d0d_0d0​ together define an expander code that corrects Ω(n)Ω(n)Ω(n) errors in O(n)O(n)O(n) time? For C0C_0C0​ being the parity-check code, the landmark work of Sipser and Spielman (IEEE-TIT'96) showed that δ>3/4δ>3/4δ>3/4 is sufficient; later Viderman (ACM-TOCT'13) improved this to δ>2/3−Ω(1)δ>2/3-Ω(1)δ>2/3−Ω(1) and he also showed that δ>1/2δ>1/2δ>1/2 is necessary. For general linear code C0C_0C0​, the previously best-known result of Dowling and Gao (IEEE-TIT'18) showed that d0=Ω(cδ−2)d_0=Ω(cδ^{-2})d0​=Ω(cδ−2) is sufficient, where ccc is the left-degree of GGG. In this paper, we give a near-optimal solution to the above question for general C0C_0C0​ by showing that δd0>3δd_0>3δd0​>3 is sufficient and δd0>1δd_0>1δd0​>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.
Sipser and Spielman (IEEE IT, [1996]) showed that any c , d )-regular expander code with expansion parameter >¾ is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, [2007]) proved that expansion parameter >⅔ + 1/3c is sufficient to correct a constant fraction of errors in polynomial time using LP decoding. In this work, we give a simple combinatorial algorithm that achieves even better parameters. In particular, our algorithm runs in linear time and works for any expansion parameter >⅔ − 1/6c. We also prove that our decoding algorithm can be executed in logarithmic time on a linear number of parallel processors.
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.