## Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes

**Hung-Peng Lee**^{1,}, **Hsin-Chiu Chang**^{1}

^{1}Department of Computer Science and Information Engineering, Fortune Institute of Technology, Kaohsiung, ROC

### Abstract

In this paper, a more efficient syndrome-weight decoding algorithm (SWDA), called the enhanced syndrome-weight decoding algorithm (ESWDA), is presented to decode up to three possible errors for the binary systematic (23, 12, 7) and (31, 16, 7) quadratic residue (QR) codes. In decoding of the QR codes, the evaluation of the error-locator polynomial in the finite field is complicated and time-consuming. To solve such a problem, the proposed ESWDA avoids evaluating the complicated error-locator polynomial, and has no need of a look-up table to store the syndromes and their corresponding error patterns in the memory. In comparison with the SWDA developed by Lin-Chang-Lee-Truong (2010), the simulation results show that the ESWDA can serve as an efficient and high-speed decoder.

### At a glance: Figures

**Keywords:** syndrome, error pattern, Golay code, quadratic residue code

*Automatic Control and Information Sciences*, 2014 2 (1),
pp 7-12.

DOI: 10.12691/acis-2-1-2

Received February 14, 2013; Revised January 17, 2014; Accepted February 09, 2014

**Copyright**© 2013 Science and Education Publishing. All Rights Reserved.

### Cite this article:

- Lee, Hung-Peng, and Hsin-Chiu Chang. "Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes."
*Automatic Control and Information Sciences*2.1 (2014): 7-12.

- Lee, H. , & Chang, H. (2014). Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes.
*Automatic Control and Information Sciences*,*2*(1), 7-12.

- Lee, Hung-Peng, and Hsin-Chiu Chang. "Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes."
*Automatic Control and Information Sciences*2, no. 1 (2014): 7-12.

Import into BibTeX | Import into EndNote | Import into RefMan | Import into RefWorks |

### 1. Introduction

The triple-error-correcting binary QR codes include (23, 12, 7) QR code and (31, 16, 7) QR code, respectively. The binary (23, 12, 7) QR code is also called the binary Golay code, which is a perfect code. The Golay code is first introduced by Golay in 1949 ^{[4]}. If an overall parity check is used, the rate is exactly 1/2, so that most of the known QR codes are the best-known codes. Among them, the extended (24, 12, 8) Golay code was utilized to act as an error control on the Voyager I and II spacecraft mission, providing clear remote pictures of Jupiter and Saturn ^{[13]}.

Several algebraic decoding algorithms (ADAs) had been developed to decode the binary Golay code ^{[3, 12]}. The key idea of decoding the Golay code by using ADA is to compute the unknown syndrome for determining the coefficients of the error-locator polynomial. One of the representative methods is inverse-free Berlekamp-Massey algorithm ^{[10]}. In ^{[11]}, Reed *et al*. developed the ADA of the extended (32, 16, 8) QR code with reducible generator polynomial. However, such an algorithm is quiet complicated. Lin *et al*. ^{[6]} thus proposed a modified ADA to reduce the decoding complexity. For ADAs, once the coefficients of the error-locator polynomial are obtained, the error positions can be determined by using the Chien search algorithm ^{[1]}, which is an exhaustive search over all the elements in the finite field. In the decoding procedure of ADAs, this step is the most time-consuming and need plenty of multiplication and division operations over the finite field.

Most recently, table-lookup decoding algorithms (TLDAs) ^{[2, 7, 9]} have played an important role in forward error correction. These types of decoders are efficient with minimum decoding delay; however, the TLDAs require a memory space in the decoder chip and increase the decoding cost rapidly when the code length is large. The SWDA proposed by Lin *et al*. ^{[7]} used the refined lookup table (RLT) to decode the triple-error-correcting binary Golay code and (31, 16, 7) QR code. For decoding the Golay code, the RLT consists of 42 syndromes and their corresponding coset leaders, and it only needs 168 bytes memory size. For decoding the (31, 16, 7) QR code, the RLT consists of 72 syndromes and their corresponding coset leaders, and it only requires 288 bytes memory size.

