Improved Gilbert-Varshamov Bounds For Hopping Cyclic Codes And Optical Orthogonal Codes

This thesis considers the improvement of Gilbert-Varshamov bound in coding theory.We use some powerful mathematical tools such as graph theory and probabilistic methods to study the improved GV-type bound for hopping cyclic codes and optical orthogonal codes.In Chapter 1,we first introduce error-correcting codes using examples of information transmission.Actually,we usually convert information into vectors for transmission through the channel.Due to the inevitable noise interference in the channel,the receiver may receive incorrect information.Therefore,we hope to detect and correct errors.This means that there must be a certain difference between the vectors transmitted in the channel.For a fixed number of errors,the greater the difference between the vectors,the easier it is to correct errors after vectors have received.In discrete channels,the difference between vectors is represented by the Hamming distance,and the greater the minimum Hamming distance between the vectors,the stronger the error-correcting capability of this group of vectors.Therefore,we hope that the transmitted group of vectors has a positive minimum Hamming distance.The process of converting the transmitted messages into vectors according to certain rules and making this group of vectors have a positive minimum Hamming distance is called Encoding.Vectors are also called codewords,forming a code with a positive minimum Hamming distance.At the same time,considering transmission efficiency and cost,we expect that there is an encoding method that allows the resulting code with a relatively large minimum Hamming distance to contain more codewords.There is a problem in coding theory,that is,given the code length,the size of alphabet and the minimum Hamming distance,what is the maximum size of the code.The GV bound is the classical lower bound for this problem.Currently,the optimal GV-type bound for general codes improves a linear factor of the code length compared to the classical GV bound.This improvement is also applicable to constant-weight codes,but it is not yet known whether non-linear cyclic codes and non-linear constant-weight cyclic codes can reach the improved GV bound.Hopping cyclic codes,a cyclic codes where each codeword and its cyclic shifts are distinct,are a special class of nonlinear cyclic codes.Optical orthogonal codes are some codewords in binary constant-weight cyclic codes.Given an optical orthogonal code,we can get the corresponding binary constant-weight cyclic code.Hopping cyclic codes and optical orthogonal codes have various practical applications and have been widely studied for many years.However,there is still a gap between the upper and lower bounds of the maximum size of codes,especially when the minimum distance is a linear factor of the code length.In this paper,we provide improved GV-type bounds for these two codes.In Chapters 2 and 3,we present the mathematical tools needed in this thesis.In Chapter 2,we introduce the independence number of graphs and show the current optimal result for the lower bound of independence number of locally sparse graphs.In the proof of the main results,we will establish auxiliary graphs,so that their independent sets have a one-to-one correspondence with the target codes,namely,hopping cyclic codes and optical orthogonal codes.Therefore,the lower bound of the maximum size of hopping cyclic codes and optical orthogonal codes can be given by the lower bound of the independent number of auxiliary graphs.In Chapter 3.we present the definition and properties of conditional expectation and introduce Doob martingales.We prove the McDiarmid inequality by applying conditional expectation and Doob martingales.The McDiarmid inequality is a powerful tool to bound the deviation between the sampled value and the expected value of certain functions when they are evaluated on independent random variables.Because the cyclic shifts of any codeword in a hopping cyclic code are distinct,however,not all vectors have this property.Therefore,when constructing auxiliary graphs,vectors that do not meet this property must be deleted.We will use the McDiarmid inequality to prove that almost all q-ary vectors with length n possess this property,and hence the vertex set of auxiliary graph contains enough vertices.In Chapter 4 and Chapter 5,the GV-type bounds of hopping cyclic codes and optical orthogonal codes were improved respectively.In Chapter 4.the GV-type bound of hopping cyclic codes is improved by a linear factor of code length.And hence there exists a nonlinear cyclic code that can achieve the improved GV bound.This conclusion can also be applied to improve the GV-type bound of frequency hopping sequence sets and errorcorrecling weakly mutually uncorrelated codes.In Chapter 5.an improvement of GV-type hound for optical orthogonal codes is given,and the result improves a linear factor of code length compared to the classical GV bound.Note that this proof can also be applied to general situation.In Chapter 6.we have summarized the article and listed the innovations and problems.