On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes

DOI10.1007/S10623-014-9932-XzbMATH Open1335.94022OpenAlexW3103406970MaRDI QIDQ398944FDOQ398944

Authors Joachim Rosenthal, Natalia Silberstein, Anna-Lena Trautmann 

Publication date 18 August 2014

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

projective spacesubspace codesnetwork codingGrassmannianlist decoding

Mathematics Subject Classification ID

Circuits, networks (94C99) Source coding (94A29) Applications to coding theory and cryptography of arithmetic geometry (14G50) Decoding (94B35)

Abstract: The finite Grassmannian $mathcal{G}_q(k,n)$ is defined as the set of all $k$-dimensional subspaces of the ambient space $mathbb{F}_q^n$. Subsets of the finite Grassmannian are called constant dimension codes and have recently found an application in random network coding. In this setting codewords from $mathcal{G}_q(k,n)$ are sent through a network channel and, since errors may occur during transmission, the received words can possible lie in $mathcal{G}_q(k^{\prime },n)$, where $k^{\prime }eqk$. In this paper, we study the balls in $mathcal{G}_q(k,n)$ with center that is not necessarily in $mathcal{G}_q(k,n)$. We describe the balls with respect to two different metrics, namely the subspace and the injection metric. Moreover, we use two different techniques for describing these balls, one is the Pl"ucker embedding of $mathcal{G}_q(k,n)$, and the second one is a rational parametrization of the matrix representation of the codewords. With these results, we consider the problem of list decoding a certain family of constant dimension codes, called lifted Gabidulin codes. We describe a way of representing these codes by linear equations in either the matrix representation or a subset of the Pl"ucker coordinates. The union of these equations and the equations which arise from the description of the ball of a given radius in the Grassmannian describe the list of codewords with distance less than or equal to the given radius from the received word.

Recommendations

• Point-line incidence on Grassmannians and majority logic decoding of Grassmann codes
• Subspace packings: constructions and bounds
• Construction of constant dimension codes in some cases
• The structure of dual Grassmann codes
• Construction of constant dimension codes in some cases

Cites work

• scientific article; zbMATH DE number 1418284 (Why is no real title available?)
• scientific article; zbMATH DE number 3075369 (Why is no real title available?)
• A Rank-Metric Approach to Error Control in Random Network Coding
• Algebraic codes for network coding
• Bilinear forms over a finite field, with applications to coding theory
• Bounds on List Decoding of Rank-Metric Codes
• Codes and Designs Related to Lifted MRD Codes
• Coding for Errors and Erasures in Random Network Coding
• Constant-Rank Codes and Their Connection to Constant-Dimension Codes
• Construction of Large Constant Dimension Codes with a Prescribed Minimum Distance
• Cyclic Orbit Codes
• Efficient algorithms for solving overdefined systems of multivariate polynomial equations
• Enumerative Coding for Grassmannian Space
• Error-Correcting Codes in Projective Space
• Error-Correcting Codes in Projective Spaces Via Rank-Metric Codes and Ferrers Diagrams
• Large constant dimension codes and lexicodes
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound
• List decoding subspace codes from insertions and deletions
• Maximum-rank array codes and their application to crisscross error correction
• Recursive Code Construction for Random Networks
• Schubert Calculus
• Theory of codes with maximum rank distance

Cited in

(2)

• Equidistant codes in the Grassmannian
• Galois geometries and coding theory

This page was built for publication: On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes

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