Constructions of Binary Constant-Weight Quasi-Cyclic Codes and Quasi-Cyclically Permutable Codes

Abstract

A theorem is proven showing how to obtain a constant-weight binary quasi-cyclic code from a p^r-ary linear cyclic code, where p is a prime and r is a positive integer, r ≥ 1, by using a representation of the elements of a Galois field, GF(p^r ), as cyclic shifts of a binary p^r -tuple. From this theorem, constructions are derived for two classes of constant-weight binary quasi-cyclic codes. These two classes are shown to achieve the Johnson upper bound on the number of codewords asymptot- ically for long blocklengths. A quasi-cyclically permutable (QCP) code is a binary code such that the codewords are quasi-cyclically distinct and have cyclic order equal to the code blocklength. A technique is described for selecting virtually the maximum number of cyclically distinct codewords of full cyclic order from Reed-Solomon (RS) codes and from Berlekamp-Justesen (BJ) codes, both known to be maximum distance separable codes. Those cyclically distinct codewords of full cyclic order from RS codes and from BJ codes are mapped to binary to produce two classes of asymptotically optimum constant-weight quasi- cyclic codes and two classes of asymptotically optimum constant- weight QCP codes. An application of QCP codes is introduced to construct protocol-sequence sets for the M-active-out-of-T users collision channel without feedback, allowing more users than strict cyclically permutable codes with the same blocklength and minimum distance.