New bound improves error correction for special finite field functions
Plotkin-type Bound on Function-Correcting Codes for Monomial Mappings
Information Theory
Summary
Sometimes, messages sent through noisy channels can get messed up, and special codes help fix them. This paper studies a new kind of code that focuses on protecting certain functions of messages, not just the messages themselves. The authors found a mathematical limit (a bound) on how efficiently these codes can work for a wide variety of functions, including those used in encryption and geometry. Their work extends older results and gives explicit formulas for some important cases.
What this means in practice
- •For coding theory engineers: Design codes that efficiently protect computations of monomial functions used in communication systems.
- •For cryptographers: Evaluate limits on error resilience for cryptographic schemes relying on monomial mappings over finite fields.
A theory result. No direct application yet.
Authors
Kanchana Lokshmii Jagatti, B. Sundar Rajan
Abstract
Function-correcting codes, recently introduced by Lenz et al.\ (2023), provide a framework for the receiver to provide a higher level of protection against channel errors than the level of protection for messages. In this paper, we derive a generalised Plotkin-type bound on the redundancy of FCCs under the Hamming metric for arbitrary functions over finite fields. The proposed bound recovers the classical Plotkin bound for classical error-correcting codes as a special case. We further obtain explicit Plotkin-type bounds for linear functions, Hamming-weight functions, and Hamming-weight threshold functions. In addition, we study FCCs for monomial mappings $f(x)=x^n$ over $\mathbb{F}_{q^k}$, which are widely utilised in coding theory, cryptography, and finite geometry, and derive an explicit Plotkin-type redundancy bound.