## Abstract

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}, . . . ,x ^{t}} if yi, ∈ {x_{i}^{1}, . . . ,x _{i}^{t}} for all i = 1, . . . , 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)^{n/s(t)} < f_{t}(n,q) < c_{2}(t)q^{⌈n/s(t)⌉} where s(t) = ⌊(t/2 + 1)^{2}⌋ - 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).

Original language | English (US) |
---|---|

Pages (from-to) | 795-807 |

Number of pages | 13 |

Journal | Combinatorics Probability and Computing |

Volume | 13 |

Issue number | 6 |

DOIs | |

State | Published - Nov 2004 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Statistics and Probability
- Computational Theory and Mathematics
- Applied Mathematics