Decoding the Ternary (23, 11, 9) Quadratic Residue Code

The algebraic decoding of binary quadratic residue codes can be performed using the Peterson or the Berlekamp-Massey algorithm once certain unknown syndromes are determined or eliminated. The technique of determining unknown syndromes is applied to the nonbinary case to decode the expurgated ternary quadratic residue code of length 23. 1. Introduction Quadratic residue (QR) codes are cyclic, nominally half-rate codes, that are powerful with respect to their error-correction capabilities. Decoding QR codes is in general a difficult task, but great progress has been made in the binary case since the work of Elia [1] and He et al. [2]. Decoding algorithms for certain nonbinary QR codes were proposed by Higgs and Humphreys in [3] and [4]. In [5], decoding of QR codes is performed by embedding them in codes over cyclotomic number fields. This paper shows that one technique used to decode binary QR codes can be applied successfully to decode nonbinary QR codes. The main idea is to determine certain unknown syndromes in order to restore linearity to Newton's identities. Once this is done, either the Peterson or the Berlekamp-Massey algorithm can be used to solve the identities. The method of determining unknown syndromes was first presented by He et al. in [2] to decode the binary QR code of length 47 and subsequently to decode several other binary QR codes; see [6] and references therein. Section 2 reviews the necessary background and the latter method, with the objective of establishing notation. In Section 3, the method is illustrated on the decoding of the expurgated ternary QR code of length 23. The focus is solely on the calculation of the error-location polynomial. Error values can be found from the evaluator polynomial [7, p. 246] once the error locations are determined. 2. Background and Terminology Let ？？={1,2,3,4,6,8,9,12,13,16,18} be the set of quadratic residues of 23 and ？？ the set of quadratic nonresidues of 23. The smallest extension of ？？3=GF(3) containing ？？, a primitive twenty-third root of unity, is ？？311=GF(311). Denote the set {0}∪？？ by ？？ and define ？？(？？)∈？？3[？？] as？？(？？)=？？∈？？？？？？？？？=？？12+？？9+？？7+？？6+2？？5+？？4+2？？3+2？？+1.(1)The cyclic code generated by ？？(？？) is the expurgated ternary QR of length 23; see [7]. Its minimum Hamming distance is equal to 9, which can be verified by direct inspection. Let ∑？？(？？)=22？？=0？？？？？？？？∈？？3[？？] be the sent code polynomial, that is, a multiple of ？？(？？). The received polynomial, denoted by ∑？？(？？)=22？？=0？？？？？？？？, satisfies ？？(？？)=？？(？？)+？？(？？) where ∑？？(？？)=22？？=0？？？？？？？？∈？？3[？？] is the error