# The art of error correcting coding - Moreloz R.H.

ISBN 0471-49581-6

**Download**(direct link)

**:**

**16**> 17 18 19 20 21 22 .. 86 >> Next

Once the codewords have been computed in accordance to matrix H', decoding is easy. The syndrome (2.2) equals the position number in which the error occurred! In a decoding procedure, after the computation of syndrome s, when regarded as an integer, the erroneous position is then corrected as

where ® denotes exclusive-or (i.e., 0©0 = 0, 0 © 1 = 1, 1 ® 0 = 1, and 1 © 1 = 0).

Program hamming. c in the ECC home page implements the above encoding and decoding procedures for binary Hamming codes.

2.2 The binary Golay code

Golay [Gol] noticed that

This equality shows the possible existence of a perfect binary (23,12,7) code, with t = 3, that is, capable of correcting all possible patterns of at most three errors in 23 bit positions. In his paper, Golay gave a generator matrix of such a triple-error correcting binary code.

Because of its relatively small length (23), dimension (12) and number of redundant bits (11), the binary (23,12,7) Golay code can be encoded and decoded simply by using look-up tables. The program go lay2 3 . c in the ECC home page uses a 16K x 23 bits encoding table and an 8K x 23 bits decoding table.

2.2.1 Encoding

Encoding is based on a look-up table (LUT) that contains a list of all the 212 = 4096 codewords, which are indexed directly by the data. Let u denote a 12-bit binary vector representing the data to be encoded, and let v denote the corresponding 23-bit codeword. The encoder LUT is constructed by generating all 4096 12-bit vectors and computing the syndrome of a pattern for which the 12 MSB equal to the information bits and the 11 LSB equal to zero. The 11-bit syndrome then becomes the LSB part of the codeword.

The LUT is a one-to-one mapping from u onto v, which can be expressed as

Decoding

vs = vs ® 1,

v = LUT(u) = (it, get_syndrome(u, 0)).

(2.3)

26

THE ART OF ERROR CORRECTING CODING

In the construction of the encoder LUT, advantage is taken from the cyclic nature of the Golay code. Its generator polynomial1 is

g(x) = x11 + z10 + x6 + x5 + x4 + x2 + 1,

which in hexadecimal notation equals C7 5. This polynomial is used to generate the syndrome in the procedure “get-syndrome” indicated in Equation (2.3) above.

2.2.2 Decoding

Recall from Chapter 1, Figure 14, that the decoder’s task is to estimate the most-likely (i.e., least Hamming weight) error vector e from the received vector f. The decoder for the Golay code is based on an LUT that accepts as input the syndrome s of the received vector r and outputs the error vector e.

The procedure to construct the decoder LUT is as follows:

1. Generate all possible error patterns e of Hamming weight less than or equal to three;

2. For each error pattern, compute the corresponding syndrome s = get_syndrome(e);

3. Store at location s of the LUT, the error vector e,

LUT(s) = e.

With the decoder LUT, upon reception of a corrupted received word f, correction of up to three bit errors is accomplished by the following:

v = f © LUT (get_syndrome(r)),

where v denotes the corrected word.

2.2.3 Arithmetic decoding of the extended (24, 12, 8) Golay code.

In this section, a decoding procedure for the extended (24.12.8) Golay code, C'24, is presented based on an arithmetic decoding algorithm [Wic, VO]. The algorithm utilizes the rows and columns of the parity submatrix B in the parity-check matrix H = (B | /12x12 ) • Note that an extended (24,12,8) Golay code, C'24, which is equivalent to C'24 up to a permutation in the bit positions, can be obtained by adding an overall parity-check bit at the end of each codeword in the (23,12, 7) Golay code.

In hexadecimal notation, the twelve rows of B, denoted row*, 1 < i < 12, are:

0x7ff, 0xee2, 0xdc5, 0xb8b, 0xfl6, 0xe2d,

0xc5b, 0x8b7, 0x96e, Oxadc, 0xdb8, 0xb71.

It is interesting to note that sub-matrix B of the parity-check matrix of C'24 satisfies B = BT. This means that code C24 is a self-dual code. Details of self-dual codes are not covered in this book. Interested readers are referred to [MS, Wic].

In program golay24. c, encoding is performed by recurrence with H, as indicated in

Equation 1.18. As before, let wln(x) denote the Hamming weight of a vector x. Decoding

steps are as follows [Wic, VO]:

1 The definition of a generator polynomial is given in Chapter 3.

HAMMING, GOLAY AND REED-MULLER CODES

27

1. Compute the syndrome s = rHT.

2. If wth(s) < 3, then set e = (s, 0) and go to step 8.

3. If wtff(s + row,) < 2, then set e = (s + row,;, Xi), where Xi is a 12-bit vector with

only the i-th coordinate nonzero.

4. Compute sB.

5. If wth(sB) < 3, then set e = (0, sB) and go to step 8.

6. If wth(sB + row,) < 2, then set e = (x,, sB + row,), with Xf defined as above,

and go to step 8.

7. r is corrupted by an uncorrectable error pattern, set error failure flag. End of decoding.

8. Set c = f + e. End of decoding.

2.3 Binary Reed-Muller codes

Binary Reed-Muller (RM) codes constitute a family of error correcting codes that are easy to decode using majority-logic circuits. In addition, codes in this family are known to have relatively simple and highly structured trellises [LKFF], More on trellises of linear block codes is discussed in Chapter 7.

**16**> 17 18 19 20 21 22 .. 86 >> Next