General error locator polynomials were introduced in 2005 as an alternative decoding for cyclic codes. We now present a conjecture on their sparsity, which would imply polynomial-time decoding for all cyclic codes. A general result on the explicit form of the general error locator polynomial for all cyclic codes is given, along with several results for specific code families, providing evidence to our conjecture. From these, a theoretical justification of the sparsity of general error locator polynomials is obtained for all binary cyclic codes with t <= 2 and n < 105, as well as for t = 3 and n < 63, except for some cases where the conjectured sparsity is proved by a computer check. Moreover, we summarize all related results, previously published, and we show how they provide further evidence to our conjecture. Finally, we discuss the link between our conjecture and the complexity of bounded-distance decoding of the cyclic codes.

On the shape of the general error locator polynomial for cyclic codes

Orsini, Emmanuela;
2017

Abstract

General error locator polynomials were introduced in 2005 as an alternative decoding for cyclic codes. We now present a conjecture on their sparsity, which would imply polynomial-time decoding for all cyclic codes. A general result on the explicit form of the general error locator polynomial for all cyclic codes is given, along with several results for specific code families, providing evidence to our conjecture. From these, a theoretical justification of the sparsity of general error locator polynomials is obtained for all binary cyclic codes with t <= 2 and n < 105, as well as for t = 3 and n < 63, except for some cases where the conjectured sparsity is proved by a computer check. Moreover, we summarize all related results, previously published, and we show how they provide further evidence to our conjecture. Finally, we discuss the link between our conjecture and the complexity of bounded-distance decoding of the cyclic codes.
2017
2017
Caruso, Fabrizio; Orsini, Emmanuela; Sala, Massimiliano; Tinnirello, Claudia
File in questo prodotto:
File Dimensione Formato  
IEEE2017.pdf

non disponibili

Descrizione: article
Tipologia: Pdf editoriale (Publisher's layout)
Licenza: Copyright dell'editore
Dimensione 300.53 kB
Formato Adobe PDF
300.53 kB Adobe PDF   Visualizza/Apri

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/11565/4054450
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 11
social impact