Algebraic Coding: Optimal Constructions & Applications

One of the main themes in coding theory is to construct codes with good parame-ters.In this thesis,we study some optimal constructions of algebraic codes and some applications of coding theory in quantum coding and distributed storage systems.As a generalization of cyclic codes,constacyclic codes are an important class of codes due to their nice algebraic structures and various applications in engineering.In[1],Ding and Ling presented a q-polynomial approach to the study of cyclic codes.In Chapter 2,we generalize their results to constacyclic codes.Specifically,we establish the fundamental theory of the q-polynomial approach to constacyclic codes and con-struct some new families of optimal and almost optimal constacyclic codes.The parameters of a maximum distance separable(MDS)Euclidean self-dual code are completely determined by its length.In Chapter 3,we study the problem for which lengths a q-ary MDS Euclidean self-dual code exists.For q is even,this problem is completely solved by Grassl and Gulliver[2].For q is odd,some q-ary MDS Euclidean self-dual codes were obtained in the literature.By using generalized Reed-Solomon(GRS for short)codes and extended GRS codes,we construct six new classes of q-ary MDS Euclidean self-dual codes.Determining all deep holes of a linear code is very important to its decoding.The deep holes of Reed-Solomon codes have been studied extensively in recent years.Gabidulin codes can be seen as the q-analog to Reed-Solomon codes,which have some applications in network coding.In Chapter 4,we study the deep holes of Gabidulin codes with both rank and Hamming metrics.Specifically,we provide a tight lower bound for the distance of any word to a Gabidulin code and a sufficient and neces-sary condition for achieving this lower bound as well.Then,a class of deep holes of a Gabidulin code is discovered.Moreover,we obtain some other deep holes for certain Gabidulin codes.Quantum error-correcting codes play an important role in quantum computation and quantum communication.A quantum code achieving the quantum Singleton bound is called an quantum MDS code.In Chapter 5,by using some additive subgroups of F_q2and multiplicative subgroups of F^*_q2,we construct some Hermitian self-orthogonal GRS codes and extended GRS codes.And then several classes of q-ary quantum MDS codes are obtained by the well-known Hermitian construction.The minimum distance of our quantum MDS codes can be larger than or equal to q/2+1.Furthermore,our constructions generalize and improve some known results.In Chapter 6,we construct several classes of MDS codes via GRS codes and ex-tended GRS codes,which we can determine the dimensions of their Euclidean hulls or Hermitian hulls.It turns out that the dimensions of Euclidean hulls or Hermitian hulls of these codes can take all or almost all possible values.As a consequence,we can apply our results to entanglement-assisted quantum error-correcting codes(EAQECCs)and obtain several families of MDS EAQECCs with flexible parameters.The required number of maximally entangled states of these MDS EAQECCs can take all or almost all possible values.In particular,several new classes of q-ary MDS EAQECCs of length n>q are obtained.In a distributed storage system,locally repairable codes with locality r(r-LRCs)were introduced by Gopalan et al.[3]to recover one failed node from at most other r available nodes.And then(r,?)locally repairable codes((r,?)-LRCs)were produced by Prakash et al.[4]for tolerating multiple failed nodes.An(r,?)-LRC is called optimal if it achieves the Singleton-type bound.It has been a great challenge to construct q-ary optimal(r,?)-LRCs with length much larger than q.Surprisingly,Luo et al.[5]presented a construction of q-ary optimal r-LRCs of minimum distances 3 and 4 with unbounded lengths via cyclic codes.In Chapter 7,we generalize their results to(r,?)-LRCs.Specifically,for any?+1?d?2?,we construct several classes of optimal cyclic(r,?)-LRCs with unbounded lengths and minimum distance d.