Skip to content

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

Research output: Contribution to journalArticle

  • Fabrizio Caruso
  • Emmanuela Orsini
  • Massimiliano Sala
  • Claudia Tinnirello
Original languageEnglish
Pages (from-to)3641-3557
Number of pages17
JournalIEEE Transactions on Information Theory
Issue number6
Early online date7 Apr 2017
DateAccepted/In press - 20 Mar 2017
DateE-pub ahead of print - 7 Apr 2017
DatePublished (current) - Jun 2017


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.

    Research areas

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

Download statistics

No data available



  • Full-text PDF (accepted author manuscript)

    Rights statement: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via IEEE at Please refer to any applicable terms of use of the publisher.

    Accepted author manuscript, 376 KB, PDF document


View research connections

Related faculties, schools or groups