In this paper, the proposed ESWDA has faster decoding speed than the SWDA, and it does not need a memory size to store the lookup table. The key idea of the proposed ESWDA is based on the weight of syndrome difference between the syndrome of the received word and the row vector of the transpose of the parity-check matrix. Therefore, the error cases can be swiftly determined. The application of the syndrome weight and the syndrome difference can constitute a high-speed decoding algorithm. Moreover, no complicated computation in the finite field is required in the proposed ESWDA. Two examples demonstrate the decoding procedure of the proposed ESWDA. The proposed ESWDA is applicable to decode other cyclic codes such as the binary (15, 5, 7) BCH code; however, the decoding steps of the proposed ESWDA need to make some slight adjustments. The decoding steps of the binary (15, 5, 7) BCH code are demonstrated in a simple example. Computer simulation result shows that the decoding time of the proposed ESWDA is superior to the SWDA.

The remainder of this paper is organized as follows: The background of the binary QR codes is briefly reviewed in Section 2. The proposed ESWDA is described in Section 3. In Section 4, we use three examples to demonstrate the proposed ESWDA. Computer simulation results of the proposed ESWDA and the SWDA are given in Section 5. Finally, this paper concludes with a brief summary in Section 6.

### 2. Background of the Binary QR Codes

The binary QR codes are a nice family of linear cyclic codes. Let (*n*, (*n*+1)/2, *d*) denote the binary QR codes with generator polynomial *g*(*x*) over *GF*(2). The length of this code is a prime number of the form *n* = 1, where *l* is some integer. Also, let* k* = (*n*+1)/2 denote the message length or information length, and *d* denote the minimum Hamming distance of the code. The set *Q*_{n} of quadratic residues modulo *n* is the set of nonzero squares modulo *n*; that is, *Q*_{n}* *= {*j *| *j *≡ *x*^{2} mod *n*, 1 ≤ *x *≤ *n*−1}. If *n* = 23, then its quadratic residue set is *Q*_{23} = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}. If *n* = 31, then its quadratic residue set is *Q*_{31} = {1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 20, 25, 28}.

Let the symbols *C*_{23} and *C*_{31} denote the binary Golay code and binary (31, 16, 7) QR code, respectively. Let *α* be a root of primitive polynomial *p*_{r}_{23}(*x*) = *x*^{11} + *x*^{2} + 1. If *α* = 2, then the 11 roots of *p*_{r}_{23}(*x*) are *α* = 2, *α*^{2} = 4, *α*^{2}^{2} = 16, *α*^{2}^{3} = 256, *α*^{2}^{4} = 160, *α*^{2}^{5} = 1064, *α*^{2}^{6} = 1605, *α*^{2}^{7} = 158, *α*^{2}^{8} = 380, *α*^{2}^{9} = 1530, *α*^{2}^{10} = 1987. Let the element = *α*^{u} be a primitive 23rd root of unity in *GF*(2^{ll}), where *u* = (2^{11} – 1) / 23 = 89. Therefore, = ^{89} = 322, where 322 is the decimal representation of . The total 23 roots are listed in Table 1.

The generator polynomial of *C*_{23} is defined by

(1) |

Now let α be a generator of the multiplicative group of all nonzero elements in *GF*(2^{5}). Then, the element β* *= *α*^{u}, where *u* = (2^{5 }− 1)/31 = 1. The *x*^{31}–1 can be factored into seven primitive minimal irreducible polynomials; that is, *x*^{31}–1 = (*x*^{5} + *x*^{2} + 1)(*x*^{5} + *x*^{4} + *x*^{2} + *x* + 1)(*x*^{5} + *x*^{3} + *x*^{2} + *x* + 1)(*x*^{5} + *x*^{4} + *x*^{3} + *x*^{2} + 1)(*x*^{5} + *x*^{3} + 1)(*x*^{5} + *x*^{4} + *x*^{3} + *x* + 1)(*x* + 1). Then, the generator polynomial of *C*_{31} is reducible, and is defined by

(2) |

where *g*_{1}(*x*), *g*_{5}(*x*), and *g*_{7}(*x*) are the minimal polynomials of *x*^{31}–1. That is, *g*_{r}(*x*) = (*x* − *ß*^{r})(*x* − *ß*^{2}^{r})…(*x* − *ß*^{2}^{4}^{r}) and *ß*^{2}^{i}^{r} ∈ *GF*(2^{5}) for 0 ≤ *i* ≤ 4 are the roots of *g*_{r}(*x*), where *r* = 1, 5, and 7. If *α* = 2, then the total 31 roots of *x*^{31} − 1 are listed in Table 2.

