On multifold packings of radius-1 balls in Hamming graphs Научная публикация
| Журнал |
IEEE Transactions on Information Theory
ISSN: 0018-9448 , E-ISSN: 1557-9654 |
||
|---|---|---|---|
| Вых. Данные | Год: 2021, Том: 67, Номер: 6, Страницы: 3585-3598 Страниц : 14 DOI: 10.1109/TIT.2020.3046260 | ||
| Ключевые слова | Hamming graph, multifold ball packings, two-fold ball packings, list decodable codes, multiple coverings, completely regular codes, linear programming bound | ||
| Авторы |
|
||
| Организации |
|
Реферат:
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.
Библиографическая ссылка:
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
Даты:
| Поступила в редакцию: | 15 нояб. 2019 г. |
| Принята к публикации: | 14 дек. 2020 г. |
| Опубликована online: | 21 дек. 2020 г. |
Идентификаторы БД:
| Web of science: | WOS:000652795200026 |
| Scopus: | 2-s2.0-85098774685 |
| РИНЦ: | 46743222 |
| OpenAlex: | W2914368414 |