Ph.D Thesis

Ph.D StudentSilberstein Natalia
SubjectCoding Theory and Projective Spaces
DepartmentDepartment of Computer Science
Supervisor PROF. Tuvi Etzion
Full Thesis textFull thesis text - English Version


The projective space of order n over a finite field Fq, denoted by Pq(n), is a set of all subspaces of the vector space Fqn. The projective space is a metric space with the distance function ds(X,Y) = dim(X) dim(Y) - 2dim(X ∩ Y), for all X, Y in Pq(n). A code in the projective space is a subset of Pq(n). Coding in the projective space has received recently a lot of attention due to its application in random network coding. If the dimension of each codeword is restricted to a fixed nonnegative integer k ≤ n, then the code forms a subset of a Grassmannian. Such a code is called a constant dimension code. Constant dimension codes in the projective space are analogous to constant weight codes in the Hamming space. In this work, we consider error-correcting codes in the projective space, focusing mainly on constant dimension codes. We start with the different representations of subspaces in Pq(n). These representations involve matrices in reduced row echelon form, associated binary vectors, and Ferrers diagrams. Based on these representations, we provide a new formula for the computation of the distance between any two subspaces in the projective space. We examine lifted maximum rank distance (MRD) codes, which are nearly optimal constant dimension codes. We prove that a lifted MRD code can be represented in such a way that it forms a block design known as a transversal design. The incidence matrix of such a design can be viewed as a parity-check matrix of a linear code in the Hamming space. We find the properties of these codes which can be viewed also as LDPC codes. We present new bounds and constructions for constant dimension codes. First, we present a multilevel construction for constant dimension codes, which can be viewed as a generalization of a lifted MRD codes construction. This construction is based on a new type of rank-metric codes, called Ferrers diagram rank-metric codes. Then we derive upper bounds on the size of constant dimension codes which contain the lifted MRD code, and provide a construction for two families of codes, that attain these upper bounds. Most of the codes obtained by these constructions are the largest known constant dimension codes. We present efficient enumerative encoding and decoding techniques for the Grassmannian. Finally we describe a search method for constant dimension lexicodes.