Search Results

A locally testable code (LTC) is an error correcting code that has a property-tester. The tester reads q bits that are randomly chosen, and rejects words with probability proportional to their distance from the code. The parameter q is called the ...

We show that quantum expander codes, a constant-rate family of quantum low-density parity check (LDPC) codes, with the quasi-linear time decoding algorithm of Leverrier, Tillich and Zémor can correct a constant fraction of random errors with very high ...

In this paper, we obtain a composition theorem that allows us to construct locally testable codes (LTCs) by repeated two-wise tensor products. This is the first composition theorem showing that repeating the two-wise tensor operation any constant number ...

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

In this work, we present the first local-decoding algorithm for expander codes. This yields a new family of constant-rate codes that can recover from a constant fraction of errors in the codeword symbols, and where any symbol of the codeword can be ...

Sipser and Spielman (IEEE IT, 1996) showed that any (c, d)-regular expander code with expansion parameter > 3/4 is decodable in linear time from a constant fraction of errors. Feldman et al. (IEEE IT, 2007) proved that expansion parameter > 2/3 + 1/3c ...

Designing short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints This problem has applications in DNA ...

A linear-programming (LP) decoder for nonbinary expander codes is presented. It is shown that the proposed decoder has the maximum-likelihood certificate properties. It is also shown that this decoder corrects any pattern of errors of a relative weight ...

Recently, Roth and Skachek presented an expander-based code construction which, by an appropriate choice of constituent code parameters, yields linear-time encodable and decodable codes that lie within an Ε away from the Singleton bound and have an ...

The decoding error probability of codes is studied as a function of their block length. It is shown that the existence of codes with a polynomially small decoding error probability implies the existence of codes with an exponentially small decoding ...

A construction of expander codes is presented with the following three properties: i) the codes lie close to the Singleton bound, ii) they can be encoded in time complexity that is linear in their code length, and iii) they have a linear-time bounded-...

In 1996, Sipser and Spielman [12] constructed a family of linear-time decodable asymptotically good codes called expander codes. Recently, Barg and Zémor [2] gave a modified construction of expander codes, which greatly improves the code parameters. In ...

An analogy is examined between serially concatenated codes and parallel concatenations whose interleavers are described by bipartite graphs with good expanding properties. In particular, a modified expander code construction is shown to behave very much ...

A class of codes is said to reach capacity {\scriptsize $Ç$} of the binary symmetric channel if for any rate $R<$ {\scriptsize $Ç$} and any $\varepsilon>0$ there is a sufficiently large N such that codes of length $\ge N$ and rate R from this class ...

We present a new class of asymptotically good, linear error-correcting codes based upon expander graphs. These codes have linear time sequential decoding algorithms, logarithmic time parallel decoding algorithms with a linear number of processors, and ...