American Journal of Mathematical and Computer Modelling
Volume 2, Issue 1, February 2017, Pages: 6-12

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

Yani Zhang, Xiaomin Bao, Zhihua Yuan, Xusheng Wu

School of Mathematics & Statistics, Southwest University, Chongqing, China

(Xiaomin Bao)

Yani Zhang, Xiaomin Bao, Zhihua Yuan, Xusheng Wu. Decoding of the Five-Error-Correcting Binary Quadratic Residue Codes. American Journal of Mathematical and Computer Modelling. Vol. 2, No. 1, 2017, pp. 6-12. doi: 10.11648/j.ajmcm.20170201.12

Received: October 29, 2016; Accepted: November 28, 2016; Published: January 6, 2017

Abstract: In this paper, a new efficient syndrome-weight decoding algorithm (NESWDA) is presented to decode up to five possible errors in a binary systematic (47, 24, 11) quadratic residue (QR) code. The main idea of NESWDA is based on the property cyclic codes together with the weight of syndrome difference. The advantage of the NESWDA decoding algorithm over the previous table look-up methods is that it has no need of a look-up table to store the syndromes and their corresponding error patterns in the memory. Moreover, it can be extended to decode all five-error-correcting binary QR codes.

Keywords: Cyclic Codes, Decoding, Quadratic Residue Code

Contents

1. Introduction

The well-known QR codes, introduced by Prange in his report [1] in 1957, are cyclic BCH codes with code rates greater than or equal to one-half and generally have large minimum distances so that most of the known QR codes are among the best-known codes. The code augmented by a parity bit, for instance, the (24, 12, 8) QR code has be used for numerous communication links, including the Voyager imaging system link of NASA [2]. In the past decades, a series of different decoding methods given in [6-15] have been developed to decode the QR code. However, these algebraic decoding techniques require a large number of complicated computations in a finite field. These complicated computations will lead to a time delay in the decoding procedures and therefore the decoding time will become unrealistic when the code length is large. Therefor, to reduce the decoding complexity, we introduce the NESWDA algorithm, which can be used to decode the (47,24,11) QR code. It allows for the correction of up to errors, where denotes the greatest integer less than or equal to x; t is the error-correcting capability and d=11 is the minimum Hamming distance of the code.

Recently, table look-up decoding algorithms have been developed to decode the (47, 24, 11) QR code. The full lookup table in the conventional table look-up decoding algorithm (CTLDA) needs

syndromes and their corresponding error patterns. It requires 1729647 × (6bytes + 3bytes) ≈ 14.85 Mbytes memory size to store the table. Such a large memory required makes the computation very complicated. An efficient algorithm named look-up table decoding (LTD) algorithm in [3] to decode the (47, 24, 11) QR code needs 1.05 Mbytes memory size to store the table. The well-known syndrome decoder [2]

Requires

syndromes corresponding to error patterns stored in a table with a 36801 × (6bytes +3bytes)=1024 ≈ 323.45 Kbytes memory size, called the reduced lookup table (RLT). However, this memory size of the RLT is still so large that one needs to further reduce the memory size of the look-up table. To achieve this end, an efficient table look-up decoding algorithm (TLDA) in [4] is developed to decode the (47, 24, 11) QR code, the memory size of the developed condensed look-up table consists of 36.6 Kbytes, and Lin et al. [5] used a novel table look-up decoding algorithm, called the cyclic weight (CW) decoding algorithm, together with a memory size 20.43 Kbytes to decode the (47, 24, 11) QR code. As shown in this paper, the proposed NESWDA does not need a memory size to store the look-up table. The prime idea of the proposed NESWDA 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. Moreover, no complicated computation in the finite field is required in the proposed NESWDA and it also can be extended to decode all five-error-correcting binary QR codes.

The remainder of this paper is organized as follows: The background of the binary QR codes is briefly given in Section 2. The proposed NESWDA is described in Section 3. In Section 4, two examples are used to demonstrate the proposed NESWDA. Finally, this paper concludes with a brief summary in Section 5.

