New bounds on 2¯-separable codes of length 2

Minquan Cheng*, Hung-Lin Fu, Jing Jiang, Yuan Hsun Lo, Ying Miao

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

12 Scopus citations


Let C be a code of length n over an alphabet of q letters. The descendant code (C0) of C0 ={c1,c2,..ct}⊆C is defined to be the set of words x =(x1,x2,..,xn) such that xi∈{ci 1,ci 2,..,ci t} for all i = 1,..,n. C is a t¯-separable code if for any two distinct C1 ,C2 ⊆C such that |C1|≤t, |C2|≤t, we always have desc(C1)≠desc(C2). The study of separable codes is motivated by questions about multimedia fingerprinting for protecting copyrighted multimedia data. Let M(t¯,n,q) be the maximal possible size of such a separable code. In this paper, we provide an improved upper bound for M(2¯,2,q) by a graph theoretical approach, and a new lower bound for M(2¯,2,q) by deleting suitable points and lines from a projective plane, which coincides with the improved upper bound in some places. This corresponds to the bounds of maximum size of bipartite graphs with girth 6 and a construction of such maximal bipartite graphs.

Original languageEnglish
Pages (from-to)31-40
Number of pages10
JournalDesigns, Codes, and Cryptography
Issue number1
StatePublished - 1 Jan 2013


  • 4-Cycle free bipartite graph
  • Multimedia fingerprinting
  • Projective plane
  • Separable code
  • Zarankiewicz number

Fingerprint Dive into the research topics of 'New bounds on 2¯-separable codes of length 2'. Together they form a unique fingerprint.

Cite this