MODIFIED ALGORITHM FOR SEARCHING THE ROOTS OF THE ERROR LOCATORS POLYNOMINAL WHILE DECODING BCH CODES
DOI:
https://doi.org/10.15588/1607-3274-2020-3-14Keywords:
BCH codes, error locator polynomial, Chan’s search, Berlekamp-Massey algorithm and Reed-Solomon codes.Abstract
Context. In telecommunications and information systems with an increased noise component the noise-resistant cyclic BCH and Reed-Solomon codes are used. The adjustment and correcting errors in a message require some effective decoding methods. One of the stages in the procedure of decoding RS and BCH codes to determine the position of distortions is the search for the roots of the error locator polynomial. The calculation of polynomial roots, especially for codes with significant correction capacity is a laborious task requiring high computational complexity. That is why the improvement of BCH and RS codes decoding methods providing to reduce the computational complexity is an urgent task.
Objective. The investigation and synthesis of the accelerated roots search algorithm of the error locator polynomial presented as an affine polynomial with coefficients in the finite fields, which allows accelerating the process of BCH and RS code decoding.
Method. The classical roots search method based on the Chan’s algorithm is performed using the arithmetic of the Galois finite fields and the laborious calculation, in this case depends on the number of addition and multiplication operations. For linearized polynomials, the roots search procedure based on binary arithmetic is performed taking into account the values obtained at the previous stages of the calculation, which provides the minimum number of arithmetic operations.
Results. An accelerated algorithm for calculating the values of the error locator polynomial at all points of the GF(2m) finite field for linearized polynomials based on the Berlekamp-Massey method has been developed. The algorithm contains a minimum number of addition operations, due to the use at each stage of the calculations the values obtained at the previous step, as well as the addition in the finite field GF(2). A modified roots search method for affine polynomials over the finite fields has been proposed to determine error positions in the code word while decoding the cyclic BCH and RS codes.
Conclusions. The scientific newness of the work is to improve the algorithm of calculating the roots of the error locator polynomial, which coefficients belong to the elements of the finite field. At the same time it simplifies the procedure for cyclic BCH and RS codes decoding, due to reducing the computational complexity of one of the decoding stages, especially finding the error positions using the modified Berlekamp-Massey algorithm. These facts are confirmed by the simulation program results of the roots search of the error locator polynomial algorithm. It is shown, that the application of the accelerated method permits to reach a gain on speed of 1.5 times.
References
Berlekamp E. R. Algebraic Coding Theory. New York, McGraw-Hill, 1968, 466 р.
Blahut Richard E. Algebraic Codes for Data Transmission. Cambridge, Cambridge University Press, 2003, 482 р.
Lin S., Costello D. J. Error control coding: fundamentals and applications. Prentice-Hall Inc, Printed in the United States of America, 2004, 624 р.
Truong T. K., Jeng J. H., Reed I. S. Fast algorithm for computing the roots of error locator polynomials up to degree 11 in Reed-Solomon decoders, IEEE Transactions on Communications, 2001, Vol. 49, Issue 5, pp. 779–783. DOI:10.1109/26.923801.
Nabipour S., Javidan J., Zare Gholamreza F. Error Detection Mechanism Based on Bch Decoder and Root Finding of Polynomial Over Finite Fields, Journal of Mathematics and Computer Science, 2014, Issue 4, pp. 271–281. DOI: http://dx.doi.org/10.22436/jmcs.012.04.03.
Fedorenko S. V., Trifonov P. V. Finding roots of polynomials over finite fields, IEEE Transactions on Communications, 2002, Vol. 50, Issue 11, pp. 1709–1711. DOI: 10.1109 / TCOMM.2002.805269.
Fedorenko S., Trifonov P., Costa E., Haas H. Improved hybrid algorithm for finding roots of error-locator polynomials, European Transactions on Telecommunications, 2003, Vol. 14, Issue 5, pp. 411–416. DOI: https://doi.org/10.1002/ett.936.
Bras-Amorós M., Michael O’Sullivan E. The Symmetric Key Equation for Reed–Solomon Codes and a New Perspective on the Berlekamp-Massey Algorithm, Symmetry, 2019, Vol. 11 (1357). DOI: 10.3390/sym11111357.
Ceria M., Mora T., Sala M. Help: a sparse error locator polynomial for BCH codes, Applicable Algebra in Engineering, Communication and Computing, 2020, Vol. 31, pp. 215–233. DOI: https://doi.org/10.1007/s00200-02000427-x.
Almuzakkia M. Z., Oharac K. Computing general error locator polynomial of 3-error-correcting BCH codes via syndrome varieties using minimal polynomial [Electronic resource], ISCS, Selected Papers, 2015, pp. 80–85. Access mode: https://mafiadoc.com/computing-general-errorlocator-polynomial_5bad280f097c479e798b4727.html.
Freyman V. I. Research of the reed-solomon codes characteristic for realization within control systems devices, Radio Electronics, Computer Science, Control, 2019, Vol. 3, pp. 143–151. DOI: https://doi.org/10.15588/1607-32742019-3-1.
Liang Z., Zhang W. Efficient Berlekamp-Massey Algorithm and Architecture for Reed-Solomon Decoder, Journal of Signal Processing Systems, 2017, Vol. 86, Issue 1, pp. 51– 65. DOI: https://doi.org/10.1007/s11265-015-1094-1.
Caruso F., Orsini E., Sala M., Tinnirello C. On the Shape of the General Error Locator Polynomial for Cyclic Codes / // IEEE Transactions on Information Theory, 2017, Vol. 63, Issue 6, pp. 3641–3657. DOI: 10.1109/TIT.2017.2692213.
Bucerzan D., Dragoi V., Richmond T. The simple roots problem [Electronic resource], Proceedings of the Romanian Academy, (Special issue), Cryptology Science, 2017, Vol. 18, pp. 317–332. Access mode: https://acad.ro/sectii2002/proceedings/doc20174s/03artSupl.pdf.
Downloads
How to Cite
Issue
Section
License
Copyright (c) 2020 V. А. Krylova, Е. Е. Тverytnykova, O. G. Vasylchenkov, T. P. Kolisnyk
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Creative Commons Licensing Notifications in the Copyright Notices
The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.
The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.
The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.
Authors who publish with this journal agree to the following terms:
-
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
-
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
-
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
