In 1990 Cooper suggested to use Groebner bases’ computations to decode cyclic codes and his idea gave rise to many research papers. In particular, as proved by Sala-Orsini, once defined the polynomial ring whose variables are the syndromes, the locations and the error values and considered the syndrome ideal, only one polynomial of a lexicographical Groebner basis for such ideal is necessary to decode (the general error locator polynomial, a.k.a. GELP). The decoding procedure only consists in evaluating this polynomial in the syndromes and computing its roots: the roots are indeed the error locations. A possible bottleneck in this procedure may be the evaluation part, since a priori the GELP may be dense. In this paper, focusing on binary cyclic codes with length n= 2 m- 1 , correcting up to two errors, we give a Groebner-free, sparse analog of the GELP, the half error locator polynomial (HELP). In particular, we show that it is not necessary to compute the whole Groebner basis for getting such kind of locator polynomial and we construct the HELP, studying the quotient algebra of the polynomial ring modulo the syndrome ideal by a combinatorial point of view. The HELP turns out to be computable with quadratic complexity and it has linear growth in the length n of the code: O(n+12).

HELP: a sparse error locator polynomial for BCH codes / Ceria, Michela; Mora, Teo; Sala, Massimiliano. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - STAMPA. - 31:3-4(2020), pp. 215-233. [10.1007/s00200-020-00427-x]

HELP: a sparse error locator polynomial for BCH codes

Ceria, Michela;Sala, Massimiliano
2020-01-01

Abstract

In 1990 Cooper suggested to use Groebner bases’ computations to decode cyclic codes and his idea gave rise to many research papers. In particular, as proved by Sala-Orsini, once defined the polynomial ring whose variables are the syndromes, the locations and the error values and considered the syndrome ideal, only one polynomial of a lexicographical Groebner basis for such ideal is necessary to decode (the general error locator polynomial, a.k.a. GELP). The decoding procedure only consists in evaluating this polynomial in the syndromes and computing its roots: the roots are indeed the error locations. A possible bottleneck in this procedure may be the evaluation part, since a priori the GELP may be dense. In this paper, focusing on binary cyclic codes with length n= 2 m- 1 , correcting up to two errors, we give a Groebner-free, sparse analog of the GELP, the half error locator polynomial (HELP). In particular, we show that it is not necessary to compute the whole Groebner basis for getting such kind of locator polynomial and we construct the HELP, studying the quotient algebra of the polynomial ring modulo the syndrome ideal by a combinatorial point of view. The HELP turns out to be computable with quadratic complexity and it has linear growth in the length n of the code: O(n+12).
2020
3-4
Ceria, Michela; Mora, Teo; Sala, Massimiliano
HELP: a sparse error locator polynomial for BCH codes / Ceria, Michela; Mora, Teo; Sala, Massimiliano. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - STAMPA. - 31:3-4(2020), pp. 215-233. [10.1007/s00200-020-00427-x]
File in questo prodotto:
File Dimensione Formato  
Ceria2020_Article_HELPASparseErrorLocatorPolynom.pdf

Solo gestori archivio

Descrizione: articolo pubblicato
Tipologia: Versione editoriale (Publisher’s layout)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 2.73 MB
Formato Adobe PDF
2.73 MB 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/11572/297585
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 7
social impact