# 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 '13**Published on: **27 Jun '13**Published in: **Designs, Codes and Cryptography**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### Abstract

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.