Computer Science – Information Theory
Scientific paper
2009-11-17
Computer Science
Information Theory
to appear in IEEE Transactions on Information Theory
Scientific paper
The Grassmannian space $\Gr$ is the set of all $k-$dimensional subspaces of the vector space~\smash{$\F_q^n$}. Recently, codes in the Grassmannian have found an application in network coding. The main goal of this paper is to present efficient enumerative encoding and decoding techniques for the Grassmannian. These coding techniques are based on two different orders for the Grassmannian induced by different representations of $k$-dimensional subspaces of $\F_q^n$. One enumerative coding method is based on a Ferrers diagram representation and on an order for $\Gr$ based on this representation. The complexity of this enumerative coding is $O(k^{5/2} (n-k)^{5/2})$ digit operations. Another order of the Grassmannian is based on a combination of an identifying vector and a reduced row echelon form representation of subspaces. The complexity of the enumerative coding, based on this order, is $O(nk(n-k)\log n\log\log n)$ digits operations. A combination of the two methods reduces the complexity on average by a constant factor.
Etzion Tuvi
Silberstein Natalia
No associations
LandOfFree
Enumerative Coding for Grassmannian Space does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Enumerative Coding for Grassmannian Space, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumerative Coding for Grassmannian Space will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-650411