Laboratory of Structural Methods of Data Analysis in Predictive
Modeling Moscow Institute of Physics and Technology
Robust parent-identifying codes and combinatorial arrays
An n-word y = (y1, . . . , yn) over a finite alphabet of cardinality q is called a descendant of a set of t words x1, . . . , xt if every coordinate yi, i = 1, . . . , n is contained in the set {x1 i , . . . , xt i}. A code C = {x1, . . . , xM} 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 t q - 1. We introduce a robust version of IPP codes which allows errorfree 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 t 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.

Авторы: Kabatiansky Grigory , Barg, A

Дата: 16 ноября 2014

Статус: опубликована

Журнал: IEEE Transactions on Information Theory

Том: 58

Выпуск: 12

Год: 2012

Google scholar:

Направления исследований

Structural optimization