Because the minimum Hamming distance of *C*_{23} and *C*_{3}_{1} is *d* = 7, the inequality 2*v** *+ 1 ≤ 7 is valid, where *v* is the actual number of errors to be corrected. Hence, the error-correcting capability is , where denotes the greatest integer less than or equal to *x*. The codeword is a multiple of generator polynomial *g*(*x*); that is, , where *C*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *n*–1, and denotes the message polynomial, where *m*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *k*–1. Let be the parity-check polynomial, where *p*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *n*–*k*–1. Let be the parity-check polynomial, where *p*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *n*–*k*–1. Let *p*(*x*) ≡ *m*(*x*)*x*^{n}^{–}^{k} mod *g*(*x*), then one obtains *m*(*x*)*x*^{n}^{–}^{k} = *q*(*x*)*g*(*x*) + *p*(*x*). The term (*p*(*x*) + *m*(*x*)*x*^{n}^{–}^{k}), which is a multiple of *g*(*x*), is a codeword polynomial given by

(3) |

where *c*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *n*–1. In this paper, the systematic encoding method is utilized. Now, let a codeword be transmitted through an additive white Gaussian noise (AWGN) channel to obtain a received word with the form *r*(*x*) = *c*(*x*) + *e*(*x*), where *e*(*x*) is the polynomial of the received error pattern expressed as , where *e*_{i} ∈ *GF*(2) for 0 ≤ *i* ≤ *n*–1. The syndromes polynomial is expressed as .

To simplify the polynomial expressions mentioned above, let the message, codeword, error pattern, received word, and syndrome polynomials be expressed as the binary vector forms , , , , and , respectively. The systematic codeword of the vector form is given by

(4) |

where **G** is called the systematic generator matrix. Let **P** be a *k*(*n*–*k*) matrix and **I**_{k} be a *k**k* identity matrix, and **G** can be expressed as

(5) |

The parity-check matrix **H** can be expressed as , where **P**^{T} denotes the (*n*–*k*)*k* transpose matrix of **P**. The vector form of the syndrome is defined by

(6) |

where **H**^{T} denotes the *n*(*n*–*k*) transpose matrix of **H**; that is, **H**^{T} can be expressed as

(7) |

For *C*_{23}, **H**^{T} has the following form:

(8) |

### 3. Decoding Algorithm and Theorems

In this section, the proposed ESWDA is used to decode the *C*_{23} and *C*_{31}. For the development of the proposed ESWDA, the following definition, theorem and corollary given in Lin *et al*. ^{[8]} are needed.

**Definition**** ****1****:** The Hamming weight of a binary vector **a** is denoted by *w*(**a)**, and the Hamming distance between **a** and **b** is denoted by *d*(**a**, **b**) = *w*(**a** + **b)**.

**Theorem 1****:** Let **a** = (*a*_{0} … *a*_{1} *a*_{n}_{-1}) and **b** = (*b*_{0} … *b*_{1} *b*_{n}_{-1}) be two binary vectors, then

(9) |

**Corollary 1****:** If *a*_{i}*b*_{i} = 0 for 1 ≤ *i* ≤ *n*, then

(10) |

The following Theorem 2 is useful to compute the syndrome of the received word when the received word shifts one bit to the left. For more detailed proof of this theorem, see [13, p118].

**Theorem 2:** Let *s*(*x*) be the syndrome polynomial corresponding to a received polynomial *r*(*x*). Also, let *r*^{(1)}(*x*) be the polynomial obtained by cyclically shifting the coefficients of *r*(*x*) one bit to the left. Then the remainder obtained when dividing *xs*(*x*) by *g*(*x*) is the syndrome *s*^{(1)}(*x*) corresponding to *r*^{(1)}(*x*).

However, for each cyclical shift of the received word, we have to divide *xs*(*x*) by *g*(*x*). If the syndrome cyclically shifts many times, then the syndrome computation is rather time-consuming for dividing *xs*(*x*) by *g*_{n}(*x*) many times. The following theorem provides an efficient method to compute **s**^{(}^{i}^{)} for 0 ≤ *i* ≤ *n*–1, and it can save a lot of computational time.

**Theorem**** 3****:** For the binary QR codes, let *r*_{j} be an element of **r** and **h**_{j} be the *j*th row vector of **H**^{T} for 0 ≤ *j* ≤ *n*–1. Then the syndrome **s**^{(}^{i}^{)} of **r**^{(}^{i}^{)} for 0 ≤ *i* ≤ *n*–1 has the form

