# 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

#### 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.