Conference abstracts

Session S07 - Finite Fields

July 29, 15:00 ~ 15:25

Galois geometries and Random network coding

Leo Storme

Ghent University, Belgium   -

Presently, a new direction in coding theory, called Random network coding, receives a lot of attention.

In random network coding, information is transmitted through a network whose topology can vary. A classical example is a wireless network where users come and go.

R. Kotter and F. Kschischang proved in an inspiring article that a very good way of transmission is obtained in networks if subspace codes are used. Here, the codewords are $k$-dimensional vector subspaces of the $n$-dimensional vector space $V(n,q)$ over the finite field of order $q$.

To transmit a codeword, i.e. a $k$-dimensional vector space, through the network, it is sufficient to transmit a basis of this $k$-dimensional vector space. But a $k$-dimensional subspace has different bases. Kotter and Kschischang proved that the transmission can be optimalized if the nodes in the network transmit linear combinations of the incoming basis vectors of the $k$-dimensional subspace which represents the codeword.

These ideas led to many new interesting problems in coding theory and in Galois geometries. For instance, it leads to the study of sets $C$ of $k$-dimensional subspaces of $V(n,q)$, where two different $k$-dimensional subspaces of $C$ pairwise intersect in at most a $t$-dimensional subspace, for some specified parameter $t$.

Since the $k$-dimensional subspaces of $V(n,q)$ define $(k-1)$-dimensional projective subspaces of the projective space PG$(n-1,q)$, this problem can also be investigated in a projective setting. Hence, Galois geometries can contribute to random network coding.

In this talk, we present a number of geometrical results on random network coding, thereby showing how Galois geometries can contribute to this new area in coding theory.

View abstract PDF