Robust parent-identifying codes and combinatorial arrays

Alexander Barg, Grigory Kabatiansky

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

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
Volume59
Issue number2
DOIs
Publication statusPublished - 2013
Externally publishedYes

Keywords

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

Fingerprint

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

Cite this