On The Sizes Of 1-Deletion/Insertion-Correcting Codes With Lengths 3 And 4

Deletion/Insertion-correcting codes are applied to correct the errors due to the deletion or insertion of symbols during the codewords transmission process.We study two kinds of perfect s-deletion/insertion correcting codes over an alphabet of size v,whose lengths come from a positive integer set K,those where all the coordinates may be equal are called a T*(t,K,v)-code,those where the coordinates must be different are called a T(t,K,v)-code,where s=min{k-t:k?K}.When v are given,the number of codewords of a T*(t,K,v)-code(or a T(t,K,v)-code)is not a constant.If the number of codewords is maximum,then the codes are optimal,denoted by OT*(t,K,v)-code(or OT(t,K,v)-code).There are some researches about OT*(t,K,v)-codes and OT(t,K,v)-codes where K={k}.Specially,when t=2 and k=3 or 4,the spectrum of sizes for a T*(2,k,v)-code spec(2,k,v)is[DL(v,k),DU(v,k)]with several exceptions,where DL(v,k)=[v/k[2v/k-1]]and DU(v,k)=[v/k[2(v-1)/k-1]]+v.In this paper,we mainly study the spectrum of sizes for a T*(2,K,v)-code with K={3,4}.We obtain the main conclusion which spec(2,{3,4},v)=[DL(v,4),DU(v,3)]with the following exceptions spec(2,{3,4},4)=[4,8],spec(2,{3,4},6)=[6,16]\{7},spec(2,{3,4},9)=[15,36],and the following possible exceptions[63,133](?)spec(2,{3,4},19)C[62,133],[197,419](?)spec(2,{3,4},34)C[196,419].In addition,the existence of an OT(2,{4,5},v)-code for v? {30,45} is deter-mined by constructing the maximum directed balance incomplete block design,thus the existence of an OT(2,{4,5},v)-code for v?0(mod 15)is completely solved.We also determine the existence of an OT(2,{4,6},87)-code.