Bounds on List Decoding of Rank-Metric Codes

DOI10.1109/TIT.2013.2274653MaRDI QIDQ5346252zbMATH OpenFDO

Authors Antonia Wachter-Zeh

Publication date 8 June 2017

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

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

Mathematics Subject Classification ID

Bounds on codes (94B65) Decoding (94B35)

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 $n$ and minimum rank distance $d$. The third bound proves that there exists a rank-metric code over $Fqm$ of length $nleqm$ 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 $n$ and $d$ 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)

• Linearized trinomials with maximum kernel
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes
• A module minimization approach to Gabidulin decoding via interpolation
• On the list decodability of rank-metric codes containing Gabidulin codes
• 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
• Non-linear maximum rank distance codes
• On the vector subspaces of \(\mathbb{F}_{2^n}\) over which the multiplicative inverse function sums to zero
• Constructions of cyclic constant dimension codes
• Randomized decoding of Gabidulin codes beyond the unique decoding radius
• LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
• Fast decoding of interleaved linearized Reed-Solomon codes and variants
• On the list decodability of self-orthogonal rank-metric codes
• Improved list-decodability of random linear binary codes
• A New Class of Rank-Metric Codes and Their List Decoding Beyond the Unique Decoding Radius
• Rank-metric codes and their applications
• Algebraic decoding of folded Gabidulin codes
• Row reduction applied to decoding of rank-metric and subspace codes
• A novel Niederreiter-like cryptosystem based on the \((u|u + \upsilon)\)-construction codes

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)