New bounds on \bar{2}-separable codes of length 2

Research paper by Minquan Cheng, Hung-Lin Fu, Jing Jiang, Yuan-Hsun Lo, Ying Miao

Indexed on: 27 Jun '13Published on: 27 Jun '13Published in: Designs, Codes and Cryptography


Let \(\mathbb{C }\) be a code of length \(n\) over an alphabet of \(q\) letters. The descendant code \(\mathsf{desc}(\mathbb C _0)\) of \(\mathbb C _0 = \{\mathbf{c}^1, \mathbf{c}^2, \ldots , \mathbf{c}^t\} \subseteq \mathbb{C }\) is defined to be the set of words \(\mathbf{x} = (x_1, x_2, \ldots ,x_n)\) such that \(x_i \in \{c^1_i, c^2_i, \ldots , c^t_i\}\) for all \(i=1, \ldots , n\). \(\mathbb{C }\) is a \(\overline{t}\)-separable code if for any two distinct \(\mathbb{C }_1, \mathbb{C }_2 \subseteq \mathbb{C }\) such that \(|\mathbb{C }_1| \le t\), \(|\mathbb{C }_2| \le t\), we always have \(\mathsf{desc}(\mathbb{C }_1) \ne \mathsf{desc}(\mathbb{C }_2)\). The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let \(M(\overline{t},n,q)\) be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for \(M(\overline{2},2,q)\) by a graph theoretical approach, and a new lower bound for \(M(\overline{2},2,q)\) by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth \(6\) and a construction of such maximal bipartite graphs.