Multilevel expander codes

By Alexander Barg, Gilles Zémor. Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., 2005

633 citations recorded by the source corpus.

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

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/3bc0ee724945f5b44569725729a432f51b8a5452

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Channel coding: The road to channel capacity (2006, methodology): “he turbo code breakthrough, several researchers with backgrounds in computer science and physics rather than in coding rediscovered the power and efﬁciency o f LDPC codes. In his thesis, Dan Spielman [84], [85] 12We note, however, that correlations do build up with iterations and that a saturation e”
Raptor codes on binary memoryless symmetric channels (2006, background): “These codes were invented by Gallager [1] in the early 1960’s but did not receive proper attention by the information theory community until years later, when their excellent decoding qualities were re-discovered independently by the information theory and the theoretical computer science communitie”
Using linear programming to Decode Binary linear codes (2005, background): “In the 1990s, they were “rediscovered” by a number of researchers [8], [4], [9], and have since received a lot of attention.”
Consensus and Cooperation in Networked Multi-Agent Systems (2007, background): “The notion of algebraic connectivity of graphs has appeared in a variety of other areas including low-density parity-check codes (LDPC) in information theory and communications [84], Ramanujan graphs [50] in number theory and quantum chaos, and combinatorial optimization problems such as the max-cut”
Tapering off qubits to simulate fermionic Hamiltonians (2017, background): “Although in general this problem is NP-hard [35], there are special classes of LDPC codes that admit a linear time decoder [31, 32].”
Fault-tolerant quantum computation with constant overhead (2013, background): “Explicit classical constructions based on expander codes [31] also work.”
Regular and irregular progressive edge-growth tanner graphs (2005, methodology): “The notion of graph expansion was first introduced as an analysis tool in coding theory [3].”
Algebraic Connectivity Ratio of Ramanujan Graphs (2007, background): “This difference has no negative effects in consensus problems but it makes a major difference in construction of expander codes [25] in information theory that result from Ramanujan graphs.”