On identifying codes in binary Hamming spaces (Q696908): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:59, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On identifying codes in binary Hamming spaces |
scientific article |
Statements
On identifying codes in binary Hamming spaces (English)
0 references
12 September 2002
0 references
This paper studies the asymptotic minimum sizes \(M_r(n)\) of binary \(r\)-identifying codes \(C\subset \{ 0,1\}^n\). That means that all the sets \(B_r(x)\cap C\) are nonempty and distinct. The result is \[ \lim_{n\to \infty} n^{-1}M_{\lfloor \rho n \rfloor} (n) =1+\rho \log_2 \rho +(1-\rho) \log_2 (1-\rho). \] For linear codes, it is shown that the problem of determining whether a given code is \(r\)-identifying is \(\Pi_2\)-complete by reducing a \(\forall \exists \) 3-dimensional matching problem to it.
0 references
Hamming space
0 references
identifying codes
0 references
covering codes
0 references
complexity
0 references