| 1. |
- Bukh, Boris, et al.
(författare)
-
An Improved Bound on the Fraction of Correctable Deletions
- 2017
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE. - 0018-9448 .- 1557-9654. ; 63:1, s. 93-103
-
Tidskriftsartikel (refereegranskat)abstract
- We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k >= 2, we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1 - (2/(k + root k)). In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(root 2+1) = root 2-1 approximate to 0.414. Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1 - Theta (1/root k), and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for k-ary codes as 1 - Theta (1/k), since 1 - 1/k is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between (root 2 - 1) and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question.
|
|
| 2. |
- Guruswami, V., et al.
(författare)
-
Combinatorial bounds for list decoding
- 2002
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 48:5, s. 1021-1034
-
Tidskriftsartikel (refereegranskat)abstract
- Informally, an error-correcting code has nice list-decodability properties if every Hamming ball of large radius has a small number of codewords in it. Here, we report linear codes with nontrivial list-decodability: i.e., codes of large rate that are nicely list-decodable, and codes of large distance that are not nicely list-decodable. Specifically, on the positive side, we show that there exist codes of rate R and block length n that have at most c codewords in every Hamming ball of radius H-1 (1-R-1/c) (.) n. This answers the main open question from the work of Elias. This result also has consequences for the construction of concatenated codes of good rate that are list decodable from a large fraction of errors, improving previous results of Guruswami and Sudan in this vein. Specifically, for every epsilon > 0, we present a polynomial time constructible asymptotically good family of binary codes of rate Omega(epsilon(4)) that can be list-decoded in polynomial time from up to a fraction (1/2 - epsilon) of errors, using lists of size O(epsilon(-2)). On the negative side, we show that for every delta and c, there exists tau < delta, c(1) > 0, and an infinite family of linear codes {C-i}(i) such that if n(i) denotes the block length of C-i, then C-i has minimum distance at least delta (.) n(i) and contains more than c(1) (.) n(i)(c) codewords in some Hamming ball of radius tau (.) n(i). While this result is still far from known bounds on the list-decodability of linear codes, it is the first to bound the radius for list-decodability by a polynomial-sized list away from the minimum distance of the code.
|
|
| 3. |
- Guruswami, Venkatesan, et al.
(författare)
-
Explicit Two-Deletion Codes With Redundancy Matching the Existential Bound
- 2021
-
Ingår i: IEEE Transactions on Information Theory. - : Institute of Electrical and Electronics Engineers (IEEE). - 0018-9448 .- 1557-9654. ; 67:10, s. 6384-6394
-
Tidskriftsartikel (refereegranskat)abstract
- We give an explicit construction of length-n binary codes capable of correcting the deletion of two bits that have size 2(n)/n(4+o(1)). This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size Omega(2(n)/n(4)). Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size Omega(2(n)/n(3+o(1))) that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear.
|
|
| 4. |
- Guruswami, Venkatesan, et al.
(författare)
-
On the List-Decodability of Random Linear Codes
- 2011
-
Ingår i: IEEE Transactions on Information Theory. - 0018-9448 .- 1557-9654. ; 57:2, s. 718-725
-
Tidskriftsartikel (refereegranskat)abstract
- The list-decodability of random linear codes is shown to be as good as that of general random codes. Specifically, for every fixed finite field, Gamma(q), p is an element of (0, 1 - 1/q) and epsilon > 0, it is proved that with high probability a random linear code C in F-q(n) of rate (1 - H-q(p) - epsilon) can be list decoded from a fraction p of errors with lists of size at most O(1/epsilon). This also answers a basic open question concerning the existence of highly list-decodable linear codes, showing that a list-size of O(1/epsilon) suffices to have rate within epsilon of the information-theoretically optimal rate of 1 - H-q(p). The best previously known list-size bound was q(O(1/epsilon)) (except in the q = 2 case where a list-size bound of O(1/epsilon) was known). The main technical ingredient in the proof is a strong upper bound on the probability that l random vectors chosen from a Hamming ball centered at the origin have too many (more than Omega(l)) vectors from their linear span also belong to the ball.
|
|
