|
Problemy Peredachi Informatsii, 2007, Volume 43, Issue 3, Pages 39–53
(Mi ppi17)
|
|
|
|
This article is cited in 26 scientific papers (total in 26 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.
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
Linking options:
https://www.mathnet.ru/eng/ppi17 https://www.mathnet.ru/eng/ppi/v43/i3/p39
|
Statistics & downloads: |
Abstract page: | 623 | Full-text PDF : | 131 | References: | 55 | First page: | 6 |
|