Decoding of the FiveErrorCorrecting Binary Quadratic Residue Codes
Yani Zhang, Xiaomin Bao, Zhihua Yuan, Xusheng Wu
School of Mathematics & Statistics, Southwest University, Chongqing, China
Email address:
To cite this article:
Yani Zhang, Xiaomin Bao, Zhihua Yuan, Xusheng Wu. Decoding of the FiveErrorCorrecting Binary Quadratic Residue Codes. American Journal of Mathematical and Computer Modelling. Vol. 2, No. 1, 2017, pp. 612. 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 syndromeweight 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 lookup methods is that it has no need of a lookup table to store the syndromes and their corresponding error patterns in the memory. Moreover, it can be extended to decode all fiveerrorcorrecting binary QR codes.
Keywords: Cyclic Codes, Decoding, Quadratic Residue Code
1. Introduction
The wellknown QR codes, introduced by Prange in his report [1] in 1957, are cyclic BCH codes with code rates greater than or equal to onehalf and generally have large minimum distances so that most of the known QR codes are among the bestknown 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 [615] 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 errorcorrecting capability and d=11 is the minimum Hamming distance of the code.
Recently, table lookup decoding algorithms have been developed to decode the (47, 24, 11) QR code. The full lookup table in the conventional table lookup 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 lookup 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 wellknown 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 lookup table. To achieve this end, an efficient table lookup decoding algorithm (TLDA) in [4] is developed to decode the (47, 24, 11) QR code, the memory size of the developed condensed lookup table consists of 36.6 Kbytes, and Lin et al. [5] used a novel table lookup 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 lookup 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 paritycheck matrix. Moreover, no complicated computation in the finite field is required in the proposed NESWDA and it also can be extended to decode all fiveerrorcorrecting 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 paritycheck 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 timeconsuming 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 paritycheck 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 paritycheck 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 ktuples 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 paritycheck 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).
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.
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 halfrate (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 lookup table to store the syndromes and their corresponding error patterns in the memory. Moreover, it can be extended to decode all fiveerrorcorrecting binary QR codes.
References