(11) |

where the suffix [*x*] of **h** denotes *x* mod *n*.

**Proof:** Let* ***r** = (*r*_{0},…,*r*_{n}_{-1}) and **r**^{(}^{i}^{)} = (*r*_{i},…, *r*_{n}_{-1},* r*_{0},…, *r*_{i}_{-1}) for 0 ≤ *i* ≤ *n*–1. By (7), we have **s**^{(}^{i}^{)} = **r**^{(}^{i}^{)}**H**^{T} = = . The proof is thus completed.

**The****orem 3****:** reveals that the syndrome of **r**^{(}^{i}^{)} can be fast computed by the vector addition. Theorem 4 also provides an efficient method to simplify the decoding step by using the syndrome weight. For a detailed proof, see ^{[8]}.

Theorem 3 reveals that the syndrome of **r**^{(}^{i}^{)} can be fast computed by the vector addition. Theorem 4 also provides an efficient method to simplify the decoding step by using the syndrome weight. For a detailed proof, see ^{[8]}.

**Theorem 4****:** For the binary QR codes, it is assumed that there are *v* errors in the received word, where 1 ≤ *v* ≤ *t*. All *v* errors are in the parity-check bits if and only if the weight of syndrome *w*(* s*) =

*v*.

By using Theorem 4, we can develop the following useful theorem.

**Theorem 5** For the binary QR codes, if *v* errors are in the information bits of the received word, where 1 ≤ *v* ≤ *t* and *t* = , then the weight of the corresponding syndrome polynomial or syndrome vector satisfies

(12) |

**Proof**: Let error polynomial *e*(*x*) present the *v* errors in the information bits; that is, *w*(*e*(*x*)) = *v*. Since *s*(*x*) ≡ *r*(*x*) ≡ *e*(*x*) (mod *g*(*x*)), we have *e*(*x*) + *s*(*x*) ≡ 0 (mod *g*(*x*)). This implies that *e*(*x*) + *s*(*x*) is a codeword and hence the codeword must satisfy *w*(*e*(*x*) + *s*(*x*)) ≥ *d*. By Corollary 1, *w*(*e*(*x*) + *s*(*x*)) = *w*(*e*(*x*)) + *w*(*s*(*x*)) ≥ *d* and then *w*(*s*(*x*)) ≥ *d* – *w*(*e*(*x*)). Thus, the weight of the syndrome polynomial satisfies *w*(*s*(*x*)) ≥ *d*–*v* or *w*(* s*) ≥ (

*d*–

*v*). The proof is thus completed.

Given a received word **r**, the syndrome of **r**^{(}^{i}^{)} can be fast computed by Theorem 3. According to Theorem 4, if 1 ≤ *w*(* s*) ≤ 3, then the error positions are in the parity-check bits of

**r**. If 1 ≤

*w*(

**s**

^{(}

^{n}

^{-}

^{k}

^{)}) ≤ 3, then the error positions are in the information bits of

**r**. Let

**h**

_{i}denote the

*i*th row vector of

**H**

^{T}, where 0 ≤

*i*≤

*n*–1. Also let

**sd**

_{w}denote the syndrome difference between the syndromes of

**r**and

**h**

_{i}in each decoding step

*w*. By using the weight of

**sd**

_{w}, the error cases can be quickly determined. Let

**u**

_{0}= (1, 0,…, 0) be a

*k*-tuples unit vector and

**u**

_{j}has only one nonzero component at the

*j*th position, where 0 ≤

*j*≤

*k*–1. By using these properties, the proposed ESWDA can be constructed.

Let upper case P, C, and H denote the error position in the parity-check bits, center bit, and information bits of * r*, respectively. For

*C*

_{23}or

*C*

_{31}, there are 15 error cases (P, PP, PPP, H, HH, HHH, C, PC, PH, PPC, PPH, PHH, CH, CHH, and PCH), which cover all and error patterns. If

*w*(

*) = 0, then*

**s****r**has no error. If 1 ≤

*w*(

*) ≤ 3 or 1 ≤*

**s***w*(

**s**

^{(}

^{n}

^{-}

^{k}

^{)}) ≤ 3, then there are 6 error cases (P, PP, PPP, H, HH, and HHH). Let the syndrome difference

