Generalized packing radii are bounded by covering radii in coding theory
On the Generalized Packing and Covering Radii of Codes
Information Theory
Summary
In coding, two important measurements describe how codes protect information: how far apart code points are (packing) and how well the code covers all possibilities (covering). Researchers extended these ideas into more detailed levels called generalized radii. It was unclear if the relationship between packing and covering seen at the basic level holds at higher levels. The authors proved this relationship is true for the second level and for all levels under certain conditions on code size and length.
What this means in practice
- •For error correction engineers: Use the guaranteed relationship between generalized packing and covering radii to design codes with predictable error correction and detection capabilities at different levels.
- •For data storage architects: Apply the bounds on generalized radii to build storage systems with optimized redundancy and reliability trade-offs for longer code lengths and specific rates.
A theory result. No direct application yet.
Authors
Wenjun Yu, Moshe Schwartz
Abstract
The minimum distance and the covering radius are two fundamental properties of the code. Both have been extended: the former to the generalized Hamming weights hierarchy, and the latter to the generalized covering radii hierarchy. In both cases, the lowest level of the hierarchies corresponds to the classical minimum distance and covering radius, respectively. From a geometric point of view, the minimum distance of the code determines the packing radius, which is upper bounded by the covering radius. It was conjectured this relation extends to all other orders of the hierarchy, namely, that the generalized packing radii are upper bounded by the generalized covering radii of the same order. In this paper we prove this conjecture is true for the second order radii. We also prove the conjecture holds for all orders when the code rate is at most $3/5$. Finally, we show that for any code rate in $(0,1)$, for all sufficiently long codes the conjecture holds for all orders.