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

Authors: J. Carmelo Interlando
Journal: Research Letters in Communications
 (2009)

---

## Abstract

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.


---

## Body

## 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 Heet 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.Section2 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 g(x)∈𝔽3[x] as(1)g(x)=∏i∈𝒵(x−αi)=x12+x9+x7+x6+2x5+x4+2x3+2x+1.The cyclic code generated by g(x) 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.Letc(x)=∑i=022cixi∈𝔽3[x] be the sent
code polynomial, that is, a multiple of g(x). The received polynomial, denoted by r(x)=∑i=022rixi, satisfies r(x)=c(x)+e(x) where e(x)=∑i=022eixi∈𝔽3[x] is the error
pattern. Let ν denote the
Hamming weight of e(x). Observe that e(x) can be
correctly determined provided ν≤4. Only g(x) and r(x) are known to
the receiver, which seeks to determine the most probable e(x). For any k∈ℤ, the syndrome sk is defined as sk=e(αk). It follows that s3k=sk3, for all k∈ℤ. Observe that for all k,ℓ∈ℤ, sk=sℓ whenever k≡ℓ(mod23). For any k∈𝒵,g(αk)=0, whence sk=r(αk). For this reason, the sℓ with ℓmod23∈𝒵 are called known syndromes. The other sℓ are called unknown syndromes.The set of indicesj for which ej≠0 is L={i1,…,iν}. We have 0≤i1<i2<⋯<iν≤22. The elements of L are called the
error locations, and the zj=αij∈𝔽311 are the
error-location numbers. These are the roots of the error-location
polynomial:(2)σ(x)=xν+∑j=0ν−1σν−jxj=∏j=1ν(x−zj),where the σi are the
elementary symmetric functions that in turn are related to the syndromes via
Newton's identities [7, pp. 244–245]:(3)sk+∑j=1νσjsk−j=0fork∈ℤ.The equations in (3) can be
solved efficiently when there are a sufficient number of consecutive known
syndromes. However, when decoding QR codes, typically this is not the case.
Such difficulty can be overcome by calculating one or more unknown syndromes
with the aid of the following result from [2, p. 1182], applied to the nonbinary case [8] (recall that sk=∑j=1νeijzjk, for all k∈ℤ).Theorem 1.
LetI={i1,i2,…,iν+1} and J={j1,j2,…,jν+1} be two subsets
of {0,…,22}. They define two (ν+1)×ν matrices and
one ν×ν diagonal matrix
given, respectively, by(4)XI=[z1i1z2i1⋯zνi1z1i2z2i2⋯zνi2⋮⋮⋱⋮z1iν+1z2iν+1⋯zνiν+1],XJ=[z1j1z2j1⋯zνj1z1j2z2j2⋯zνj2⋮⋮⋱⋮z1jν+1z2jν+1⋯zνjν+1],YI=[ei10⋯00ei2⋯0⋮⋮⋱⋮00⋯eiν].Then the (ν+1)×(ν+1) matrix defined
by S(I,J)=XIYIXJT is equal to(5)S(I,J)=[si1+j1si1+j2⋯si1+jν+1si2+j1si2+j2⋯si2+jν+1⋮⋮⋱⋮siν+1+j1siν+1+j2⋯siν+1+jν+1].Furthermore, detS(I,J)=0.IfS(I,J) has entries
that are unknown syndromes, then Theorem 1 can be used to determine them from
the equation detS(I,J)=0.


## 3.  Calculation ofσ(x)   for the Ternary (23,11,9)   QR Code

In this section the use of Theorem1 for decoding
nonbinary QR codes is illustrated. The focus is on the ternary QR code of
length 23 generated by g(x). The final result is an algorithm for finding σ(x), the error-location polynomial, from r(x). The decoder will determine the coefficients of σ(x), namely, the σi, from (3). Knowledge of a sequence of consecutive
syndromes is required. One choice is s22=s−1,s0,s1,s2,s3,s4,s5,s6. Observe that any syndrome sk where k∈𝒵 can be readily
computed by the decoder as r(αk). Since 5∉𝒵, s5 is the unknown
syndrome to be determined during the decoding procedure described next. Since 5⋅9≡22(mod23), one has s−1=s22=s59.LetI1={1,2,5,9,21},J1={3,4,7,11,22},I2={0,4,8,19,20}, and J2={4,5,8,12,16}. Form the matrices S(I1,J1) and S(I2,J2) as in
(5),(6)S(I1,J1)=[s4s5¯s8s12s0s5¯s6s9s13s1s8s9s12s16s4s12s13s16s20¯s8s1s2s5¯s9s20¯],S(I2,J2)=[s4s5¯s8s12s16s8s9s12s16s20¯s12s13s16s20¯s1s0s1s4s8s12s1s2s5¯s9s13].All the entries in S(I1,J1) and S(I2,J2) are known
except for s5 and s20. However, s20=s527. Therefore, f1=detS(I1,J1) and f2=detS(I1,J1) are polynomials
in a single variable, namely, s5. The next proposition was verified for each one of
the 156906 error patterns
of weights 1,2,3, and 4, using Magma [9].Proposition 1.
Forν=1,2,3,4, gcd(f1,f2) is a
first-degree polynomial in s5.The above yields the following procedure for
determiningσ(x).Step 1.
Ifs0=s1=0, then declare that ν=0 and exit.
Otherwise, proceed to Step 2.Step 2.
Letf=gcd(f1,f2). If degf=1, solve f=0 for s5 and proceed to
Step 3. Otherwise, declare that ν>4 and exit.Step 3.
Determine the coefficients of the
error-location polynomialσ(x) by solving the
following linear system for the elementary symmetric functions:(7)sk=−∑j=k−4k−1sjσk−jfork=3,4,5,6.If the linear system is
nonsingular and σ(x) has four roots x1,…,x4∈𝔽311 which satisfy xi23=1 for i=1,…,4, then declare ν=4 and exit.
Otherwise, proceed to Step 4.Step 4.
Solve the following linear system
for the elementary symmetric functions:(8)sk=−∑j=k−3k−1sjσk−jfork=4,5,6.If the linear system is
nonsingular and σ(x) has three roots x1,x2,x3∈𝔽311 which satisfy xi23=1 for i=1,2,3, then declare ν=3 and exit.
Otherwise, proceed to Step 5.Step 5.
Solve the following linear system
for the elementary symmetric functions:(9)sk=−∑j=k−2k−1sjσk−jfork=5,6.If the linear system is
nonsingular and σ(x) has two roots x1,x2∈𝔽311 which satisfy xi23=1 for i=1,2, then declare ν=2 and exit.
Otherwise, proceed to Step 6.Step 6.
If we get to this point, then
eitherν=1 or ν>4. The coefficient σ1 of σ(x) is calculated
as σ1=−s6/s5. If σ1∈𝔽311 is such that σ123=1, then ν=1. Otherwise, declare that ν>4. Exit.



---

*Source: 107432-2009-04-29.xml*