Previous [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 10] [ 11] [ 12] [ 13] [ 14] [ 15] [ 16] [ 17] [ 18] [ 19] [ 20]

¡@

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.