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