On Linear Codes in Projective Spaces

Abstract

The projective space $\mathbb{P}_q(n)$ of order $n$ over a finite field $\mathbb{F}_q$ is defined as the collection of all subspaces of the ambient space $\mathbb{F}_q^n$. The Grassmannian $\mathcal{G}_q(n, k)$ is the set of all members of $\mathbb{P}_q(n)$ with fixed dimension $k$. The subspace distance function, defined as $d_S(X, Y) = \dim(X+Y) - \dim(X \cap Y)$ serves as a suitable metric to turn the projective space $\mathbb{P}_q(n)$ into a metric space. A code in the projective space $\mathbb{P}_q(n)$ is a subset of $\mathbb{P}_q(n)$. Projective space has been shown previously by Koetter and Kschischang to be the ideal coding space for error and erasure correction in random network coding.

Linear codes find huge applications in classical error-correction. The notion of linearity was introduced in codes in projective space recently. A subspace code $\mathcal{U}$ in $\mathbb{P}_q(n)$ that contains $\left\{ 0\right\}$ is linear if there exists a function $\boxplus : \mathcal{U} \times \mathcal{U} \rightarrow \mathcal{U}$ such that $(\mathcal{U}, \boxplus)$ is an abelian group with identity element as $\left\{ 0\right\}$, all elements of $\mathcal{U}$ are idempotent with respect to $\boxplus$, and the operation $\boxplus$ is isometric. It was conjectured that the size of any linear subspace code in $\mathbb{P}_q(n)$ can be at most $2^n$.

In this work, we focus on different classes of linear subspace codes with a view to proving the conjectured upper bound for them as well as characterizing the maximal cases. We study connections of linear codes with lattices and a few combinatorial objects.

Binary linear block codes and linear subspace codes are subspaces of a finite vector space over $\mathbb{F}_2$. We identify common features in their structures and prove analogous results for subspace codes including the Union-Intersection theorem.

We investigate a class of linear subspace codes which are closed under intersection and show that these codes are equivalent to codes derived from a partition of a linearly independent set. The set of indecomposable codewords in a linear code closed under intersection is proved to generate the code. We verify the conjectured upper bound of $2^n$ for this class of linear codes and show that the maximal codes are essentially codes derived from a fixed basis. We prove linear codes that are sublattices of the projective lattice are precisely those closed under intersection. The sublattice is geometric distributive. We also give an alternate definition of codes derived from a fixed basis and prove that it is equivalent to the one presented in the existing literature.

A code in a projective space is equidistant if the distance between each pair of distinct codewords are equal. A similarity in structure is established between equidistant linear subspace codes and $\lambda$-intersecting families, which are studied in the combinatorics of finite sets. We prove the conjectured bound for equidistant linear codes in $\mathbb{P}_2(n)$ and also determine the extremal case which is shown to be closely related to the Fano plane. Equidistant linear codes attaining maximum cardinality for all values of $n \ge 4$ are constructed. Such constructions are shown as $q$-analogs of a particular class of intersecting families called sunflowers. For positive integer values of $r$, construction of equidistant linear codes in $\mathbb{P}_q(n)$ is shown to be possible from any $(2^r - 1)$-subset of a Grassmannian $\mathcal{G}_q(n, 2k)$ with certain intersecting property. This proves constant distance decouples the translation invariance on the subspace distance metric for linear codes. We generalize linear subspace codes as $L$-intersecting families and give a construction for $|L| = 2$ that attains size $2^n$ with larger minimum distance than codes derived from a fixed basis. The conjectured upper bound is proved to hold for $L$-intersecting codes when $|L| = 2, q = 2$.