Sharp Bounds and New Constructions for Single-Error Detection and Correction in Analog Codes

Abstract

We study single-error detection and correction for analog codes over $\mathbb{R}$. The key performance measures are the parameters $\hat{I}{“}_1(\mathcal{C})$ and $\hat{I}{“}_2(\mathcal{C})$, which quantify, respectively, the minimum separation required between large outlying errors that must be detected or located and the magnitude of tolerable perturbations. First, we prove that every real linear $[n,k]$ code $\mathcal{C}$ satisfies \[ Γ_1(\mathcal{C})\ge 2\left\lceil\frac{n}{n-k}\right\rceil. \] Moreover, when $k=n-2$, we prove that every real linear $[n,n-2]$ code $\mathcal{C}$ satisfies \[ Γ_2(\mathcal{C})\ge \frac{1}{\sin^2(π/2n)}. \] Together, these two lower bounds settle all four open problems of Roth concerning the optimality of single-error-detecting and single-error-correcting analog codes. The proof of the first bound is based on a double-induction argument, while the proof of the second combines a zonotope-based geometric characterization of $\hat{I}{“}_2(\mathcal{C})$ with a cyclic sine-product inequality. In addition, we construct analog codes with higher fixed redundancy and show that, for every fixed $r\ge 2$, there exists a class of linear $[n,\ge n-r]$ codes over $\mathbb{R}$ such that \[ Γ_2(\mathcal{C})\le O\left(n^{1+\frac{1}{r-1}}\right). \] This gives a new upper bound in the fixed-redundancy regime, which was not covered by previously known constructions.

21 pages, 4 figures