Source-linked AI summary
On systematicity of linear function-correcting codes
Duy Ho
TL;DR
The paper asks how much redundancy is imposed by systematic encodings when both the prescribed function and encoding are linear. It introduces function-separation distance and its coding-theoretic representations, then determines free redundancy generally and systematic redundancy through d ≤3, with d = 4 left more involved.
Problem
The paper studies whether requiring systematic encodings increases redundancy for linear function-correcting codes.
Method
It formulates free and systematic linear separation problems using function-separation distance and relates that distance to UEP parameters and relative generalized Hamming weight.
Results
The optimal free linear redundancy depends only on function rank, while systematic linear redundancy is determined for d ≤3; at d = 3, the systematicity gap can be arbitrarily large.
Takeaways & Limitations
Systematicity is a genuine structural constraint whose gap depends on the position of ker f relative to the distinguished basis.
Takeaways & Limitations
The systematic linear separation problem at d = 4 is more involved because it requires controlling combinations of up to three rows of the parity matrix.
Abstract
from arXiv · showhide
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$.
1 Introduction
This section frames function-correcting codes as a relaxation of classical error correction and studies the redundancy cost of requiring systematic linear encodings. It introduces function-separation distance, connects it to UEP and relative generalized Hamming weight, and states the paper’s main separation results.
- Motivation: Function-correcting codes protect prescribed function values rather than requiring recovery of every transmitted message.The framework imposes distance requirements only between codewords whose messages have distinct function values.
- Motivation: Systematic encodings retain message coordinates and append redundancy, but this structural constraint may increase the required redundancy.The paper compares arbitrary linear encodings with encodings systematic relative to a distinguished basis.
- Framework: The function-separation distance is the minimum Hamming distance between encoded messages with distinct function values.The basic separation requirement is δEnc(f) ≥ d.
- Results: The paper determines optimal free linear redundancy for every prescribed separation and optimal systematic linear redundancy for all d ≤3.At d = 3, it characterizes exactly when the systematicity gap is zero and shows that the gap can be arbitrarily large.
- Framework: For linear functions and encodings, classical UEP parameters become function-separation distances, which coincide with a relative generalized Hamming weight.The correspondence includes coordinate and projection maps and extends to arbitrary linear functions.
2 Preliminaries
The preliminaries define encodings, redundancy, systematicity, function-correcting codes, and function-separation distance. They establish that separation 2t+1 is equivalent to recovering the prescribed function under at most t errors and that, for linear functions, the kernel determines the distance.
- Encodings: An encoding is a bijection from the message space to a code, with redundancy equal to its length minus the message dimension.Linear encodings correspond to generator matrices and linear codes.
- Systematic encodings: A systematic encoding preserves the message coordinates relative to a distinguished basis and appends parity coordinates.For linear encodings, its generator matrix has the form [I_k | P].
- Function-correcting codes: The function-separation distance measures the minimum Hamming distance between codewords whose messages have different function values.The paper introduces it as the main parameter for general, not necessarily linear, encodings.
- Function-correcting codes: Separation 2t+1 is equivalent to recovering the function value in the presence of at most t errors.The equivalence follows from disjoint Hamming balls around encodings of messages with distinct function values.
- Linear functions: For linear functions, the function-separation distance depends only on the kernel, because distinct function values correspond to different kernel cosets.Linear functions with the same kernel therefore have identical separation distances for every encoding.
3 A correspondence between function-separation distances and UEP parameters
This section identifies classical UEP parameters as instances of function-separation distance and extends the correspondence to arbitrary linear functions. For linear encodings, the distance is represented through relative code distances and separation vectors.
- UEP correspondence: Output-coordinate, input-coordinate, and component UEP parameters are function-separation distances of corresponding coordinate and projection maps.The correspondence provides a common function-separation interpretation for the three classical parameter families.
- UEP correspondence: For linear encodings and linear functions, function-separation distance generalizes the UEP correspondence beyond coordinate and projection maps.Conversely, under a suitable basis change, the distance becomes a UEP parameter.
- UEP correspondence: For a component projection, its function-separation distance equals the corresponding component separation.The equality follows because both quantities take the same minimum over message pairs separated by that projection.
- Linear representation: For a linear function f, the function-separation distance equals the first relative generalized Hamming weight of the code relative to the encoded kernel.The same quantity coincides with the coset-code distance under the cited formulation.
- Systematic characterization: For systematic linear encodings, function correction is characterized by the distance between the code and the encoding of ker f.The required condition is d(C, Enc(ker f)) ≥ 2t + 1.
4 Optimal redundancy and the systematicity gap
The paper formulates free and systematic linear separation problems and connects optimal free redundancy to classical unequal error-protection code lengths. It then studies systematicity, proving rank-based free redundancy and exact systematic constructions in several cases.
- Separation problems: The free linear separation problem asks for the least redundancy of a linear encoding achieving prescribed separation d.The systematic variant adds the requirement that the encoding be systematic relative to a distinguished basis.
- Free linear redundancy: An encoding exists exactly when r + ℓ ≥ N_q^lin(ℓ, d), so optimal free redundancy is determined by the shortest length of a linear [N, ℓ, ≥d]_q code.The separation-vector formulation uses d for the ℓ function coordinates and 1 for the remaining coordinates.
- Free linear redundancy: The optimal free linear redundancy depends on the prescribed function only through rank(f).This expresses the free problem through a classical UEP quantity after choosing a suitable basis.
- Systematicity: Systematicity is an additional structural constraint, and the paper studies its effect through the systematic linear redundancy and systematicity gap.The paper notes that the systematic and free quantities cannot generally be compared directly when their encoding classes differ.
- Systematicity: For surjective linear functions to F_q, the lower bound for systematic linear redundancy is attained when ℓ = 1, and the optimum is attained by a systematic linear encoding for every d ≥ 1.The construction repeats the function value in d−1 appended coordinates, giving separation at least d.
- Systematicity: Monomially equivalent surjective linear functions have the same systematic redundancy at every separation.The proof transfers a systematic encoding through a monomial coordinate transformation while preserving redundancy and separation.
5 The linear separation problem at small separations
The paper determines free and systematic linear redundancies for separations d=1,2,3, characterizing the d=3 systematic case through projective geometry. It also shows that the systematicity gap can be arbitrarily large for fixed q.
- d=1 is immediate: every encoding has separation at least 1, so free and systematic redundancies coincide.
- d=1 and d=2 have zero systematicity gap.
- For d=3, systematic encodings require each relevant parity row to have Hamming weight at least 2 and correspond to a non-coordinate projective point.
- At d=3, a systematic encoding exists with redundancy r exactly when the function invariant νE(f) is at most Λq(r).
- The d=3 construction assigns distinct non-coordinate projective points to the one-dimensional function-value subspaces and verifies separation by checking message weights up to two.
6 Conclusion
The paper establishes a function-separation framework connecting FCCs with UEP codes and characterizes linear redundancy under free and systematic encodings. It determines systematic optima through separation 3 and shows that systematicity can impose an arbitrarily large gap.
- Function-separation framework: UEP parameters are function-separation distances, and linear separation distance equals a first relative generalized Hamming weight.The characterization applies to output-coordinate, input-coordinate, and component UEP parameters, with a separation-vector representation also obtained.
- Linear separation problems: The paper formulates free and systematic linear separation problems and their corresponding optimal redundancies.These problems distinguish arbitrary linear encodings from encodings constrained by systematicity.
- Redundancy results: The optimal free linear redundancy is identical for all linear functions having the same rank.The result is stated as Theorem 4.4.
- Redundancy results: Monomially equivalent functions have the same optimal systematic linear redundancy.This invariance is stated as Theorem 4.10.
- Systematicity gap: For d ≤3, the optimal systematic redundancy is determined, and at d = 3 the systematicity gap is exactly characterized as either zero or arbitrarily large.The cases d = 1 and d = 2 follow from Proposition 5.1, while d = 3 follows from Theorem 5.6 and its corollaries.