covid
Buscar en
Journal of Applied Research and Technology. JART
Toda la web
Inicio Journal of Applied Research and Technology. JART High-Speed Decoding of the Binary Golay Code
Información de la revista
Vol. 11. Núm. 3.
Páginas 331-337 (junio 2013)
Compartir
Compartir
Descargar PDF
Más opciones de artículo
Visitas
14466
Vol. 11. Núm. 3.
Páginas 331-337 (junio 2013)
Open Access
High-Speed Decoding of the Binary Golay Code
Visitas
14466
H.P. Lee1, C.H. Chang1, S.I. Chu2
1 Department of Computer Science and Information Engineering, Fortune Institute of Technology, Kaohsiung 83160, Taiwan
2 Department of Electronic Engineering, National Kaohsiung University of Applied Sciences, Kaohsiung 807, Taiwan
Este artículo ha recibido

Under a Creative Commons license
Información del artículo
Resumen
Texto completo
Bibliografía
Descargar PDF
Estadísticas
Figuras (1)
Tablas (4)
Table 1. MSLT for the Binary Systematic Golay Code.
Table 2. Computer Decoding Time for Decoding the Binary Golay Code (in μs).
Mostrar másMostrar menos
Abstract

Recently, some table-lookup decoding algorithms (TLDAs) have been used to correct the binary Golay code. This paper proposes an efficient high-speed TLDA called message-syndrome decoding algorithm (MSDA) by using the message syndrome to correct the binary systematic Golay code. The proposed MSDA is based on the novel message-syndrome lookup table (MSLT). The MSLT merely consists of 12 candidate syndromes and its memory size is significantly smaller than other existing lookup tables. Computer software simulation results show that the decoding speed of the proposed MSDA is superior to other proposed TLDAs.

Key words:
Golay code
weight
syndrome
error pattern
Texto completo
1Introduction

The well-known binary Golay code, also called the binary (23, 12, 7) quadratic residue (QR) code [2], was first discovered by Golay [1] in 1949. It is a very useful perfect linear error-correcting code; particularly, it has been used in the past decades for a variety of applications involving a parity bit being added to each word to yield a half-rate code called the binary (24, 12, 8) extended Golay code. One of its most interesting applications is the provision of error control in the Voyager missions [2]. The Golay code can allow the correction of up to t=⌊(d-1)/2⌋=⌊(7-1)/2⌋=3 errors, where ⌊x⌋ denotes the greatest integer less than or equal to x, t is the error-correcting capability, and d is the minimum Hamming distance of the code.

In the past few decades, several decoding techniques have been developed to decode the binary Golay codes, for example, the famous algebraic decoding algorithm (ADA) developed by Elia [3], the notable shift-search algorithm proposed by Reed et al. [4] after that, and the inverse-free Berlekamp–Massey algorithm used to obtain the error-locator polynomial by Chen et al. [5]. The above is some representative literature on ADAs used to correct Golay codes.

Recently, the TLDAs given in [6-9] have acquired a prominent role in error-correcting decoding. A TLDA with a refined lookup table (RLT) has been proposed by Lin et al. [8]; the RLT only needs 168 bytes memory size. The memory size of the RLT is the smallest memory size required to correct the Golay code until now. In general, the TLDA makes considerably faster decoding speeds possible for the cyclic codes, in comparison with the ADA. However, the TLDA requires an extra memory space in the decoder chip or software and it increases the decoding cost rapidly when the code length is large. Although the ADA does not need any lookup table, it requires a large number of complicated computations in the finite field. These complicated computations will degrade the decoding performance and lead to a serious decoding delay as the code length increases [10].

Chen et al. [7] proposed the fast lookup table decoding algorithm (FLTDA) with a lookup table of 1.35K bytes by using the shift-search algorithm [4] to decode the Golay code. The famous syndrome decoding algorithm (SDA) with a reduced-size lookup table (RSLT) given in [2, p119] requires 89 syndromes and their corresponding error patterns, whereas the RSLT requires 445 bytes of memory.

Lin et al. [8] proposed the syndrome-weight decoding algorithm (SWDA) with RLT which needs 168 bytes of memory, and the simulation result shows that the decoding speed is approximately 9.7 times faster than the improved Elia’s decoding algorithm (EDA).

In this paper, an efficient high-speed MSDA with a MSLT is proposed to decode the binary systematic Golay code. The novel MSLT consists only of 12 candidate syndromes which have one error in the message part of the received vector, and it merely requires 24 bytes of memory. Software simulation results show that the average decoding speed is the fastest among the TLDAs as mentioned above. In the four-error soft-decision decoder in [11], the improved EDA is the role of the hard-decision decoder. We substituted the proposed MSDA for the improved EDA in the four-error soft-decision decoder. Apparently, the decoding speed of the soft-decision decoder was faster than before.

