Probabilistic Existence Results for Separable Codes

DOI10.1109/TIT.2015.2473848MaRDI QIDQ2977095zbMATH OpenOpenAlexFDO

Authors Simon R. Blackburn

Publication date 28 April 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1505.02597

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Burst-correcting codes (94B20)

Abstract: Separable codes were defined by Cheng and Miao in 2011, motivated by applications to the identification of pirates in a multimedia setting. Combinatorially, $overlinet$-separable codes lie somewhere between $t$-frameproof and $(t-1)$-frameproof codes: all $t$-frameproof codes are $overlinet$-separable, and all $overlinet$-separable codes are $(t-1)$-frameproof. Results for frameproof codes show that (when $q$ is large) there are $q$-ary $overlinet$-separable codes of length $n$ with approximately $q^{lceiln/tceil}$ codewords, and that no $q$-ary $overlinet$-separable codes of length $n$ can have more than approximately $q^{lceiln/(t-1)ceil}$ codewords. The paper provides improved probabilistic existence results for $overlinet$-separable codes when $tgeq3$. More precisely, for all $tgeq3$ and all $ngeq3$, there exists a constant $kappa$ (depending only on $t$ and $n$) such that there exists a $q$-ary $overlinet$-separable code of length $n$ with at least $kappa{q}^{n/(t-1)}$ codewords for all sufficiently large integers $q$. This shows, in particular, that the upper bound (derived from the bound on $(t-1)$-frameproof codes) on the number of codewords in a $overlinet$-separable code is realistic. The results above are more surprising after examining the situation when $t=2$. Results due to Gao and Ge show that a $q$-ary $overline2$-separable code of length $n$ can contain at most $frac32q^{2lceiln/3ceil}-frac12q^{lceiln/3ceil}$ codewords, and that codes with at least $kappa{q}^{2n/3}$ codewords exist. So optimal $overline2$-separable codes behave neither like $2$-frameproof nor $1$-frameproof codes. Also, the Gao--Ge bound is strengthened to show that a $q$-ary $overline2$-separable code of length $n$ can have at most [ q^{lceil 2n/3 ceil}+ frac{1}{2}q^{lfloor n/3 floor}(q^{lfloor n/3 floor}-1) ] codewords.

Cited in

(13)

• Bounds on the rate of separating codes
• Separable collusion-secure multimedia codes
• A note on \(\overline{2} \)-separable codes and \(B_2\) codes
• Multimedia IPP codes with efficient tracing
• List decoding for a multiple access hyperchannel
• Bounds and constructions for \(\overline{3}\)-separable codes with length 3
• scientific article; zbMATH DE number 4127218 (Why is no real title available?)
• Asymptotically optimal \(\overline {2}\)-separable codes with length 4
• New Turán Exponents for Two Extremal Hypergraph Problems
• \(\overline{2}\)-separable codes with length 5
• Frameproof codes, separable codes and \(B_2\) codes: bounds and constructions
• On anti-collusion codes for averaging attack in multimedia fingerprinting
• Constructions of \(\bar{3}\)-separable codes with length 4

This page was built for publication: Probabilistic Existence Results for Separable Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2977095)