pipette
ENEnglish

The Asymptotic Number of Anticodes in Hamming Spaces

Anna-Lena Horlemann, Ananthakrishnan Ravi

Preprint

En palabras de los autores

In the Hamming space , a -anticode is a subset in which every pair of points has Hamming distance at most , or equivalently, a set of diameter at most . Let denote the maximum size of a -anticode and let be the family of all -anticodes. We show that for fixed , as , the total number of -anticodes satisfies \[ |\mathcal{A}_q(n,d)|=2^{(1+o(1))m_q(n,d)} \] for , except when and . We also count linear -anticodes, that is, subspaces of with diameter at most . For fixed and , their number is polynomial in . For growing , we determine the exponential order as in the sublinear regime and when . In the near-full regime , we obtain the sharper count . A random-generator construction further improves the binary lower bound for every fixed linear diameter.

Resultado principalLimitación que admiten los autores

Apareció: viernes, 23 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: Two figures. Comments are welcome