Asymptotic Overview on Separating Codes

Abstract

Separating codes (or systems) are known from combinatorics, and they enjoy increasing attention due to applications in digital fingerprinting. Previous applications are found in automata theory and the construction of fault-tolerant systems. Let Γ be a code of length n, and (T,U) a pair of disjoint subsets of Γ. We say that (T,U) is separated if there exists a coordinate i, such that for any codeword (c1,...,cn) ∈ T and any codeword (c ′ 1,...,c ′ n) ∈ U, ci � = c ′ i. The code Γ is (t,u)separating if all pairs (T,U) with #T = t and #U = u are separated. In this report, we give an overview of existing techniques for bounding the asymptotical rate of separating codes, including some constructions and construction techniques. We provide numerical results for binary (t,u)-separating codes for some small values of t and u. The report includes both old and new results. Keywords separating system, intersecting code