On identifying codes in binary Hamming spaces. (English) Zbl 1005.94030
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.
Reviewer: Kim Hang Kim (Montgomery)
MSC:
| 94B60 | Other types of codes |
| 94B75 | Applications of the theory of convex sets and geometry of numbers (covering radius, etc.) to coding theory |
References:
| [1] | Alon, N.; Bergmann, E. E.; Coppersmith, D.; Odlyzko, A. M., Balancing sets of vectors, IEEE Trans. Inform. Theory, 34, 128-130 (1998) · Zbl 0647.94018 |
| [2] | Barthélemy, J.-P.; Cohen, G.; Lobstein, A., Algorithmic Complexity and Communication Problems (1996), Univ. College of London: Univ. College of London London · Zbl 0765.68005 |
| [3] | Blass, U.; Honkala, I.; Litsyn, S., On binary codes for identification, J. Combin. Des., 8, 151-156 (2000) · Zbl 1016.94041 |
| [4] | Blass, U.; Honkala, I.; Litsyn, S., Bounds on identifying codes, Discrete Math., 241, 119-128 (2001) · Zbl 0991.94061 |
| [5] | Cohen, G., A nonconstructive upper bound on covering radius, IEEE Trans. Inform. Theory, 29, 352-353 (1983) · Zbl 0545.94010 |
| [6] | Cohen, G.; Frankl, P., On tilings of the binary vector space, Discrete Math., 31, 271-277 (1980) · Zbl 0452.05018 |
| [7] | Cohen, G.; Frankl, P., Good coverings of Hamming spaces with spheres, Discrete Math., 56, 125-131 (1985) · Zbl 0579.94017 |
| [8] | Cohen, G.; Honkala, I.; Litsyn, S.; Lobstein, A., Covering Codes (1997), Elsevier: Elsevier Amsterdam · Zbl 0874.94001 |
| [9] | Delsarte, P.; Piret, P., Do most binary linear codes achieve the Goblick bound on the covering radius?, IEEE Trans. Inform. Theory, 32, 826-828 (1986) · Zbl 0611.94010 |
| [10] | G. Exoo, Computational results on identifying \(t\); G. Exoo, Computational results on identifying \(t\) |
| [11] | Gabidulin, E. M.; Davydov, A. A.; Tombak, L. M., Linear codes with covering radius 2 and other new covering codes, IEEE Trans. Inform. Theory, 37, 219-224 (1991) · Zbl 0713.94018 |
| [12] | Garey, M. R.; Johnson, D. S., Computers and Intractability, a Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [13] | Haynes, T. W.; Hedetniemi, S. T.; Slater, P. J., Fundamentals of Domination in Graphs (1998), Marcel Dekker: Marcel Dekker New York · Zbl 0890.05002 |
| [14] | Honkala, I., On the identifying radius of codes, Proceedings of the Seventh Nordic Combinatorial Conference, Turku, 39-43 (1999) · Zbl 0988.94038 |
| [15] | Honkala, I.; Laihonen, T.; Ranto, S., On codes identifying sets of vertices in Hamming spaces, Des. Codes Cryptogr., 24, 193-204 (2001) · Zbl 1008.94028 |
| [16] | I. Honkala, T. Laihonen, and, S. Ranto, On strongly identifying codes, Discrete Math, to appear.; I. Honkala, T. Laihonen, and, S. Ranto, On strongly identifying codes, Discrete Math, to appear. · Zbl 1005.94029 |
| [17] | I. Honkala, and, A. Lobstein, On the complexity of the identification problem in Hamming spaces, submitted.; I. Honkala, and, A. Lobstein, On the complexity of the identification problem in Hamming spaces, submitted. · Zbl 1034.68043 |
| [18] | Kabatyanskii, G. A.; Panchenko, V. I., Unit sphere packings and coverings of the Hamming space, Problems Inform. Transmission, 24-4, 261-272 (1988) · Zbl 0679.94015 |
| [19] | Karpovsky, M. G.; Chakrabarty, K.; Levitin, L. B., On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44, 599-611 (1998) · Zbl 1105.94342 |
| [20] | T. Laihonen, Optimal codes for strong identification, European J. Combin, to appear.; T. Laihonen, Optimal codes for strong identification, European J. Combin, to appear. · Zbl 1011.94027 |
| [21] | Laihonen, T., Sequences of optimal identifying codes, IEEE Trans. Inform. Theory, 48, 774-776 (2002) · Zbl 1071.94541 |
| [22] | T. Laihonen, and, S. Ranto, Families of optimal codes for strong identification, Discrete Appl. Math, to appear.; T. Laihonen, and, S. Ranto, Families of optimal codes for strong identification, Discrete Appl. Math, to appear. · Zbl 1005.94031 |
| [23] | van Lint, J. H., Introduction to Coding Theory (1982), Springer: Springer Berlin · Zbl 0485.94015 |
| [24] | MacWilliams, F. J.; Sloane, N. J.A., The Theory of Error-Correcting Codes (1977), Elsevier: Elsevier Amsterdam · Zbl 0369.94008 |
| [25] | McLoughlin, A., The complexity of computing the covering radius of a code, IEEE Trans. Inform. Theory, 30, 800-804 (1984) · Zbl 0556.94009 |
| [26] | S. Ranto, I. Honkala, and, T. Laihonen, Two families of optimal identifying codes in binary Hamming spaces, IEEE Trans. Inform. Theory, to appear.; S. Ranto, I. Honkala, and, T. Laihonen, Two families of optimal identifying codes in binary Hamming spaces, IEEE Trans. Inform. Theory, to appear. · Zbl 1061.94080 |
| [27] | Struik, R., Covering codes (1994), Eindhoven Univ. of Technology |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
