On PGZ decoding of alternant codes
- PDF / 337,657 Bytes
- 13 Pages / 439.37 x 666.142 pts Page_size
- 26 Downloads / 245 Views
On PGZ decoding of alternant codes Rafel Farré1 · Narcís Sayols1 · Sebastià Xambó-Descamps1 Received: 5 May 2018 / Revised: 30 August 2018 / Accepted: 9 October 2018 © SBMAC - Sociedade Brasileira de Matemática Aplicada e Computacional 2019
Abstract In this paper, we first review the classical Petterson–Gorenstein–Zierler decoding algorithm for the class of alternant codes, which includes Reed–Solomon, Bose–Chaudhuri– Hocquenghem and classical Goppa codes. Afterwards, we present an improvement of the method to find the number of errors and the error-locator polynomial. Finally, we illustrate the procedure with several examples. In two appendices, we sketch the main features of the computer algebra system designed and developed to support the computations. Keywords Alternant codes · RS codes · BCH codes · Classical Goppa codes · Computer algebra systems Mathematics Subject Classification 11T71 · 94B05 · 94B35 · 94B15
Introduction The Petterson–Gorenstein–Zierler decoding algorithm (PGZ for short) was first developed for Reed–Solomon codes (RS), and later applied to Bose–Chaudhuri–Hocquenghem codes (BCH). In Xambó-Descamps (2003), two flavours of it were presented for alternant codes, with due attention to the computational aspects. The main interest of working with the class of alternant codes is that it includes many interesting subclasses, like RS codes, BCH codes (the most relevant class of cyclic codes), and classical Goppa codes. The practical bonus of this realization is that all these families of codes can be constructed by specializing the general constructor of alternant codes and, most fundamentally, that any effective decoding algorithm for alternant codes is sufficient (and effective) for all those subclasses.
Communicated by Carlos Hoppen.
B
Sebastià Xambó-Descamps [email protected] Rafel Farré [email protected] Narcís Sayols [email protected]
1
Universitat Politècnica de Catalunya, Barcelona, Spain
123
R. Farré et al.
In this paper, we present a natural improvement, both conceptual and computational, of the PGZ algorithm. The key point is that the output of the Gauss–Jordan reduction of a (Hankel-like) matrix constructed from the syndrome vector gives directly and at the same time the number of errors and the error-locator polynomial. The organization is as follows. In the first section, we briefly review alternant codes. This includes details about how the classes of codes just mentioned can be constructed with special calls to the main constructor. The second section is devoted to present the mathematical basis of the PGZ approach for the decoding of alternant codes. Our improvement of PGZ is explained in detail in the third section and in the fourth we provide several examples. Finally, Appendix A contains listings of the key Python functions that we have designed and coded to get clear implementations of the computations and in the Appendix B we sketch the main features of the Python package (Sayols and Xambó-Descamps 2017) used to script the examples. Notations and conventions I
Data Loading...
