Let k,n,m in {mathbb Z} ^{+} be integers such that kleq n leq m , let mathrm {G}_{n,k}in {mathbb F} _{q^{m}}^{n} be a Delsarte-Gabidulin code. Recently, Wachter-Zeh proved that codes belonging to this family cannot be efficiently list decoded for any radius au , providing au is large enough. This achievement essentially relies on proving a lower bound for the list size of some specific words in {mathbb F}_{q^{m}}^{n}. Some years later, Raviv and Wachter-Zeh improved this bound in a special case, i.e. when nmid m. As a consequence, they were able to detect infinite families of Delsarte-Gabidulin codes that cannot be efficiently list decoded at all. In this article we determine similar lower bounds for Maximum Rank Distance codes belonging to a wider class of examples, containing Generalized Gabidulin codes, Generalized Twisted Gabidulin codes, and examples recently described by Trombetti and Zhou. By exploiting arguments such as those used by Raviv and Wachter-Zeh, when nmid m , we also show infinite families of generalized Gabidulin codes that cannot be list decoded efficiently at any radius greater than or equal to left lfloor{ rac {d-1}2 } ight floor +1 , where d is its minimum distance. Nonetheless, in all the examples belonging to above mentioned class, we detect infinite families that cannot be list decoded efficiently at any radius greater than or equal to left lfloor{ rac {d-1}2 } ight floor +2 , where d is its minimum distance. In particular, this leads to show infinite families of Gabidulin codes, with underlying parameters not already covered by the result of Raviv and Wachter-Zeh, having this decodability defect. Finally, relying on the properties of a set of subspace trinomials recently presented by McGuire and Mueller, we are able to prove our main result, that is any rank-metric code of {mathbb F}_{q^{m}}^{n} of order q^{kn} with n dividing m , such that 4n-3 is a square in mathbb {Z} and containing mathrm {G}_{n,2} , is not efficiently list decodable at some values of the radius au .

On the List Decodability of Rank Metric Codes

Zullo F.
2020

Abstract

Let k,n,m in {mathbb Z} ^{+} be integers such that kleq n leq m , let mathrm {G}_{n,k}in {mathbb F} _{q^{m}}^{n} be a Delsarte-Gabidulin code. Recently, Wachter-Zeh proved that codes belonging to this family cannot be efficiently list decoded for any radius au , providing au is large enough. This achievement essentially relies on proving a lower bound for the list size of some specific words in {mathbb F}_{q^{m}}^{n}. Some years later, Raviv and Wachter-Zeh improved this bound in a special case, i.e. when nmid m. As a consequence, they were able to detect infinite families of Delsarte-Gabidulin codes that cannot be efficiently list decoded at all. In this article we determine similar lower bounds for Maximum Rank Distance codes belonging to a wider class of examples, containing Generalized Gabidulin codes, Generalized Twisted Gabidulin codes, and examples recently described by Trombetti and Zhou. By exploiting arguments such as those used by Raviv and Wachter-Zeh, when nmid m , we also show infinite families of generalized Gabidulin codes that cannot be list decoded efficiently at any radius greater than or equal to left lfloor{ rac {d-1}2 } ight floor +1 , where d is its minimum distance. Nonetheless, in all the examples belonging to above mentioned class, we detect infinite families that cannot be list decoded efficiently at any radius greater than or equal to left lfloor{ rac {d-1}2 } ight floor +2 , where d is its minimum distance. In particular, this leads to show infinite families of Gabidulin codes, with underlying parameters not already covered by the result of Raviv and Wachter-Zeh, having this decodability defect. Finally, relying on the properties of a set of subspace trinomials recently presented by McGuire and Mueller, we are able to prove our main result, that is any rank-metric code of {mathbb F}_{q^{m}}^{n} of order q^{kn} with n dividing m , such that 4n-3 is a square in mathbb {Z} and containing mathrm {G}_{n,2} , is not efficiently list decodable at some values of the radius au .
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11591/458847
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 4
social impact