Codes with the identifiable parent property for multimedia fingerprinting

Abstract

Let be a q-ary code of length n and size M, and be the set of ith coordinates of . The descendant code of a sub-code is defined to be . 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 of a multimedia t-IPP code , one can always identify, as IPP codes do in the generic digital scenario, at least one codeword in . 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.