PROLIFIC CODES WITH THE IDENTIFIABLE PARENT PROPERTY

Abstract:  Abstract. Let C be a code of length n over an alphabet of size q. A word d is a descendant of a pair of codewords x, y ? C if di ? {xi, yi} for 1 = i = n. A code C is an identifiable parent property (IPP) code if the following property holds. Whenever we are given C and a descendant d of a pair of codewords in C, it is possible to determine at least one of these codewords. The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all q n words are descendants. It is shown that linear prolific IPP codes fall into three infinite (?trivial?) families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds. Key words. error-correcting codes, identifying parent property, linear codes, MDS codes, orthogonal arrays, copyright protection. AMS subject classifications. 94B60, 94A60, 94B65