×

zbMATH — the first resource for mathematics

Some new results on superimposed codes. (English) Zbl 1169.94350
Summary: A \((w,r)\) cover-free family is a family of subsets of a finite set such that no intersection of \(w\) members of the family is covered by a union of \(r\) others. A \((w,r)\) superimposed code is the incidence matrix of such a family. Such a family also arises in cryptography as the concept of key distribution pattern. In the present paper, we give some new results on superimposed codes. First we construct superimposed codes from super-simple designs which give us results better than superimposed codes constructed by other known methods. Next we prove the uniqueness of the (1,2) superimposed code of size \(9 \times 12\), the (2,2) superimposed code of size \(14 \times 8\), and the (2,3) superimposed code of size \(30 \times 10\). Finally, we improve numerical values of upper bounds for the asymptotic rate of some (\(w,r\)) superimposed codes.

MSC:
94B25 Combinatorial codes
05B05 Combinatorial aspects of block designs
PDF BibTeX Cite
Full Text: DOI
References:
[1] and CRC handbook of combinatorial designs, CRC Press, Inc., Boca Raton, Florida, 1996. · Zbl 0836.00010
[2] D’yachkov, J Combin Theory Ser A 99 pp 195– (2002)
[3] D’yachkov, IEEE Trans Inform Theory 46 pp 284– (2000)
[4] and New results in the theory of superimposed codes, Proc of the seventh international workshop on algebraic and combinatorial coding theory, 2000, pp. 126-136.
[5] D’yachkov, Problemy Peredachi Informatsii 17 pp 7– (1982)
[6] and Upper bounds on the rate of superimposed (s,l)-codes based on Engel’s inequality, Proc of the eighth international workshop on algebraic and combinatorial coding theory, 2002, pp. 95-99.
[7] Engel, Combin Prob Comput 5 pp 373– (1996) · Zbl 0868.05036
[8] Erdos, Israel J Math 51 pp 75– (1985)
[9] Gronau, J Combin Math Combin Comput 11 pp 113– (1992)
[10] Kim, J Combin Designs 12 pp 79– (2004)
[11] and On optimality of trivial (w,r) cover-free codes, accepted in Problems of Information Transmission.
[12] Some tables for (w,r) superimposed codes, Proc. of the eighth international workshop on algebraic and combinatorial coding theory, 2002, pp. 185-189.
[13] Lebedev, Problems of Information Transmission 39 pp 75– (2003)
[14] and The theory of error-correcting codes, North-Holland, Amsterdam, 1983.
[15] Mitchell, Discrete Appl Math 21 pp 215– (1988)
[16] Semakov, Problemy Peredachi Informatsii 5 pp 28– (1969)
[17] Stinson, Codes and Cryptography 12 pp 215– (1997)
[18] Stinson, J Combin Designs 8 pp 189– (2000)
[19] Stinson, J Combin Theory Ser A 90 pp 224– (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.