On the size of identifying codes in binary hypercubes

Details On the size of identifying codes in binary hypercubes On the size of identifying codes in binary hypercubes

2008-04-18

arxiv.org/abs/0804.3029v1

Mathematics

Combinatorics

13 pages

Scientific paper

We consider identifying codes in binary Hamming spaces F^n, i.e., in binary hypercubes. The concept of identifying codes was introduced by Karpovsky, Chakrabarty and Levitin in 1998. Currently, the subject forms a topic of its own with several possible applications, for example, to sensor networks. Let C be a subset of F^n. For any subset X of F^n, denote by I_r(X)=I_r(C;X) the set of elements of C within distance r from at least one x in X. Now C is called an (r,<= l)-identifying code if the sets I_r(X) are distinct for all subsets X of size at most l. We estimate the smallest size of such codes with fixed l and r/n converging to some number rho in (0,1). We further show the existence of such a code of size O(n^{3/2}) for every fixed l and r slightly less than n/2, and give for l=2 an explicit construction of small such codes for r the integer part of n/2-1 (the largest possible value).

Affiliated with

Also associated with

No associations

Rating

On the size of identifying codes in binary hypercubes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the size of identifying codes in binary hypercubes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the size of identifying codes in binary hypercubes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-304179