Generalized Howell Designs And Multiply Constant-weight Codes

Combinatorial designs on square arrays have been the subject of much attention.The common mutually orthogonal Latin squares,Room squares,Howell designs and Kirkman squares are all combinatorial designs on square arrays,and their existence problems are solved one after another.A generalized Howell design(GHD)is not only a class of doubly resolvable packing designs,but also a class of combinatorial designs on square arrays.At the same time,it generalizes the Howell design and the Kirkman square.So it has important theoretical significance.On the other hand,in order to improve the reliability of certain physically unclonable function(PUF)response,Cherif et al.proposed the concept of multiple constant weight codes(MCWCs).Multiple constant weight codes are a natural extension of constant weight codes.Abel et al.found that generalized Howell designs can be used to construct special generalized packing designs.Chee et al.used the generalized packing designs to construct multiply constant-weight codes.It can be seen that generalized Howell designs can be used to construct multiply constant-weight codes.However,there are relatively few research results on generalized Howell designs,and there are still many theoretical problems to be solved.In this dissertation,the equivalent relation between generalized Howell designs and a class of optimal multiply constant-weight codes is established.Then,the construction methods and the existence of generalized Howell designs and their new application in coding—constructing the optimal multiply constant-weight codes,are discussed.This dissertation is organized as follows.In Chapter 1,we give a brief introduction to the background of generalized Howell designs and multiply constant-weight codes,and give the main results of this disserta-tion.In Chapter 2,the basic definitions and relevant known results of generalized How-ell designs and multiply constant-weight codes are given,and the upper bounds of t-wo classes of multiply constant-weight codes are established.At last,the equivalence between generalized Howell designs and a class of optimal multiply constant-weight codes is established.In Chapter 3,we discuss construction methods of generalized Howell designs.We propose the concept of incomplete generalized Howell designs(IGHDs),and define the unified recursive tool—generalized Howell frames(GHFs),so unified recursive construction methods are established.Next,we generalize the classic method of the starter-adder,a series of GHDs and IGHDs with small orders are constructed as the input designs required in the recursive constructions.In Chapter 4,we consider the existence of generalized Howell designs(denoted by GHD(s,3n)’s).Using the construction methods in Chapter 3,we establish the spectrums of GHD(3n-3/2,3n)’s,GHD(3n-5/2,3n)’s and GHD(n+2,3n)’s.Furthermore,the existence of GHD(s,3n)’s in other cases is considered.In Chapter 5,we discuss the asymptotic existence of a class of generalized Howell frames(denoted by(1,λ;k)-GHFs of type(g/2,g)n)From the perspective of decompos-able designs,the generalized Howell frame is a(k,λ)-frame of type gn with a pair of orthogonal frame resolutions.We establish an asymptotic existence theorem for(k,λ)-frames of type gn with a pair of orthogonal frame resolutions via decompositions of edge-colored complete digraphs into prescribed edge-colored subgraphs.In Chapter 6,we consider using the known generalized Howell designs to construct multiply constant-weight codes.Firstly,according to the equivalence between GHD-s and optimal MCWCs in Chapter 2,we obtain a number of classes of new optimal MCWCs with total weight 5 and distance 8 and determine the maximum sizes of the corresponding MCWCs.Secondly,according to the asymptotic existence of general-ized Howell frames in Chapter 5,the asymptotic existences of some classes of GHDs and optimal MCWCs with total weight 5 and distance 8 are obtained by applying the basic frame construction.Finally,we generalize multiple constant weight codes and obtain several classes of two dimensional multiple constant-weight codes.In Chapter 7,we summarize the dissertation briefly and look forward to furthering research works.