**sd**

_{3}= (

**s**–

**h**

_{i}) for

*n*–

*k*≤

*i*≤

*n*–1. If 0 ≤

*w*(

**sd**

_{3}) ≤ 2, then there are 5 error cases (C, PC, PH, PPC, and PPH). Let the syndrome difference

**sd**

_{4}= (

**s**

^{(}

^{n}

^{-}

^{k}

^{)}–

**h**

_{i}) for

*n*–

*k*≤

*i*≤

*n*–1. If

*n*–

*k*≤

*i*≤

*n*–2 and

*w*(

**sd**

_{4}) = 2, then there is only 1 error case (PHH). If

*i*=

*n*–1 and 1 ≤

*w*(

**sd**

_{4}) ≤ 2, then there are 2 error cases (CH and CHH). Let the syndrome difference

**sd**

_{5}= ((

**s**–

**h**

_{n}

_{-}

_{k})–

**h**

_{i}) for

*k*≤

*i*≤

*n*–1. If

*w*(

**sd**

_{5}) = 1, then there is only 1 error case (PCH). The decoding steps of the proposed ESWDA work as follows:

1). (No error, P, PP, and PPP cases.) By Theorem 3, compute **s** and *w*(**s**). If 0 ≤ *w*(* s*) ≤ 3, then the information vector is

**m**= (

*r*

_{n}

_{-}

_{k},…,

*r*

_{n}

_{-1}). Go to step 6.

2). (H, HH, and HHH cases.) By Theorem 3, compute **s**^{(}^{n}^{-}^{k}^{)} and *w*(**s**^{(}^{n}^{-}^{k}^{)}). If 1 ≤ *w*(**s**^{(}^{n}^{-}^{k}^{)}) ≤ 3, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + (**s**^{(}^{n}^{-}^{k}^{)} >>1), where “>>” denotes the logical right shift operator in programming or the extension by zeros on the right in mathematics. Go to step 6.

3). (C, PC, PH, PPC, and PPH cases.) Compute the syndrome difference **sd**_{3} = (**s**–**h**_{i}) for *n*–*k* ≤ *i* ≤ *n*–1 and *w*(**sd**_{3}). If 0 ≤ *w*(**sd**_{3}) ≤ 2, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + **u**_{i}_{-(}_{n}_{-}_{k}_{)}. Go to step 6.

4). (PHH, CH, and CHH cases) Compute the syndrome difference **sd**_{4} = (**s**^{(}^{n}^{-}^{k}^{)}–**h**_{i}) for *n*–*k* ≤ *i* ≤ *n*–1 and *w*(**sd**_{4}). If *n*–*k* ≤ *i* ≤ *n*-2 and *w*(**sd**_{4}) = 2, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + (**sd**_{4} >>1). If *i* = *n*–1 and 1 ≤ *w*(**sd**_{4}) ≤ 2, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) +** u**_{0} + (**sd**_{4} >> 1). Go to step 6.

5). (PCH case.) Compute the syndrome difference **sd**_{5} = ((**s**–**h**_{n}_{-}_{k})–**h**_{i}) for *k* ≤ *i* ≤ *n*–1 and *w*(**sd**_{5}). If *w*(**sd**_{5}) = 1, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + **u**_{0} + **u**_{i}_{-(}_{n}_{-}_{k}_{)}. Go to step 6.

6). Stop.

Table 3 lists all the 15 error cases and the number of error patterns in each decoding steps of the proposed ESWDA. The flowchart of the proposed ESWDA is shown in Figure 1.

**Fig**

**ure**

**1**

**.**Flowchart of the proposed ESWDA

### 4. Examples

In this section, three examples are presented to illustrate the proposed ESWDA. Example 1 and 2 show the decoding steps for the binary systematic Golay code. Example 3 shows the decoding steps for the binary systematic (15, 5, 7) BCH code, denoted by *C*_{15}; however, the decoding steps of the proposed ESWDA have to make some slight adjustments.

**Example 1:** Let a message **m**** **= (000110101010) be encoded into a *C*_{23} codeword **c**** **= (11011010100000110101010). If the received word **r** = (11011010100010111001010), then the error pattern **e** = (00000000000010001100000), which means a HHH error case. The decoding steps are shown below.

1). Compute **s** = (10101100100) and *w*(**s**) = 5. Since *w*(**s**) > 3, go to step 2.

