This paper presents a method to lowerbound
the distance of closest approach between points on an unsafe
set and points along system trajectories. Such a minimal
distance is a quantifiable and interpretable certificate of safety
of trajectories, as compared to prior art in barrier and density
methods which offers a binary indication of safety/unsafety.
The distance estimation problem is converted into a infinitedimensional
linear program in occupation measures based
on existing work in peak estimation and optimal transport.
The momentSOS hierarchy is used to obtain a sequence of
lower bounds obtained through solving semidefinite programs
in increasing size, and these lower bounds will converge to the
true minimal distance as the degree approaches infinity under
mild conditions (e.g. Lipschitz dynamics, compact sets).
more »
« less
A Complete Linear Programming Hierarchy for Linear Codes
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 semidefinite 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 "higherorder" version taking into account interactions of 𝓁 words. Our method also generalizes to translation schemes under mild assumptions.
more »
« less
 Award ID(s):
 1900460
 NSFPAR ID:
 10339897
 Editor(s):
 Braverman, Mark
 Date Published:
 Journal Name:
 Leibniz international proceedings in informatics
 Volume:
 215
 ISSN:
 18688969
 Page Range / eLocation ID:
 51:151:22
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


—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 kinput 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 repetitionlike. 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 nonzero 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

An expurgating linear function (ELF) is an outer code that disallows lowweight codewords of the inner code. ELFs can be designed either to maximize the minimum distance or to minimize the codeword error rate (CER) of the expurgated code. A listdecoding sieve can efficiently identify ELFs that maximize the minimum distance of the expurgated code. For convolutional inner codes, this paper provides analytical distance spectrum union (DSU) bounds on the CER of the concatenated code. For short codeword lengths, ELFs transform a good inner code into a great concatenated code. For a constant message size of K = 64 bits or constant codeword blocklength of N = 152 bits, an ELF can reduce the gap at CER 10−6 between the DSU and the randomcoding union (RCU) bounds from over 1 dB for the inner code alone to 0.23 dB for the concatenated code. The DSU bounds can also characterize puncturing that mitigates the rate overhead of the ELF while maintaining the DSUtoRCU gap. List Viterbi decoding guided by the ELF achieves maximum likelihood (ML) decoding of the concatenated code with a sufficiently large list size. The rateK/(K+m) ELF outer code reduces rate and list decoding increases decoder complexity. As SNR increases, the average list size converges to 1 and average complexity is similar to Viterbi decoding on the trellis of the inner code. For rare largemagnitude noise events, which occur less often than the FER of the inner code, a deep search in the list finds the ML codeword.more » « less

Generalized bicycle (GB) codes is a class of quantum errorcorrecting codes constructed from a pair of binary circulant matrices. Unlike for other simple quantum code ansätze, unrestricted GB codes may have linear distance scaling. In addition, lowdensity paritycheck GB codes have a naturally overcomplete set of lowweight stabilizer generators, which is expected to improve their performance in the presence of syndrome measurement errors. For such GB codes with a given maximum generator weight w, we constructed upper distance bounds by mapping them to codes local in D≤w−1 dimensions, and lower existence bounds which give d≥O(n1/2). We have also conducted an exhaustive enumeration of GB codes for certain prime circulant sizes in a family of twoqubit encoding codes with row weights 4, 6, and 8; the observed distance scaling is consistent with A(w)n1/2+B(w), where n is the code length and A(w) is increasing with w.more » « less

null (Ed.)This paper applies errorexponent and dispersionstyle analyses to derive finiteblocklength achievability bounds for lowdensity paritycheck (LDPC) codes over the pointtopoint channel (PPC) and multiple access channel (MAC). The errorexponent analysis applies Gallager's error exponent to bound achievable symmetrical and asymmetrical rates in the MAC. The dispersionstyle analysis begins with a generalization of the random coding union (RCU) bound from random code ensembles with i.i.d. codewords to random code ensembles in which codewords may be statistically dependent; this generalization is useful since the codewords of random linear codes such as LDPC codes are dependent. Application of the RCU bound yields finiteblocklength error bounds and asymptotic achievability results for both i.i.d. random codes and LDPC codes. For discrete, memoryless channels, these results show that LDPC codes achieve first and secondorder performance that is optimal for the PPC and identical to the best prior results for the MAC.more » « less