On Decoding of Quadratic Residue Codes

Abstract

A binary Quadratic Residue(QR) code of length n is an (n, (n+1)/2) cyclic code over GF(2m) with generator polynomial g(x) where m is some integer. The length of this code is a prime number of the form n = 8l + 1 where l is some integer. The generator polynomial g(x) is defined by g(x)=∏_(i∈Q_n) (x-βi ) where β is a primitive nth root of unity in the finite field GF(2m) with m being the smallest positive integer such that n|2m-1 and Qn is the collection of all nonzero quadratic residues modulo n given by Qn={i│i≡j2 mod n for 1≤j≤n-1}. Algebraic approaches to the decoding of the quadratic residue (QR) codes were studied in [2], [3], [4], [5], [6] and [13]. Here, in this thesis, some new more general properties are found for the syndromes of the subclass of binary QR codes of length n = 8m + 1 or n = 8m - 1. A new algebraic decoding algorithm for the (41, 21, 9) binary QR code is presented by having the unknown syndrome S3 which is a necessary condition for decoding the (41, 21, 9) QR code.