Bounds and Constructions for $\overline{3}$-Separable Codes with Length $3$

Abstract

Separable codes were introduced to provide protection against illegal redistribution of copyrighted multimedia material. Let $\mathcal{C}$ be a code of length $n$ over an alphabet of $q$ letters. The descendant code $\mathsf{desc}({\mathcal{C}}_0)$ of ${\mathcal{C}}_0=\{{\mathbf{c}}_1,{\mathbf{c}}_2,\dots ,{\mathbf{c}}_t\}\subseteq \mathcal{C}$ is defined to be the set of words $\mathbf{x}=(x_1,x_2,\dots ,x_n{)}^T$ such that $x_i\in \{c_{1,i},c_{2,i},\dots ,c_{t,i}\}$ for all $i=1,\dots ,n$, where ${\mathbf{c}}_j=(c_{j,1},c_{j,2},\dots ,c_{j,n}{)}^T$. $\mathcal{C}$ is a $\overline{t}$-separable code if for any two distinct ${\mathcal{C}}_1,{\mathcal{C}}_2\subseteq \mathcal{C}$ with $|{\mathcal{C}}_1|\le t$, $|{\mathcal{C}}_2|\le t$, we always have $\mathsf{desc}({\mathcal{C}}_1)\ne \mathsf{desc}({\mathcal{C}}_2)$. Let $M(\overline{t},n,q)$ denote the maximal possible size of such a separable code. In this paper, an upper bound on $M(\overline{3},3,q)$ is derived by considering an optimization problem related to a partial Latin square, and then two constructions for $\overline{3}$-SC$(3,M,q)$s are provided by means of perfect hash families and Steiner triple systems.

19 pages