Research On Constant-Dimension Codes For Network Coding

Constant-dimension codes form the most important class of subspace codes, a particular class of error-correcting codes with underlying alphabet the set of subspaces of a projective geometry over a finite field. Subspace codes were introduced for the first time by Koetter and Kschischang in their work on noncoherent network coding. Every codeword of a subspace code is a subspace of a projective geometry in contrast with classical error-correcting codes, whose elements are n-tuples. The study of subspace codes can solve many problems in the current network coding theory and practice.The new mathematical discipline of subspace coding addresses the engineering problem of providing efficient coding schemes for networks in the same way as ordinary algebraic coding theory addresses the problem of finding efficient channel codes. Roughly speaking, subspace coding is devoted to the study of the subspace metric spaces (S, ds), obtained from finite projective geometriesPG(m-1,q)=PG(Fqm) over a finite field Fq by taking S as the set of all flats of PG(m-1, q)(i.e. vector subspaces of Fqm) and defining the subspace distance of two subspaces U,V as ds(U,V)=dim(U+V)-dim(U∩V). The main problem of constant dimension codes is thus the determination of the best (m, M, d; w)subspace codes over, that is M-subsets C={U1,…, UM}(?) S (with S depending on n and q in the way described above) satisfying dim(Ui)=w and ds(C)=min{ds(Ui,Uj),1≤i≤j≤M}=d, and M, d as large as possible.In the thesis, we develop the algebraic theory of subspaces good for removal from the relations between points, lines and planes of a projective geometry. A definition of subspaces good for removal is given, which ensures that more codewords can be added when a fixed number of LMRD codewords are removed. Gabidulin codes form a class of linear optimal rank distance codes which can be used to construct LMRD codes, and linear subcodes of Gabidulin codes are good candidates for removing subspaces. Different dimension of good removed subspaces are tested to get as many codewords as possible. The additive cosets and multiplicative cosets of3-dimensional removed subspaces are tested using the clique of an undirected graph. This results in the construction of two constant-dimension codes with concrete parameters (6,77,4;3) and (7,329,4;3), the former is optimal and the second is the best known so far. ILP are introduced to solve problem of the upper bound of constant-dimension codes and a possible route to the construction of a2-analogue of the Fano plane, or at least a large(7, M,4;3) subspace code, is outlined. We also conclude the paper with a list of open questions arising from the present work.