An official website of the United States government
Consider a binary linear code of length N, minimum distance dmin, transmission over the binary erasure channel with parameter 0 < < 1 or the binary symmetric channel with parameter 0 < < 1 2 , and block-MAP decoding. It was shown by Tillich and Zemor that in this case the error probability of the block-MAP decoder transitions “quickly” from δ to 1−δ for any δ > 0 if the minimum distance is large. In particular the width of the transition is of order O(1/ √ dmin). We strengthen this result by showing that under suitable conditions on the weight distribution of the code, the transition width can be as small as Θ(1/N 1 2 −κ ), for any κ > 0, even if the minimum distance of the code is not linear. This condition applies e.g., to Reed-Mueller codes. Since Θ(1/N 1 2 ) is the smallest transition possible for any code, we speak of “almost” optimal scaling. We emphasize that the width of the transition says nothing about the location of the transition. Therefore this result has no bearing on whether a code is capacity-achieving or not. As a second contribution, we present a new estimate on the derivative of the EXIT function, the proof of which is based on the Blowing-Up Lemma.
more »
« less
Input-output distance properties of good linear codes
—Consider a linear code defined as a mapping between vector spaces of dimensions k and n. Let β∗ denote the minimal (relative) weight among all images of input vectors of full Hamming weight k. Operationally, β∗ characterizes the threshold for adversarial (erasure) noise beyond which decoder is guaranteed to produce estimate of k-input with 100% symbol error rate (SER). This paper studies the relation between β∗ and δ, the minimum distance of the code, which gives the threshold for 0% SER. An optimal tradeoff between β∗ and δ is obtained (over large alphabets) and all linear codes achieving β∗ = 1 are classified: they are repetition-like. More generally, a design criteria is proposed for codes with favorable graceful degradation properties. As an example, it is shown that in an overdetermined system of n homogeneous linear equations in k variables (over a field) it is always possible to satisfy some k − 1 equations with non-zero assignments to every unknown, provided that any subset of k equations is linearly independent. This statement is true if and only if n ≥ 2k − 1.
more »
« less
- Award ID(s):
- 1717842
- PAR ID:
- 10063529
- Date Published:
- Journal Name:
- 2018 IEEE Int. Symp. Inf. Theory (ISIT)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)A collection of sets displays a proximity gap with respect to some property if for every set in the collection, either (i) all members are δ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members are δ-close to the property. In particular, no set in the collection has roughly half of its members δ-close to the property and the others δ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed-Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to any δ smaller than the Johnson/Guruswami-Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least) linear size in the RS code dimension, for δ smaller than the unique decoding radius. Concretely, if δ is smaller than half the minimal distance of an RS code V ⊂ Fq n , every affine space is either entirely δ-close to the code, or alternatively at most an ( n/q)-fraction of it is δ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed-Solomon codes (due to Berlekamp-Welch and Guruswami-Sudan) on a formal element of an affine space. This involves working with Reed-Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.more » « less
-
A collection of sets displays aproximity gapwith respect to some property if for every set in the collection, either (i) all members areδ-close to the property in relative Hamming distance or (ii) only a tiny fraction of members areδ-close to the property. In particular, no set in the collection has roughly half of its membersδ-close to the property and the othersδ-far from it. We show that the collection of affine spaces displays a proximity gap with respect to Reed–Solomon (RS) codes, even over small fields, of size polynomial in the dimension of the code, and the gap applies to anyδsmaller than the Johnson/Guruswami–Sudan list-decoding bound of the RS code. We also show near-optimal gap results, over fields of (at least)linearsize in the RS code dimension, forδsmaller than the unique decoding radius. Concretely, ifδis smaller than half the minimal distance of an RS code\(V\subset {\mathbb {F}}_q^n \), every affine space is either entirelyδ-close to the code, or alternatively at most an (n/q)-fraction of it isδ-close to the code. Finally, we discuss several applications of our proximity gap results to distributed storage, multi-party cryptographic protocols, and concretely efficient proof systems. We prove the proximity gap results by analyzing the execution of classical algebraic decoding algorithms for Reed–Solomon codes (due to Berlekamp–Welch and Guruswami–Sudan) on aformal elementof an affine space. This involves working with Reed–Solomon codes whose base field is an (infinite) rational function field. Our proofs are obtained by developing an extension (to function fields) of a strategy of Arora and Sudan for analyzing low-degree tests.more » « less
-
Braverman, Mark (Ed.)A longstanding open problem in coding theory is to determine the best (asymptotic) rate R₂(δ) of binary codes with minimum constant (relative) distance δ. An existential lower bound was given by Gilbert and Varshamov in the 1950s. On the impossibility side, in the 1970s McEliece, Rodemich, Rumsey and Welch (MRRW) proved an upper bound by analyzing Delsarte’s linear programs. To date these results remain the best known lower and upper bounds on R₂(δ) with no improvement even for the important class of linear codes. Asymptotically, these bounds differ by an exponential factor in the blocklength. In this work, we introduce a new hierarchy of linear programs (LPs) that converges to the true size A^{Lin}₂(n,d) of an optimum linear binary code (in fact, over any finite field) of a given blocklength n and distance d. This hierarchy has several notable features: 1) It is a natural generalization of the Delsarte LPs used in the first MRRW bound. 2) It is a hierarchy of linear programs rather than semi-definite programs potentially making it more amenable to theoretical analysis. 3) It is complete in the sense that the optimum code size can be retrieved from level O(n²). 4) It provides an answer in the form of a hierarchy (in larger dimensional spaces) to the question of how to cut Delsarte’s LP polytopes to approximate the true size of linear codes. We obtain our hierarchy by generalizing the Krawtchouk polynomials and MacWilliams inequalities to a suitable "higher-order" version taking into account interactions of 𝓁 words. Our method also generalizes to translation schemes under mild assumptions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
