Source-linked AI summary
On Function-Correcting Lee Metric Codes with Data Protection
Gyanendra K. Verma, Abhay Kumar Singh
TL;DR
Function-correcting codes protect function values, while conventional error-correcting codes protect the full data vector. This paper develops a Lee-metric framework that protects both data and function values, and establishes redundancy bounds and constructions for this setting.
Problem
Function-correcting codes target function values, whereas conventional error-correcting schemes target full-vector recovery; the paper addresses joint protection of data and function values.
Source: §1 · pp. 1–2Method
Results
The paper establishes redundancy bounds, including a Plotkin-like lower bound, and explicit bounds for specific functions, the Lee weight function, locally bounded functions, and modular sum functions.
Source: §6 · p. 18Takeaways & Limitations
The work lays a foundation for studying function-correcting codes with data protection in the Lee metric.
Source: §6 · p. 18The research remains in progress, with further structural properties, stronger bounds, and related constructions planned for a subsequent version.
Source: §6 · p. 18
Abstract
from arXiv · showhide
Function-correcting codes are designed to protect the function values of a prescribed function against errors. Every error-correcting code that provides data protection inherently offers some degree of protection for functions defined on the data. In this work, we introduce a class of codes over $\mathbb{Z}_m$, termed function-correcting Lee metric codes with data protection (FCLMCs with data protection), which simultaneously provide error protection for both the data and the corresponding function values under the Lee metric. We consider codes that provide protection against a prescribed level of error for the function values that exceeds the level of protection guaranteed for the underlying data. We present a general construction of these codes and derive lower and upper bounds on the optimal redundancy, including a Plotkin-type lower bound. Furthermore, we derive explicit upper bounds on the redundancy of FCLMCs with data protection for several important classes of functions, including locally binary Lee functions, the Lee weight function, and the modular sum function. Finally, since the Lee metric coincides with the Hamming metric over $\mathbb{Z}_2$, all of our results remain valid over $\mathbb{Z}_2$ with respect to the Hamming metric.
1 Introduction
Function-correcting codes protect a specified function or attribute rather than requiring recovery of the full information vector, while a related framework extends protection to both data and function values. This paper develops that joint-protection approach under the Lee metric.
1 Introduction
- FCCs, introduced in, protect a specific function or attribute rather than the entire information vector.In many applications, recovering only the function or attribute is sufficient.Source: §1 · pp. 1–2
- Prior FCC studies considered varied metrics and target functions and derived bounds on code parameters, error correction, and redundancy.The introduction points to Table X as a comparative overview of these contributions.Source: §1 · p. 2
- Rajput et al. [8] introduced a Hamming-metric framework that protects both the underlying data and its corresponding function values.The introduction identifies applications in which the decoder is interested in both.Source: §1 · p. 2
- The paper introduces function-correcting Lee metric codes with data protection, extending joint protection of data and function values to the Lee metric.The paper also previews bounds and explicit redundancy bounds for several function classes.Source: §1 · p. 2
- The paper outlines preliminaries, Lee-metric definitions and redundancy bounds, function-specific bounds, and a concluding section.The function classes named in the roadmap include locally bounded, Lee weight, and modular functions.Source: §1 · p. 2
2 Preliminaries
The preliminaries set notation for vectors over Z_m and describe Lee-metric distances, function-correcting codes, and redundancy. They also connect these codes to irregular-distance codes and recall bounds used later.
2 Preliminaries
- The Lee metric generalizes Hamming weight by assigning different weights to distinct nonzero elements of Z_m.The section sets Z_m as the residue ring modulo m, with m at least 2.Source: §2 · p. 3
- An (f,t)L-FCLMC requires codewords for messages with different function values to have Lee distance at least 2t + 1, enabling correction of up to t function-value errors.The preliminaries also define optimal redundancy as the smallest redundancy permitting such a code.Source: §2 · p. 4
- The preliminaries define Lee distance requirement matrices and D-codes, then relate optimal FCLMC redundancy to minimum D-code lengths.They also introduce a function Lee distance matrix for distances between function values.Source: §2 · pp. 4–5
- The section recalls an upper bound on N_L(λ, 2t) and a Plotkin low-rate average-distance bound for Lee-metric code redundancy.N_L(λ, 2t) denotes the minimum length of an error-correcting code with λ codewords and minimum Lee distance 2t.Source: §2 · pp. 5–6
3 Function-correcting code with data protection in Lee metric codes
This section develops Lee-metric function-correcting codes that protect both data and function values, presenting a general construction and redundancy bounds, including a Plotkin-like bound with separate cases for even and odd m and a binary specialization.
3 Function-correcting code with data protection in Lee metric codes
- FCLMCs with data protection protect both messages and function values; data protection implies function-value protection, but not conversely.When the data and function-value distance requirements are equal, the code is an error-correcting code with that minimum Lee distance.Source: §3 · pp. 6–7
- The general construction composes a data encoding with a function encoding, yielding redundancy r = rd + rf when the function-value protection level exceeds the data level.The data encoding provides td-error correction, while the function encoding separates codewords for inputs with different function values.Source: §3 · p. 7
3.1 Bound on redundancy of FCLMCs with data protection
- The optimal redundancy equals the minimum length of a Lee-metric D-code for the associated distance-requirement matrix.The section introduces coded Lee distance requirement matrices to express the pairwise separation needed for data and function protection.Source: §3.1 · pp. 8–9
- For functions with |Im(f)| ≤ (m − 1)k, Theorem 3.10 gives a lower bound; over Z2, r_H ≥ 2tf + td.Over Z2 the Lee and Hamming metrics coincide.Source: §3.1 · pp. 9–10, §3.2 · p. 12
- Given a td-error-correcting data encoder of redundancy rd, the optimal redundancy is at most NL(DEd,f(tf, u1, …, uM)) + rd.The matrix records the additional Lee-distance requirements between encoded inputs whose function values differ.Source: §3.1 · pp. 8, 11
3.2 A Plotkin-like bound for FCLMC with data protection
- The alternate Plotkin-type lower bound depends only on dd, df, and the function, avoiding the need for all pairwise Lee distances required by the general bound [13, Lemma 4.1].The section notes that Theorem 3.10 applies only when the function image has cardinality at most (m − 1)k.Source: §3.2 · p. 12
- A Plotkin-like bound for (f, d_d, d_f)-FCLMCs over Z_m is stated separately for even and odd m.The supplied passages do not include enough of the bound’s formula to report its value.Source: §3.2 · pp. 12–13
- Corollary 3.17 states a binary specialization for functions from Z_2^k to Im(f).The supplied passages do not include the corollary’s bound formula.Source: §3.2 · p. 13
4 FCLMCs with data protection for specific functions
This section develops redundancy bounds and constructions for Lee-metric function-correcting codes with data protection, then specializes them to locally bounded functions, Lee weight, and modular sum.
4 FCLMCs with data protection for specific functions
- The section derives general lower and upper bounds on optimal redundancy and constructions for selected function classes.Source: §4 · p. 13
4.1 Locally bounded functions
- Locally binary Lee functions are singled out for an upper bound on optimal redundancy, with a systematic data code of minimum distance 2t+d+1 in the stated construction setting.Source: §4.1 · p. 14
4.2 The Lee weight function
- The upper-bound proof encodes u as (E_d(u), C_{f(u)} mod 2t_f+1), where C has 2t_f+1 codewords, length n_2, and minimum Lee distance 2(t_f−t_d).Source: §4.2 · p. 15
4.3 Modular sum function
- For modular sum, it derives lower and upper redundancy bounds, with an upper-bound construction using an m-codeword Lee code of distance 2(tf-td).Source: §4.3 · p. 16
5 Lee distance graphs and strict (f, dd, df)L-FCLMCs
This section uses Lee-distance graph connectivity to characterize strict FCLMCs: disconnection is necessary, and a component-grouping condition gives a sufficient criterion.
5 Lee distance graphs and strict (f, dd, df)L-FCLMCs
- For a strict code with df>d, its α-Lee distance graph is disconnected whenever d≤α<df.Source: §5 · p. 17
- More generally, if the α-Lee distance graph has η connected components, the code cannot be strict for any function.Source: §5 · p. 17
- A sufficient criterion groups graph components into disjoint unions matching the function-output fiber sizes, yielding a strict code with dd=d and df=α+1.Source: §5 · p. 17
6 Conclusion
The conclusion presents a Lee-metric framework that protects both message data and function values, with bounds and constructions for several function classes.
6 Conclusion
- The proposed framework simultaneously protects message data and corresponding function values in the Lee metric.Source: §6 · p. 18
- The work establishes redundancy bounds, including a Plotkin-like bound, and explicit constructions for function-correcting Lee metric codes with data protection.Source: §6 · p. 18
- The explicit bounds cover the Lee weight function, locally bounded Lee-metric functions, and modular sum functions.Source: §6 · p. 18
- Further structural properties, stronger bounds, and related constructions remain ongoing work for a subsequent version.Source: §6 · p. 18