The hybrid method for finding the roots of a polynomial over finite fields based on affine expansion
140 viewsDOI:
https://doi.org/10.54939/1859-1043.j.mst.CSCE7.2023.71-80Keywords:
Finite field; Coding and Information theory; Affine polynomial; Polynomial basis; Normal basis; Error control coding; BCH code; Reed-Solomon code.Abstract
This paper proposes a hybrid method to find the roots of a polynomial in a finite field based on combining the polynomial decomposition into the sum of multiples of the affine polynomial with the analytical method to find the roots of low-order polynomials. The proposed method allows a significant reduction in complexity and is applicable in the design of low-latency BCH and Reed-Solomon decoders.
References
[1]. Elwyn R. Berlekamp, “Algebraic Coding Theory (Revised Edition),” World Scientific Publishing Co. Pte. Ltd. (2015). DOI: https://doi.org/10.1142/9407
[2]. F. J. M. Williams, N. J. A. Sloane, “The theory of error correction codes,” Elselvier (1977).
[3]. Tood K. Moon, “Error correction coding: Mathematical methods and algorithms,” John & sons, Inc. (2005).
[4]. K. Deerganghao, “Channel coding technique for wireless communications,” Springer, India (2015). DOI: https://doi.org/10.1007/978-81-322-2292-7
[5]. D. Strukov, “The area and latency tradeoffs of binary bit-parallel BCH decoders for prospective nano electronic memories”, ACSSC Papers, (2007).
[6]. X. Zhang, Z. Wang, “A low complexity three error correcting for optical transport network”, IEEE Transaction on circuit and systems, Vol. 59, Issue 10, (2012). DOI: https://doi.org/10.1109/TCSII.2012.2208678
[7]. D. Strukov, “The area and latency tradeoffs of binary bit-parallel BCH decoders for prospective nano electronic memories,” ACSSC Papers, (2007). DOI: https://doi.org/10.1109/ACSSC.2006.354942
[8]. J. Fredenberger, “A configurable Bose Chauhuri Hocquenghem codec architecture for flash controller applications,” Journal of circuits, systems and computer, Vol. 23, No. 02, (2013). DOI: https://doi.org/10.1142/S0218126614500194
[9]. K. Huber et al, “Solving Equations in Finite Fields and Some Results Concerning the Structure of GF(pm)”, IEEE Trans. on Information Theory 38(3):1154-1162, (1992). DOI: https://doi.org/10.1109/18.135660
[10]. K. P. Yiu, “On the root computation of polynomial over a finite field using a stored table approach”, Proceeding of the IEEE, Vol.71, No.4, (1983). DOI: https://doi.org/10.1109/PROC.1983.12628
[11]. Муттер .“Основы помехоустойчивой телепередачи информации”, Л.: Энергоатомиздат, Ленинградское отделение, (1990).
[12]. J. Fredenberger, B. N. Bailon, M. Shafies, “Reduced complexity hard and soft decoding of BCH codes with application in concatenated codes,” EIT circuit, devices and systems, pp. 284-296, (2021). DOI: https://doi.org/10.1049/cds2.12026
[13]. B. Bhaskar, H. Vincent, “Efficient root finding of polynomilas over fields of characteristic 2”, Hal, 00626997, (2009).
[14]. Hoan Pham Khac, Thai Ha Tran, Son Ha Vu, “An algeraic transformation method to solving equations in the extened alois field”, Journal of science and technique, Vol. 17, No. 4, (2022).
[15]. Pham Khac Hoan, Nguyen Tien Thai, Vu Son Ha, “Low latency BCH decoder using the affine polynomial over the finite field”, Journal of Military Science and Technology, Special issue No 6, (2022). DOI: https://doi.org/10.54939/1859-1043.j.mst.CSCE6.2022.105-113
[16]. Fedorenko S. V., Trifonov P. V. “Finding roots of polynomials over finite fields, IEEE Transactions on Communications”, Vol. 50, Issue 11, (2002). DOI: https://doi.org/10.1109/TCOMM.2002.805269
