It is proved that the optimal free redundancy depends only on the rank of the function, and the optimal systematic redundancy for prescribed separations $d\leq3$ is determined.
Abstract
The standard formulation of function-correcting codes uses systematic encodings. We study the redundancy cost of this constraint when both the prescribed function and the encoding are linear. We introduce the function-separation distance and show that several classical unequal error protection parameters are special cases. For linear functions and encodings, this distance is the first relative generalized Hamming weight of the code relative to the encoded kernel. We formulate free and systematic linear separation problems. We prove that the optimal free redundancy depends only on the rank of the function, and determine the optimal systematic redundancy for prescribed separations $d\leq3$.
Function correcting codes (FCCs) are designed to protect a specified function evaluation of messages at a higher level than the level of protection for messages, against errors while reducing the redundancy required for reliable communication. FCCs have thus far been studied for channels matched to various distances, i...
Kanchana Lokshmii Jagatti, K. Hareesh, N. T. Rashid Ummer et al.· 0 citations
Let $C_m:=\mathrm{BCH}(3,m)$ be the binary primitive triple-error-correcting BCH code of length $2^m-1$. We determine its second generalized covering radius exactly: $R_2(C_m)=8$ for every $m\geq5$. Equivalently, every two-dimensional syndrome subspace is contained in the binary span of at most eight parity-check colum...
Isaac Barouch Essayag, Aryeh Lev Zabokritskiy· 6 citations
This work generalizes the SPARC construction, and considers the class of \emph{additive orthogonal} regression codes, of which standard SPARCs are a special case, and derives nonasymptotic bounds on the squared-error distortion by tracking the evolution of the encoding residual across stages.
We study linear codes for insertion and deletion (insdel) errors through the lens of evaluation codes. We develop a general framework for analyzing random puncturings of evaluation codes, where the edit distance is controlled by only the size of the evaluation domain and the maximum number of zeros of a nonzero functio...
