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

arXiv:cs/0502079

Multilevel expander codes

Alexander Barg, Gilles Zémor

Published Feb 19, 2005• 0 citations
arXivHTMLPDF

Abstract

We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound on the minimum distance. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes.

DOI
10.48550/arxiv.cs/0502079

Related papers

Multilevel expander codes

Alexander Barg, Gilles Zémor

We define multilevel codes on bipartite graphs which have properties analogous to multilevel serial concatenations. A linear-time decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes, i.e. equals the best-known exponent achievable by a polynomial-time decoding algorithm

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

Multilevel expander codes

Alexander Barg, Gilles Zémor

We define multilevel codes on bipartite graphs which have properties analogous to multilevel serial concatenations. A linear-time decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel codes, i.e. equals the best-known exponent achievable by a polynomial-time decoding algorithm

DIMACS series in discrete mathematics and theoretical computer science•Jul 19, 2005•1 citation

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

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

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

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
We define multilevel codes on bipartite graphs that have properties analogous to multilevel serial concatenations. A decoding algorithm is described that corrects a proportion of errors equal to half the Blokh-Zyablov bound on the minimum distance. The error probability of this algorithm has exponent similar to that of serially concatenated multilevel 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.
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.
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