International Journal of Networks and Communications

p-ISSN: 2168-4936    e-ISSN: 2168-4944

2012;  2(1): 11-16

doi:10.5923/j.ijnc.20120201.02

A Viewpoint on the Decoding of the Quadratic Residue Code of Length 89

Hung-Peng Lee

Department of Computer Science and Information Engineering, Fortune Institute of Technology, Kaohsiung, 83160, Taiwan

Correspondence to: Hung-Peng Lee, Department of Computer Science and Information Engineering, Fortune Institute of Technology, Kaohsiung, 83160, Taiwan.

Email:

Copyright © 2012 Scientific & Academic Publishing. All Rights Reserved.

Abstract

A viewpoint on the weight-6 error patterns of the algebraic decoding of the (89, 45, 17) quadratic residue (QR) code with reducible generator polynomial, proposed by Truong et al. (2008), is presented in this paper. Some weight-6 error patterns will cause a zero value in the syndrome S1. However, in this case, the inverse-free Berlekamp-Massey (IFBM) algorithm is still valid to determine the error-locator polynomial of six errors in the finite field GF(211). An example demonstrates the fact.

Keywords: Quadratic Residue Code, Algebraic Decoding Algorithm, Error Pattern, Syndrome

Cite this paper: Hung-Peng Lee, A Viewpoint on the Decoding of the Quadratic Residue Code of Length 89, International Journal of Networks and Communications, Vol. 2 No. 1, 2012, pp. 11-16. doi: 10.5923/j.ijnc.20120201.02.

1. Introduction

The famous QR codes, introduced by Prange [1] in 1957, are cyclic BCH codes with code rates greater than or equal to one-half. In addition, the codes generally have large minimum distances so that most of the known QR codes are the best-known codes. In the past decades, several decoding skills have been developed to decode the binary QR codes. The ADAs most used to decode the QR codes are the Newton identities with either Sylvester resultants [3-6,10-11] or Gröbner bases [13], or IFBM algorithm [7-9,12] to determine the error-locator polynomial. The ADA of the (89, 45, 17) QR code [9,12] can correct up to eight errors in GF(211), because the error-correcting capability of the code is errors, where denotes the greatest integer less than or equal to x, and d = 17 is the minimum Hamming distance of the code. In each decoding procedure, the IFBM algorithm[14] is used to determine the error-locator polynomial of the received sequence[9,12]. Finally, the Chien algorithm[15] is applied to find the roots of the error-locator polynomial. For the QR codes with irreducible generator polynomial, syndrome S1 = 0 means that the received word has no errors. However, for the (89, 45, 17) QR codes, the syndrome S1 = 0 means that S2, S4, …, are all equal to zero and the zero S1 does not cause a decoding failure in decoding weight-6 error patterns while using the IFBM algorithm to determine the error-locator polynomial.
The rest parts of the paper are organized as follows: The background of (89, 45, 17) QR codes is briefly given in Section 2. The discussion of the weight-6 error patterns ispresented in Section 3. Finally, this paper concludes with a brief summary in Section 4.

2. Background of the Binary (89, 45, 17) QR Code

The codeword of the binary (n, k, d) QR code is defined algebraically as a multiple of its generator polynomial g(x) with coefficients in GF(2). Let the length of the code n be a prime number of the form n = 8m ± 1, where m is a positive integer and m be the smallest positive integer such that ≡ 1 (mod n). Thus, GF(2m) is the extension field of GF(2). Also, let k = (n+1)/2 be the message length and d be the minimum Hamming distance or Hamming weight of the code. The generator polynomial as a cyclic code is given by
(1)
where the element β is a primitive nth root of unity in GF(2m) and Qn denotes the set of quadratic residues given by Qn = {jjx2 mod n for 1 ≤ x ≤ (n–1)/2}.
The set Qn can thus be represented as a disjoint union of cyclotomic cosets, modulo n. These cyclotomic cosets are defined as Qr = {r2jj = 0, 1, … , nr–1}, where nr is the smallest positive integer such that , nr divides (n–1)/2, and r is the smallest element in Qr. The element r is called the representative element of the cyclotomic cosets Qr. The set S, consisting of all representatives of the QR code, is called the base set of the QR code. These definitions and properties cause the equality relating Qn to the cyclotomic cosets, modulo n. Let an element α ∈ GF(211) be a root of the primitive polynomial p(x) = x11 + x2 + 1. Then, α generates the multiplicative group of nonzero elements in GF(211). Also, let an element β = αu, where u = ( – 1)/n = (211 – 1)/89 = 23, is a primitive 89th root of unity in GF(211); that is, β = α23. The base set of this code is S = {1, 3, 5, 9, 11, 13, 19, 33} and rS. Therefore, the eight cyclotomic cosets Qr are shown in Table 1.
Table 1. The cyclotomic cosets of the (89, 45, 17) QR code
     