2). Compute **s**^{(11)} = (10001100000) and *w*(**s**^{(11)}) = 3 ≤ 3. The corrected information word **m** = (010111001010) + (010001100000) = (000110101010). Go to stop.

**Example 2:** This example demonstrates the worst decoding case. Let a message **m**** **= (000110101010) be encoded into a *C*_{23} codeword **c**** **= (11011010100000110101010). If the received word **r** = (01011010100100110101011), then the error pattern **e** = (10000000000100000000001), which means a PCH error case. The decoding steps are shown below.

1). Compute * s* = (11001001111) and

*w*(

*) = 7. Since*

**s***w*(

*) > 3, go to step 2.*

**s**2). Compute **s**^{(11)} = (01001001110) and *w*(**s**^{(11)}) = 5. Since *w*(**s**^{(11)}) > 3, go to step 3.

3). Compute **sd**_{3} = (**s**–**h**_{i}) for 11 ≤ *i* ≤ 22 and *w*(**sd**_{3}).

**sd**_{3} = (**s**–**h**_{11}) = (11001001111) – (11000111010) = (00001110101).* w*(**sd**_{3}) = 5.

**sd**_{3} = (**s**–**h**_{12}) = (11001001111) – (01100011101) = (10101010010).* w*(**sd**_{3}) = 5.

…

**sd**_{3} = (**s**–**h**_{21}) = (11001001111) – (10010011111) = (01011010000).* w*(**sd**_{3}) = 4.

**sd**_{3} = (**s**–**h**_{22}) = (11001001111) – (10001110101) = (01000111010).* w*(**sd**_{3}) = 5.

Since every* w*(**sd**_{3}) > 2, go to step 4.

4).Compute **sd**_{4} = (**s**^{(11)}–**h**_{i}) for 11 ≤ *i* ≤ 22 and *w*(**sd**_{4}).

**sd**_{4} = (**s**^{(11)}–**h**_{11}) = (01001001110) – (11000111010) = (10001110100).* w*(**sd**_{4}) = 5.

**sd**_{4} = (**s**^{(11)}–**h**_{12}) = (01001001110) – (01100011101) = (00101010011).* w*(**sd**_{4}) = 5.

…

**sd**_{4} = (**s**^{(11)}–**h**_{21}) = (01001001110) – (10010011111) = (11011010001).* w*(**sd**_{4}) = 6.

**sd**_{4} = (**s**^{(11)}–**h**_{22}) = (01001001110) – (10001110101) = (11000111011).* w*(**sd**_{4}) = 7.

Since every *w*(**sd**_{4}) > 2, go to step 5.

5).Compute **sd**_{5} = ((**s**–**h**_{11})–**h**_{i}) = (00001110101) – **h**_{i} for 12 ≤ *i* ≤ 22 and *w*(**sd**_{5}).

**sd**_{5} = (**s**–**h**_{11})–**h**_{12} = (00001110101) – (11000111010) = (11001001111). *w*(**sd**_{5}) = 7.

**sd**_{5} = (**s**–**h**_{11})–**h**_{13} = (00001110101) – (11110110100) = (11111000001). *w*(**sd**_{5}) = 6.

…

**sd**_{5}_{ }= (**s**–**h**_{11})–**h**_{21} = (00001110101) – (10010011111) = (10011101010). *w*(**sd**_{5}) = 6.

**sd**_{5 }= (**s**–**h**_{11})–**h**_{22} = (00001110101) – (10001110101) = (10000000000). *w*(**sd**_{5}) = 1.

Since *w*(**sd**_{5}) = 1, the corrected information word **m** = (*r*_{11},…, *r*_{22}) + **u**_{0} + **u**_{22-11} = (100110101011) + (100000000000) + (000000000001) = (000110101010). Go to stop.

PCH case is the worst case; however, only 121 error patterns, namely 5.91%, will enter step 5.

**Example 3:** Let a message **m**** **= (00011) be encoded into a codeword of *C*_{15} with *g*(*x*) = *x*^{10} + *x*^{9} + *x*^{8} + *x*^{6} + *x*^{5} + *x*^{2} + 1, and obtain the codeword **c**** **= (101100101000011). If the received word **r** = (101110101011011), then the error pattern **e** = (000010000011000), which means a PHH error case. First, the decoding steps of the proposed ESWDA mentioned in Section 3 can be slightly adjusted as follows:

