# Bounds and constructions for $${\overline{3}}$$ 3 ¯ -separable codes with length 3

Research paper by Minquan Cheng, Jing Jiang; Haiyan Li; Ying Miao; Xiaohu Tang

Indexed on: 19 Aug '16Published on: 01 Nov '16Published in: Designs, Codes and Cryptography

#### Abstract

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, \ldots , \mathbf{c}_t\} \subseteq {{\mathcal {C}}}$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)^T$$ such that $$x_i \in \{c_{1,i}, c_{2,i}, \ldots , c_{t,i}\}$$ for all $$i=1, \ldots , n$$ , where $$\mathbf{c}_j=(c_{j,1},c_{j,2},\ldots ,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, and then two constructions for $${\overline{3}}\hbox {-SC}(3,M,q)$$ s are provided by means of perfect hash families and Steiner triple systems.AbstractSeparable 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, \ldots , \mathbf{c}_t\} \subseteq {{\mathcal {C}}}$$ is defined to be the set of words $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)^T$$ such that $$x_i \in \{c_{1,i}, c_{2,i}, \ldots , c_{t,i}\}$$ for all $$i=1, \ldots , n$$ , where $$\mathbf{c}_j=(c_{j,1},c_{j,2},\ldots ,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, and then two constructions for $${\overline{3}}\hbox {-SC}(3,M,q)$$ s are provided by means of perfect hash families and Steiner triple systems. $${\mathcal {C}}$$ $${\mathcal {C}}$$nq $${\mathsf{desc}}({\mathcal {C}}_0)$$ $${\mathsf{desc}}({\mathcal {C}}_0)$$ $${\mathcal {C}}_0 = \{\mathbf{c}_1, \mathbf{c}_2, \ldots , \mathbf{c}_t\} \subseteq {{\mathcal {C}}}$$ $${\mathcal {C}}_0 = \{\mathbf{c}_1, \mathbf{c}_2, \ldots , \mathbf{c}_t\} \subseteq {{\mathcal {C}}}$$ $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)^T$$ $$\mathbf{x} = (x_1, x_2, \ldots ,x_n)^T$$ $$x_i \in \{c_{1,i}, c_{2,i}, \ldots , c_{t,i}\}$$ $$x_i \in \{c_{1,i}, c_{2,i}, \ldots , c_{t,i}\}$$ $$i=1, \ldots , n$$ $$i=1, \ldots , n$$ $$\mathbf{c}_j=(c_{j,1},c_{j,2},\ldots ,c_{j,n})^T$$ $$\mathbf{c}_j=(c_{j,1},c_{j,2},\ldots ,c_{j,n})^T$$ $${\mathcal {C}}$$ $${\mathcal {C}}$$ $${\overline{t}}$$ $${\overline{t}}$$ $${\mathcal {C}}_1, {\mathcal {C}}_2 \subseteq {\mathcal {C}}$$ $${\mathcal {C}}_1, {\mathcal {C}}_2 \subseteq {\mathcal {C}}$$ $${\mathcal {C}}_1 \le t$$ $${\mathcal {C}}_1 \le t$$ $${\mathcal {C}}_2 \le t$$ $${\mathcal {C}}_2 \le t$$ $${\mathsf{desc}}({\mathcal {C}}_1) \ne {\mathsf{desc}}({\mathcal {C}}_2)$$ $${\mathsf{desc}}({\mathcal {C}}_1) \ne {\mathsf{desc}}({\mathcal {C}}_2)$$ $$M({\overline{t}},n,q)$$ $$M({\overline{t}},n,q)$$ $$M({\overline{3}},3,q)$$ $$M({\overline{3}},3,q)$$ $${\overline{3}}\hbox {-SC}(3,M,q)$$ $${\overline{3}}\hbox {-SC}(3,M,q)$$