Robust parent-identifying codes and combinatorial arrays

Alexander Barg, Grigory Kabatiansky

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


An n-word y=(y-{1},dots, y-{n}) over a finite alphabet of cardinality q is called a descendant of a set of t words x1,dots, xt if every coordinate y-i,i=1,\dots, n, is contained in the set x1-i,dots, xt-i. A code {cal C=x1,dots, x M is said to have the t-IPP property if for any n -word y that is a descendant of at most t parents belonging to the code, it is possible to identify at least one of them. From earlier works, it is known that t-IPP codes of positive rate exist if and only if tleq q-1. We introduce a robust version of IPP codes which allows error-free identification of parents in the presence of a certain number of mutations, i.e., coordinates in y that can break away from the descent rule, taking arbitrary values from the alphabet or becoming completely unreadable. We show existence of robust t-IPP codes for all tleq q-1 and some positive proportion of such coordinates. We uncover a relation between the hash distance of codes and the IPP property and use it to find the exact proportion of mutant coordinates that permits identification of pirates with zero probability of error in the case of size-2 coalitions.

Original languageEnglish
Article number6311469
Pages (from-to)994-1003
Number of pages10
JournalIEEE Transactions on Information Theory
Issue number2
Publication statusPublished - 2013
Externally publishedYes


  • Fingerprinting
  • hash distance
  • separating codes
  • zero-error identification


Dive into the research topics of 'Robust parent-identifying codes and combinatorial arrays'. Together they form a unique fingerprint.

Cite this