¡@
Journal of Information Science and Engineering, Vol. 25 No.
4, pp. 1283-1294 (July 2009)
Decoding Binary Quadratic Residue Codes Using
the Euclidean Algorithm*
PEI-YU SHIH, WEN-KU SU, TRIEU-KIEN TRUONG AND YAOTSU CHANG+
Department of Information Engineering
+Department of Applied Mathematics
I-Shou University
Kaohshiung, 840 Taiwan
A simplified algorithm for decoding binary quadratic residue (QR) codes is developed
in this paper. The key idea is to use the efficient Euclidean algorithm to determine
the greatest common divisor of two specific polynomials which can be shown to be the
error-locator polynomial. This proposed technique differs from the previous schemes developed
for QR codes. It is especially simple due to the well-developed Euclidean algorithm.
In this paper, an example using the proposed algorithm to decode the (41, 21, 9)
quadratic residue code is given and a C++ program of the proposed algorithm has been
executed successfully to run all correctable error patterns. The simulations of this new
algorithm compared with the Berlekamp-Massey (BM) algorithm for the (71, 36, 11) and
(79, 40, 15) quadratic residue codes are shown.
Keywords:
quadratic residue code, the euclidean algorithm, unknown syndromes, known
syndromes, syndrome polynomial, error-locator polynomial, the Chien search
Retrieve PDF document (200907_20.pdf)
Received August 2, 2007; revised December 10, 2007; accepted March 13, 2008.
Communicated by Chi-Jen Lu.
* This work was presented in part at the proceedings of the International Computer Symposium, 2006, Taipei,
Taiwan, and supported by the National Science Council of Taiwan, R.O.C., under grants No. NSC 95-2221-
E-214-042 and NSC 96-2221-E-214.