Let T = {1, 5, 9, 11} and rT, the quadratic residue set of the code is given by
(2)
The minimal polynomial gr(x) can also be expressed as ; therefore, the g(x) consists of four minimum polynomials given below:
(3)
Since the codeword of the QR code is a multiple of the g(x), the codeword polynomial of the QR code of length 89 can be represented by , where CiGF(2) for 0 ≤ i ≤ 88, and m(x) = m44x44 + + m1x + m0 denotes information polynomial, where miGF(2) for 0 ≤ i ≤ 44. In such a representation, this type of codeword is called the non-systematic encoding. In practice, the encoding procedure is often implemented by the use of systematic encoding. Let p(x) = p43x43 + + p1x + p0 be the parity-check polynomial, where piGF(2) for 0 ≤ i ≤ 43. Also, let m(x)xn-k divide by g(x), then we get the following identity:
(4)
Multiplying both sides of (4) by xk and using xn = 1, Then, it yields d(x)xk + m(x) = (q(x)xk)g(x). The term d(x)xk + m(x), which is a multiple of g(x), has m(x) in its lower k bits and p(x) = d(x)xk in its higher nk bits. Thus, the codeword can be represented by the equation below.
(5)
As shown in (5), this form of the codeword is called systematic encoding. Now, let a codeword be transmitted through an additive white Gaussian noise (AWGN) channel, and obtain a received word of the form r(x) = c(x) + e(x), where e(x) = e88x88 ++ e1x + e0 is the error polynomial and eiGF(2). For simplification, the polynomial form can be expressed as the vector form. For example, c(x) can be expressed as c = (c88, …, c1, c0). The syndromes or known syndromes of the code are defined by
(6)
where i (mod 89) ∈ Q89. If iQ89, the syndromes are called unknown syndromes. All the known and unknown syndromes can be expressed as some powers of S1, S5, S9, S11, and S3, S13, S19, S33, called the primary known and unknown syndromes, respectively. Notice that S0 = 0 or 1 depends on the fact that v is even or odd, where vt is the actual number of errors to be corrected and 1 ≤ v ≤ 8.
If there are v errors in r(x), then e(x) has v nonzero terms over GF(2); that is, , where 0 ≤ r1 < r2 < ... < rvn–1. For i Qn, the syndrome can be written as . Assuming that v errors occur, the error-locator polynomial Lv(x) is defined by
(7)
where are called the error locators, the σj are called the elementary symmetric functions for 1 ≤ j v, and σ0 = 1. The roots of Lv(x) are the inverse of the v error locators {Xj}.
To determine the error-locator polynomial, the steps of the IFBM algorithm [14] are summarized as below:
1. Initialize k = 0, μ(0)(x) = 1, λ(0)(x)=1, l(0) = 0, γ(0) = 1.
2. Set k = k + 1. If k > 2t, then go to stop. Otherwise Compute
(8)
where μj(k1) is the coefficient of μ(k–1)(x).
3. Compute
(9)
4. Compute
(10)
5. Set k = k + 1. If k ≤ 2t, then go to 2. Otherwise stop.

3. Discussion of the Weight-6 Error Patterns

