Bounds on List Decoding of Rank-Metric Codes
From MaRDI portal
Abstract: So far, there is no polynomial-time list decoding algorithm (beyond half the minimum distance) for Gabidulin codes. These codes can be seen as the rank-metric equivalent of Reed--Solomon codes. In this paper, we provide bounds on the list size of rank-metric codes in order to understand whether polynomial-time list decoding is possible or whether it works only with exponential time complexity. Three bounds on the list size are proven. The first one is a lower exponential bound for Gabidulin codes and shows that for these codes no polynomial-time list decoding beyond the Johnson radius exists. Second, an exponential upper bound is derived, which holds for any rank-metric code of length and minimum rank distance . The third bound proves that there exists a rank-metric code over of length such that the list size is exponential in the length for any radius greater than half the minimum rank distance. This implies that there cannot exist a polynomial upper bound depending only on and similar to the Johnson bound in Hamming metric. All three rank-metric bounds reveal significant differences to bounds for codes in Hamming metric.
Cited in
(20)- Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
- Extension of Overbeck's attack for Gabidulin-based cryptosystems
- Constructions of cyclic constant dimension codes
- On the list decodability of self-orthogonal rank-metric codes
- LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
- On the list decodability of rank-metric codes containing Gabidulin codes
- Linearized trinomials with maximum kernel
- Non-linear maximum rank distance codes
- On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes
- List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
- Improved list-decodability of random linear binary codes
- A novel Niederreiter-like cryptosystem based on the \((u|u + \upsilon)\)-construction codes
- Randomized decoding of Gabidulin codes beyond the unique decoding radius
- Row reduction applied to decoding of rank-metric and subspace codes
- Algebraic decoding of folded Gabidulin codes
- A module minimization approach to Gabidulin decoding via interpolation
- A New Class of Rank-Metric Codes and Their List Decoding Beyond the Unique Decoding Radius
- Rank-metric codes and their applications
- Fast decoding of interleaved linearized Reed-Solomon codes and variants
- On the vector subspaces of \(\mathbb{F}_{2^n}\) over which the multiplicative inverse function sums to zero
This page was built for publication: Bounds on List Decoding of Rank-Metric Codes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5346252)
