Some Constructions Of Difference Systems Of Sets

Difference System of Sets (DSS) are combinatorial problems that arise in connection with code synchronization. One method that solves code synchronization is constructing comma-free codes, that is constructing a code C∈Fpu such that the overlap of any two codewords, which can be the same one, is not a codeword of code C, where F^is a set of all vectors of length u over a set Fp={0,1,...,p-1}. When considering the problems of synchronization and error correction together, we need comma-free codes with prescribed comma-free index. In1971, V.I.Levenshtein introduced difference system of sets, which can be used to construct codes with prescribed comma-free index. A DSS with parameters (u,{T0,T1,..., Tp-1},p, p) is a collection of p disjoint subsets Bi of any abelian group G of order u,|Bi|=Ti,0≤i≤p-1, such that the multiset {a-b:a∈Bi,b∈Bj,0≤i≠j<p-1} contains every non-identity element of G, at least p times. In this application of DSSs to codes for synchronization, we requires that the redundancy is as small as possible. A DSS is called optimal if it has minimum redundancy for the given parameters.Construction problems is one of the fundamental problems of the theory of combina-torial designs. So the construction problems of DSSs are concerned much more by scholars at home and abroad. In this paper, we construct DSSs using three algebra structures.In the first part, we construct DSSs by vector space Fq(2t), where q is a prime power and t is a positive integer. By applying properties of vector space, we obtain a series of recursive constructions of DSSs over Zu{u=q2t-1) and some infinite families of optimal DSSs.In the second part, by dividing some of cosets of Zv relative to a subgroup of order k, we obtain a construction of DSSs over Zv and some infinite families of optimal DSSs, where v=km is a composite number, k and m are positive integers.In the third part, for a special association scheme χ=(Zv,{Ri}0≤i≤v-1), where Ri={(x,y)|x-y=i (mod v),x,y∈Zv}, i∈Zv, by applying properties of association scheme and difference set, we get a construction of DSSs over Zv×Zv.