The ADA given in [9,12] utilized the IFBM algorithm to determine the error-locator polynomial. In order to apply the IFBM algorithm, the consecutive syndromes Si for 1 ≤ i ≤ 16 need to be computed. Among them, the unknown syndromes S3, S6, S7, S12, S13, S14, and S15 can be expressed as some powers of the primary unknown syndrome S3 or S13 that cannot be computed directly from the received word. The determination of the S3 and S13 is given in [9,12].
For the (89, 45, 17) QR code, a C++ program shows that over 200,000 weight-6 error patterns will cause a zero S1. However, the zero S1 does not cause a decoding failure while using the IFBM algorithm to determine the error-locator polynomial. The following example demonstrates the fact.
Example 1
If a message m(x) = 10, by (4) and (5), then one obtains the systematic codeword c(x) = x86 + x85 + x84 + x81 + x77 + x75 + x72 + x65 + x62 + x60 + x56 + x53 + x52 + x51 + x47 + x45 + x3 + x. If there is a weight-6 error pattern e(x) = x26 + x15 + x3 + x2 + x + 1 occurred in the received word, then one obtains r(x) = x86 + x85 + x84 + x81 + x77 + x75 + x72 + x65 + x62 + x60 + x56 + x53 + x52 + x51 + x47 + x45 + x26 + x15 + x2 + 1.
By (6), one obtains S1 = S2 = S4 = S8 = 0, S3 = 57, S5 = 746, S6 = S32 = 1345, S7 = S332 = 1938, S9 = 711, S10 = S52 = 1766, S11 = 376, S12 = S34 = 686, where the values of all syndromes are expressed in decimal number. Then, by using the IFBM algorithm to obtain the error-locator polynomial L6(x), one has the following detailed steps.
1. Define the initial values as follows: k = 0, μ(0)(x) = 1, λ(0)(x)=1, l(0) = 0, and γ(0) = 1.
2. Set k = 1. By (8), one has δ(1) = 0.
3. By (9), compute μ(1)(x) = γ(0)μ(0)(x) – δ(1)λ(0)(x)x = γ(0)μ(0)(x) = 1∙1 = 1.
4. By (10), δ(1) = 0. Then, compute λ(1)(x) = xλ(0)(x) = x1 = x, l(1) = l(0) = 0, and γ(1) = γ(0) = 1, respectively. Go to step 2.
2. Set k = 2. By (8), one has δ(2) = 0.
3. By (9), compute μ(2)(x) = γ(1)μ(1)(x) – δ(2)λ(1)(x)x = γ(1)μ(1)(x) = 1∙1 = 1.
4. By (10), δ(2) = 0. Then, compute λ(2)(x) = xλ(1)(x) =x2, l(2) = l(1) = 0, and γ(2) = γ(1) = 1, respectively. Go to step 2.
2. Set k = 3. By (8), one has δ(2) = S3.
3. By (9), compute μ(3)(x) = γ(2)μ(2)(x) – δ(3)λ(2)(x)x = 1∙1 – S3x2x = 1 + S3x3. Notice that the addition and subtraction are the same in GF(2).
4. By (10), δ(3) = S3 ≠ 0 and 2l(2) = 0 ≤ k – 1 = 3 – 1 = 2. Then, compute λ(3)(x) = μ(k-1)(x) = μ(2)(x) = 1, l(3) = kl(2) = 3 – 0 = 3, and γ(3) = δ(3) = S3, respectively. Go to step 2.
2. Set k = 4. By (8), one has δ(4) = 0.
3. By (9), compute μ(4)(x) = γ(3)μ(3)(x) – δ(4)λ(3)(x)x = γ(3)μ(3)(x) = S3(1 + S3x3) = S3 + S32x3.
4. By (10), δ(4) = 0. Then, compute λ(4)(x) = xλ(3)(x) = x, l(4) = l(3) = 3, and γ(4) = γ(3) = S3, respectively. Go to step 2.
2. Set k = 5. By (8), one has δ(5) = S3S5.
3. By (9), compute μ(5)(x) = γ(4)μ(4)(x) – δ(5)λ(4)(x)x = S3(S3 +S32x3) – S3S5xx = S32 + S3S5x2 + S33x3.
4. By (10), 2l(4) = 6 > k – 1 = 5 – 1 = 4. Then, compute λ(5)(x) = xλ(4)(x) = xx = x2, l(5) = l(4) = 3, and γ(5) = γ(4) = S3, respectively. Go to step 2.
2. Set k = 6. By (8) and S6 = S32, one has δ(6) = 0.
3. By (9), compute μ(6)(x) = γ(5)μ(5)(x) – δ(6)λ(5)(x)x = γ(5)μ(5)(x) = S3(S32 + S3S5x2 + S33x3) = S33 + S32S5x2 + S34x3.
4. By (10), δ(6) = 0. Then, compute λ(6)(x) = xλ(5)(x) = x3, l(6) = l(5) = 3, and γ(6) = γ(5), respectively. Go to step 2.
2. Set k = 7. By (8) and S7 = S332, one has δ(7) = S335 + S32S52.
3. By (9), compute μ(7)(x) = γ(6)μ(6)(x) – δ(7)λ(6)(x)x = S3(S33 + S32S5x2 + S34x3) – (S335 + S32S52)x3x = S34 + S33S5x2 + S35x3 + (S335 + S32S52)x4.
4. By (10), δ(7) ≠ 0 and 2l(6) = 6 ≤ k – 1 = 7 – 1 = 6. Then, compute λ(7)(x) = μ(6)(x) = S33 + S32S5x2 + S34x3, l(7) = kl(6) = 7 – 3 = 4, and γ(7) = δ(7), respectively. Go to step 2.
2. Set k = 8. By (8), one has δ(8) = 0.
3. By (9), compute μ(8)(x) = γ(7)μ(7)(x) – δ(8)λ(7)(x)x = γ(7)μ(7)(x) = (S335 + S32S52)(S34 + S33S5x2 + S35x3 + (S335 + S32S52)x4) = (S339 + S36S52) + (S338S5 + S35S53)x2 + (S340 + S37S52)x3 + (S370 + S34S54)x4.
4. By (10), δ(8) = 0. Then, compute λ(8)(x) = xλ(7)(x) = x(S33 + S32S5x2 + S34x3) = S33x + S32S5x3 + S34x4, l(8) = l(7) = 4, and γ(8) = γ(7) = S335 + S32S52, respectively.
2. Set k = 9. By (8), one has δ(9) = S339S9 + S36S52S9 + S337S53 +S342 + S39S52 + S34S55.
3. By (9), compute μ(9)(x) = γ(8)μ(8)(x) – δ(9)λ(8)(x)x = (S335 + S32S52)((S339 + S36S52) + (S338S5 + S35S53)x2 – (S340 + S37S52)x3 + (S370 + S34S54)x4) – (S339S9 + S36S52S9 + S337S53 +S342 + S39S52 + S34S55)(S33x + S32S5x3 + S34x4)x = (S374 + S38S54) + (S373S5 + S342S9 + S39S52S9 + S340S53 + S345 + S312S52)x2 + (S375 + S39S54)x3 + (S3105 + S372S52 + S341S5S9 + S38S53S9 + S344S5 + S311S53)x4 + (S343S9 + S310S52S9 + S341S53 + S346 + S313S52 + S38S55)x5.
4. By (10), δ(9) ≠ 0 and 2l(8) = 8 ≤ k – 1 = 9 – 1 = 8. Then, compute λ(9)(x) =μ(8)(x) = (S339 + S36S52) + (S338S5 + S35S53)x2 + (S340 + S37S52)x3 + (S370 + S34S54)x4, l(9) = kl(8) = 9 – 4 = 5, and γ(9) = δ(9), respectively. Go to step 2.
2. Set k = 10. By (8) and S10 = S52, one has δ(10) = 0.
3. By (9), compute μ(10)(x) = γ(9)μ(9)(x) – δ(10)λ(9)(x)x = γ(9)μ(9)(x) = (S339S9 + S36S52S9 + S337S53 +S342 + S39S52 + S34S55)((S374 + S38S54) + (S373S5 + S342S9 + S39S52S9 + S340S53 + S345 + S312S52)x2 + (S375 + S39S54)x3 + (S3105 + S372S52 + S341S5S9 + S38S53S9 + S344S5 + S311S53)x4 + (S343S9 + S310S52S9 + S341S53 + S346 + S313S52 + S38S55)x5) = (S3113S9 + S3116 + S312S59 + S317S56 + S345S57 + S350S54 + S378S55 + S383S52 + S3111S53 + S314S56S9 + S347S54S9 + S380S52S9) + (S3115S5 + S3112S5S9 + S3110S54 + S387 + S382S53 + S381S92 + S379S53S9 + S349S55 + S346S55S9 + S344S58 + S321S54 + S316S57 + S315S54S92 + S313S57S9)x2 + (S3117 + S9S3114 + S3112S53 + S384S52 + S9S381S52 + S379S55 + S351S54 + S9S348S54 + S346S57 + S318S56 + S9S315S56 + S313S59)x3 + (S3147 + S3144S9 + S3142S53 + S386S5 + S380S5S92 + S376S57 + S320S55 + S315S58 + S314S55S92 + S312S58S9)x4 + (S388 + S385S9 + S380S53S9 + S378S56 + S352S52S9 + S349S52S92 + S347S55S9 + S345S9 + S342S92 + S340S53S9 + S322S54 + S316S54S92 + S312S510 + S312S52S9 + S39S52S92 + S37S55S9)x5.
4. By (10), δ(10) = 0. Then, compute λ(10)(x) = xλ(9)(x) = (S339 + S36S52)x + (S338S5 + S35S53)x3 + (S340 + S37S52)x4 + (S370 + S34S54)x5, l(10) = l(9) = 5, and γ(10) = γ(9), respectively.
2. Set k = 11. By (8), one has δ(11) = S3179 + S3176S9 + S3174S53 + S3118S5 + S11S3116 + S3115S5S9 + S11S3113S9 + S11S3111S53 + S3110S54S9 + S3108S57 + S390 + S387S9 + S384S92 + S11S383S52 + S382S53S9 + S381S93 + S380S56 + S11S380S52S9 + S379S53S92 + S11S378S55 + S352S55 + S11S350S54 + S349S55S9 + S347S58 + S11S347S54S9 + S11S345S57 + S324S54 + S321S54S9 + S318S54S92 + S11S317S56 + S316S57S9 + S315S54S93 + S314S510 + S11S314S56S9 + S313S57S92 + S11S312S59.
3. μ(11)(x) = γ(10)μ(10)(x) – δ(11)λ(10)(x)x = (S339S9 + S36S52S9 + S337S53 +S342 + S39S52 + S34S55)((S3113S9 + S3116 + S312S59 + S317S56 + S345S57 + S350S54 + S378S55 + S383S52 + S3111S53 + S314S56S9 + S347S54S9 + S380S52S9) + (S3115S5 + S3112S5S9 + S3110S54 + S387 + S382S53 + S381S92 + S379S53S9 + S349S55 + S346S55S9 + S344S58 + S321S54 + S316S57 + S315S54S92 + S313S57S9)x2 + (S3117 + S9S3114 + S3112S53 + S384S52 + S9S381S52 + S379S55 + S351S54 + S9S348S54 + S346S57 + S318S56 + S9S315S56 + S313S59)x3 + (S3147 + S3144S9 + S3142S53 + S386S5 + S380S5S92 + S376S57 + S320S55 + S315S58 + S314S55S92 + S312S58S9)x4 + (S388 + S382S92 + S378S56 + S322S54 + S316S54S92 + S312S510)x5) – (S3179 + S3176S9 + S3174S53 + S3118S5 + S11S3116 + S3115S5S9 + S11S3113S9 + S11S3111S53 + S3110S54S9 + S3108S57 + S390 + S387S9 + S384S92 + S11S383S52 + S382S53S9 + S381S93 + S380S56 + S11S380S52S9 + S379S53S92 + S11S378S55 + S352S55 + S11S350S54 + S349S55S9 + S347S58 + S11S347S54S9 + S11S345S57 + S324S54 + S321S54S9 + S318S54S92 + S11S317S56 + S316S57S9 + S315S54S93 + S314S510 + S11S314S56S9 + S313S57S92 + S11S312S59)((S339 + S36S52)x + (S338S5 + S35S53)x3 + (S340 + S37S52)x4 + (S370 + S34S54)x5)x = (S3158 + S316S514 + S326S58 + S3148S56 + S3152S92 + S320S58S92) + (S3218 + S3215S9 + S3213S53 + S3185S52 + S3182S52S9 + S3180S55 + S11S3155 + S3154S5S9 + S11S3152S9 + S3151S5S92 + S11S3150S53 + S3149S54S9 + S386S58 + S383S58S9 + S381S511 + S353S510 + S350S510S9 + S348S513 + S11S323S58 + S322S59S9 + S11S320S58S9 + S319S59S92 + S11S318S511 + S317S512S9)x2 + (S3159 + S3153S92 + S3149S56 + S327S58 + S321S58S92 + S317S514)x3 + (S3217S5 + S3214S5S9 + S3212S54 + S3189 + S3184S53 + S3183S92 + S3181S53S9 + S11S3154S5 + S3153S52S9 + S11S3151S5S9 + S3150S52S92 + S11S3149S54 + S3148S55S9 + S385S59 + S382S59S9 + S380S512 + S357S58 + S352S511 + S351S58S92 + S349S511S9 + S11S322S59 + S321S510S9 + S11S319S59S9 + S318S510S92 + S11S317S512 + S316S513S9)x4 + (S3219 + S9S3216 + S3214S53 + S3186S52 + S9S3183S52 + S3181S55 + S3158S5 + S11S3156 + S9S3155S5 + S11S9S3153 + S11S3151S53 + S9S3150S54 + S3148S57 + S387S58 + S9S384S58 + S382S511 + S354S510 + S9S351S510 + S349S513 + S326S59 + S11S324S58 + S9S323S59 + S11S9S321S58 + S11S319S511 + S9S318S512 + S316S515)x5 + (S3249 + S3246S9 + S3244S53 + S3188S5 + S11S3186 + S3185S5S9 + S3183S54 + S11S3183S9 + S11S3181S53 + S3160 + S3157S9 + S3154S92 + S11S3153S52 + S3152S53S9 + S3151S93 + S3150S56 + S11S3150S52S9 + S3149S53S92 + S11S3148S55 + S3117S58 + S3114S58S9 + S3112S511 + S356S59 + S11S354S58 + S353S59S9 + S351S512 + S11S351S58S9 + S11S349S511 + S328S58 + S325S58S9 + S322S58S92 + S11S321S510 + S320S511S9 + S319S58S93 + S318S514 + S11S318S510S9 + S317S511S92 + S11S316S513)x6.
4. By (10), δ(11) ≠ 0 and 2l(10) = 10 ≤ k – 1 = 11 – 1 = 10. Then, compute λ(11)(x) = μ(10)(x), l(11) = kl(10) = 11 – 5 = 6, and γ(11) = δ(11), respectively. Go to step 2.
2. Set k = 12. One has δ(12) = 0.
3. By (15) in[14], compute the error-locator polynomial of degree 6, μ(12)(x) = γ(11)μ(11)(x) – δ(12)λ(11)(x)x = γ(11)μ(11)(x) = (S3179 + S3176S9 + S3174S53 + S3118S5 + S11S3116 + S3115S5S9 + S11S3113S9 + S11S3111S53 + S3110S54S9 + S3108S57 + S390 + S387S9 + S384S92 + S11S383S52 + S382S53S9 + S381S93 + S380S56 + S11S380S52S9 + S379S53S92 + S11S378S55 + S352S55 + S11S350S54 + S349S55S9 + S347S58 + S11S347S54S9 + S11S345S57 + S324S54 + S321S54S9 + S318S54S92 + S11S317S56 + S316S57S9 + S315S54S93 + S314S510 + S11S314S56S9 + S313S57S92 + S11S312S59)((S3158 + S316S514 + S326S58 + S3148S56 + S3152S92 + S320S58S92) + (S3218 + S3215S9 + S3213S53 + S3185S52 + S3182S52S9 + S3180S55 + S11S3155 + S3154S5S9 + S11S3152S9 + S3151S5S92 + S11S3150S53 + S3149S54S9 + S386S58 + S383S58S9 + S381S511 + S353S510 + S350S510S9 + S348S513 + S11S323S58 + S322S59S9 + S11S320S58S9 + S319S59S92 + S11S318S511 + S317S512S9)x2 + (S3159 + S3153S92 + S3149S56 + S327S58 + S321S58S92 + S317S514)x3 + (S3217S5 + S3214S5S9 + S3212S54 + S3189 + S3184S53 + S3183S92 + S3181S53S9 + S11S3154S5 + S3153S52S9 + S11S3151S5S9 + S3150S52S92 + S11S3149S54 + S3148S55S9 + S385S59 + S382S59S9 + S380S512 + S357S58 + S352S511 + S351S58S92 + S349S511S9 + S11S322S59 + S321S510S9 + S11S319S59S9 + S318S510S92 + S11S317S512 + S316S513S9)x4 + (S3219 + S9S3216 + S3214S53 + S3186S52 + S9S3183S52 + S3181S55 + S3158S5 + S11S3156 + S9S3155S5 + S11S9S3153 + S11S3151S53 + S9S3150S54 + S3148S57 + S387S58 + S9S384S58 + S382S511 + S354S510 + S9S351S510 + S349S513 + S326S59 + S11S324S58 + S9S323S59 + S11S9S321S58 + S11S319S511 + S9S318S512 + S316S515)x5 + (S3249 + S3246S9 + S3244S53 + S3188S5 + S11S3186 + S3185S5S9 + S3183S54 + S11S3183S9 + S11S3181S53 + S3160 + S3157S9 + S3154S92 + S11S3153S52 + S3152S53S9 + S3151S93 + S3150S56 + S11S3150S52S9 + S3149S53S92 + S11S3148S55 + S3117S58 + S3114S58S9 + S3112S511 + S356S59 + S11S354S58 + S353S59S9 + S351S512 + S11S351S58S9 + S11S349S511 + S328S58 + S325S58S9 + S322S58S92 + S11S321S510 + S320S511S9 + S319S58S93 + S318S514 + S11S318S510S9 + S317S511S92 + S11S316S513)x6) = S11S3274 + S3276S5 + S3245S9 + S3334S9 + S3248 + S3337 + S330S524 + S350S512 + S363S522 + S368S519 + S373S516 + S378S513 + S396S520 + S3116S58 + S3124S521 + S3144S59 + S3162S516 + S3182S54 + S3190S517 + S3210S55 + S3228S512 + S3256S513 + S3322S59 + S3327S56 + S3332S53 + S3233S95 + S3236S94 + S3328S93 + S3331S92 + S11S328S523 + S11S333S520 + S11S338S517 + S11S343S514 + S11S361S521 + S11S366S518 + S11S371S515 + S11S376S512 + S11S394S519 + S11S399S516 + S11S3104S513 + S11S3109S510 + S11S3127S517 + S11S3132S514 + S11S3137S511 + S11S3142S58 + S11S3160S515 + S11S3165S512 + S11S3170S59 + S11S3175S56 + S11S3193S513 + S11S3198S510 + S11S3203S57 + S11S3208S54 + S11S3226S511 + S11S3231S58 + S11S3236S55 + S11S3241S52 + S11S3259S59 + S11S3264S56 + S11S3269S53 + S11S3265S93 + S11S3268S92 + S332S521S9 + S337S518S9 + S342S515S9 + S347S512S9 + S365S519S9 + S375S513S9 + S398S517S9 + S3103S514S9 + S3108S511S9 + S3113S58S9 + S3126S518S9 + S3131S515S9 + S3136S512S9 + S3141S59S9 + S3164S513S9 + S3169S510S9 + S3174S57S9 + S3179S54S9 + S3192S514S9 + S3197S511S9 + S3202S58S9 + S3207S55S9 + S3230S59S9 + S3235S56S9 + S3240S53S9 + S3258S510S9 + S3263S57S9 + S3267S5S93 + S3268S54S9 + S3270S5S92 + S3324S56S9 + S329S521S92 + S331S518S93 + S333S515S94 + S335S512S95 + S336S515S93 + S338S512S94 + S339S515S92 + S367S516S92 + S369S513S93 + S372S513S92 + S395S517S92 + S397S514S93 + S399S511S94 + S3101S58S95 + S3102S511S93 + S3104S58S94 + S3105S511S92 + S3128S515S92 + S3130S512S93 + S3135S59S93 + S3138S59S92 + S3161S513S92 + S3163S510S93 + S3165S57S94 + S3167S54S95 + S3168S57S93 + S3170S54S94 + S3171S57S92 + S3194S511S92 + S3196S58S93 + S3201S55S93 + S3204S55S92 + S3227S59S92 + S3229S56S93 + S3231S53S94 + S3234S53S93 + S3237S53S92 + S3260S57S92 + S3262S54S93 + S3326S53S92 + S11S3271S9 + S3273S5S9 + S11S330S520S9 + S11S340S514S9 + S11S363S518S9 + S11S373S512S9 + S11S396S516S9 + S11S3106S510S9 + S11S3129S514S9 + S11S3139S58S9 + S11S3162S512S9 + S11S3172S56S9 + S11S3195S510S9 + S11S3205S54S9 + S11S3228S58S9 + S11S3238S52S9 + S11S3261S56S9 + S11S332S517S92 + S11S334S514S93 + S11S337S514S92 + S11S365S515S92 + S11S367S512S93 + S11S370S512S92 + S11S398S513S92 + S11S3100S510S93 + S11S3103S510S92 + S11S3131S511S92 + S11S3133S58S93 + S11S3136S58S92 + S11S3164S59S92 + S11S3166S56S93 + S11S3169S56S92 + S11S3197S57S92 + S11S3199S54S93 + S11S3202S54S92 + S11S3230S55S92 + S11S3232S52S93 + S11S3235S52S92 + S11S3263S53S92 + (S112S3271 + S112S3265S92 + S112S3261S56 + S112S3238S52 + S112S3232S52S92 + S112S3228S58 + S112S3205S54 + S112S3199S54S92 + S112S3195S510 + S112S3172S56 + S112S3166S56S92 + S112S3162S512 + S112S3139S58 + S112S3133S58S92 + S112S3129S514 + S112S3106S510 + S112S3100S510S92 + S112S396S516 + S112S373S512 + S112S367S512S92 + S112S363S518 + S112S340S514 + S112S334S514S92 + S112S330S520 + S11S3273S5 + S11S3270S5S9 + S11S3268S54 + S11S3267S5S92 + S11S3264S5S93 + S11S3263S57 + S11S3262S54S92 + S11S3260S57S9 + S11S3258S510 + S11S3245 + S11S3240S53 + S11S3237S53S9 + S11S3235S56 + S11S3234S53S92 + S11S3233S94 + S11S3231S53S93 + S11S3230S59 + S11S3229S56S92 + S11S3227S59S9 + S11S3207S55 + S11S3204S55S9 + S11S3202S58 + S11S3201S55S92 + S11S3198S55S93 + S11S3197S511 + S11S3196S58S92 + S11S3194S511S9 + S11S3192S514 + S11S3179S54 + S11S3174S57 + S11S3171S57S9 + S11S3169S510 + S11S3168S57S92 + S11S3167S54S94 + S11S3165S57S93 + S11S3164S513 + S11S3163S510S92 + S11S3161S513S9 + S11S3141S59 + S11S3138S59S9 + S11S3136S512 + S11S3135S59S92 + S11S3132S59S93 + S11S3131S515 + S11S3130S512S92 + S11S3128S515S9 + S11S3126S518 + S11S3113S58 + S11S3108S511 + S11S3105S511S9 + S11S3103S514 + S11S3102S511S92 + S11S3101S58S94 + S11S399S511S93 + S11S398S517 + S11S397S514S92 + S11S395S517S9 + S11S375S513 + S11S372S513S9 + S11S370S516 + S11S369S513S92 + S11S366S513S93 + S11S365S519 + S11S364S516S92 + S11S362S519S9 + S11S360S522 + S11S347S512 + S11S342S515 + S11S339S515S9 + S11S337S518 + S11S336S515S92 + S11S335S512S94 + S11S333S515S93 + S11S332S521 + S11S331S518S92 + S11S329S521S9 + S3397 + S3391S92 + S3387S56 + S3364S52 + S3358S52S92 + S3354S58 + S3336S5 + S3333S5S9 + S3331S54 + S3330S5S92 + S3327S5S93 + S3326S57 + S3325S54S92 + S3323S57S9 + S3321S510 + S3308 + S3296S94 + S3288S512 + S3275S52 + S3272S52S9 + S3267S55S9 + S3266S52S93 + S3263S52S94 + S3262S58S9 + S3261S55S93 + S3257S511S9 + S3255S514 + S3244S5S9 + S3242S54 + S3239S54S9 + S3234S57S9 + S3233S54S93 + S3232S5S95 + S3230S54S94 + S3229S510S9 + S3228S57S93 + S3222S516 + S3209S56 + S3206S56S9 + S3201S59S9 + S3200S56S93 + S3197S56S94 + S3196S512S9 + S3195S59S93 + S3191S515S9 + S3189S518 + S3178S55S9 + S3176S58 + S3173S58S9 + S3168S511S9 + S3167S58S93 + S3166S55S95 + S3164S58S94 + S3163S514S9 + S3162S511S93 + S3156S520 + S3143S510 + S3140S510S9 + S3135S513S9 + S3134S510S93 + S3133S516 + S3131S510S94 + S3130S516S9 + S3129S513S93 + S3127S516S92 + S3125S519S9 + S3112S59S9 + S3110S512 + S3107S512S9 + S3102S515S9 + S3101S512S93 + S3100S518 + S3100S59S95 + S398S512S94 + S397S518S9 + S396S515S93 + S394S518S92 + S377S514 + S374S514S9 + S372S517 + S368S514S93 + S367S520 + S366S517S92 + S365S514S94 + S364S520S9 + S362S523 + S361S520S92 + S346S513S9 + S341S516S9 + S336S519S9 + S335S516S93 + S334S513S95 + S331S522S9 + S330S519S93)x2 + (S3338 + S3335S9 + S3333S53 + S3332S92 + S3329S93 + S3328S56 + S3327S53S92 + S3325S56S9 + S3323S59 + S3277S5 + S11S3275 + S3274S5S9 + S11S3272S9 + S3271S5S92 + S11S3270S53 + S3269S54S9 + S11S3269S92 + S3268S5S93 + S11S3266S93 + S11S3265S56 + S3264S57S9 + S11S3264S53S92 + S3263S54S93 + S11S3262S56S9 + S3261S57S92 + S11S3260S59 + S3259S510S9 + S3257S513 + S3249 + S3246S9 + S11S3242S52 + S3241S53S9 + S11S3239S52S9 + S3238S53S92 + S11S3237S55 + S3237S94 + S3236S56S9 + S11S3236S52S92 + S3235S53S93 + S3234S95 + S11S3233S52S93 + S11S3232S58 + S3232S53S94 + S3231S59S9 + S11S3231S55S92 + S3230S56S93 + S3229S512 + S11S3229S58S9 + S3228S59S92 + S11S3227S511 + S3211S55 + S11S3209S54 + S3208S55S9 + S11S3206S54S9 + S3205S55S92 + S11S3204S57 + S3203S58S9 + S11S3203S54S92 + S3202S55S93 + S11S3200S54S93 + S11S3199S510 + S3198S511S9 + S11S3198S57S92 + S3197S58S93 + S11S3196S510S9 + S3195S511S92 + S11S3194S513 + S3193S514S9 + S3191S517 + S3183S54 + S3180S54S9 + S11S3176S56 + S3175S57S9 + S11S3173S56S9 + S3172S57S92 + S11S3171S59 + S3171S54S94 + S3170S510S9 + S11S3170S56S92 + S3169S57S93 + S3168S54S95 + S11S3167S56S93 + S11S3166S512 + S3166S57S94 + S3165S513S9 + S11S3165S59S92 + S3164S510S93 + S3163S516 + S11S3163S512S9 + S3162S513S92 + S11S3161S515 + S3145S59 + S11S3143S58 + S3142S59S9 + S11S3140S58S9 + S3139S59S92 + S11S3138S511 + S3137S512S9 + S11S3137S58S92 + S3136S59S93 + S11S3134S58S93 + S11S3133S514 + S3132S515S9 + S11S3132S511S92 + S3131S512S93 + S11S3130S514S9 + S3129S515S92 + S11S3128S517 + S3127S518S9 + S3125S521 + S3117S58 + S3114S58S9 + S11S3110S510 + S3109S511S9 + S11S3107S510S9 + S3106S511S92 + S11S3105S513 + S3105S58S94 + S3104S514S9 + S11S3104S510S92 + S3103S511S93 + S3102S58S95 + S11S3101S510S93 + S11S3100S516 + S3100S511S94 + S399S517S9 + S11S399S513S92 + S398S514S93 + S397S520 + S11S397S516S9 + S396S517S92 + S11S395S519 + S379S513 + S11S377S512 + S376S513S9 + S374S516 + S11S374S512S9 + S373S513S92 + S11S372S515 + S11S371S512S92 + S370S513S93 + S369S519 + S368S516S92 + S11S368S512S93 + S11S367S518 + S366S519S9 + S11S366S515S92 + S364S522 + S11S364S518S9 + S11S362S521 + S351S512 + S348S512S9 + S11S344S514 + S343S515S9 + S11S341S514S9 + S340S515S92 + S11S339S517 + S339S512S94 + S338S518S9 + S11S338S514S92 + S337S515S93 + S336S512S95 + S11S335S514S93 + S11S334S520 + S334S515S94 + S333S521S9 + S11S333S517S92 + S332S518S93 + S331S524 + S11S331S520S9 + S330S521S92 + S11S329S523)x3 + (S112S3270S5 + S112S3264S5S92 + S112S3260S57 + S112S3237S53 + S112S3231S53S92 + S112S3227S59 + S112S3204S55 + S112S3198S55S92 + S112S3194S511 + S112S3171S57 + S112S3165S57S92 + S112S3161S513 + S112S3138S59 + S112S3132S59S92 + S112S3128S515 + S112S3105S511 + S112S399S511S92 + S112S395S517 + S112S372S513 + S112S366S513S92 + S112S362S519 + S112S339S515 + S112S333S515S92 + S112S329S521 + S11S3305 + S11S3302S9 + S11S3300S53 + S11S3299S92 + S11S3296S93 + S11S3295S56 + S11S3294S53S92 + S11S3292S56S9 + S11S3290S59 + S11S3244S5 + S11S3232S5S94 + S11S3224S513 + S11S3178S55 + S11S3166S55S94 + S11S3158S517 + S11S3112S59 + S11S3100S59S94 + S11S392S521 + S11S346S513 + S11S341S516 + S11S338S516S9 + S11S336S519 + S11S335S516S92 + S11S334S513S94 + S11S332S516S93 + S11S331S522 + S11S330S519S92 + S11S328S522S9 + S3396S5 + S3390S5S92 + S3386S57 + S3368 + S3365S9 + S3362S92 + S3359S93 + S3358S56 + S3355S56S9 + S3335S52 + S3332S52S9 + S3330S55 + S3329S52S92 + S3326S52S93 + S3325S58 + S3324S55S92 + S3322S58S9 + S3320S511 + S3304S5S9 + S3301S5S92 + S3299S54S9 + S3298S5S93 + S3295S5S94 + S3294S57S9 + S3293S54S93 + S3291S57S92 + S3289S510S9 + S3279 + S3276S9 + S3274S53 + S3268S53S92 + S3267S94 + S3264S95 + S3259S512 + S3258S59S92 + S3256S512S9 + S3254S515 + S3243S52S9 + S3235S55S92 + S3231S52S95 + S3229S55S94 + S3225S511S92 + S3223S514S9 + S3213S54 + S3210S54S9 + S3208S57 + S3202S57S92 + S3201S54S94 + S3198S54S95 + S3193S516 + S3192S513S92 + S3190S516S9 + S3188S519 + S3177S56S9 + S3169S59S92 + S3165S56S95 + S3163S59S94 + S3159S515S92 + S3157S518S9 + S3147S58 + S3144S58S9 + S3142S511 + S3136S511S92 + S3135S58S94 + S3132S517 + S3132S58S95 + S3127S520 + S3124S520S9 + S3111S510S9 + S3104S516 + S3103S513S92 + S3101S516S9 + S399S510S95 + S398S516S92 + S397S513S94 + S395S516S93 + S394S522 + S393S519S92 + S381S512 + S378S512S9 + S376S515 + S371S518 + S370S515S92 + S369S512S94 + S368S518S9 + S366S521 + S366S512S95 + S365S518S92 + S362S518S93 + S345S514S9 + S340S517S9 + S335S520S9 + S334S517S93 + S333S514S95 + S330S523S9 + S329S520S93)x4 + (S112S3272 + S112S3266S92 + S112S3262S56 + S112S3239S52 + S112S3233S52S92 + S112S3229S58 + S112S3206S54 + S112S3200S54S92 + S112S3196S510 + S112S3173S56 + S112S3167S56S92 + S112S3163S512 + S112S3140S58 + S112S3134S58S92 + S112S3130S514 + S112S3107S510 + S112S3101S510S92 + S112S397S516 + S112S374S512 + S112S368S512S92 + S112S364S518 + S112S341S514 + S112S335S514S92 + S112S331S520 + S11S3246 + S11S3234S94 + S11S3226S512 + S11S3180S54 + S11S3168S54S94 + S11S3160S516 + S11S3114S58 + S11S3102S58S94 + S11S394S520 + S11S348S512 + S11S336S512S94 + S11S328S524 + S3398 + S3392S92 + S3388S56 + S3365S52 + S3359S52S92 + S3355S58 + S3309 + S3297S94 + S3289S512 + S3270S52S92 + S3264S52S94 + S3260S58S92 + S3248S5 + S3243S54 + S3237S54S92 + S3236S5S94 + S3228S513 + S3227S510S92 + S3223S516 + S3204S56S92 + S3198S56S94 + S3194S512S92 + S3182S55 + S3177S58 + S3171S58S92 + S3170S55S94 + S3162S517 + S3161S514S92 + S3157S520 + S3138S510S92 + S3134S516 + S3132S510S94 + S3124S522 + S3116S59 + S3111S512 + S3105S512S92 + S3104S59S94 + S3101S518 + S396S521 + S372S514S92 + S366S514S94 + S362S520S92 + S350S513 + S339S516S92 + S338S513S94 + S333S516S94 + S330S525 + S329S522S92)x5 + (S112S3302 + S112S3296S92 + S112S3292S56 + S112S338S516 + S112S332S516S92 + S112S328S522 + S3428 + S3422S92 + S3418S56 + S3362S54 + S3356S54S92 + S3352S510 + S3306S52 + S3300S52S92 + S3290S58S92 + S3286S514 + S3250 + S3244S92 + S3240S56 + S3238S94 + S3232S96 + S3230S512 + S3228S56S94 + S3224S512S92 + S3220S518 + S3184S54 + S3178S54S92 + S3174S510 + S3172S54S94 + S3166S54S96 + S3162S510S94 + S3118S58 + S3112S58S92 + S3108S514 + S3106S58S94 + S3100S58S96 + S396S514S94 + S352S512 + S346S512S92 + S340S512S94 + S336S518S92 + S334S512S96 + S332S524 + S330S518S94)x6.
4. By (10), δ(12) = 0. Then, compute λ(12)(x) = xλ(11)(x), l(12) = l(11) = 6, and γ(12) = γ(11), respectively.
2. Set k = 13. Because k = 13 > 2t = 12, the recursion stops.
Finally, the error-locator polynomial μ(12)(x) = L6(x) of degree 6 is obtained. By applying Chien search method, the roots of L6(x) are exactly the inverse of the six error locators {0, 1, 2, 3, 15, 26}. A C++ program shows that the total weight-6 error patterns with S1 = 0 can be corrected.

