Linear Size Constant-Composition Codes Meeting the Johnson Bound

Abstract

The Johnson-type upper bound on the maximum size of a code of length $n$, distance $d=2w-1$ and constant composition $\overline{w}$ is $\lfloor \frac{n}{w_1}\rfloor$, where $w$ is the total weight and $w_1$ is the largest component of $\overline{w}$. Recently, Chee et al. proved that this upper bound can be achieved for all constant-composition codes of sufficiently large lengths. Let $N_{ccc}(\overline{w})$ be the smallest such length. The determination of $N_{ccc}(\overline{w})$ is trivial for binary codes. This paper provides a lower bound on $N_{ccc}(\overline{w})$, which is shown to be tight for all ternary and quaternary codes by giving new combinatorial constructions. Consequently, by refining method, we determine the values of $N_{ccc}(\overline{w})$ for all $q$-ary constant-composition codes provided that $3w_1\ge w$ with finite possible exceptions.

11 pages

References in corpus (2)

• Group Divisible Codes and Their Application in the Construction of Optimal Constant-Composition Codes of Weight Three
• Decompositions of Edge-Colored Digraphs: A New Technique in the Construction of Constant-Weight Codes and Related Families