Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes

Hung-Peng Lee^1, and Hsin-Chiu Chang¹

¹Department of Computer Science and Information Engineering, Fortune Institute of Technology, Kaohsiung, ROC

Cite this paper:
Hung-Peng Lee and Hsin-Chiu Chang. Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes. Automatic Control and Information Sciences. 2014; 2(1):7-12. doi: 10.12691/acis-2-1-2

Abstract

In this paper, a more efficient syndrome-weight decoding algorithm (SWDA), called the enhanced syndrome-weight decoding algorithm (ESWDA), is presented to decode up to three possible errors for the binary systematic (23, 12, 7) and (31, 16, 7) quadratic residue (QR) codes. In decoding of the QR codes, the evaluation of the error-locator polynomial in the finite field is complicated and time-consuming. To solve such a problem, the proposed ESWDA avoids evaluating the complicated error-locator polynomial, and has no need of a look-up table to store the syndromes and their corresponding error patterns in the memory. In comparison with the SWDA developed by Lin-Chang-Lee-Truong (2010), the simulation results show that the ESWDA can serve as an efficient and high-speed decoder.

Keywords:
syndrome error pattern Golay code quadratic residue code

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	Chien, R.T., “Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes,” IEEE Trans. Inform. Theory, 10(4). 357-363. Oct. 1964.
[2]	Chen, Y.H., Chien, C.H., Huang, C.H., Truong, T.K., and Jing, M.H., “Efficient decoding of systematic (23, 12, 7) and (41, 21, 9) quadratic residue codes,” J. Inform. Sci. and Eng., 26(5). 1831-1843. Sept. 2010.
[3]	Elia, M., “Algebraic decoding of the (23, 12, 7) Golay codes,” IEEE Trans. Inform. Theory, 33(1). 150-151. Jan. 1987.
[4]	Golay, M.J.E., “Notes on digital coding,” Proc. IRE, 37, 657. 1949.
[5]	Lee, C.D., “Weak general error locator polynomials for triple-error-correcting binary Golay code,” IEEE Comm. Letters, 15(8). 857-859. Aug. 2011.
[6]	Lin, T.C., Chang, H.C., Lee, H.P., Chu, S.I, and Truong, T.K., “Decoding of the (31, 16, 7) quadratic residue code,” J. Chinese Institute of Engineers, 33(4). 573-580. June 2010.
[7]	Lin, T.C., Chang, H.C., Lee, H.P., and Truong, T.K., “On the decoding of the (24, 12, 8) Golay code,” Inform. Sci., 180(23). 4729-4736. Dec. 2010.
[8]	Lin, T.C., Lee, H.P., Chang, H.C., Chu, S.I, and Truong, T.K., “High speed decoding of the binary (47, 24, 11) quadratic residue code,” Inform. Sci., 180(20). 4060-4068. Oct. 2010.
[9]	Lin, T.C., Lee, H.P., Chang, H.C., and Truong, T.K., “A cyclic weight algorithm of decoding the (47, 24, 11) quadratic residue code,” Inform. Sci., 197. 215-222. Aug. 2012.
[10]	Reed, I.S., Shih, M.T., and Truong, T.K., “VLSI design of inverse-free Berlekamp-Massey algorithm,” IEE Proc. Comput. Digit. Tech., 138(5). 295-298. Sept. 1991.
[11]	Reed, I.S., Yin, X., and Truong, T.K., “Algebraic decoding of the (32, 16, 8) quadratic residue code,” IEEE Trans. Inform. Theory, 36 (4). 876-880. July 1990.
[12]	Reed, I.S., Yin, X., Truong, T.K., and Holmes, J.K., “Decoding the (24, 12, 8) Golay code,” IEE Proc. Comput. Digit. Tech., 137(3). 202-206. May 1990.
[13]	Wicker, S.B. Error control systems for digital communication and storage, Prentice Hall, New Jersey, 1995.