On Optimal Codes with $\omega$-Identifiable Parents Property

Yu Xiong, Jun Ma, and Hao Shen
Department of Mathematics, Shanghai Jiao Tong University, Shanghai 200240, P. R. China


Abstract     Full Text  PDF

In order to protect copyrighted material, codes may be embedded in the content or codes may be associated with the keys used to recover the content. Codes can offer protection by providing some form of traceability for pirated data. The concept of a code with identifiable parents property (IPP) was first introduced by Hollmann et al. Such codes play an important role in copyright protection. Staddon et al. generalized this concept to codes with w-identifiable parents property($\omega$-IPP). In this paper, we give necessary and sufficient conditions for a code to be a $\omega$-IPP code. Furthermore, by the methods of graph theory, we give necessary and sufficient conditions for a code of length $\omega + 1$ to be a $\omega$-IPP code. We investigate the existence of optimal $\omega$-IPP codes of length $\omega+1$. Let $F_{\omega}(\omega+1; q)$ denote the maximum cardinality of $q$-ary $\omega$-IPP codes of length $\omega + 1$. We obtain the bounds for $F_{\omega}(\omega+1; q)$ and give an efficient $(O(q^{w+1}))$ algorithm to find the values of $F_{\omega}(\omega+1; q)$