The remainder of this paper is organized as follows: The background of the binary systematic Golay code is briefly reviewed in Section 2. Some related TLDAs and related theorems are briefly introduced in Section 3. The proposed MSDA is presented in Section 4. Computer simulation results are given in Section 5. Finally, this paper concludes with a brief summary in Section 6.

2Background of the binary systematic Golay code

The binary (23, 12, 7) Golay code can be defined as a linear cyclic code or QR code [2]. For the binary Golay code over finite field GF(211), its quadratic residue set is given by

The generator polynomial g(x) of the binary Golay code is defined by

where β is a primitive 23rd root of unity in GF(211). Let the codeword polynomial C(x)=∑i=0n-1Cixi, where CiGF(2) for 0i22, and the message polynomial m(x)=∑i=0k-1mixi, where k=12 is the message length and miGF(2) for 0i11. C(x) is a multiple of g(x), namely, C(x)=m(x)g(x). Also, let the product m(x)x11 divide by g(x), then one has m(x)x11=q(x)g(x)+d(x). Multiplying both sides of last expression by x12 and using x23=1, one yields d(x)x12+m(x)=(q(x)x12)g(x). The term (d(x)x12+m(x)), which is a multiple of g(x), is a systematic codeword given by

where p(x)=∑i=1222pixi denotes the parity-check polynomial [12] of a codeword and piGF(2) for 12i22.

The binary systematic Golay code is practically applied in the standard of the communication system for automatic link establishment (ALE) by the United States Department of Defense [13]. Now, let a 12-bit message be encoded into a 23-bit systematic codeword and be transmitted through a noisy channel to obtain a received word of the form r(x)=c(x)+e(x). e(x)=∑i=022eixi is the error pattern polynomial, where eiGF(2) for 0i22. The syndromes of the code are defined by

where iQ23.

To simplify the polynomial expressions above, the message, codeword, error pattern, received word, and syndrome polynomials can be expressed as the binary vector forms m=(m11... m1m0), c=(c22... c1c0), e=(e22... e1e0), r=c+e=(r22... r1r0), and s=(s10... s1s0), respectively. For the binary systematic Golay code, it follows from [2, p85] that the systematic generator matrix G can be expressed as follows:

where P and I12 denote the 12×11 matrix and the 12×12 identity matrix, respectively. The systematic vector form of the codeword can be obtained by

The parity-check polynomial h(x)=x12+x10+x7+x4+x3+x2+x+1 is a factor of x23 – 1. The 11×23 parity-check matrix H can be expressed as follows:

where PT is a 11×12 transpose matrix of P and I11 is a 11×11 identity matrix.

The HT denotes the 23×11 transpose matrix of H; that is, HT=[I11P]23×11. The vector form of the syndrome can be defined by

The following lemma given in [14] shows that the mapping between the syndromes and error patterns under the error-correcting capability is one-to-one.

Lemma 1.

The mapping between the syndromes of a code and the corresponding error patterns of weightt is one-to-one.

3Related work and theorems

In this section, some related TLDAs and theorems are briefly introduced in order to develop the proposed MSDA. For the TLDA, the following definition, theorems and corollary given in [9] are needed.

Definition 1.

Let the Hamming norm or weight of a binary vector a=(an-1... a1a0) be designated by w(a). The Hamming distance between two binary vectors a and b is defined by d(a, b)=w(a+b).

Theorem 1.

Let a=(an-1... a1a0) and b=(bn-1... b1b0) be two binary vectors, then

Corollary 1.

Let a and b, defined in Definition 1, be two binary vectors. If aibi=0 for 1in, then

Theorem 2.

For the binary systematic (n, k, d) QR codes, let us assume that there are v errors in the received word, where 1vt. All v errors occur in the nk parity-check bits if and only if the weight of syndrome w(s)=v.

As mentioned above, the error-correcting capability of the binary Golay code is t=3. The full lookup table (FLT) in the conventional table lookup decoding algorithm (CTLDA) requires ∑i=1323i=2,047 syndromes and their corresponding error patterns by Lemma 1. Each syndrome and error pattern needs 2 bytes and 3 bytes, respectively, to store in the FLT. Thus, the total memory size needed for the FLT is (2047×(2+3))=10,235 bytes. However, such a large memory is less efficient in practice.

