A class of I.P.P. codes with efficient identification

Alexander Barg, Gregory Kabatiansky

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)

Abstract

Let 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 ∈ {xi l, ...,xi t} 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).

Original languageEnglish
Pages (from-to)137-147
Number of pages11
JournalJournal of Complexity
Volume20
Issue number2-3
DOIs
Publication statusPublished - 2004
Externally publishedYes

Keywords

  • Code concatenation
  • Digital finger printing
  • Identifiable parent property
  • List decoding
  • Traceability

Fingerprint

Dive into the research topics of 'A class of I.P.P. codes with efficient identification'. Together they form a unique fingerprint.

Cite this