Coding Theory and Projective Spaces

Natalia Silberstein (Ph.D. Thesis Seminar)

Tuesday, 28.06.2011, 12:30

Taub 601

Advisor: Prof. Tuvi Etzion

The projective space of order n over the finite field F is the set of all the subspaces of the vector space F^n. A code C in the projective space is defined as a subset of the projective space, i.e., the codewords in C are subspaces of F^n. If all the codewords in C have the same dimension, then C is called a constant dimension code. These codes gained renewed interest due to the work by Koetter and Kschischang (2008), where they presented an application of such codes to error correction in random network coding.
In the first part of the talk we will present a method to design error-correcting codes in the projective space. We use a multilevel approach to design our codes. First, we select a constant weight code. Each codeword defines a skeleton of a basis for a subspace in reduced row echelon form. This skeleton contains a Ferrers diagram on which we design a rank-metric code. Each such rank-metric code is lifted to a constant dimension code. The union of these codes is our final constant dimension code. In particular the codes constructed by Koetter and Kschischang are a subset of our codes.
In the second part of the talk we will discuss a relationship between constant dimension codes and combinatorial designs. We consider lifted maximum rank distance codes. We first prove that each such code forms a transversal design in sets and it also forms a structure akin to transversal design in subspaces. We present bounds on the size of codes which contain lifted maximum rank distance codes and describe constructions of codes which attain these bounds. Finally, we present LDPC codes based on the lifted maximum rank distance codes and discuss their properties.