Recently, some useful TLDAs have been presented in the literature to reduce the memory size of the FLT. The LTDA [7] used the shift-search method [4] to reduce the memory size of the FLT and the binary-search method to reduce the search time in the FLT. The shift-search method deletes all v=t error patterns and keeps 1vt – 1 error patterns.

Therefore, the LTDA needs ∑i=1t-123i=∑i=1223i=276 syndromes and their corresponding error patterns; that is, the FLT needs 276×(2+3)=1,380 bytes memory size. Nevertheless, the memory size of the FLT is still large and the simulation result shows that the average decoding time of the proposed MSDA is about 10.6 times faster that the LTDA. To develop the following TLDAs, Theorem 3 is useful to reduce the memory size of the FLT. The well-known SDA with RSLT [2, p119] has the following useful theorem of the cyclic codes to dramatically reduce the memory size of the FLT. For more detailed proof of this theorem, see [2, p118].

Theorem 3.

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

Decoding the binary systematic Golay code by Theorem 3, the RSLT of the SDA only needs 1/23 memory size of the FLT, namely 10,235/23=445 bytes memory size [8]. Nonetheless, the memory size of the RSLT is still large and can be further reduced. Similarly, by Theorem 3, r(j)(x) is the polynomial obtained by cyclically shifting the coefficients of r(x) j bits to the left. Next, the syndrome difference sdi is defined by sdi=ssi for 1iN, where s is the syndrome of r, si is the syndrome in lookup table, and N is the table size. Similarly, the syndrome difference sdi(j) is defined by sdi(j)=s(j)-si for 1jn, where s(j) is the syndrome of r(j). By using the property of the syndrome difference, the RLT of the SWDA only requires 168 bytes. However, the decoding speed is not very outstanding according to the simulation result. To overcome this problem, the MSDA is presented by using the syndrome that only one error occurred in the message part of the received word.

4MSDA for the binary Golay code

In this section, an efficient high-speed MSDA with a MSLT for decoding the binary systematic Golay code is developed to further reduce the decoding time and the memory size of the RLT. By Theorem 2 and (8), it is obvious that at least one error is in the message bits if the weight of syndrome w(s)>3.

Definition 2.

The message-syndrome lookup table (MSLT) is a table of all the error patterns occurred in the message part with weight 1≤v≤⌊t/2⌋ together with their corresponding syndromes, where ⌊x⌋ denotes the smallest integer less than or equal to x.

Therefore, the novel MSLT merely consists of 12 candidate syndromes which are the syndromes of having one error in the message part; that is, si is the syndrome of ei which is one error located at bit i for 1i12. The MSLT is listed in Table 1.

Table 1.

MSLT for the Binary Systematic Golay Code.

Syndrome  Syndrome 
s1=(01011100011)  s2=(10111000110) 
s3=(00101101111)  s4=(01011011110) 
s5=(10110111100)  s6=(00110011011) 
s7=(01100110110)  s8=(11001101100) 
s9=(11000111011)  s10=(11010010101) 
s11=(11111001001)  s12=(10101110001) 

To develop the proposed MSDA by using the MSLT, the following lemma and properties are necessary.

Lemma 2.

For the binary Golay code, let e be an error pattern, and let ep and em be its parity-check part and message part, respectively. Let sp and sm be the syndromes corresponding to ep and em, respectively. Assume that w(e)3, then we have

  • (i)

    w(sp)=w(ep);

  • (ii)

    w(sm) ≥dw(em), whered=7;

  • (iii)

    ((sm<<12)+em) is always a codeword, where “<<“ denotes the logical left shift operator in programming or the extension by zeros on the right in mathematics.

Proof: By Equation (8), (i) is obvious. Again, by Equation (8), given that ((sm<<12)+em)HT=((sm<<12)+em)[l11P]=(sm<<12)[l11P]+em[l11P]=sm+sm=0, ((sm<<12)+em) is thus a codeword, which proves (iii). Hence, w((sm<<12)+em)=w(sm)+w(em) ≥ d, that is, w(sm) ≥ dw(em). The proof is thus completed.

By Lemma 2, if vt, then one can obtain the following two properties.

Property 1.

For the binary Golay code, the weight of the syndrome difference w(sdi) has the following cases:

Case 1:  If w(s)3, then all three errors are in the parity-check part and no error is in the message part. 
Case 2:  If w(s)>3 and w(sdi)<3, then only 1 error is in the message part. 
Case 3:  If w(s)>3 and w(sdi)>3, than at least 2 errors are in the message part. 

