Technical Report PHD-2011-13

Title: Coding Theory and Projective Spaces
Authors: Natalia Silberstein
Supervisors: prof. Tuvi Etzion
Abstract: The projective space of order $n$ over a finite field $\F_q$, denoted by $\mathcal{P}_{q}(n)$, is a set of all subspaces of the vector space $\F_q^{n}$. The projective space is a metric space with the distance function $d_{s}(X,Y)=\mbox{dim}(X)+\mbox{dim}(Y)-2\mbox{dim}(X\cap Y)$, for all $X, Y\in\mathcal{P}_{q}(n)$. A code in the projective space is a subset of $\mathcal{P}_{q}(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\leq n$, then the code forms a subset of a Grassmannian, which is the set of all $k$-dimensional subspaces of $\F_q^{n}$, denoted by $\Gr$. 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 $\Ps$. 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. A slightly different representation of this design makes it similar to a $q$-analog of transversal design. The incidence matrix of the transversal design derived from a lifted MRD code 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. We provide an upper bound on the size of Ferrers diagram rank-metric codes and present a construction of codes that attain this bound. 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 generalize the well-known concept of a punctured code for a code in the projective space to obtain large codes which are not constant dimension.

We present efficient enumerative encoding and decoding techniques for the Grassmannian. These coding techniques are based on two different lexicographic orders for the Grassmannian induced by different representations of $k$-dimensional subspaces of $\F_q^n$. Finally we describe a search method for constant dimension lexicodes. Some of the codes obtained by this search are the largest known constant dimension codes with their parameters.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the PHD technical reports of 2011
To the main CS technical reports page

Computer science department, Technion