Error-correcting codes based on partial injective maps of finite sets

摘要

Let [n] = {1, 2,..., n} and ([n]/k) be the set of all k-subsets of [n], where k = 0, 1, ..., n. A pair (A, f) is called a k-partial injective map of [n] , if A ∈ ([n]/k) and f : A → [n] is an injective map. Let I_k~([n]) be the set of all k-partial injective maps of [n] and I~([n]) = ∪_(k=0)~n I_k~([n]). If we define the measure of distance in I~([n]), then I~([n]) is a metric space. So any non-empty subset of I~([n]) is a code. In this paper, we will discuss several upper bounds and lower bounds on the size of codes in I_k~([n]).