Dear Label_Name,

Greetings! I hope you are well.

I am writing on behalf of an international publishing house, Science and Education Publishing, USA (http://www.sciepub.com).

Science and Education Publishing (SciEP) is a multidisciplinary open access publisher of Journals covering the fields of Science, Technology and Medicine. All SciEP publications are subject to high-quality peer review, editorial and production processes and are freely available online.

Welcome to the April, 2013 edition of SciEP newsletter, providing monthly summaries of articles on science & education related topics of interest to scientist and professionals. The mission of our journals is to provide an open access forum for publishing new findings on issues pertinent to scientific and academic field. We also invite you to submit original research papers, review articles, short reports, or case studies are considered for publication in our Multidisciplinary Journals.

American Journal of Public Health Research
DOI: 10.12691/ajphr-1-1-3

The Implementation of a Tele-Homecare System with Service Oriented Architecture and HL7 Message Transmission Standard
Ching-Sung Wang

American Journal of Medical and Biological Research
DOI: 10.12691/ajmbr-1-1-2

The Influence of Ethanol on Pyruvate Kinases Activity in Vivo, in Vitro, in Silico
Lelevich Sergey Vladimirovich, Khrustalev Vladislav Victorovich, Barkovsky Eugene Victorovich, Shedogubova Tatyana Aleksandrovna

American Journal of Medical Sciences and Medicine
DOI: 10.12691/ajmsm-1-1-1

Clinical and Histological Features in Wegener Granulomatosis
Li Cavoli Gioacchino, Passantino Rita, Bono Luisa, Tortorici Calogera, Ferrantelli Angelo, Giammarresi Carlo, Rotolo Ugo

American Journal of Infectious Diseases and Microbiology
DOI: 10.12691/ajidm-1-1-2

The Curse of Lymphatic Filariasis: Would the Continual Use of Diethylcarbamazine Eliminate this Scourge in Papua New Guinea?
Anne Lanham, Lillian Mwanri

We have released issues of some journals on February 2013.
American Journal of Public Health Research
American Journal of Medical Sciences and Medicine
American Journal of Medical and Biological Research
American Journal of Pharmacological Sciences
American Journal of Clinical Medicine Research
American Journal of Nursing Research
American Journal of Cancer Prevention
American Journal of Medicine Studies
American Journal of Infectious Diseases and Microbiology
American Journal of Cardiovascular Disease Research
American Journal of Biomedical Research
American Journal of Mechanical Engineering
American Journal of Microbiological Research
Journal of Preventive Medicine
American Journal of Food and Nutrition
American Journal of Hypertension Research
American Journal of Sports Science and Medicine
Journal of Cancer Research and Treatment
American Journal of Zoological Research
Journal of Biomedical Engineering and Technology
American Journal of Microbiological Research
Biomedical Science and Engineering

We are pleased to announce that submissions are now being accepted for peer review for all the journals across all our subject areas in SciEP.

Please submit your manuscript via our online submission system:
http://www.sciepub.com/author/signin

To unsubscribe from our mailing list, please click on the following link: unsubscribe

I am looking forward to hearing from you.

Kind regards,

David Rain
Email:join@sciepub.com
Science and Education Publishing (http://www.sciepub.com)

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

Hung-Peng Lee*, Hsin-Chiu Chang

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.

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

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

Citation: Hung-Peng Lee, Hsin-Chiu Chang, Decoding of the Triple-Error-Correcting Binary Quadratic Residue Codes. Automatic Control and Information Sciences, 2 (1). 7-12. January 2014. doi:10.12691/acis-2-1-2

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 Qn of quadratic residues modulo n is the set of nonzero squares modulo n; that is, Qn = {j | j ≡ x² mod n, 1 ≤ x ≤ n−1}. If n = 23, then its quadratic residue set is Q₂₃ = {1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18}. If n = 31, then its quadratic residue set is Q₃₁ = {1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 20, 25, 28}.

Let the symbols C₂₃ and C₃₁ denote the binary Golay code and binary (31, 16, 7) QR code, respectively. Let α be a root of primitive polynomial pr₂₃(x) = x¹¹ + x² + 1. If α = 2, then the 11 roots of pr₂₃(x) are α = 2, α² = 4, α²² = 16, α²³ = 256, α²⁴ = 160, α²⁵ = 1064, α²⁶ = 1605, α²⁷ = 158, α²⁸ = 380, α²⁹ = 1530, α²¹⁰ = 1987. Let the element = αu be a primitive 23rd root of unity in GF(2ll), where u = (2¹¹ – 1) / 23 = 89. Therefore, = ⁸⁹ = 322, where 322 is the decimal representation of . The total 23 roots are listed in Table 1.

Table 1. The total 23 roots of x²³ – 1 (in decimal number)

The generator polynomial of C₂₃ is defined by

[picture] | (1)

Now let α be a generator of the multiplicative group of all nonzero elements in GF(2⁵). Then, the element β = αu, where u = (25 − 1)/31 = 1. The x³¹–1 can be factored into seven primitive minimal irreducible polynomials; that is, x³¹–1 = (x⁵ + x² + 1)(x⁵ + x⁴ + x² + x + 1)(x⁵ + x³ + x² + x + 1)(x⁵ + x⁴ + x³ + x² + 1)(x⁵ + x³ + 1)(x⁵ + x⁴ + x³ + x + 1)(x + 1). Then, the generator polynomial of C₃₁ is reducible, and is defined by

[picture] | (2)

where g₁(x), g₅(x), and g₇(x) are the minimal polynomials of x³¹–1. That is, gr(x) = (x − ßr)(x − ß²r)…(x − ß²⁴r) and ß²ir ∈ GF(2⁵) for 0 ≤ i ≤ 4 are the roots of gr(x), where r = 1, 5, and 7. If α = 2, then the total 31 roots of x³¹ − 1 are listed in Table 2.

Table 2. The total 31 roots of x³¹ – 1 (in decimal number)

Because the minimum Hamming distance of C₂₃ and C₃₁ is d = 7, the inequality 2v + 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 Ci ∈ GF(2) for 0 ≤ i ≤ n–1, and denotes the message polynomial, where mi ∈ GF(2) for 0 ≤ i ≤ k–1. Let be the parity-check polynomial, where pi ∈ GF(2) for 0 ≤ i ≤ n–k–1. Let be the parity-check polynomial, where pi ∈ GF(2) for 0 ≤ i ≤ n–k–1. Let p(x) ≡ m(x)xn–k mod g(x), then one obtains m(x)xn–k = q(x)g(x) + p(x). The term (p(x) + m(x)xn–k), which is a multiple of g(x), is a codeword polynomial given by

[picture] | (3)

where ci ∈ 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 ei ∈ 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

[picture] | (4)

where G is called the systematic generator matrix. Let P be a k(n–k) matrix and Ik be a kk identity matrix, and G can be expressed as

[picture] | (5)

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

[picture] | (6)

where HT denotes the n(n–k) transpose matrix of H; that is, HT can be expressed as

[picture] | (7)

For C₂₃, HT has the following form:

[picture] | (8)

3. Decoding Algorithm and Theorems

In this section, the proposed ESWDA is used to decode the C₂₃ and C₃₁. 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₀ … a₁ an₋₁) and b = (b₀ … b₁ bn₋₁) be two binary vectors, then

[picture] | (9)

Corollary 1: If aibi = 0 for 1 ≤ i ≤ n, then

[picture] | (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⁽¹⁾(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⁽¹⁾(x) corresponding to r⁽¹⁾(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 gn(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 rj be an element of r and hj be the jth row vector of HT for 0 ≤ j ≤ n–1. Then the syndrome s⁽i⁾ of r⁽i⁾ for 0 ≤ i ≤ n–1 has the form

[picture] | (11)

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

Proof: Let r = (r₀,…,rn₋₁) and r⁽i⁾ = (ri,…, rn₋₁, r₀,…, ri₋₁) for 0 ≤ i ≤ n–1. By (7), we have s⁽i⁾ = r⁽i⁾HT = = . The proof is thus completed.

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 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

[picture] | (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 hi denote the ith row vector of HT, where 0 ≤ i ≤ n–1. Also let sdw denote the syndrome difference between the syndromes of r and hi in each decoding step w. By using the weight of sdw, the error cases can be quickly determined. Let u₀ = (1, 0,…, 0) be a k-tuples unit vector and uj has only one nonzero component at the jth 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₂₃ or C₃₁, 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(s) = 0, then r has no error. If 1 ≤ w(s) ≤ 3 or 1 ≤ w(s⁽n⁻k⁾) ≤ 3, then there are 6 error cases (P, PP, PPP, H, HH, and HHH). Let the syndrome difference sd₃ = (s–hi) for n–k ≤ i ≤ n–1. If 0 ≤ w(sd₃) ≤ 2, then there are 5 error cases (C, PC, PH, PPC, and PPH). Let the syndrome difference sd₄ = (s⁽n⁻k⁾–hi) for n–k ≤ i ≤ n–1. If n–k ≤ i ≤ n–2 and w(sd₄) = 2, then there is only 1 error case (PHH). If i = n–1 and 1 ≤ w(sd₄) ≤ 2, then there are 2 error cases (CH and CHH). Let the syndrome difference sd₅ = ((s–hn₋k)–hi) for k ≤ i ≤ n–1. If w(sd₅) = 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 = (rn₋k,…, rn₋₁). 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 = (rn₋k,…, rn₋₁) + (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₃ = (s–hi) for n–k ≤ i ≤ n–1 and w(sd₃). If 0 ≤ w(sd₃) ≤ 2, then the corrected information vector is m = (rn₋k,…, rn₋₁) + ui₋₍n₋k₎. Go to step 6.

4). (PHH, CH, and CHH cases) Compute the syndrome difference sd₄ = (s⁽n⁻k⁾–hi) for n–k ≤ i ≤ n–1 and w(sd₄). If n–k ≤ i ≤ n-2 and w(sd₄) = 2, then the corrected information vector is m = (rn₋k,…, rn₋₁) + (sd₄ >>1). If i = n–1 and 1 ≤ w(sd₄) ≤ 2, then the corrected information vector is m = (rn₋k,…, rn₋₁) + u₀ + (sd₄ >> 1). Go to step 6.

5). (PCH case.) Compute the syndrome difference sd₅ = ((s–hn₋k)–hi) for k ≤ i ≤ n–1 and w(sd₅). If w(sd₅) = 1, then the corrected information vector is m = (rn₋k,…, rn₋₁) + u₀ + ui₋₍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.

Table 3. The number of error patterns in each decoding step of C₂₃ and C₃₁

Figure 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₁₅; 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₂₃ 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⁽¹¹⁾ = (10001100000) and w(s⁽¹¹⁾) = 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₂₃ 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(s) = 7. Since w(s) > 3, go to step 2.

2). Compute s⁽¹¹⁾ = (01001001110) and w(s⁽¹¹⁾) = 5. Since w(s⁽¹¹⁾) > 3, go to step 3.

3). Compute sd₃ = (s–hi) for 11 ≤ i ≤ 22 and w(sd₃).

sd₃ = (s–h₁₁) = (11001001111) – (11000111010) = (00001110101). w(sd₃) = 5.

sd₃ = (s–h₁₂) = (11001001111) – (01100011101) = (10101010010). w(sd₃) = 5.

…

sd₃ = (s–h₂₁) = (11001001111) – (10010011111) = (01011010000). w(sd₃) = 4.

sd₃ = (s–h₂₂) = (11001001111) – (10001110101) = (01000111010). w(sd₃) = 5.

Since every w(sd₃) > 2, go to step 4.

4).Compute sd₄ = (s⁽¹¹⁾–hi) for 11 ≤ i ≤ 22 and w(sd₄).

sd₄ = (s⁽¹¹⁾–h₁₁) = (01001001110) – (11000111010) = (10001110100). w(sd₄) = 5.

sd₄ = (s⁽¹¹⁾–h₁₂) = (01001001110) – (01100011101) = (00101010011). w(sd₄) = 5.

…

sd₄ = (s⁽¹¹⁾–h₂₁) = (01001001110) – (10010011111) = (11011010001). w(sd₄) = 6.

sd₄ = (s⁽¹¹⁾–h₂₂) = (01001001110) – (10001110101) = (11000111011). w(sd₄) = 7.

Since every w(sd₄) > 2, go to step 5.

5).Compute sd₅ = ((s–h₁₁)–hi) = (00001110101) – hi for 12 ≤ i ≤ 22 and w(sd₅).

sd₅ = (s–h₁₁)–h₁₂ = (00001110101) – (11000111010) = (11001001111). w(sd₅) = 7.

sd₅ = (s–h₁₁)–h₁₃ = (00001110101) – (11110110100) = (11111000001). w(sd₅) = 6.

…

sd₅ = (s–h₁₁)–h₂₁ = (00001110101) – (10010011111) = (10011101010). w(sd₅) = 6.

sd5 = (s–h₁₁)–h₂₂ = (00001110101) – (10001110101) = (10000000000). w(sd₅) = 1.

Since w(sd₅) = 1, the corrected information word m = (r₁₁,…, r₂₂) + u₀ + u₂₂₋₁₁ = (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₁₅ with g(x) = x¹⁰ + x⁹ + x⁸ + x⁶ + x⁵ + x² + 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 = (rn₋k,…, rn₋₁), 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 = (rn₋k,…, rn₋₁) + (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₃ = (s–hi) for n–k ≤ i ≤ n–1 and w(sd₃). If 0 ≤ w(sd₃) ≤ 2, then the corrected information vector is m = (rn₋k,…, rn₋₁) + ui₋₍n₋k₎, and go to step 5.

4). (PHH case) Compute the syndrome difference sd₄ = (s⁽n⁻k⁾–hi) for n–k ≤ i ≤ n–1 and w(sd₄). If w(sd₄) = 2, then the corrected information vector is m = (rn₋k,…, rn₋₁) + (sd₄ & (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.

Table 4. The number of error patterns in each decoding step of C₁₅

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⁽⁵⁾ = (1101111101) and w(s⁽⁵⁾) = 8. Since w(s⁽⁵⁾) > 3, go to step 3.

3). Compute sd₃ = (s–hi) for 10 ≤ i ≤ 14 and w(sd₃).

sd₃ = (s–h₁₁) = (1001001011) – (1101100101) = (0100101110). w(sd₃) = 5.

sd₃ = (s–h₁₂) = (1001001011) – (0110101111) = (1111100100). w(sd₃) = 6.

sd₃ = (s–h₁₃) = (1001001011) – (1101011110) = (0100010101). w(sd₃) = 4.

sd₃ = (s–h₁₄) = (1001001011) – (0111011001) = (1110010010). w(sd₃) = 5.

sd₃ = (s–h₁₅) = (1001001011) – (1110110010) = (0111111001). w(sd₃) = 7.

Since every w(sd₃) > 2, go to step 4.

4). Compute sd₄ = (s⁽⁵⁾–hi) for 10 ≤ i ≤ 14 and w(sd₄).

sd₄ = (s⁽⁵⁾–h₁₁) = (1101111101) – (1101100101) = (0000011000). w(sd₄) = 2.

Since w(sd₄) = 2, the corrected information word m = (r₁₀,…, r₁₄) + (sd₄ & (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 2k codewords with all error patterns were created to check every possible error pattern of C₁₅, C₂₃, and C₃₁, respectively. In other words, the error patterns of C₁₅, C₂₃, and C₃₁ 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 5. Comparison of the decoding time (in µs) and memory requirement (in bytes) for the Golay code between two algorithms

Table 6. Comparison of the decoding time (in µs) and memory requirement (in bytes) for the (31, 16, 7) QR code between two algorithms

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₁₅, C₂₃, and C₃₁. 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 sdw, 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.
[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.
[3]   | Elia, M., “Algebraic decoding of the (23, 12, 7) Golay codes,” IEEE Trans. Inform. Theory, 33(1). 150-151. Jan. 1987.
[4]   | Golay, M.J.E., “Notes on digital coding,” Proc. IRE, 37, 657. 1949.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[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.
[13]   | Wicker, S.B. Error control systems for digital communication and storage, Prentice Hall, New Jersey, 1995.