r-Identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube

摘要

We study about monotonicity of r-identifying codes in binary Hamming space, q-ary Lee space and incomplete hypercube. Also, we give the lower bounds for M1,q(≤l)(n) where M1,q(≤l)(n) is the smallest cardinality among all r-identifying codes in ?qn with respect to the Lee metric. We prove the existence of 1-identifying code in an incomplete hypercube. Also, we give the construction techniques for r-identifying codes in the incomplete hypercubes in Secs. 4.1 and 4.2. Using these techniques, we give the tables (see Tables 1–6) of upper bounds for MIH,r(k) where MIH,r(k) is the smallest cardinality among all r-identifying codes in an incomplete hypercube with k processors. Also, we give the exact values of MIH,r(k) for small values of r and k (see Sec. 4.3).