A class of I.P.P. codes with efficient identification
2004; Elsevier BV; Volume: 20; Issue: 2-3 Linguagem: Inglês
10.1016/j.jco.2003.08.012
ISSN1090-2708
AutoresAlexander Barg, Gregory Kabatiansky,
Tópico(s)DNA and Biological Computing
ResumoLet 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 x1,…,xt if yi∈{xi1,…,xit} 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).
Referência(s)