Next, for Case 3 of Property 1, the r and s are cyclically shifted left by 11 bits, then one obtains r(11) and s(11), respectively. Thus, one yields the following property.

Property 2

For the binary Golay code, if w(s)>3 and w(sdi)>3, then the weight of s(11) and sdi(11) have the following cases:

Case 1:  If w(s(11))=2 or 3, then r has at least 2 errors in the message part and no error is in the parity-check part. 
Case 2:  If w(s(11))>3 and w(sdi(11))≤2, then r has at least 2 errors in the message part. 
Case 3:  If w(s(11))>3 or w(sdi(11))>3, then 2 errors are in the message part and one of them is at the position of bit 0. 

By using the MSLT, the decoding process of the MSDA is as follows:

  • (1)

    Giving a received vectorr.

  • (2)

    Compute the syndromes=rHT and its weightw(s).

  • (3)

    Ifw(s)3, then returnc=r – (s<<12), and go to step 13.

  • (4)

    For 1i12, compute the syndromesdi=ssi and its weightw(sdi).

  • (5)

    Ifw(sdi)2, then returnc=r – (sdi<<12) – (1<<(i – 1)), and go to step 13.

  • (6)

    Cyclically shiftr ands left by 11 bits obtainingr(11) ands(11), and then computew(s(11)).

  • (7)

    Ifw(s(11))=2 or 3, then returnc=((r(11) – (s(11)<<12))<<12) – ((r(11) – (s(11)<<12))>>11), and go to step 13.

  • (8)

    For 1i12, compute the syndrome sdi(11)=s(11)-si and its weight w(sdi(11)).

  • (9)

    If w(sdi(11)) or 2, then return c=((r(11)-(sdi(11)<<12)-(1<<(i-1)))<<12)-((r(11)-(sdi(11)<<12)-(1<<(i-1)))>>11), and go to step 13.

  • (10)

    Computer=r – 1 ands=ss1.

  • (11)

    For 2i12, compute the syndromesdi=s’ –si and its weightw(sdi).

  • (12)

    Ifw(sdi)=1, then returnc=r’ – (sdi<<12) – (1<<(i – 1)).

  • (13)

    Stop.

An example is given below. By (6), a message vector m=(100000000000) is encoded into a binary systematic Golay code c=(10101110001100000000000). Assume that a noise vector is e=(00010000000000010000001), then the received word becomes r=c+e=(10111110001100010000001). The decoding steps proceed as follows:

  • (1)

    The received vector isr=(10111110001100010000001).

  • (2)

    Compute the syndromes=(10000001111) and its weightw(s)=5.

  • (3)

    Given thatw(s)>3, go to step 4.

  • (4)

    Fori=1, compute the syndromesd1=ss1=(11011101100) and its weightw(sd1)=7.

  • (5)

    Given thatw(sd1)>2, go to step 4. …repeating steps 4 and 5…

  • (4)

    Fori=12, compute the syndromesd12=ss12=(00101111110) and its weightw(sd12)=7.

  • (5)

    Given thatw(sd12)>2, go to step 6.

  • (6)

    Cyclically shiftr ands left by 11 bits obtainingr(11)=(10001000000110111110001) ands(11)=(01101011101), and then computew(s(11))=7.

  • (7)

    Given thatw(s(11)) ≠ 2 or 3, go to step 8.

  • (8)

    Fori=1, compute the syndrome sd1(11)=s(11)-s1=(00110111110) and its weight w(sd1(11))=7.

  • (9)

    Given that w(sd1(11))>2, go to step 8.…repeating steps 8 and 9…

  • (8)

    Fori=12, compute the syndrome sd12(11)=s(11)-s12=(1100010100) and its weight w(sd12(11))=5.

  • (9)

    Given that w(sd12(11))>2, go to step 10.

  • (10)

    Computer=r – 1=(10111110001100010000000) ands=s – s1=(11011101100).

  • (11)

    Fori=2, compute the syndromesd>2=s’ –s2=(01100101010) and its weightw(sd2)=5.

  • (12)

    Given thatw(sd2)>1, go to step 11. …repeating steps 11 and 12…

  • (13)

    Fori=8, compute the syndromesd8=s’ –s8=(00010000000) and its weightw(sd8)=1.

  • (14)

    Ifw(sd8)=1, then return the correct codewordc=r1 – (sd8<<12) – (1<<(i – 1))=(10111110001100010000000) – (00010000000000000000000) – (10000000)=(10101110001100000000000). Go to step 13.

  • (15)

    Stop.

Therefore, the correct message can be retrieved from the received vector.

5Simulation results

