## Abstract

Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, $\overline{t}$-separable codes lie somewhere between $t$-frameproof and $(t-1)$-frameproof codes: all $t$-frameproof codes are $\overline{t}$-separable, and all $\overline{t}$-separable codes are $(t-1)$-frameproof. Results for frameproof codes show that (when $q$ is large) there are $q$-ary $\overline{t}$-separable codes of length $n$ with approximately $q^{\lceil n/t\rceil}$ codewords, and that no $q$-ary $\overline{t}$-separable codes of length $n$ can have more than approximately $q^{\lceil n/(t-1)\rceil}$ codewords.

The paper provides improved probabilistic existence results for $\overline{t}$-separable codes when $t\geq 3$. More precisely, for all $t\geq 3$ and all $n\geq 3$, there exists a constant $\kappa$ (depending only on $t$ and $n$) such that there exists a $q$-ary $\overline{t}$-separable code of length $n$ with at least $\kappa q^{n/(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 $\overline{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 $\overline{2}$-separable code of length $n$ can contain at most $\frac{3}{2}q^{2\lceil n/3\rceil}-\frac{1}{2}q^{\lceil n/3\rceil}$ codewords, and that codes with at least $\kappa q^{2n/3}$ codewords exist. Thus optimal $\overline{2}$-separable codes behave neither like $2$-frameproof nor $1$-frameproof codes.

The paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a $q$-ary $\overline{2}$-separable code of length $n$ is at most

\[

q^{\lceil 2n/3\rceil}+\tfrac{1}{2}q^{\lfloor n/3\rfloor}(q^{\lfloor n/3\rfloor}-1).

\]

The paper provides improved probabilistic existence results for $\overline{t}$-separable codes when $t\geq 3$. More precisely, for all $t\geq 3$ and all $n\geq 3$, there exists a constant $\kappa$ (depending only on $t$ and $n$) such that there exists a $q$-ary $\overline{t}$-separable code of length $n$ with at least $\kappa q^{n/(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 $\overline{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 $\overline{2}$-separable code of length $n$ can contain at most $\frac{3}{2}q^{2\lceil n/3\rceil}-\frac{1}{2}q^{\lceil n/3\rceil}$ codewords, and that codes with at least $\kappa q^{2n/3}$ codewords exist. Thus optimal $\overline{2}$-separable codes behave neither like $2$-frameproof nor $1$-frameproof codes.

The paper also observes that the bound of Gao and Ge can be strengthened to show that the number of codewords of a $q$-ary $\overline{2}$-separable code of length $n$ is at most

\[

q^{\lceil 2n/3\rceil}+\tfrac{1}{2}q^{\lfloor n/3\rfloor}(q^{\lfloor n/3\rfloor}-1).

\]

Original language | English |
---|---|

Pages (from-to) | 5822-5827 |

Number of pages | 6 |

Journal | IEEE Transactions on Information Theory |

Volume | 61 |

Issue number | 11 |

Early online date | 22 Sept 2015 |

DOIs | |

Publication status | E-pub ahead of print - 22 Sept 2015 |