Constant Weight Conflict-Avoiding Codes
Koji Momihara, Meinard Müller, Junya Satoh, Masakazu Jimbo · SIAM Journal on Discrete Mathematics · 2007
A conflict-avoiding code (CAC) C of length n with weight k is a family of binary sequences of length n and weight k satisfying $\sum_{0\le t\le n-1}x_{it}x_{j,t+s}\le \lambda$ for any distinct codewords $x_i=(x_{i0},x_{i1},\ldots,x_{i,n-1})$ and $x_j=(x_{j0},x_{j1},\ldots,x_{j,n-1})$ in C and for any integer s, where the subscripts are taken modulo n. A CAC with maximum code size for given n and k is said to be optimal. A CAC has been studied for sending messages correctly through a multiple-access channel. The use of an optimal CAC enables the largest possible number of potential users to transmit information efficiently and reliably. In this paper, the case $\lambda=1$ is treated, and various direct and recursive constructions of optimal CACs for weight $k=4$ and 5 are obtained by providing constructions of CACs for general weight k. In particular, the maximum code size of CACs satisfying certain sufficient conditions is determined through number theoretical and combinatorial approaches.