Robust parent-identifying codes and combinatorial arrays

Alexander Barg, Grigory Kabatiansky

Результат исследований: Вклад в журналСтатьярецензирование

6 Цитирования (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.

Язык оригиналаАнглийский
Номер статьи6311469
Страницы (с-по)994-1003
Число страниц10
ЖурналIEEE Transactions on Information Theory
Том59
Номер выпуска2
DOI
СостояниеОпубликовано - 2013
Опубликовано для внешнего пользованияДа

Fingerprint

Подробные сведения о темах исследования «Robust parent-identifying codes and combinatorial arrays». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать