Linear codes proven to meet coverage bounds up to redundancy fourteen
Auxiliary Codes and the Generalized Packing-Covering Conjecture
Information Theory
Summary
This paper studies special patterns called linear codes used to detect and correct errors in data. It looks at two key measures—how many errors can be spotted (packing radius) and how well the code can cover all possible error patterns (covering radius). The authors prove that for a wide class of codes, the packing radius is always at most the covering radius, settling this question up to a certain code complexity. They also find new bounds relating code properties and show some codes behave differently at large sizes.
What this means in practice
- •For error correction engineers: Design error-correcting codes with proven guarantees on coverage and detection up to moderate redundancy levels, improving reliability assessments.
- •For digital communication developers: Optimize coding schemes for data transmission by leveraging known bounds for packing and covering properties at practical code sizes.
A theory result. No direct application yet.
Authors
Isaac Barouch Essayag, Aryeh Lev Zabokritskiy
Abstract
The generalized packing--covering conjecture asks whether, at every order, the packing radius of a linear code is at most its covering radius. We prove the conjecture for every linear code of redundancy at most fourteen over every finite field, extending the previously established redundancy-seven range. We also prove the generalized Hamming-weight bound $d_t(C)\le2R_t(C)+1$ whenever the alphabet size $q$ satisfies $q\ge R_t(C)$, using an auxiliary-code criterion that converts a syndrome-space covering property into a weight bound. For binary primitive BCH codes, the packing radius is strictly smaller than the covering radius for every fixed error parameter and order, both at least two, once the extension degree is sufficiently large; this follows from existing covering bounds.