Combinatorial Design Solving Via A New Compression Technique

In combinatorial design theory,periodic complementary sequences(PCS)are widely used to construct various cyclic D-optimal matrices which attain the largest determinants.In particular,such a matrix can be constructed by using binary PCS whose alphabet only contains-1/(10)1.Typical binary PCS which have been widely studied include D-optimal sequences,generalized Legendre pairs and periodic Golay pairs.In this thesis,we study the problem of searching for PCS efficiently.To overcome the weakness of data redundancy and low efficiency in the existing methods,this paper presents a new compression method based on run encoding and converts the problem of searching for PCS into that of ordered partitioning of integers.After analyzing the constraints of PCS,the combinatorial information of the encoded ordered partitions for PCS is extracted.Moreover,the search space is further narrowed down by PSD(power spectral density)test to find various PCSs which satisfy specified requirements.Experimental results show that the above method can be applied to searching for various PCS with different lengths,showing a general applicability.In particular,when the size of the problem is fixed,the new method can search for all non-equivalent solutions while keeping high efficiency.Furthermore,one can avoid unnecessary testing for equivalent binary sequences and thus improve the searching efficiency to a considerable extent.