Codes with the Identifiable Parent Property for Multimedia Fingerprinting

Let $\mathcal{C}$ be a $q$-ary code of length $n$ and size $M$, and ${\cal C}(i) = {{\bf c}(i) \ | \ {\bf c}=({\bf c}(1), {\bf c}(2), \ldots, {\bf c}(n))^{T} \in {\cal C}}$bethesetof$i$thcoordinatesof${\cal C}$. The descendant code of a sub-code ${\mathcal{C}}^{{}^{\mathrm{\prime }}}\subseteq \mathcal{C}$ is defined to be ${\cal C}^{‘}(1) \times {\cal C}^{’}(2) \times \cdots \times {\cal C}^{'}(n)$. In this paper, we introduce a multimedia analogue of codes with the identifiable parent property (IPP), called multimedia IPP codes or $t$-MIPPC$(n,M,q)$, so that given the descendant code of any sub-code ${\mathcal{C}}^{{}^{\mathrm{\prime }}}$ of a multimedia $t$-IPP code $\mathcal{C}$, one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in ${\mathcal{C}}^{{}^{\mathrm{\prime }}}$. We first derive a general upper bound on the size $M$ of a multimedia $t$-IPP code, and then investigate multimedia $3$-IPP codes in more detail. We characterize a multimedia $3$-IPP code of length $2$ in terms of a bipartite graph and a generalized packing, respectively. By means of these combinatorial characterizations, we further derive a tight upper bound on the size of a multimedia $3$-IPP code of length $2$, and construct several infinite families of (asymptotically) optimal multimedia $3$-IPP codes of length $2$.