The proposed MSDA has been programmed in C++language. On an Intel Q6600 PC, all codewords with up to three errors, namely 212×∑i=13Ci23=8,384512 received vectors, were created to check every possible error pattern. The detailed decoding times for decoding the binary systematic Golay code with different decoding algorithms are given in Table 2. The proposed MSDA has the fastest average decoding time and works perfectly with an average decoding time of 0.6038 μs per error pattern.

Table 2.

Computer Decoding Time for Decoding the Binary Golay Code (in μs).

AlgorithmsNumber of errors
Average 
Proposed MSDA  0.3396  0.4228  0.6364  0.6038 
SDA with RSLT  0.7332  0.8612  0.8876  0.8705 
FLTDA with table  0.1774  0.1813  7.406  6.419 
SWDA with RLT  4.651  5.957  7.551  7.321 
Improved EDA  16.32  27.25  27.33  26.86 

From Table 2, the proposed MSDA has the fastest average decoding time and is about 44.5 times faster than the improved EDA. Furthermore, we substituted the proposed MSDA for the improved EDA in the four-error soft-decision decoder [11]. Apparently, the decoding speed of the soft-decision decoder was about 44.5 times faster than before. The decoding time of the two hard-decision decoders with respect to the SNR values is shown in Figure 1.

Figure 1.

Decoding Time of Two Hard-Decision Decoders at SNR of 0~6 dB.

(0.14MB).
6Conclusions

This paper presented a simple and more efficient decoding algorithm for decoding the binary systematic Golay code. The key ideas of the MSDA are based on the properties of cyclic codes, the one-error syndrome in the message part, the weight of syndrome, the weight of syndrome difference, Property 1, and Property 2. The MSLT of the MSDA merely requires a very small memory size of 24 bytes. These facts lead to a substantial improvement in decoding the binary systematic Golay code. Simulation results show that, following the new decoding strategies, the proposed MSDA achieves the best efficiency. Hence, it is naturally suitable and proper for DSP or embedded system software implementation.

References
[1]
M. Golay.
Notes on digital coding.
Proc. IRE, 37 (1949), pp. 657
[2]
S. Wicker.
Error Control Systems for Digital Communication and Storage, Prentice Hall, (1995),
[3]
M. Elia.
Algebraic decoding of the (23, 12, 7) Golay code.
IEEE Trans Inf Theory, 33 (1987), pp. 150-151
[4]
I.S. Reed, et al.
Decoding the (24, 12, 8) Golay code.
IEE P-COMPUT DIG T, 137 (1990), pp. 202-206
[5]
Y.H. Chen, et al.
Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm.
J Inf Sci Eng, 23 (2007), pp. 127-145
[6]
H. Chang, et al.
A weight method of decoding the (23, 12, 7) Golay code Using Reduced Lookup Table.
2008 International Conference On Communication, Circuits and Systems (ICCCAS 2008), pp. 1-5
[7]
Y.H. Chen, et al.
Efficient decoding of systematic (23, 12, 7) and (41, 21, 9) quadratic residue codes.
J Inf Sci Eng, 26 (2010), pp. 1831-1843
[8]
T.C. Lin, et al.
On the decoding of the (24, 12, 8) Golay code.
Inf Sci, 180 (2010), pp. 4729-4736
[9]
T.C. Lin, et al.
High speed decoding of the binary (47, 24, 11) quadratic residue code.
Inf Sci, 180 (2010), pp. 4060-4068
[10]
S. Lin, E.J. Jr Weldon.
Long BCH codes are bad.
Inf Contr, 11 (1967), pp. 445-451
[11]
S.I. Chu, et al.
Fast decoding of the (23, 12, 7) Golay code with four-error-correcting capability.
Eur Trans Telecomm, 22 (2011), pp. 388-395
[12]
C.A. Vázquez-Fernández, G. Vega-Hernández.
On the Weight Distribution of the Dual of some Cyclic Codes with Two Non Conjugated Zeros.
J Appl Res Technol, 9 (2011), pp. 36-48
[13]
MIL-STD-188/141B. Department of Defense Interface Standard: Interoperability and Performance Standards for Medium and High Frequency Radio Systems. http://www.everyspec.com/MIL-STD/MILSTD+(0100+-+0299)/MIL_STD_188_141B_1703
[14]
I.S Reed, et al.
The algebraic decoding of the (41, 21, 9) quadratic residue code.
IEEE Trans Inf Theory, 38 (1992), pp. 974-986
Copyright © 2013. Universidad Nacional Autónoma de México
Descargar PDF
Opciones de artículo