Constructions Of Optimal Difference Systems Of Sets

Comma-free codes, first introduced by S.W. Golomb, B. Gordon and L.R. Welch in theirpaper"Comma-free Codes", are designed to solve the code synchronization. When the prob-lems of synchronization and error correction are considered together, comma-free codes withprescribed comma-free index are naturally need. In 1971, V.I. Levenshtein introduced a com-binatorial structure, called difference system of sets (DSS), which can be used to constructcodes with prescribed comma-free index. In this application of DSSs to code synchroniza-tion, the redundancy is required to be as small as possible. A DSS is optimal if it has mini-mum redundancy for the given parameters. In this paper, we concentrate on the constructionsof DSSs. By studying its related combinatorial structures, we obtain a series of recursiveconstructions of DSSs and some infinite families of optimal DSSs.The paper is described as below.In Chapter 1, we introduce the background, and describe the concept of difference sys-tems of sets and the relation of difference systems of sets and comma-free codes. We alsosummarize others'works on DSSs and list our main results.In Chapter 2, we use the combinatorial structure called a partition-type difference pack-ing (PCDP), give a series of constructions of DSSs. Especially, we apply cyclic almost differ-ence sets and cyclic Hadamard difference sets to our constructions, and obtain some infinitefamilies of optimal DSSs, this is a new application of cyclic almost difference sets and cyclicHadamard difference sets to code synchronization.In Chapter 3, we study the relation of DSSs and a combinatorial structure called apartition-type difference packing with a hole, get some direct and recursive constructionsof DSSs. By applying the known results, some infinite families of optimal DSSs are obtained.In Chapter 4, we generalize the construction of DSSs from hyperplane partition, furtherstudy the properties of the t-?ats in projective geometry PG(2t + 1,q), obtain a series ofrecursive constructions of DSSs and some infinite families of optimal DSSs.In Chapter 5, we study a type of cyclic difference sets, deduce some recursive construc-tions of DSSs and some infinite families of optimal DSSs. We also use the cyclic (v,k, 1)- difference set, obtain a direct construction of optimal DSSs.In Chapter 6, we list some further problem.In Chapter 7, we list the main results of optimal DSSs in this paper.