Problemy Peredachi Informatsii
General information
Latest issue
Impact factor
Guidelines for authors

Search papers
Search references

Latest issue
Current issues
Archive issues
What is RSS

Probl. Peredachi Inf.:

Personal entry:
Save password
Forgotten password?

Probl. Peredachi Inf., 2007, Volume 43, Issue 3, Pages 39–53 (Mi ppi17)  

This article is cited in 13 scientific papers (total in 13 papers)

Coding Theory

Conflict-Avoiding Codes and Cyclic Triple Systems

V. I. Levenshtein

Abstract: The paper deals with the problem of constructing a code of the maximum possible cardinality consisting of binary vectors of length $n$ and Hamming weight 3 and having the following property: any $3\times n$ matrix whose rows are cyclic shifts of three different code vectors contains a $3\times3$ permutation matrix as a submatrix. This property (in the special case $w=3$) characterizes conflict-avoiding codes of length $n$ for $w$ active users, introduced in [1]. Using such codes in channels with asynchronous multiple access allows each of $w$ active users to transmit a data packet successfully in one of $w$ attempts during n time slots without collisions with other active users. An upper bound on the maximum cardinality of a conflict-avoiding code of length $n$ with $w=3$ is proved, and constructions of optimal codes achieving this bound are given. In particular, there are found conflict-avoiding codes for $w=3$ which have much more vectors than codes of the same length obtained from cyclic Steiner triple systems by choosing a representative in each cyclic class.

Full text: PDF file (1735 kB)
References: PDF file   HTML file

English version:
Problems of Information Transmission, 2007, 43:3, 199–212

Bibliographic databases:

UDC: 621.391.5
Received: 20.02.2007

Citation: V. I. Levenshtein, “Conflict-Avoiding Codes and Cyclic Triple Systems”, Probl. Peredachi Inf., 43:3 (2007), 39–53; Problems Inform. Transmission, 43:3 (2007), 199–212

Citation in format AMSBIB
\by V.~I.~Levenshtein
\paper Conflict-Avoiding Codes and Cyclic Triple Systems
\jour Probl. Peredachi Inf.
\yr 2007
\vol 43
\issue 3
\pages 39--53
\jour Problems Inform. Transmission
\yr 2007
\vol 43
\issue 3
\pages 199--212

Linking options:

    SHARE: FaceBook Twitter Livejournal

    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. Mishima Miwako, Fu Hung-Lin, Uruno Shoichi, “Optimal conflict-avoiding codes of length $n\equiv 0$ (mod 16) and weight 3”, Des. Codes Cryptogr., 52:3 (2009), 275–291  crossref  mathscinet  zmath  isi
    2. Shum K.W., Wong W.Sh., “A tight asymptotic bound on the size of constant-weight conflict-avoiding codes”, Des. Codes Cryptogr., 57:1 (2010), 1–14  crossref  mathscinet  isi
    3. Shum K.W., Wong W.Sh., Chen Ch.Sh., “A general upper bound on the size of constant-weight conflict-avoiding codes”, IEEE Trans. Inform. Theory, 56:7 (2010), 3265–3276  crossref  mathscinet  isi
    4. Zhang Y., Shum K.W., Wong W.Sh., “Completely irrepressible sequences for the asynchronous collision channel without feedback”, IEEE Transactions on Vehicular Technology, 60:4 (2011), 1859–1866  crossref  isi
    5. Zhang Y., Shum K.W., Wong W.Sh., “Strongly conflict-avoiding codes”, SIAM J. Discrete Math., 25:3 (2011), 1035–1053  crossref  mathscinet  zmath  isi
    6. Ma W. Zhao Ch.-e. Shen D., “New Optimal Constructions of Conflict-Avoiding Codes of Odd Length and Weight 3”, Des. Codes Cryptogr., 73:3 (2014), 791–804  crossref  mathscinet  zmath  isi
    7. Fu H.-L., Lo Yu.-H., Shum K.W., “Optimal Conflict-Avoiding Codes of Odd Length and Weight Three”, Des. Codes Cryptogr., 72:2 (2014), 289–309  crossref  mathscinet  zmath  isi
    8. Lin Y. Mishima M. Satoh J. Jimbo M., “Optimal Equi-Difference Conflict-Avoiding Codes of Odd Length and Weight Three”, Finite Fields their Appl., 26 (2014), 49–68  crossref  mathscinet  zmath  isi
    9. Yu Zh., Wang J., “Strongly Conflict-Avoiding Codes With Weight Three”, Wirel. Pers. Commun., 84:1 (2015), 153–165  crossref  isi
    10. Lo Yu.-H., Fu H.-L., Lin Y.-H., “Weighted Maximum Matchings and Optimal Equi-Difference Conflict-Avoiding Codes”, Des. Codes Cryptogr., 76:2 (2015), 361–372  crossref  mathscinet  zmath  isi
    11. T. Baicheva, S. Topalova, “Optimal conflict-avoiding codes for $3$, $4$ and $5$ active users”, Problems Inform. Transmission, 53:1 (2017), 42–50  mathnet  crossref  isi  elib
    12. Baicheva Ts. Topalova S., “On Tight Optimal Conflict-Avoiding Codes For 3, 4, 5 and 6 Active Users”, Cybern. Inf. Technol., 18:5, SI (2018), 5–11  crossref  mathscinet  isi  scopus
    13. Feng T., Wang L., Wang X., “Optimal 2-D (Nxm,3,2,1)-Optical Orthogonal Codes and Related Equi-Difference Conflict Avoiding Codes”, Designs Codes Cryptogr., 87:7 (2019), 1499–1520  crossref  mathscinet  zmath  isi  scopus
  • Проблемы передачи информации Problems of Information Transmission
    Number of views:
    This page:460
    Full text:111
    First page:6

    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021