Probabilistic Existence Results for Separable Codes
Simon R. Blackburn⋆ · IEEE Transactions on Information Theory · 2015
Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, t̅-separable codes lie somewhere between t-frameproof and (t - 1)-frameproof codes: all t-frameproof codes are t̅-separable, and all t̅-separable codes are (t - 1)-frameproof. Results for frameproof codes show that (when q is large) there are q-ary t̅-separable codes of length n with approximately q[n/t]codewords, and that no q-ary t̅-separable codes of length n can have more than approximately q[n/(t-l)]codewords. This paper provides improved probabilistic existence results for t-separable codes when t ≥ 3. More precisely, for all t ≥ 3 and all n ≥ 3, there exists a constant κ (depending only on t and n), such that there exists a q-ary t̅-separable code of length n with at least κqn/(t-1)codewords for all sufficiently large integers q. This shows, in particular, that the upper bound [derived from the bound on (t - 1)-frameproof codes] on the number of codewords in a t̅-separable code is realistic. The results above are more surprising after examining the situation when t = 2. Results due to Gao and Ge show that a q-ary 2̅-separable code of length n can contain at most 3/2q2[n/3]- 1/2q[n/3]codewords, and that codes with at least κq2n/3codewords exist. Thus, optimal 2̅-separable codes behave neither like two-frameproof nor one-frameproof codes. This paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a q-ary 2̅-separable code of length n is at most q[2n/3]+ 1/2 q[n/3](q[n/3]-1).