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

IEEE Information Theory Workshop (ITW)

Generalized minimum distance iterative decoding of expander codes

Vitaly Skachek, Ron M. Roth

Published Mar 1, 2004• 27 citations
Publisher

Abstract

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.

DOI
10.1109/itw.2003.1216740

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

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

Rutuja Kshirsagar, Gretchen L. Matthews

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.

Journal of Algebra and Its Applications•Apr 16, 2025•0 citations

Generalized minimum distance iterative decoding of Tanner codes

Saejoon Kim

In this letter, we present a linear-time decoding algorithm for Tanner codes that can correct errors up to close to half the minimum distance of the code. The algorithm is a simple generalization to the iterative decoding algorithm of expander codes proposed by Skachek and Roth (2003).

IEEE Communications Letters•Aug 1, 2005•1 citation

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

Decoding of expander codes at rates close to capacity

Alexei Ashikhmin, Vitaly Skachek

The concatenation of nearly-MDS expander codes of Roth and Skachek, "On Nearly-MDS Expander Codes," Proc. IEEE ISIT'04, with 'typical' LDPC codes is investigated. It is shown that for the rates R = (1 - epsi)C (C is the capacity of the binary symmetric channel (BSC)), under certain condition on the parameters of LDPC codes, these concatenated codes have decoding time linear in their length and polynomial in 1/epsi, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes," IEEE Trans. Inform. Theory, 2002, and "Concatenated Codes: Serial and Parallel," IEEE Trans. Inform. Theory, 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties

IEEE International Symposium on Information Theory (ISIT)•Jan 1, 2005•1 citation

Improved Decoding of Tanner Codes

Zhaienhe Zhou, Zeyu Guo

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.12293•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations
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.
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.
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.
The concatenation of nearly-MDS expander codes of Roth and Skachek, "On Nearly-MDS Expander Codes," Proc. IEEE ISIT'04, with 'typical' LDPC codes is investigated. It is shown that for the rates R = (1 - epsi)C (C is the capacity of the binary symmetric channel (BSC)), under certain condition on the parameters of LDPC codes, these concatenated codes have decoding time linear in their length and polynomial in 1/epsi, and the decoding error probability decays exponentially. These codes are compared to the recently presented codes of Barg and Zemor, "Error Exponents of Expander Codes," IEEE Trans. Inform. Theory, 2002, and "Concatenated Codes: Serial and Parallel," IEEE Trans. Inform. Theory, 2005. It is shown that the latter families can not be tuned to have all the aforementioned properties
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δd0>2\delta d_{0}>2δd0​>2, corrects up toαn\alpha nαnerrors for a Tanner codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​), whereGGGis a (c,d,α,δc, d, \alpha, \deltac,d,α,δ) bipartite expander withnnnleft vertices, andC0⊆F2dC_{0} \subseteq \mathbb{F}_{2}^{d}C0​⊆F2d​is a linear inner code with minimum distanced0d_{0}d0​. This result improves upon the previous work of Cheng, Ouyang, Shangguan, and Shen (RANDOM 2024), which requiredδd0>3\delta d_{0}>3δd0​>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αn\alpha nαn, compared with the previous radius of2αd0(1+0.5cδ)n\frac{2 \alpha}{d_{0}(1+0.5 c \delta)} nd0​(1+0.5cδ)2α​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 codeT(G,C0)T\left(G, C_{0}\right)T(G,C0​)is approximatelyfδ−1(1d0)αnf_{\delta}^{-1}\left(\frac{1}{d_{0}}\right) \alpha nfδ−1​(d0​1​)αn, wherefδ(⋅)f_{\delta}(\cdot)fδ​(⋅)is the Size-Expansion Function. As another application, we improve the decoding radius of our decoding algorithms fromαn\alpha nαnto approximatelyfδ−1(2d0)αnf_{\delta}^{-1}\left(\frac{2}{d_{0}}\right) \alpha nfδ−1​(d0​2​)αn.