4. Conclusions

In this paper, a study on the algebraic decoding of the weight-6 error patterns of the algebraic decoding of the (89, 45, 17) QR code with reducible generator polynomial, proposed by Truong et al. (2008), is presented. A detailed example shows that the IFBM algorithm can obtain a valid error-locator polynomial L6(x) to correct the all weight-6 error patterns with S1 = 0 in the (89, 45, 17) QR code.

References

[1]  E. Prange, “Cyclic error-correcting codes in two symbols,” AFCRC-TN-57-103, Air Force Cambridge Research Center, Cambridge, Mass. Sept. 1957.
[2]  S. B. Wicker, Error Control Systems for Digital Communication and Storage, Englewood Cliffs, NJ: Prentice Hall, 1995.
[3]  M. Elia, “Algebraic decoding of the (23, 12, 7) Golay codes,” IEEE Trans. Inf. Theory, vol. 33, no. 1, pp. 150–151, Jan. 1987.
[4]  I. S. Reed, X. Yin, T. K. Truong, and J. K. Holmes, “Decoding the (24, 12, 8) Golay code,” Proc. IEE, vol. 137, no. 3, pp. 202–206, May 1990.
[5]  I. S. Reed, X. Yin, and T. K. Truong, “Algebraic decoding of the (32, 16, 8) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 36, no. 4, pp. 876–880, July 1990.
[6]  R. He, I. S. Reed, T. K. Truong, and X. Chen, “Decoding the (47, 24, 11) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 47, no. 3, pp. 1181–1186, Mar. 2001.
[7]  Y. Chang, T. K. Truong, I. S. Reed, H. Y. Cheng, and C. D. Lee, “Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes,” IEEE Trans. on Comm., vol. 51, no. 9, pp. 1463–1473, Sept. 2003.
[8]  Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S.H. Chen, “Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm,” J. Inf. Sci. Eng., vol. 23, no. 1, pp. 127–145, Jan. 2007.
[9]  T. K Truong, P. Y. Shih, W. K. Su, C. D. Lee, and Y Chang, “Algebraic decoding of the (89, 45, 17) quadratic residue code,” IEEE Trans. Inf. Theory, vol. 54, no. 11, pp. 5005–5011, Nov. 2008.
[10]  T. C. Lin, T. K. Truong, H. P. Lee, and H. C. Chang, “Algebraic decoding of the (41, 21, 9) quadratic residue code,” Inf. Sci., vol. 179, no. 19, pp. 3451–3459, Sept. 2009.
[11]  T. C. Lin, H. C. Chang, H. P. Lee, S. I. Chu, and T. K. Truong, “Decoding of the (31, 16, 7) quadratic residue code,” J. Chin. Inst. Eng., vol. 33, no. 4, pp. 573–580, June 2010.
[12]  T. C. Lin, W. K. Su, P. Y. Shih, and T. K. Truong, “Fast decoding of the (89, 45, 17) quadratic residue code,” IEEE Communications Letters, vol. 15, no. 2, pp. 226–228, Feb. 2011.
[13]  X. Chen, I. S. Reed, T. Helleseth, T. K. Truong, “Use of Grobner bases to decode binary cyclic codes up to the true minimum distance,” IEEE Trans. on Comm., vol. 40, no. 5, pp. 1654–1661, Sept. 1994.
[14]  I. S. Reed, M. T. Shih, and T. K. Truong, “VLSI design of inverse-free Berlekamp-Massey algorithm,” IEE Proc. On Computers and Digital Techniques, vol. 138, no. 5, pp. 295–298, Sept. 1991.
[15]  R. T. Chien, “Cyclic decoding procedure for the Bose- Chaudhuri-Hocquenghem codes,” IEEE Trans. on Inf. Theory, vol. 10, no. 4, pp. 357–363, Oct. 1964.