On the Shape of the General Error Locator Polynomial for Cyclic Codes

Fabrizio Caruso, Emmanuela Orsini, Massimiliano Sala, Claudia Tinnirello

Research output: Contribution to journalArticle (Academic Journal)

6 Citations (Scopus)
248 Downloads (Pure)

Abstract

General error locator polynomials were introduced in 2005 as an alternative decoding for cyclic codes. We present now 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 cyclic codes.
Original languageEnglish
Pages (from-to)3641-3557
Number of pages17
JournalIEEE Transactions on Information Theory
Volume63
Issue number6
Early online date7 Apr 2017
DOIs
Publication statusPublished - Jun 2017

Keywords

  • Bounded-distance decoding
  • Symmetric function
  • Cyclic codes
  • Finite fileds

Fingerprint Dive into the research topics of 'On the Shape of the General Error Locator Polynomial for Cyclic Codes'. Together they form a unique fingerprint.

  • Projects

    TIPS Fellowship

    Smart, N. P.

    1/10/1630/09/21

    Project: Research

    Cite this