2. Background of the Binary QR Codes

The binary QR codes are a nice family of linear cyclic codes. Let  or  denote the binary QR codes with generator polynomial  over . The length of this code is a prime number of the form , where l is some integer. Also, let  denote the message length or information length, and  denote the minimum Hamming distance of the code. The set  of quadratic residues modulo  is the set of nonzero squares modulo ; that is, . If = 47, then its quadratic residue set is

Let the symbol  denote the binary (47, 24, 11) QR code. Let  be a root of primitive irreducible polynomial such that  is a generator of the multiplicative group of all nonzero elements in . Then, the element  where , 481, is a primitive 47th root of unity in . The generator polynomial of the binary (47, 24, 11) QR code is defined by

where the degree of  is 23, which is the multiplicative order of the integer 2 modulo the code length 47; that is,. The (47, 24, 11) QR code generated by this manner can correct up to five errors.

A codeword of binary QR code is a polynomial  such that it is a multiple of the generator polynomial . If the codeword  is transmitted through a noisy channel, then the received polynomial  can be expressed as the sum of the codeword polynomial  and the error polynomial . For simplicity, let the message or information, codeword, error pattern, received word, and syndrome be expressed as the binary vector forms m, c, e, r  and s , respectively. The systematic codeword of the vector form is given by , where  is called the systematic generator matrix. Let be amatrix and  be a identity matrix, and G can be expressed as G . The parity-check matrix  can be expressed as, where  denotes the transpose matrix of . The vector form of the syndrome is defined by , where  denotes the  transpose matrix of ; that is,  can be expressed as

(1)

For , has the following form:

Figure 1.  of .

3. Decoding Algorithm and Theorems

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  and b be two binary vectors, then

w(a+b) = w(a) + w(b) −           (2)

Corollary 1. If for , then

w(a+b) = w(a) + w(b).                   (3)

The following Theorem is useful to compute the syndrome of the received word when the received word shifts one bit to the right.

Theorem 2. Let  be the syndrome polynomial corresponding to a received polynomial . Also, let  be the polynomial obtained by cyclically shifting the coefficients of one bit to the right. Then the remainder obtained when dividing  by  is the syndrome corresponding to .

For a detailed proof, see [2].

However, if the syndrome cyclically shifts many times, then the syndrome computation is quite time-consuming for dividing  by  many times. The following theorem provides an efficient method to compute  for , and it can save a lot of computational time.

Theorem 3. For the binary QR codes, let  be an element of r and  be the jth row vector of  for . Then the syndrome  of  for  has the form

(4)

where the suffix  of  denotes  mod .

Proof. Let  and for . We have

The proof is thus completed.

Theorem 3 reveals that the syndrome of  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.

Theorem 4. For the binary QR codes, it is assumed that there are errors in the received word, where and . All  errors are in the parity-check bits if and only if the weight of syndrome .

For a detailed proof, see [4].

Theorem 5. For the binary QR codes, if  errors are in the information bits of the received word, whereand , then the weight of the corresponding syndrome vector satisfies

(5)

For a detailed proof, see [5].

Theorem 6. For the binary QR codes, let  be an error pattern and , be respectively its message section and parity check section. Assume that ,  and , where , then the weight of the corresponding syndrome vector satisfies

(6)

Proof. As

the proof is thus completed.

Given a received word , the syndrome  of  can be fast computed by theorem 3. According to theorem 4, if  then error positions are in the parity-check bits of . If , then the error positions are in the information bits of . Let  denote the jth row vector of , where . Also let  denote the syndrome difference between the syndromes of  and  in each decoding step . By using the weight of , the error cases can be quickly determined. Let  be a k-tuples unit vector and  has only one nonzero component at the th position, where . By using these properties the decoding algorithm can be constructed. Let case I, C, P denote the error position in the information bits, center bit, and parity-check bits of , respectively. The decoding steps of the proposed NESWDA work as follows:

(1)   (No error, P, PP, PPP, PPPP, and PPPPP cases) By theorem 3, compute  and . If , then the information vector is . Go to step (8).

