Enumerative Coding for Grassmannian Space

DOI10.1109/TIT.2010.2090252MaRDI QIDQ5281130zbMATH OpenOpenAlexFDO

Authors Natalia Silberstein, Tuvi Etzion

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.3256

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Applications to coding theory and cryptography of arithmetic geometry (14G50) Coding theorems (Shannon theory) (94A24)

Abstract: 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)lognloglogn)$ digits operations. A combination of the two methods reduces the complexity on average by a constant factor.

Cited in

(8)

• Message encoding and retrieval for spread and cyclic orbit codes
• Constructions of optimal Ferrers diagram rank metric codes
• New constructions of Sidon spaces
• Several classes of optimal Ferrers diagram rank-metric codes
• Enumerative coding for line polar Grassmannians with applications to codes
• On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes
• Bilateral multilevel construction of constant dimension codes
• New lower bounds for partial k‐parallelisms

This page was built for publication: Enumerative Coding for Grassmannian Space

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5281130)