Source-linked AI summary
A General Plotkin-type Bound on Function-Correcting Codes with Wyner-Graham Distance
Kanchana Lokshmii Jagatti, K. Hareesh, N. T. Rashid Ummer, B. Sundar Rajan
TL;DR
Existing FCC Plotkin-type bounds for arbitrary functions require extensive pairwise-distance computations. The paper derives a Wyner–Graham bound using preimage-set cardinalities and within-set distance sums, then specializes it to linear and several important functions.
Problem
Existing arbitrary-function Plotkin-type bounds depend on pairwise distances among all message vectors, making them difficult and computationally intensive to evaluate.
Method
The paper derives a general Wyner–Graham Plotkin-type bound based on preimage-set cardinalities and pairwise distances within each preimage set.
Results
The bound yields simplified results for linear functions and several Hamming- and Lee-distance function classes, while recovering existing linear-function bounds as special cases.
Takeaways & Limitations
The proposed formulation reduces the computations required to evaluate Plotkin-type bounds and makes specialized bounds easier to compute for specific functions.
Abstract
from arXiv · showhide
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, including the Hamming and Lee distances. Every function partitions the message space into preimage sets corresponding to its distinct function values. Existing Plotkin-type bounds on the optimal redundancy of FCCs under the studied distances, applicable to arbitrary functions on the message space, depend on the pairwise distances among all the message vectors. This makes these bounds difficult to compute. We derive a general Plotkin-type bound on the optimal redundancy of FCCs under Wyner Graham distances, which include the Hamming and Lee distances as special cases. Our bound depends only on the cardinalities of the preimage sets and the sum of pairwise distances only among vectors within each preimage set. This approach significantly reduces the computations required to evaluate the existing Plotkin-type bounds and yields simplified bounds that are easier to compute for specific functions. We obtain simplified Plotkin-type bound for linear functions under the Wyner-Graham distance. Furthermore, the existing simplified bounds for linear functions under the Hamming and Lee distances are recovered as special cases of the proposed bound. We also obtain simplified bounds for several important classes of functions, including the Hamming weight function, the Hamming weight distribution function, the monomial functions under the Hamming distance, and the modular sum function, the Lee weight function, and the Lee weight distribution function under the Lee distance.
I. INTRODUCTION
Function-correcting codes protect specified function evaluations over noisy channels, but existing arbitrary-function Plotkin-type bounds can be computationally intensive. This paper exploits preimage partitions to derive more tractable bounds under Wyner–Graham distances, including Hamming and Lee distances.
- Existing Plotkin-type bounds for arbitrary functions require pairwise distances among many message-vector pairs, making evaluation computationally intensive.
- Every function partitions the message space into preimage sets, enabling bounds based on set cardinalities and within-set pairwise-distance sums.The proposed approach avoids distances between vectors belonging to different preimage sets.
- The paper introduces a general Plotkin-type bound for arbitrary functions under the Wyner–Graham distance framework.The framework includes Hamming and Lee distances as special cases.
- The resulting bound reduces the computations needed to evaluate existing Plotkin-type bounds and yields specialized bounds for Hamming and Lee distances.
- Simplified bounds are derived for linear functions and for functions including Hamming weight, weight distributions, monomials, modular sums, and Lee weight functions.The listed specializations cover Hamming- and Lee-distance settings.
- Wyner–Graham distances are a class of distances that includes Hamming and Lee distances and satisfies conditions introduced by Wyner and Graham.
B. Function-correcting codes with Wyner-Graham distance dX
The section defines FCCs under the Wyner-Graham distance and develops general and specialized Plotkin-type bounds for arbitrary functions. The proposed formulation uses preimage-set structure to reduce the computations required by existing bounds.
- Definitions: An FCC encodes u systematically as (u, p(u)) and must preserve function-value distinguishability under at most t errors.The encoding has length k+r, and distinct function values require codeword distance at least 2t+1.
- Definitions: The optimal redundancy is the smallest r permitting an FCC that recovers f(u) from any received vector within distance t.
- General bound: The proposed general bound depends on preimage-set cardinalities and within-set pairwise-distance sums, rather than cross-set distances.This replaces computation over distance requirements between message vectors associated with distinct function values.
- Specializations: The Wyner-Graham bound specializes to Hamming and Lee distances, producing corresponding arbitrary-function Plotkin-type bounds.
- Comparison with existing bounds: Existing Hamming and Lee bounds require DRM entries or distance requirements across the message space, making evaluation computationally intensive as the message space grows.
IV. PLOTKIN-TYPE BOUND FOR FCCS FOR LINEAR FUNCTIONS
For linear functions over a finite ring, the paper simplifies the general Wyner-Graham Plotkin-type bound using kernel cosets and their distance distributions. Translation invariance yields a further simplification, recovering known Hamming and Lee bounds.
- Kernel partition: Linearity partitions the message space into cosets of ker(f), with each coset containing vectors mapped to one function value.
- Translation invariance: When the distance is translation-invariant, all kernel cosets share the kernel’s distance distribution.This permits the within-preimage distance terms to be characterized through ker(f).
- Wyner-Graham bound: The paper derives a simplified lower bound on optimal redundancy for linear functions under the Wyner-Graham distance, with a further translation-invariant form.
- Hamming specialization: For Hamming distance, the specialized linear-function bound exactly matches the Plotkin bound previously obtained for Hamming-distance FCCs.
- Lee specialization: For Lee distance, the specialized linear-function bound exactly matches the previously obtained Lee-distance Plotkin bound.
V. SIMPLIFIED PLOTKIN-TYPE BOUNDS FOR FUNCTIONS UNDER THE HAMMING DISTANCE
The paper simplifies its Hamming-distance Plotkin-type bound for several function classes by characterizing preimage partitions and within-class distance sums.
- Scope: The simplification covers Hamming weight, Hamming weight distribution, and monomial functions under the Hamming distance.
A. Hamming weight function
For the Hamming weight function, the paper evaluates preimage sizes and within-class distance sums to obtain a simplified redundancy bound. The resulting bound applies in all parameter regimes.
- Partition structure: The Hamming weight function partitions Fq^k into classes Ui={u:wH(u)=i}, with each vector in Ui having exactly i nonzero coordinates.
- Distance sums: Each weight class is invariant under coordinate permutations, so coordinate-wise ordered-pair counts are identical across coordinates.
- Distance sums: The within-class distance sums are obtained by separating zero and nonzero coordinate values and summing contributions across all weight classes.
- Bound: The resulting expression yields a simplified lower bound on optimal redundancy for the Hamming weight function.
- Example: For k=3 and t=1, the bound gives rw_H(3,1)≥2 after enforcing integer redundancy.
- Scope: Unlike earlier simplified bounds for the Hamming weight function, this bound applies in all parameter regimes rather than only k>t.
B. Hamming weight distribution function
The Hamming weight distribution function partitions vectors into classes according to weight intervals, enabling explicit computation of class sizes and intra-class distance sums for a simplified redundancy bound.
- B. Hamming weight distribution function: The function assigns each vector to a preimage class based on the interval [jT, (j + 1)T −1] containing its Hamming weight.The number of intervals is E = (k + 1)/T when T divides k + 1.
- B. Hamming weight distribution function: The derivation computes the sum of squared preimage sizes required by the general Plotkin-type bound.This computation is performed after determining the cardinalities of the interval-based preimage sets.
- B. Hamming weight distribution function: Coordinate-permutation invariance of each preimage class supports calculating its total intra-class pairwise Hamming distance.The classes are invariant under coordinate permutations, allowing the distance calculation to exploit their symmetry.
- B. Hamming weight distribution function: Substituting the computed class-size and distance expressions yields a lower bound on optimal FCC redundancy for the Hamming weight distribution function.The resulting bound is stated in the subsequent corollary.
C. Monomial function
For monomial functions f(x) = x^n over finite fields, the paper characterizes preimage structure through the kernel and derives a simplified Hamming-distance Plotkin-type redundancy bound.
- C. Monomial function: A monomial function f(x) = x^n is gcd(n, q −1)-to-1 on the nonzero elements of its finite-field domain.The paper separately analyzes the zero preimage and the nonzero preimage classes.
- C. Monomial function: The paper derives a simplified Plotkin-type bound for monomial functions by explicitly evaluating preimage sizes and intra-class Hamming distances.The zero preimage is a singleton, while the nonzero classes have size ℓ; these quantities are substituted into the general bound.
- C. Monomial function: Every nonzero image value of f(x) = x^n has exactly ℓ = gcd(n, q^k −1) preimages.This establishes uniform cardinality for all nonzero preimage sets.
- C. Monomial function: The kernel K = {x ∈ F_q^k : x^n = 1} is a multiplicative subgroup, and every nonempty preimage set is a multiplicative coset of K.Thus, the nonzero preimage classes have a structured algebraic form.
- C. Monomial function: For f(x) = x^5 over F_2^4, three nonzero preimage sets of size five give total intra-class distance S = 128 and, for t = 1, the bound r ≥ 2.One class contributes total Hamming distance 44; repeating the calculation over all three classes yields S = 128.
VI. SIMPLIFIED PLOTKIN-TYPE BOUNDS FOR FUNCTIONS UNDER THE LEE DISTANCE
The Lee-distance section simplifies the general Plotkin-type FCC bound for the Lee weight, Lee weight distribution, and modular sum functions by evaluating their induced partitions and intra-class distances.
- VI. SIMPLIFIED PLOTKIN-TYPE BOUNDS FOR FUNCTIONS UNDER THE LEE DISTANCE: The paper studies the Lee weight, Lee weight distribution, and modular sum functions under the Lee distance.For each function, the simplification uses the sizes of its partition classes and pairwise distances within those classes.
A. Lee weight function
For the Lee weight function, the paper counts vectors by Lee weight, exploits coordinate-permutation symmetry, and substitutes the resulting class sizes and distance sums into a redundancy bound.
- A. Lee weight function: The Lee weight function maps each vector to the sum of its coordinate Lee weights and partitions Z_q^k by total Lee weight.The preimage class for weight i is U_i = {u ∈ Z_q^k : w_L(u) = i}.
- A. Lee weight function: For odd q, each nonzero Lee weight is represented by two symbols, while for even q the maximum Lee weight has one representation.These symbol multiplicities determine the counting expressions for the preimage sizes.
- A. Lee weight function: For the Lee weight function on Z_5^2, the preimage-class cardinalities are (1, 4, 8, 8, 4).The classes correspond to Lee weights 0 through 4.
- A. Lee weight function: The preimage classes are invariant under coordinate permutations, so every coordinate contributes identically to the aggregate intra-class Lee distance.A bijection between coordinate-restricted subsets establishes that each coordinate column is a permutation of the first.
- A. Lee weight function: For the Lee weight-2 class in Z_4^2, |U_2| = 6 and its summed coordinate distance is 72, verifying the derived distance formula.The example confirms the simplified expression for q = 4 and k = 2.
- A. Lee weight function: Substituting the class sizes and intra-class distance sums produces the simplified redundancy bound for the Lee weight function, applicable in all parameter regimes.The paper contrasts this scope with earlier bounds restricted to particular q, k, or t regimes.
B. Lee weight distribution function
The Lee weight distribution function groups Lee-weight preimage sets into partition sets, enabling explicit cardinalities and within-set pairwise Lee-distance sums for a simplified Plotkin-type bound.
- The Lee weight distribution function maps vectors according to their Lee-weight distribution, with expressiveness E.
- Partition sets V_j combine consecutive Lee-weight classes U_i, where each U_i contains vectors of Lee weight i.
- For the example over Z_5^2 with T = 2, the preimage cardinalities are (1, 4, 8, 8, 4), yielding partition cardinalities (5, 16, 4).
- Coordinate-permutation invariance makes every coordinate column a permutation of the first, simplifying within-set Lee-distance calculations.
- Substituting the resulting cardinalities and within-set Lee-distance sums into Corollary 2 produces a simplified bound for the Lee weight distribution function.
C. Modular sum function
The modular sum function is linear, so its preimages are equal-sized kernel cosets; this structure yields an explicit Plotkin-type bound applicable for every error-correction parameter t.
- The modular sum function computes the component sum modulo q.
- The modular sum function is linear, allowing the linear-function Plotkin-type bound to specialize directly to this function.
- Its preimages are cosets of ker(S_m), and every preimage has cardinality q^(k−1).
- Each symbol occurs q^(k−2) times in every coordinate position of the kernel, enabling evaluation of its total Lee weight through additivity.
- The resulting Corollary 10 bound applies for all t, unlike the existing simplified bound, which is restricted to sufficiently large t for even q.
VII. CONCLUSION
The paper develops Wyner–Graham Plotkin-type bounds for FCCs using preimage cardinalities and within-preimage distance sums, then specializes them to linear and important nonlinear functions.
- The Wyner–Graham framework includes the Hamming and Lee distances as special cases.
- The general bound depends on preimage cardinalities and within-preimage pairwise distance sums rather than cross-preimage distances.
- The proposed formulation requires fewer computations than existing arbitrary-function Plotkin-type bounds.
- Simplified bounds are derived for linear functions and for Hamming- and Lee-based weight, distribution, monomial, and modular-sum functions.
- Future work includes extending the approach to other distance measures, including b-symbol and s-gram distances.