(2)   (I, II, III, IIII, and IIIII cases) By theorem 3, compute and . If , then the corrected information vector is . Go to step (8).

(3)   (IP, IPP, IPPP, IPPPP, C, CP, CPP, CPPP, and CPPPP cases) Compute the syndrome difference  for  and . If , then the corrected information vector . Go to step (8).

(4)   (IC, IIC, IIIC, IIIIC, IIP, IIIP, and IIIIP cases) Compute the syndrome difference  for  and . If  and , then the corrected information vector . If  and, then the corrected information vector. Go to step (8).

Table 1. The number of error patterns in each decoding step of C47.

 Steps Cases Number of error patterns 1 P, PP, PPP, PPPP, PPPPP 44551 2 I, II, III, IIII, IIIII 44551 3 IP,IPP,IPPP,IPPPP,C,CP,CPP,CPPP,CPPPP 261649 4 IC, IIC, IIIC, IIIIC, IIP, IIIP, IIIIP 261119 5 IIPP, IIPPP, ICP, ICPP, ICPPP 559153 6 IICP, IIICP, IIIPP 494615 7 IICPP 64009 Sum 35

(5)   (IIPP, IIPPP, ICP, ICPP, and ICPPP cases) Compute the syndrome difference  for and . If , then the corrected information vector . Go to step (8).

(6)   (IICP, IIICP, and IIIPP cases) Compute the syndrome difference for  and . If and , then the corrected information vector . If  and , then the corrected information vector . Go to step (8).

(7)   (IICPP case) Compute the syndrome difference  for  and. If , then the corrected information vector . Go to step (8).

(8)   Stop.

Table 1 lists all the 35 error cases and the number of error patterns in each decoding step of of the proposed NESWDA. The flowchart of the proposed NESWDA is shown in figure 1.

4. Example

In this section, two examples are presented to illustrate the proposed NESWDA.

Example 1. Let a information m = (010000000000000000000000) be encoded into a  codeword

c = (01000000000000000000000001111011101101110001100).

If the received word

r = (11110000000000000000000001111011101101110001100),

then the error pattern

e = (10110000000000000000000000000000000000000000000),

which means a III error case. The decoding procedure is composed of the following steps.

(1)   Compute s = (11010100010110000111101) and w(s) = 12. Since w(s) > 5, go to step 2.

(2)   Compute  = (10110000000000000000000) and w() = 3 ≤ 5. The corrected information vector is

m = (111100000000000000000000) + (101100000000000000000000)

= (010000000000000000000000).

Go to stop.

Figure 2. Flowchart of the proposed NESWDA.

Example 2. Let a information m = (010000000000000000000000) be encoded into a  codeword

c = (01000000000000000000000001111011101101110001100).

If the received word

r = (01110000000000000000000100111011101101110001100),

then the error pattern

e = (00110000000000000000000101000000000000000000000),

which means a IICP case. The decoding procedure is composed of the following steps.

(1)   Compute s = (10000101111010100000100) and w(s) = 9 > 5, go to step 2.

(2)   Compute = (11111010101101011011110) and w() = 16 > 5, go to step 3.

(3)   Compute  for  and w().

= (10000101111010100000100) -

(11110111011011100011000)

= (01110010100001000011100),

w() = 9.

= (10000101111010100000100) −

(01111011101101110001100)

= (11111110010111010001000),

w() = 13:

= (10000101111010100000100) −

(10000100011011110000110)

= (00000001100001010000010),

w() = 5.

= (10000101111010100000100) −

(11100110110111000100001)

= (01100011001101100100101),

w() = 11.

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

(4)   Compute  forand w().

= (11111010101101011011110) −

(11110111011011100011000)

= (00001101110110111000110),

w() = 12.

= (11111010101101011011110) −

(01111011101101110001100)

= (10000001000000101010010),

w() = 6.

= (11111010101101011011110) −

(11100110110111000100001)

= (00011100011010011111111),

