The Generalized Covering Radii of Linear Codes

DOI10.1109/TIT.2021.3115433MaRDI QIDQ5032643zbMATH OpenOpenAlexFDO

Authors Dor Elimelech, Marcelo Firer, Moshe Schwartz

Publication date 17 February 2022

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2012.06467

zbMATH Keywords

generalized covering radiusgeneralized Hamming weights

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05) Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory (94B75)

Abstract: Motivated by an application to database linear querying, such as private information-retrieval protocols, we suggest a fundamental property of linear codes -- the generalized covering radius. The generalized covering-radius hierarchy of a linear code characterizes the trade-off between storage amount, latency, and access complexity, in such database systems. Several equivalent definitions are provided, showing this as a combinatorial, geometric, and algebraic notion. We derive bounds on the code parameters in relation with the generalized covering radii, study the effect of simple code operations, and describe a connection with generalized Hamming weights.

Cited in

(14)

• Linear codes with covering radius 3
• scientific article; zbMATH DE number 4016768 (Why is no real title available?)
• Linear inequalities for covering codes. I. Pair covering inequalities
• Linear inequalities for covering codes. II. Triple covering inequalities
• On the structure of linear codes with covering radius two and three
• scientific article; zbMATH DE number 1057770 (Why is no real title available?)
• On the Newton and covering radii of linear codes
• The second-order football-pool problem and the optimal rate of generalized-covering codes
• Determining the exact value of the second-order generalized covering radius of two classes of binary cyclic codes
• New infinite families of uniformly packed near-MDS codes and multiple coverings, based on the ternary Golay code
• The third generalized covering radius for binary primitive double-error-correcting BCH codes
• The second generalized covering radius of binary primitive double-error-correcting BCH codes
• On the second generalized covering radius for binary primitive triple-error-correcting BCH codes
• Some optimal codes from algebraic geometry and their covering radii

This page was built for publication: The Generalized Covering Radii of Linear Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5032643)