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

ISBN 0471-49581-6

**Download**(direct link)

**:**

**11**> 12 13 14 15 16 17 .. 86 >> Next

Si = (e; + v)HT = eiHT, (1.22)

which is independent of the particular choice of v ? C. The simplified decoding procedure is: Compute the syndrome of the received word f = ei> + v,

Si' = (e,/ +v)HT = ei'HT,

and find Sii in the leftmost column of the standard array. Then read out the value of e, from the second column, an add it to the received word to obtain the closest codeword v' 6 C to f. Therefore instead of n x 2n bits, standard array decoding can be implemented with an array of n x 2n~k bits.

Example 6 Consider again the binary linear (4,2,2) code from Example 3. Suppose that the codeword v = (0110) is transmitted and that f = (0010) is received. Then the syndrome is

1 1X = fH 1 = (0010) I } °

0 1/

= (1 0).

From the standard array of the code, the corresponding coset leader e! = (0100) is found, and therefore the estimated codeword is v' = f + e' = (0010) + (0100) = (0110). One error has been corrected! This may sound strange, since the minimum distance of the code is only two and thus according to (1.8) single error correction is impossible. However, this can be explained by looking again at the standard array of this code (Example 5 above). Note that the third row of the array contains two distinct binary vectors of weight one. This means that only three out of a total of four single-error patterns can be corrected. The error above is one of those correctable single-error patterns.

It turns out that this (4,2,2) code is the simplest instance of a linear unequal error protection (LUEP) code [WV, Van], This LUEP code has a separation vector s = (3,2), which means that the minimum distance between any two codewords for which the first message bit differs is at least three and that for the second message bit is at least two.

If encoding is systematic, then the above procedure gives the estimated message u' in the first k positions of v'. This is a plausible reason for having a systematic encoding.

INTRODUCTION

11

1.3.3 Hamming spheres, decoding regions and the standard array

The standard array is also a convenient way of understanding the concept of Hamming sphere and error correcting capability of a linear code C, introduced in Section 1.1.2.

By construction, note that the 2k rightmost columns of the standard array, denoted Colj, for 1 < j < 2k, contain a codeword vj G C and a set of 2n~k - 1 words at the smallest Hamming distance from vj, that is,

Col j = {vj + e*|ei G Ro Wi, 0 < i < 2n~k} . (1-23)

The sets Colj are the decoding regions, in the Hamming space, around each codeword vj G C, for 0 < j < 2k — 1. This is to say that if codeword Vj G C is transmitted over a BSC and the received word f lies in the set Col j, then it will be successfully decoded into Vj.

Hamming bound

The set Colj and the error correcting capability t of code C are related by the Hamming sphere St(vj): A binary linear (n, k, dmin) code C has decoding regions Colj that properly contain Hamming spheres St{vj), i.e., St(Cj) ? Colj.

By noticing that the size of Colj is 2n~k, and using Equation (1.6), we obtain the celebrated Hamming bound

E

< 2" . (1.24)

\ ». /

i=0

The Hamming bound has several combinatorial interpretations. One of them is:

The number of syndromes, 2rl~k, must be greater than or equal to the number of correctable error patterns, (”)•

Example 7 The binary repetition (3,1,3) code has generator matrix G = (1 1 1) and

parity-check matrix

1 1 O'

H='l 0 1 Accordingly, its standard array is the following:

s 0 1

00 000 111

11 100 on

10 010 101

01 001 110

The four vectors in the second column of the array (i.e., the coset leaders) are the elements of the Hamming sphere Si (000) in Figure 4, which consists of all binary vectors of length three with Hamming weight less that or equal to one. Similarly, the entries of the third (rightmost) column of the array are the elements of Si (111). For this code, the Hamming bound (1.24) holds with equality.

Block codes satisfying the bound (1.24) are said to be perfect codes. The only perfect nontrivial codes are the binary Hamming (2"i — 1, 2m — m — 1,3) codes, the nonbinary

12

THE ART OF ERROR CORRECTING CODING

Hamming (fq_^ ?, l'q'~i) — tu — 1,3) codes, q > 2, the repetition (n, 1, n) codes, the parity-check (n,n — 1,2) codes, the binary Golay (23,12,7) code and the ternary Golay (11,6,5) code. The extended codes (obtained by appending an overall parity-check bit) of the Hamming and Golay codes are also perfect.

For nonbinary linear codes, defined over a field of q elements, with q — pm and p > 2 a prime number, the Hamming bound becomes

?(n)(g-i)‘<9n“fc- d-25)

i=0 ' '

1.4 Weight distribution and error performance

When selecting a particular coding scheme, it is important to assess its error performance. There are several measures of the performance of an ECC scheme. In this section, expressions for linear codes are introduced, for three basic channel models: The BSC model, the additive white Gaussian noise (AWGN) channel model and the flat Rayleigh fading channel model.

**11**> 12 13 14 15 16 17 .. 86 >> Next