1). (No error, P, PP, and PPP cases.) By Theorem 3, compute **s** and *w*(**s**). If 0 ≤ *w*(**s**) ≤ 3, then the information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}), and go to step 5.

2). (H, HH, HHH, PH, PPH, and PHH cases.) By Theorem 3, compute **s**^{(}^{n}^{-}^{k}^{)} and *w*(**s**^{(}^{n}^{-}^{k}^{)}). If 1 ≤ *w*(**s**^{(}^{n}^{-}^{k}^{)}) ≤ 3, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + (**s**^{(}^{n}^{-}^{k}^{)} & (11111)), where the notation “&” denotes the bitwise AND operator, and go to step 5.

3). (PH and PPH cases.) Compute the syndrome difference **sd**_{3} = (**s**–**h**_{i}) for *n*–*k* ≤ *i* ≤ *n*–1 and *w*(**sd**_{3}). If 0 ≤ *w*(**sd**_{3}) ≤ 2, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + **u**_{i}_{-(}_{n}_{-}_{k}_{)}, and go to step 5.

4). (PHH case) Compute the syndrome difference **sd**_{4} = (**s**^{(}^{n}^{-}^{k}^{)}–**h**_{i}) for *n*–*k* ≤ *i* ≤ *n*–1 and *w*(**sd**_{4}). If *w*(**sd**_{4}) = 2, then the corrected information vector is **m** = (*r*_{n}_{-}_{k},…, *r*_{n}_{-1}) + (**sd**_{4} & (11111)), and go to step 5.

5). Stop.

For this code, there are 9 error cases. Table 4 lists all the 9 error cases and the number of error patterns in each decoding steps.

The decoding steps are shown below.

1). Compute **s** = (1001001011) and *w*(**s**) = 5. Since *w*(**s**) > 3, go to step 2.

2). Compute **s**^{(}^{5}^{)} = (1101111101) and *w*(**s**^{(}^{5}^{)}) = 8. Since *w*(**s**^{(}^{5}^{)}) > 3, go to step 3.

3). Compute **sd**_{3} = (**s**–**h**_{i}) for 10 ≤ *i* ≤ 14 and *w*(**sd**_{3}).

**sd**_{3} = (**s**–**h**_{11}) = (1001001011) – (1101100101) = (0100101110).* w*(**sd**_{3}) = 5.

**sd**_{3} = (**s**–**h**_{12}) = (1001001011) – (0110101111) = (1111100100).* w*(**sd**_{3}) = 6.

**sd**_{3} = (**s**–**h**_{13}) = (1001001011) – (1101011110) = (0100010101).* w*(**sd**_{3}) = 4.

**sd**_{3} = (**s**–**h**_{14}) = (1001001011) – (0111011001) = (1110010010).* w*(**sd**_{3}) = 5.

**sd**_{3} = (**s**–**h**_{15}) = (1001001011) – (1110110010) = (0111111001).* w*(**sd**_{3}) = 7.

Since every* w*(**sd**_{3}) > 2, go to step 4.

4). Compute **sd**_{4} = (**s**^{(}^{5}^{)}–**h**_{i}) for 10 ≤ *i* ≤ 14 and *w*(**sd**_{4}).

**sd**_{4} = (**s**^{(}^{5}^{)}–**h**_{11}) = (1101111101) – (1101100101) = (0000011000).* w*(**sd**_{4}) = 2.

Since *w*(**sd**_{4}) = 2, the corrected information word **m** = (*r*_{1}_{0},…, *r*_{14}) + (**sd**_{4} & (11111)) = (11011) + ((0000011000) & (11111)) = (00011). Go to stop.

### 5. Simulation Results

The proposed ESWDA has been programmed in C++ language. On an Intel Q6600 PC with XP operating system, all 2^{k} codewords with all error patterns were created to check every possible error pattern of *C*_{15}, *C*_{23}, and *C*_{3}_{1}, respectively. In other words, the error patterns of *C*_{15}, *C*_{23}, and *C*_{3}_{1} are , , and , respectively. The decoding times of the proposed ESWDA and the SWDA are shown in the Table 5, Table 6, and Table 7, respectively. For *v* = 1, it means that one error of that code input to the decoder, and for the average decoding time, it means that all the error patterns of that code input to the decoder. In these three tables, the average decoding time of the proposed ESWDA is about 10.6 times, 19.6 times, and 4 times faster than the SWDA, respectively. The memory requirements of the two algorithms are also shown in Table 5, Table 6, and Table 7, respectively. It is obvious that the proposed ESWDA significantly reduces decoding time with the increase of the code length.

