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

DOI10.1007/S10623-014-9932-XzbMATH Open1335.94022arXiv1309.0403OpenAlexW3103406970MaRDI 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)

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.

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

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

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)

Cites Work

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

Cited In (2)

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

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)