Bounds on r-identifying codes in q-ary Lee space

  • Dhanalakshmi Ramalingam Bharathidasan University
  • Chinnapillai Durairajan Bharathidasan University


Identifying codes are used to locate malfunctioning processors in multiprocessor systems. In this paper, we study identifying codes in a $q$-ary hypercube which is used in parallel processing. Computing upper and lower bounds of $M_{r,q}(n),$ the smallest cardinality among all $r$-identifying codes in $\mathbb{Z}_q^n$ with respect to the Lee metric, is an important research problem in this area. Using our constructions, we produce tables for upper and lower bounds for $M_{r,q}(n)$. The upper and the lower bounds of $M_{r,4}(n)$ known only when $r=1$ but using our results, we compute the bounds for $M_{r,4}(n)$ for all $r\geq 1$. Also we improve upon the currently known upper bounds of $M_{1,4}(n)$ due to J. L. Kim and S. J. Kim. Upper bounds of $M_{r,q}(n)$ for $q>4$ are known previously for some cases of $n$. We improve some of these bounds and we also compute bounds for all $n$ by using our results.


[1] J. Astola, The Theory of Lee Codes, Tech. rep., Lappeenranta University 340 of Technology (1982).

[2] R. M. Roth, Introduction to Coding Theory, Cambridge University Press, 2006.

[3] M. G. Karpovsky, K. Chakrabarty, L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory 44 (1998) 345 599-611.

[4] R. M. Hord, Parallel Supercomputing in MIMD Architectures, CRC Press, 1993.

[5] W. J. Dally, The message-driven processor: A multicomputer processing node with efficient mechanisms, IEEE Micro 12 (1992)

[6] M. Laifenfeld, A. Trachtenberg, Identifying codes and covering problems, IEEE Trans. Inform. Theory 54(9) (2008) 3929-3950.

[7] J. L. Kim, S. J. Kim, Identifying codes in q-ary hypercubes., Bull. Inst. Combin. Appl. 59 (2010) 93-102.

[8] I. Charon, G. Cohen, O. Hudry, New identifying codes in the binary Ham- 355 ming space, Eur. J. Combin. 31 (2010) 491-501.

[9] I. Honkala, A. Lobstein, On the complexity of the identification problem in Hamming spaces, Acta Informatica 38 (2002) 839-845.

[10] G. Exoo, V. Junnila, T. Laihonen, S. Ranto, Improved bounds on identify- ing codes in binary Hamming spaces, Eur. J. Combin. 31 (2010) 813-827.