DIMACS TR: 2002-36

A class of i.p.p. codes with efficient identification

Authors: Alexander Barg and Gregory Kabatiansky


Let C be a code of length n over a q-ary alphabet. An n-word y is called a descendant of a set of t codewords x^1,...,x^t if y_i \in {x^1_i,...,x^t_i} for all i=1,...,n. A code is said to have the t-identifying parent property (t-i.p.p.) if for any n-word y that is a descendant of at most t parents it is possible to identify at least one of them.

An explicit construction is presented of t-i.p.p. codes of rate bounded away from zero, for which identification can be accomplished with complexity poly(n).

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-36.ps.gz

DIMACS Home Page