(2006-2008) Constant-Weight and Constant-Composition Codes

I started working on constant-weight and constant-composition codes in 2006, as a Master student.

An (error-correcting) code of length n is simply a set of vectors of length n, called codewords, whose coordinates belong to F_q, the finite field of q elements. A code is said to have distance d if for every pair of codewords, the number of coordinates where they differ is at least d. A code is said to have constant weight w if every codeword has exactly w nonzero coordinates. A code is said to be a constant composition code if each symbol α in F_q appears in every codeword the same number of times. Constant-weight codes and constant-composition codes have applications in numerous areas such as in construction of frequency hopping lists in GSM networks, in design of VLSI chips, and design of oligonucleotide sequences for DNA computing.

My project aimed at establishing new constructions of optimal nonbinary constant-weight and constant-composition codes. Specifically, given the length, the weight (or the composition), and the distance, our goal was to design codes of smallest size (i.e., smallest number of codewords). Employing several tools from combinatorial design theory (Golomb rulers, Difference Triangle Sets), we provided constructions of optimal constant-weight and constant-composition codes when d = 2w – 1 for all sufficiently large lengths. In particular, we completely settled an open problem raised by Tuvi Etzion (1997) in design theory. Our work was summarized in the following paper:

[1] Y. M. Chee, S. H. Dau, A. C. H. Ling, and S. Ling, "Linear size optimal q-ary constant-weight codes and constant-composition codes," IEEE Transactions on Information Theory, 56 (1), pp. 140-151, 2010.

Apart from the above constructions, we also obtained a novel construction of optimal codes of weight 4, distance 3, based on special sequences. This result was presented in the following paper:

[2] Y. M. Chee, S. H. Dau, A. C. H. Ling, and S. Ling, "The sizes of optimal q-ary codes of weight three and distance four: a complete solution," IEEE Transactions on Information Theory, 54 (3), pp. 1291-1295, 2008.