Asymptotic Overview on Separating Codes

Gérard D. Cohen, Hans Georg Schaathun

Reports in Informatics No. 248, May 2003, Department of Informatics, University of Bergen, Norway.

Abstract

Separating codes (or systems) are known from combinatorics, and they enjoy increasing attention due to applications in digital fingerprinting. Previous applications are found in automata theory and the construction of fault-tolerant systems. Let $\Gamma$ be a code of length $n$, and $(T,U)$ a pair of disjoint subsets of $\Gamma$. We say that $(T,U)$ is separated if there exists a coordinate $i$, such that for any codeword $(c_1,\ldots,c_n)\in T$ and any codeword $(c'_1,\ldots,c'_n)\in U$, $c_i\neq c'_i$. The code $\Gamma$ is $(t,u)$-separating if all pairs $(T,U)$ with $\#T=t$ and $\#U=u$ are separated. In this report, we give an overview of existing techniques for bounding the asymptotical rate of separating codes, including some constructions and construction techniques. We provide numerical results for binary $(t,u)$-separating codes for some small values of $t$ and $u$. The report includes both old and new results.

Keywords

separating system, intersecting code

Download

Synthèse asymptotique sur les codes séparants

Gérard D. Cohen, Hans Georg Schaathun

Résumé

Les codes, ou systèmes, séparants sont connus en Combinatoire; ils ont été utilisés, sous des vocables divers, dans des problèmes de tatouage numérique. Les premières utilisations de ce concept remontent à la théorie des automates et aux systèmes tolérant les fautes. Soit $\Gamma$ un code de longeur $n$, et $(T,U)$ un couple de sous-ensembles disjoints de $\Gamma$. On dit que $(T,U)$ est séparé s'il existe une position $i$ telle que pour tout mot $(c_1,\ldots,c_n)\in T$ et tout mot $(c'_1,\ldots,c'_n)\in U$, $c_i\neq c_i'$. Le code $\Gamma$ est dit $(t,u)$-séparant si tout tel couple où $\#T=t$ et $\#U=u$ est séparé. Nous présentons de nouvelles et d'anciennes bornes, des généralisations et des constructions de codes séparants. Nous fournissons des résultats numériques pour les petites valeurs de $t$ et $u$.

Mots-clefs

système séparant, code intersectant

Download

Asymptotisk oversyn over skiljande kodar

Gérard D. Cohen, Hans Georg Schaathun

Samandrag

Me kjenner skiljande kodar frå kombinatorikken. I dei siste åra har dei dukka opp i samband med digital fingerprenting. Andre bruksområde er i autamatateori og konstruksjon av feil-tolerante system. Lat $\Gamma$ vera ein kode med lengd $n$, og lat $(T,U)$ vera eit par av disjunkte delmengder av $\Gamma$. Me seier at $(T,U)$ er skilt dersom det er ein plass $i$ slik at for alle ord $(c_1,\ldots,c_n)\in T$ og alle ord $(c'_1,\ldots,c'_n)\in U$, har me $c_i\neq c_i'$. Koden $\Gamma$ er skiljande om alle slike par med $\#T=t$ og $\#U=u$ er skilde. Rapporten gjev eit oversyn over kjende teknikkar for å finna skrankar for den asymptotiske raten til skiljande kodar. Me får og med eit par eksplisitte konstruksjonar, og me gjev numeriske resultat for binære $(t,u)$-skiljande kodar for somme små verdiar av $t$ og $u$. Rapporten omfattar både nye og gamle resultat.

Stikkord

skiljande system, snittande kode

Download


Back