Quantcast

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)\)