Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-12T22:39:22.254Z Has data issue: false hasContentIssue false

New Bounds on Parent-Identifying Codes: The Case of Multiple Parents

Published online by Cambridge University Press:  03 November 2004

NOGA ALON
Affiliation:
Schools of Mathematics and Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: noga@math.tau.ac.il)
URI STAV
Affiliation:
School of Computer Science, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: suri@tau.ac.il)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $C$ be a code of length $n$ over an alphabet of $q$ letters. A codeword $y$ is called a descendant of a set of $t$ codewords $\{x^1,\dots,x^t\}$ if $y_i \in \{x^1_i,\dots,x^t_i\}$ for all $i=1,\dots,n$. A code is said to have the Identifiable Parent Property of order $t$ if, for any word of length $n$ that is a descendant of at most $t$ codewords (parents), it is possible to identify at least one of them. Let $f_t(n,q)$ be the maximum possible cardinality of such a code. We prove that for any $t,n,q$, $(c_1(t)q)^{\frac{n}{s(t)}} < f_t(n,q) < c_2(t)q^{\lceil{\frac{n}{s(t)}}\rceil}$ where $s(t) = \lfloor(\frac{t}{2}+1)^2 \rfloor -1$ and $c_1(t),c_2(t)$ are some functions of $t$. We also show some bounds and constructions for $f_3(5,q)$, $f_3(6,q)$, and $f_t(n,q)$ when $n < s(t)$.

Information

Type
Paper
Copyright
2004 Cambridge University Press