Studies On Some Topics Of Theory Of Codes

The theory of codes has developed into several independent branches,such as the information theory,the theory of error-correcting codes,the theory of variable-length codes.In this thesis,we focus on the theory of variable-length codes,mainly study the properties and structure of solid codes,maximal infix codes,(k,m)-comma codes and n-(k,1)-comma codes,where k?0,m?1,n=1,2.There are six chapters.In Chapter 1,we introduce the background and its recent development,and give some basic notions and related resultsIn Chapter 2 and 3,we discuss combinatorial properties of solid codes and maximal solid codes.In Chapter 2,we first give some characterizations of solid codes by means of infix codes and unbordered words;and then,discuss the decomposition of solid codes and maximal solid codes;finally,investigate several properties of the products of solid codes and some other kinds of codes,and obtain two sufficient and necessary conditions under which the product of two solid codes on the same alphabet becomes a solid codes.In Chapter 3,we present a series of characterizations of maximal infix codes by using so-called shuffle complete;explore the relations between maximal infix codes and maximal solid codes,and the operations on maximal infix codes.The composition and decomposition of codes is one of the important methods to study the structure of codes.In Chapter 4,we first study the composition and decomposition of(k,1)-comma code;and then,we characterize the(k,1)-comma codes,the solid codes with a minimum length greater than k,the(k,m)-comma codes(m?2)which are infix codes from different perspectives;next,discuss the closure properties of(k,m)-comma codes under concatenation;finally,the class of bifix codes is classified by means of the(k,m)-comma codes,on the base of this result,we prove the decidability of(k,m)-comma codes properties for regular bifix codes.In Chapter 5,we first characterize the 2-(k,1)-comma codes(k?0)by using infix codes and unbordered words;next,partially describe the family of 1-(k,1)-comma codes(k?2);finally,based on B.Cui,L.Kari and S.Seki's description of 1-(1,1)-comma codes(k?2),we show it is decidable whether a regular language is an 1-(1,1)-comma code.In Chapter 6,we investigate the completion of regular(k,1)-comma codes,show that a regular(k,1)-comma codes can be embedded into a maximal regular(k,1)-comma codes by using constructing method,where k?1.As a by-product,a test of maximality for regular(1,1)-comma codes which is effective is obtained.