Problemy Peredachi Informatsii
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Guidelines for authors Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Probl. Peredachi Inf.: Year: Volume: Issue: Page: Find

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

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

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
\Bibitem{Lev07} \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 \mathnet{http://mi.mathnet.ru/ppi17} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=2360016} \zmath{https://zbmath.org/?q=an:1136.94328} \transl \jour Problems Inform. Transmission \yr 2007 \vol 43 \issue 3 \pages 199--212 \crossref{https://doi.org/10.1134/S0032946007030039} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000255782800003} \scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-35948969770} 

• http://mi.mathnet.ru/eng/ppi17
• http://mi.mathnet.ru/eng/ppi/v43/i3/p39

 SHARE:

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
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
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
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
5. Zhang Y., Shum K.W., Wong W.Sh., “Strongly conflict-avoiding codes”, SIAM J. Discrete Math., 25:3 (2011), 1035–1053
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
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
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
9. Yu Zh., Wang J., “Strongly Conflict-Avoiding Codes With Weight Three”, Wirel. Pers. Commun., 84:1 (2015), 153–165
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
11. T. Baicheva, S. Topalova, “Optimal conflict-avoiding codes for $3$, $4$ and $5$ active users”, Problems Inform. Transmission, 53:1 (2017), 42–50
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
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
•  Number of views: This page: 460 Full text: 111 References: 42 First page: 6