Unique optima of the Delsarte linear program
Abstract The Delsarte linear program is used to bound the size of codes given their block length n and minimal distance d by taking a linear relaxation from codes to quasicodes. We study for which values of (n, d) this linear program has a unique optimum: while we show that it does not...
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer US
2023
|
| Online Access: | https://hdl.handle.net/1721.1/147882 |
| Summary: | Abstract
The Delsarte linear program is used to bound the size of codes given their block length n and minimal distance d by taking a linear relaxation from codes to quasicodes. We study for which values of (n, d) this linear program has a unique optimum: while we show that it does not always have a unique optimum, we prove that it does if
$$d>n/2$$
d
>
n
/
2
or if
$$d \le 2$$
d
≤
2
. Introducing the Krawtchouk decomposition of a quasicode, we prove there exist optima to the (n, 2e) and
$$(n-1,2e-1)$$
(
n
-
1
,
2
e
-
1
)
linear programs that have essentially identical Krawtchouk decompositions, revealing a parity phenomenon among the Delsarte linear programs. We generalize the notion of extending and puncturing codes to quasicodes, from which we see that this parity relationship is given by extending/puncturing. We further characterize these pairs of optima, in particular demonstrating that they exhibit a symmetry property, effectively halving the number of decision variables. |
|---|