w() = 14.

Since every w() > 4, go to step 5.

(5)   Compute  for and w().

= (00001001001100110010000), w() = 6.

= (01001111010111111011010), w() = 15.

= (10010100010110000111101), w() = 11.

= (11000011100001101001110), w() = 11.

= (00011000100000010101001), w() = 7.

= (01010000010100101110110), w() = 10.

Since every w() > 3, go to step 6.

(6)   Compute  for  and w().

= (01110110011011001001010), w() = 12.

= (00110000000000000000000), w() = 2.

Since w() = 2 ≤ 3, and . The corrected information

=

(011100000000000000000001) +

(000000000000000000000001) +

(001100000000000000000000)

= (010000000000000000000000).

Go to stop.

5. Conclusions

A new NESWDA decoding algorithm is developed to correct up to five errors for the approximate half-rate (47, 24, 11) QR code. The main idea behind the proposed NESWDA is based on the fact that it makes use of the properties of cyclic codes, the weight of syndrome difference. The proposed NESWDA has no need of a look-up table to store the syndromes and their corresponding error patterns in the memory. Moreover, it can be extended to decode all five-error-correcting binary QR codes.

References

1. E. Prange, Some Cyclic Error-Correcting Codes with Simple Decoding Algorithms, Air Force Cambridge Research Center, Cambridge, MA, 1958 (TN-58-156).
2. S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, 1995.
3. Y. H. Chen, T. K. Truong, C. H. Huang, C. H. Chien, A lookup table decoding of systematic (47, 24, 11) quadratic residue code, Information Science 179 (2009) 2470-2477.
4. T. C. Lin, H. P. Lee, H. C. Chang, S. I. Chu, T. K. Truong, High speed decoding of the binary (47, 24, 11) quadratic residue code, Information Science 180 (2010) 4060-4068.
5. T. C. Lin, H. P. Lee, H. C. Chang, T. K. Truong, A cyclic weight algorithm of decoding (47, 24, 11) quadratic residue code, Information Science 197 (2012) 215-222.
6. G. Dubney, I. S. Reed, T. K. Truong, J. Yang, Decoding the (47, 24,11) quadratic residue code using bit-error probability estimates, IEEE Transactions on Communications 57 (2009).
7. R. He, I. S. Reed, T. K. Truong, X. Chen, Decoding the (47, 24,11) quadratic residue code, IEEE Transactions on Information Theory 47 (2001) 1181-1186.
8. T. C. Lin, T. K. Truong, and H. P. Lee, Algebraic decoding of the (41, 21, 9) quadratic residue code, Information Sciences 179 (2009) 3451-3459.
9. X. Chen, I. S. Reed, T. Helleseth, and T. K. Truong, Use of Grobner bases to decode binary cyclic codes up to the true minimum distance, IEEE Transactions on Information Theory 40 (1994) 1654-1661.
10. Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, S. H. Chen, Algebraic decoding of Quadratic Residue codes using Berlekamp–Massey algorithm, Journal of Information Science and Engineering 23 (2007) 127-145.
11. I. S. Reed, X. Chen, Error-Control Coding for Data Networks, Kluwer, Boston, MA, 1999.
12. I. S. Reed, M. T. Shih, T. K. Truong, VLSI design of inverse-free Berlekamp-Massey algorithm, Processings IEE 138 (1991) 295-298.
13. I. S. Reed, T. K. Truong, X. Chen, X. Yin, The algebraic decoding of the (41, 21, 9) Quadratic Residue code, IEEE Transactions on Information Theory 38(1992) 974-986.
14. I. S. Reed, X. Yin, T. K. Truong, Algebraic decoding of the (32, 16, 8) Quadratic Residue code, IEEE Transactions on Information Theory 36 (1990) 876-880.
15. I. S. Reed, X. Yin, T. K. Truong, J. K. Holmes, Decoding the (24, 12, 8) Golay code, IEE Proceedings 137 (3) (1990) 202-206.

 Contents 1. 2. 3. 4. 5.
Article Tools