On the Maximal Codes of Length 3 with the 2-Identifiable Parent Property
Vu Dong Tô, Reihaneh Safavi–Naini · SIAM Journal on Discrete Mathematics · 2004
A q-ary code has identifiable parent property (IPP) if it allows one of the parents of a descendant word to be found. A 2-IPP code ensures that at least one parent of a pirate word constructed by a coalition of two users can be found. In this paper, we answer a question raised in [H. D. L. Hollmann et al., J. Combin. Theory Ser. A, 82 (1998), pp. 121--133] and show that F(q), the maximum number of codewords in a 2-IPP code of length 3, satisfies $|{\cal G}_0| \leq F(q) \leq |{\cal G}_0| +2$, where ${\cal G}_0$ is a well-defined graph. We also give an efficient algorithm (O(q 3 )) for finding maximal codes.