#### Table 7. Comparison of the decoding time (in *µ*s) and memory requirement (in bytes) for the (15, 5, 7) BCH code between two algorithms

### 6. Conclusions

Binary QR codes are well known for their good features. A high-speed and efficient ESWDA is developed to decode *C*_{15}, *C*_{23}, and *C*_{31}. The proposed ESWDA neither stores large lookup table in the memory nor computes complicated algebraic computations. By using Theorem 3, Theorem 4, Theorem 5, and the weight of **sd**_{w}, the error cases can be quickly identified and corrected. Therefore, the proposed ESWDA is a very efficient and low-cost decoder for decoding the triple-error-correcting QR codes. The proposed ESWDA can be extended to decode other QR codes or BCH codes; however, the decoding steps of the proposed ESWDA need to make some slight adjustments.

### References

[1] | Chien, R.T., “Cyclic decoding procedure for the Bose-Chaudhuri-Hocquenghem codes,” IEEE Trans. Inform. Theory, 10(4). 357-363. Oct. 1964. | ||

In article | CrossRef | ||

[2] | Chen, Y.H., Chien, C.H., Huang, C.H., Truong, T.K., and Jing, M.H., “Efficient decoding of systematic (23, 12, 7) and (41, 21, 9) quadratic residue codes,” J. Inform. Sci. and Eng., 26(5). 1831-1843. Sept. 2010. | ||

In article | |||

[3] | Elia, M., “Algebraic decoding of the (23, 12, 7) Golay codes,” IEEE Trans. Inform. Theory, 33(1). 150-151. Jan. 1987. | ||

In article | CrossRef | ||

[4] | Golay, M.J.E., “Notes on digital coding,” Proc. IRE, 37, 657. 1949. | ||

In article | |||

[5] | Lee, C.D., “Weak general error locator polynomials for triple-error-correcting binary Golay code,” IEEE Comm. Letters, 15(8). 857-859. Aug. 2011. | ||

In article | CrossRef | ||

[6] | Lin, T.C., Chang, H.C., Lee, H.P., Chu, S.I, and Truong, T.K., “Decoding of the (31, 16, 7) quadratic residue code,” J. Chinese Institute of Engineers, 33(4). 573-580. June 2010. | ||

In article | CrossRef | ||

[7] | Lin, T.C., Chang, H.C., Lee, H.P., and Truong, T.K., “On the decoding of the (24, 12, 8) Golay code,” Inform. Sci., 180(23). 4729-4736. Dec. 2010. | ||

In article | CrossRef | ||

[8] | Lin, T.C., Lee, H.P., Chang, H.C., Chu, S.I, and Truong, T.K., “High speed decoding of the binary (47, 24, 11) quadratic residue code,” Inform. Sci., 180(20). 4060-4068. Oct. 2010. | ||

In article | CrossRef | ||

[9] | Lin, T.C., Lee, H.P., Chang, H.C., and Truong, T.K., “A cyclic weight algorithm of decoding the (47, 24, 11) quadratic residue code,” Inform. Sci., 197. 215-222. Aug. 2012. | ||

In article | CrossRef | ||

[10] | Reed, I.S., Shih, M.T., and Truong, T.K., “VLSI design of inverse-free Berlekamp-Massey algorithm,” IEE Proc. Comput. Digit. Tech., 138(5). 295-298. Sept. 1991. | ||

In article | CrossRef | ||

[11] | Reed, I.S., Yin, X., and Truong, T.K., “Algebraic decoding of the (32, 16, 8) quadratic residue code,” IEEE Trans. Inform. Theory, 36 (4). 876-880. July 1990. | ||

In article | CrossRef | ||

[12] | Reed, I.S., Yin, X., Truong, T.K., and Holmes, J.K., “Decoding the (24, 12, 8) Golay code,” IEE Proc. Comput. Digit. Tech., 137(3). 202-206. May 1990. | ||

In article | CrossRef | ||

[13] | Wicker, S.B. Error control systems for digital communication and storage, Prentice Hall, New Jersey, 1995. | ||

In article | |||