On multifold packings of radius-1 balls in Hamming graphs Full article
| Journal |
IEEE Transactions on Information Theory
ISSN: 0018-9448 , E-ISSN: 1557-9654 |
||
|---|---|---|---|
| Output data | Year: 2021, Volume: 67, Number: 6, Pages: 3585-3598 Pages count : 14 DOI: 10.1109/TIT.2020.3046260 | ||
| Tags | Hamming graph, multifold ball packings, two-fold ball packings, list decodable codes, multiple coverings, completely regular codes, linear programming bound | ||
| Authors |
|
||
| Affiliations |
|
Abstract:
A λ-fold r-packing (multiple radius-r covering) in a Hamming metric space is a code C such that the radius-r balls centered in the codewords of C cover each vertex of the space by not more (not less, respectively) than λ times. The well-known r-error-correcting codes correspond to the case λ = 1, while in general multifold r-packing are related with list decodable codes. We (a) propose asymptotic bounds for the maximum size of a q-ary 2-fold 1-packing as q grows; (b) prove that a q-ary distance-2 MDS code of length n is an optimal n-fold 1-packing if q ≥ 2n; (c) derive an upper bound for the size of a binary λ-fold 1-packing and a lower bound for the size of a binary multiple radius-1 covering (the last bound allows to update the small-parameters table); (d) classify all optimal binary 2-fold 1-packings up to length 9, in particular, establish the maximum size 96 of a binary 2-fold 1-packing of length 9; (e) prove some properties of 1-perfect unitrades, which are a special case of 2-fold 1-packings.
Cite:
Krotov D.S.
, Potapov V.N.
On multifold packings of radius-1 balls in Hamming graphs
IEEE Transactions on Information Theory. 2021. V.67. N6. P.3585-3598. DOI: 10.1109/TIT.2020.3046260 WOS Scopus РИНЦ OpenAlex
On multifold packings of radius-1 balls in Hamming graphs
IEEE Transactions on Information Theory. 2021. V.67. N6. P.3585-3598. DOI: 10.1109/TIT.2020.3046260 WOS Scopus РИНЦ OpenAlex
Dates:
| Submitted: | Nov 15, 2019 |
| Accepted: | Dec 14, 2020 |
| Published online: | Dec 21, 2020 |
Identifiers:
| Web of science: | WOS:000652795200026 |
| Scopus: | 2-s2.0-85098774685 |
| Elibrary: | 46743222 |
| OpenAlex: | W2914368414 |