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
-
treaming codes take a string of source symbols as input and output a string of coded symbols in real time, which eliminate the queueing delay of traditional block codes and are thus especially appealing for delay sensitive applications. This work studies the asymptotics of random linear streaming codes (RLSCs) in the large finite-field-size regime under the i.i.d. symbol erasure channel models. Two important scenarios are analyzed: (i) tradeoff between decoding deadline Δ and probability of error p_e assuming infinite memory α=∞ ; and (ii) tradeoff between α and pe assuming infinite Δ=∞ . For each scenario, this work derives the corresponding asymptotic constant ρ , power β and decay rate η that satisfy p_e(x)∼ρ*x^βe^(−ηx) . The results of (i) and (ii) are then used to study an important code design problem: Under a given target deadline Δ , what is the memory length α needed for the error probability p_e to be within a factor of c>1 of the best possible p_e^* over α . Further analysis also suggests that regardless the c value being considered, the necessary memory length is approximately 3–7% of the target deadline Δ when Δ is large, the actual percentage depending on the channel model and the coding rate. Such a prediction is consistent with existing brute-force-based evaluations.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
